Fox-Star Search Fun

A recent question asked about the A* Search algorithm (https://cplusplus.com/forum/beginner/285875/#msg1243408), something I had never messed with, so I decided to play with it and learn something.

This is what I made. :O)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
// Fox Star
//----------------------------------------------------------------------------
// Example program demonstrating the A* Search algorithm
//----------------------------------------------------------------------------
// We do it over a gameboard populated by GRASS, BUSHES, and WALLS.
//
// The FOX can move horizontally, vertically, and diagonally over the GRASS in
// search of the delicious berries.
//
// The FOX may not pass through WALLS or BUSHES.
// It may not pass diagonally by a WALL, but it may do so by a BUSH.
//

// Copyright 2024 Michael Thomas Greer.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
//  https://www.boost.org/LICENSE_1_0.txt )

#ifdef _WIN32
	#define _CRT_SECURE_NO_WARNINGS
#endif

#ifdef __cplusplus
	#error "Hey! No C++ here! (Use a C compiler.)"
#endif

#ifndef __STDC_VERSION__
	#error "Requires C99 or greater. (C89/90 is 35 years old!)"
#endif

#include <iso646.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#if __STDC_VERSION__ < 201112L
	#define noreturn
#else
	#include <stdnoreturn.h>
#endif


//----------------------------------------------------------------------------
// A super simple RNG so that we can refer to specific gameboards
//----------------------------------------------------------------------------

unsigned long seed_ = 0;
void my_srand( long seed ) { seed_ = (unsigned long) seed; }
long my_rand( void )
{
	const unsigned long a = 1103515245UL, c = 12345UL, m = 2147483648UL;
	return seed_ = (a * seed_ + c) % m;
}
#define srand(x) my_srand(x)
#define rand() my_rand()
#undef RAND_MAX
#define RAND_MAX 2147483648UL


//----------------------------------------------------------------------------
// Unrecoverable Failures
//----------------------------------------------------------------------------
// For simplicity, memory failures --> crash & burn (with complaint)

noreturn
void failure( const char * message )
{
	fprintf( stderr, "%s\n", message );
	exit( 1 );
}


//----------------------------------------------------------------------------
// Terminal Control Functions
//----------------------------------------------------------------------------
// For simplicity we will use the terminal to display our gameboard.
// We assume that your terminal emulator:
//   • has at minimum 80×25 character cells,
//   • has TrueColor support (https://gist.github.com/sindresorhus/bed863fb8bedf023b833c88c322e44f9),
//   • can display fullwidth characters == two halfwidth character cells.
// Windows Console / Windows Terminal needs a little help to get started.

#ifndef _WIN32
	#include <unistd.h>
#else
	#define WIN32_LEAN_AND_MEAN
	#include <windows.h>

	static DWORD console_output_mode;
	static UINT  console_output_codepage;

	void finalize_console( void )
	{
		SetConsoleOutputCP( console_output_codepage );
		SetConsoleMode( GetStdHandle( STD_OUTPUT_HANDLE ), console_output_mode );
	}
#endif


void initialize_console( void )
{
	#ifdef _WIN32
		if (!GetConsoleMode( GetStdHandle( STD_OUTPUT_HANDLE ), &console_output_mode ))
	#else
		if (!isatty( 1 ))
	#endif
			failure( "Output must be attached to the console/terminal." );

	#ifdef _WIN32
		SetConsoleMode( GetStdHandle( STD_OUTPUT_HANDLE ),
				ENABLE_PROCESSED_OUTPUT | ENABLE_VIRTUAL_TERMINAL_PROCESSING );
		console_output_codepage = GetConsoleOutputCP();
		SetConsoleOutputCP( 65001 );  // UTF-8 output
		atexit( finalize_console );
	#endif
}


void clear_screen( void )    { printf( "\033[2J" );                 fflush( stdout ); }
void goto_xy( int x, int y ) { printf( "\033[%d;%d""H", y+1, x+1 ); fflush( stdout ); }


//----------------------------------------------------------------------------
// An (x,y) point object
//----------------------------------------------------------------------------
// Used to index the 2D gameboard.

struct XY { int x, y; } typedef XY;


XY xy( int x, int y )
{
	XY p = { .x=x, .y=y };
	return p;
}


bool is_xy_eq( XY a, XY b )
{
	return (a.x == b.x) and (a.y == b.y);
}


//----------------------------------------------------------------------------
// Directions the “player” can walk
//----------------------------------------------------------------------------
// This lists all valid ways to access an adjacent gameboard cell, regardless
// of whether it is permissible.

XY directions[] =
{
	{ -1, -1 }, {  0, -1 }, { +1, -1 },
	{ -1,  0 },             { +1,  0 },
	{ -1, +1 }, {  0, +1 }, { +1, +1 }
};

bool is_diagonal[] =
{
	true, false, true,
	false,       false,
	true, false, true
};

const int NUM_DIRECTIONS = sizeof(directions) / sizeof(directions[0]);


Last edited on
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
//----------------------------------------------------------------------------
// The Gameboard
//----------------------------------------------------------------------------
// A 2D array of glyphs to display.
//
// For simplicty we will limit our gameboard size to fit in the (assumed)
// terminal size. One gameboard cell == two terminal character cells. And
// we will fill it with random trees and walls, surrounded by water.
//
// Also, we aren’t being particularly careful to distinguish between the
// gameboard and the game pieces here -- everything is treated the same.

#define GAMEBOARD_WIDTH  38
#define GAMEBOARD_HEIGHT 24


#define GLYPHS(F) \
	/* name,      likelihood,  fg color,      bg color,   glyph */ \
	F(Background, 0,           "192;192;192", "0;0;0",       "  ") \
	\
	/* player can “walk” on the grass */ \
	F(Grass,      0.235690236, "55;159;19",   "85;179;49",   " ^") \
	F(Grass1,     0.117845118, "55;159;19",   "85;179;49",   "↯ ") \
	F(Grass2,     0.353535353, "55;159;19",   "85;179;49",   "  ") \
	\
	/* player cannot walk through this stuff */ \
	F(Wall,       0.038825757, "55;55;55",    "93;101;52",   ":∶") \
	F(Wall1,      0.038825757, "55;55;55",    "83;101;52",   ".:") \
	F(Wall2,      0.038825757, "55;55;55",    "103;101;52",  "∶:") \
	F(Wall3,      0.038825757, "55;55;55",    "93;101;52",   "·.") \
	F(Bush,       0.137626264, "157;242;106", "57;142;6",    "🌿") \
	\
	/* ...nor water, but it is only used to frame the gameboard */ \
	F(Water,      0,           "55;106;128",  "54;167;216",  "〰") \
	F(Water2,     0,           "55;106;128",  "54;167;216",  " ~") \
	F(Water3,     0,           "55;106;128",  "54;167;216",  "  ") \
	\
	/* bit-toggle with grass */ \
	F(Start,      0,           "255;170;85",  "85;179;49",   "🦊") \
	F(Goal,       0,           "255;128;128", "85;179;49",   "🫐") \
	F(Path,       0,           "255;255;192", "85;179;49",   "〇")

#define F(NAME,P,F,B,S) Glyph_##NAME,
enum { GLYPHS(F) NUM_GLYPHS };
#undef F

#define F(N,PROBABILITY,F,B,S) PROBABILITY,
const double glyph_probability[NUM_GLYPHS] = { GLYPHS(F) };
#undef F

#define F(N,P,FOREGROUND,B,S) FOREGROUND,
const char * fg_colors[NUM_GLYPHS] = { GLYPHS(F) };
#undef F

#define F(N,P,F,BACKGROUND,S) BACKGROUND,
const char * bg_colors[NUM_GLYPHS] = { GLYPHS(F) };
#undef F

#define F(N,P,F,B,SYMBOL) SYMBOL,
const char * glyphs[NUM_GLYPHS] = { GLYPHS(F) };
#undef F


int * gameboard_data;
int   gameboard_width  = GAMEBOARD_WIDTH;
int   gameboard_height = GAMEBOARD_HEIGHT;


int * gameboard( int x, int y )
{
	return gameboard_data + y * gameboard_width + x;
}


void initialize_gameboard( bool is_grass_only )
{
	gameboard_data = malloc( sizeof(gameboard_data[0]) * gameboard_width * gameboard_height );
	if (!gameboard_data)
		failure( "Cannot create gameboard: Dynamic memory allocation failure!" );

	// Grass and random WALLS and BUSHES
	for (int y = 1;  y < gameboard_height - 1; y++)
	for (int x = 1;  x < gameboard_width  - 1; x++)
	{
		double value = rand() * 1.0 / RAND_MAX;
		double sum   = 0.0;

		if (is_grass_only)
		{
			*gameboard( x, y ) = Glyph_Grass;
			continue;
		}

		for (int n = Glyph_Grass;  n < Glyph_Water;  n++)
		{
			sum += glyph_probability[n];
			if (value < sum)
			{
				*gameboard( x, y ) = n;
				break;
			}
		}
	}

	// Border it all with WATER
	for (int y = 0;  y < gameboard_height;  y++)
		*gameboard( 0, y ) = *gameboard( gameboard_width - 1,  y ) = Glyph_Water + (rand() % 3);

	for (int x = 0;  x < gameboard_width;   x++)
		*gameboard( x, 0 ) = *gameboard( x, gameboard_height - 1 ) = Glyph_Water + (rand() % 3);
}


static
void draw_glyph( int glyph )
{
	printf( "\033[38;2;%s;48;2;%s""m%s", fg_colors[glyph], bg_colors[glyph], glyphs[glyph] );
}


void draw_gameboard( void )
{
	goto_xy( 0, 0 );
	for (int y = 0;  y < gameboard_height;  y++)
	{
		for (int x = 0;  x < gameboard_width;  x++)
		{
			draw_glyph( *gameboard( x, y ) );
		}
		puts("");
	}
}


bool is_walkable( int x, int y )
{
	if ((x < 1) or (x > gameboard_width-2))  return false;
	if ((y < 1) or (y > gameboard_height-2)) return false;
	int glyph = *gameboard( x, y );
	return ((glyph >= Glyph_Grass) and (glyph <= Glyph_Grass2)) or (glyph == Glyph_Goal);
}


int count_walkable_cells( void )
{
	int count = 0;
	for (int y = 0;  y < gameboard_height;  y++)
	for (int x = 0;  x < gameboard_width;   x++)
		count += is_walkable( x, y );
	return count;
}


bool is_wall( int x, int y )
{
	int glyph = *gameboard( x, y );
	return (Glyph_Wall <= glyph) and (glyph <= Glyph_Wall3);
}


bool is_walkable_to( XY from, int direction )
{
	int x = from.x + directions[direction].x;
	int y = from.y + directions[direction].y;

	if (!is_walkable( x, y )) return false;
	if (!is_diagonal[ direction ]) return true;
	return !is_wall( x, from.y ) and !is_wall( from.x, y );
}


void draw_status( const char * message, long seed )
{
	char s[50];
	sprintf( s, "%ld", seed );
	printf( "\033[38;2;55;112;112;48;2;%s""m", bg_colors[Glyph_Background] );
	printf( "\r%*s", (int)(gameboard_width * 2 - 6 - strlen(s)), " " );
	printf( "seed:%s ", s );
	printf( "\r\033[38;2;%s""m %s", fg_colors[Glyph_Background], message );
	printf( "\033[0m" );
	fflush( stdout );
}


//----------------------------------------------------------------------------
// Priority Queue for XY positions
//----------------------------------------------------------------------------
// Implemented as a min-heap

struct priority_queue
{
	struct pq_node
	{
		int priority;
		XY  value;      // data value ::= XY position
	}
	*   data;           // array of data
	int size;           // array size
};


bool pq_create( struct priority_queue * pq, int capacity )
{
	pq->data = malloc( capacity * sizeof(struct pq_node) );
	pq->size = 0;
	return !! pq->data;
}


void pq_free( struct priority_queue * pq )
{
	free( pq->data );
	pq->size = 0;
}


static
void pq_sink( struct priority_queue * pq, int index )
{
	for (int parent = index;;)
	{
		// Find the first child of the parent node
		int child = (parent * 2) + 1;
		if (child >= pq->size)
			return;

		// Find the child with the minimum priority
		if (child+1 < pq->size)
			if (pq->data[child+1].priority < pq->data[child].priority)
				child += 1;

		// Priority for parent must be minimum of (parent, children...)
		if (pq->data[parent].priority <= pq->data[child].priority)
			return;

		// (swap)
		struct pq_node node = pq->data[parent];
		pq->data[parent]    = pq->data[child];
		pq->data[child]     = node;

		// (next)
		parent = child;
	}
}


void pq_insert( struct priority_queue * pq, XY value, int priority )
{
	// Append the new value to the pq data
	int child                = pq->size ++;
	pq->data[child].priority = priority;
	pq->data[child].value    = value;

	// Apply the heap property for each parent of the new value
	while (child)
	{
		int parent = (child - 1) / 2;
		pq_sink( pq, parent );
		child = parent;
	}
}


XY pq_pop( struct priority_queue * pq )
{
	XY result = pq->data[0].value;         // Result is the min-heap value
	pq->data[0] = pq->data[ -- pq->size ]; // Move the last value in the heap data to the min-heap position...
	pq_sink( pq, 0 );                      // ...then sink it
	return result;
}

Last edited on
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
//----------------------------------------------------------------------------
// A* Search Algorithm
//----------------------------------------------------------------------------
// Returns a malloc()ed array of XY points ("start" to "goal", inclusive),
// if a path is found that links the two points. Returns the length of this
// list, or zero/NULL if no path is found.
//
// You must free() this list.

// The lookup of costs is an allocated 2D array matching the gameboard
// dimensions. There are all kinds of ways to reduce the memory footprint
// and decouple from the gameboard, but they all require more code --
// things like hash tables, etc -- and this suffices our little example.

struct astar
{
	XY  whence;  // Position we came from
	int cost;    // Total cost so far
};


static
struct astar * node_at( struct astar * costs, XY xy )
{
	return costs + xy.y * gameboard_width + xy.x;
}


#define whence_to( xy ) node_at( costs, xy )->whence
#define cost_to( xy )   node_at( costs, xy )->cost


static
struct astar * create_costs( void )
{
	int size = gameboard_width * gameboard_height;  // <-- aaaaahhh!
	struct astar * costs = malloc( size * sizeof(struct astar) );
	if (costs)
		for (int n = 0;  n < size;  n++)
			costs[n].cost = INT_MAX;
	return costs;
}


// The following two functions are used to construct the resulting
// path found by the algorithm.

static
int length_of_path_to( struct astar * costs, XY where )
{
	int count = 1;
	while (!is_xy_eq( whence_to( where ), where ))
	{
		count += 1;
		where = whence_to( where );
	}
	return count;
}


static
int extract_path( struct astar * costs, XY where, XY ** result )
{
	int size = length_of_path_to( costs, where );
	if (!size)
	{
		*result = NULL;
		return 0;
	}

	*result = malloc( size * sizeof(XY) );
	if (*result)
	{
		int n = size;
		while (!is_xy_eq( whence_to( where ), where ))
		{
			result[0][--n] = where;
			where = whence_to( where );
		}
		**result = where;
	}
	return size;
}


// The following two functions directly control the algorithm's correctness.
//
//  • The heuristic function is your standard Manhattan Distance.
//
//  • The adjacent cost helps us by computing a better cost when headed
//    in the direction of the goal (and worse costs when heading away).
//
//    You could add all kinds of stuff here, such as avoiding obstacles
//    like enemies, or locations that are harder to traverse, etc, but
//    are still passable as part of a valid path to the goal.

static
int compute_heuristic( XY a, XY b )
{
	return abs(b.x - a.x) + abs(b.y - a.y);
}


int adjacent_cost( XY from, int direction, XY goal )
{
	double angle[] =
	{
		 2.35619449,  1.570796327,  0.785398163,
		 3.141592654,               0.0,
		-2.35619449, -1.570796327, -0.785398163,
	};
	double offset = 0.392699082; // 22.5°
	double desired = atan2( goal.y-from.y, from.x-goal.x );
	double difference = fabs( desired - angle[direction] );
	int n = 0;
	while (++n < 4)
		if (difference < n*offset)
			break;
	return n + is_diagonal[direction];
}


// And here is the A* search algorithm function!
// The THREE functions that parameterize it are:
//  • compute_heuristic()
//  • adjacent_cost()
//  • is_walkable_to()

int find_path( XY start, XY goal, struct XY ** result )
{
	int size = 0;
	*result = NULL;

	struct priority_queue frontier;
	struct astar * costs = create_costs();
	if (!pq_create( &frontier, count_walkable_cells() ) or !costs)
		failure( "Cannot compute path from FOX to BERRIES: Dynamic memory allocation failure!" );

	// Add the starting position
	whence_to( start ) = start;
	cost_to  ( start ) = 0;
	pq_insert( &frontier, start, 0 );

	// While there are positions yet to examine
	while (frontier.size)
	{
		XY current = pq_pop( &frontier );

		// Did we find the goal?
		if (is_xy_eq( current, goal ))
		{
			size = extract_path( costs, goal, result );
			if (!*result)
				failure(
					"There is a path, but Dynamic memory allocation\n"
					"failure (so I cannot show it to you, alas)!" );
			break;
		}

		for (int direction = 0;  direction < NUM_DIRECTIONS;  direction++)
		{
			// Ignore this direction if it is not a place the player can go
			if (!is_walkable_to( current, direction ))
				continue;

			// whither ::= cell adjacent to current
			XY whither = xy(
				current.x + directions[direction].x,
				current.y + directions[direction].y );

			// compute the new total cost to whither
			int new_cost = cost_to( current )
				+ adjacent_cost( current, direction, goal );

			// if (whither is not in costs)
			// or (new_cost is better than whither's current cost)
			if (new_cost < cost_to( whither ))
			{
				int priority = new_cost + compute_heuristic( whither, goal );
				whence_to( whither ) = current;
				cost_to  ( whither ) = new_cost;
				pq_insert( &frontier, whither, priority );
			}
		}
	}

	free( costs );
	pq_free( &frontier );
	return size;
}

#undef whence_to
#undef cost_to


//----------------------------------------------------------------------------
int main( int argc, char ** argv )
//----------------------------------------------------------------------------
{
	// Initializations
	long seed = (argc == 2) ? atol(argv[1]) : (long)time(NULL);
	srand( seed );

	initialize_console();
	initialize_gameboard( seed < 0 );

	clear_screen();

	// We’ll start in the lower-left corner
	// And try to plot a path to the upper-right corner
	XY start = xy( 1, GAMEBOARD_HEIGHT - 2 );
	XY goal  = xy( GAMEBOARD_WIDTH - 2,  1 );
	*gameboard( start.x, start.y ) = Glyph_Start;
	*gameboard( goal.x,  goal.y  ) = Glyph_Goal;

	// (Attempt to) Solve using A* Search Algorithm
	XY * path;
	int size = find_path( start, goal, &path );
	if (size)
	{
		// Show the gameboard before solving
		draw_gameboard();

		// Let the user decide when to show the solution
		draw_status( "Press ENTER to solve...", seed );
		{
			int c;
			do c = getchar();
			while ((c != EOF) and (c != '\n'));
		}

		// ...and draw the solution on the gameboard
		for (int n = 1;  n < size-1;  n++)
			*gameboard( path[n].x, path[n].y ) = Glyph_Path;
		free( path );
	}

	// Show the gameboard after attempted path solution
	draw_gameboard();
	draw_status( path ? "Success!\n" : "No path found.\n", seed );

	return 0;
}
Last edited on
TO COMPILE:

  • Clang • clang -Wall -Wextra -Werror -pedantic-errors -O3 -std=c11 -lm fox-star.c
  • MSVC • cl /EHsc /W4 /Ox /std:clatest fox-star.c


Honestly, I wound-up messing more with the pretty pictures in the terminal than anything else, heh.

Make sure you are using a terminal emulator that understands UTF-8 full-width characters and TrueColor. Things like Windows Console and Gnome Terminal will do.

I haven’t had a chance to fully test on Windows — my Windows box is still down. Let me know if I goofed.


The fox cannot pass through walls or bushes. (Or water!)

The fox can travel diagonally around a bush or through the grass,
but must go orthogonally around a wall.

Hence, it may pass diagonally between two touching bushes, but not a bush and a wall, nor two walls.


You can pass as command-line argument a random seed to use to create the gameboard — the code includes a simple RNG so that the seed produces the same board on all systems. If you give a negative value as argument you get a gameboard with just grass. (And water!)


I am considering turning this into a little game.
Feel free to play with it yourselves.


Random notes: I originally designed it using a half-shifted cell approach, like this:
▐█▌• •
 A •▐█▌
▐█████▌
Stupid “fixed” font is uneven on the new site’s markup.
But I obviously decided to just play with the full-width characters directly. The output is prettier, but requires a smarter terminal. Fortunately the requirements are pretty common these days, so I don’t feel bad about it.
Last edited on
Reminds me of my AI class, had to create a program that could solve those stupid number slider games. Used something similar to an A* algorithm.

This being the hardest puzzle the program had to solve (0 is the blank space):

1
2
3
4
5
6
7
vector<vector<unsigned char>> a =
{
	{	0,	12,      9,	13	},
	{	15,	11,	10,	14	},
	{	3,	7,	5,	6	},
	{	4,	8,	2,	1	}
};



There were no students in the Discord channel for the class that I recall having actually created a program that could solve this puzzle (at least in a reasonable amount of time).

Mine was able to get it:

Solved in 176 moves!
3.00898 seconds
There were 2050452 nodes generated!
Last edited on
That was an AI class?
Last edited on
A* and other path finding algorithms can/are considered to be forms of AI.

I consider the game-playing programs I've made on Codingame.com to be "more so" AI (due to those games being more complex), but it is what it is.

The program can solve nearly any number slider puzzle you toss at it. Programs that play games that require problem-solving are definitely gonna be considered AI.


EDIT:

To be fair, this was a assignment early in the semester, but also turned out to be the *only* code we ever actually wrote. The rest was basically just higher level AI concepts. Interesting, but not fun.

This was also the professor who yelled at me for not circling the answer on my test, looked me the eyes when telling the class some of "us" should consider dropping it, and overall was just a terrible guy.


But, it was pretty fun and cool to code, I'd recommend. We can see who has the most efficient algorithm 👀
Last edited on
As I said in "that other thread":

I found a lot of info and a few C implementations for the A* Search algorithm on the interwebz:

https://duckduckgo.com/?t=ffab&q=a*+search+in+c&atb=v188-1&ia=web

I can't say whether the info is useful since I have only done a cursory glance at a couple of links. This one seems to be helpful:

https://codingclutch.com/a-star-algorithm-explanation-implement-in-c/

For me personally I'd be looking for C++ implementations as well as C ones.

https://duckduckgo.com/?q=a*+search+in+c+and+c%2B%2B&t=ffab&atb=v188-1&ia=web

Peace! I'm out'ta here!

To be honest I've never really had a need for the A* search algorithm, and if I ever did I'd more likely lean towards using some solution well tested instead of my own feeble attempt(s) that are more than likely chock full of stupid mistakes.
A* isn’t so difficult you can’t roll you own, especially for your own learning purposes — as this is.

I always used things like Dijkstra’s algorithm for pathfinding stuff before. Learning A* was worth it, methinks.
The graphic looks nice, especially considering it's a console application.

A* is often used in games. It's essentially a more optimized version of Dijkstra's algorithm for situations when you can estimate the distance to the goal (to be guaranteed to get the shortest path you must never overestimate the distance).

A nice thing about these algorithms is that you can give higher "costs" to certain nodes to make the algorithm prefer or avoid certain areas. This could for example be used in a game to make an NPC avoid enemy territory or tiles that are crowded. You could also use this to let different types of creates have different preferences (e.g. dogs might like water tiles better than cats do).

In other words, a lot of fun things to play with. :)
Last edited on
A* isn’t so difficult you can’t roll you own, especially for your own learning purposes — as this is.

I certainly won't dispute that. :)

Currently I have lots of other things to muck around with and learn. Learning the intricacies of A* is on my list, but way down the list. Waaaay down the list.

Last edited on
[Learing A* is waaaaaaaaaaaay down on my list.]

You’re not missing anything. I honestly had more fun messing with the pretty picture than anything else.
Last edited on
Hehtm. I know what the allure of a shiny object can be. :Þ
You’re not missing anything. I honestly had more fun messing with the pretty picture than anything else.

The challenge is still on the table. Can you make a better algorithm for solving the sliding puzzle game?

The timing will be different for each computer, so the number of nodes generated will be a better indicator.

The number of moves to solve the puzzle can also be smaller. I believe for that particular puzzle, it can be as low as 80 moves.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//Around 80 Moves
vector<vector<unsigned char>> hard =
{
	{	0,	12,	9,	13	},
	{	15,	11,	10,	14	},
	{	3,	7,	5,	6	},
	{	4,	8,	2,	1	}
};

//Around 30 Moves
vector<vector<unsigned char>> medium =
{
	{	9,	1,	3,	4	},
	{	5,	6,	8,	7	},
	{	13,	2,	11,	12	},
	{	14,	10,	15,	0	}
};

//Around 14 Moves
vector<vector<unsigned char>> easy =
{
	{	0,	6,	2,	4	},
	{	1,	10,	3,	7	},
	{	5,	9,	14,	8	},
	{	13,	15,	11,	12	}
};



Edit:

I asked ChatGPT to take a shot at it. It was able to get it down to 152 moves, but it took around 30 seconds to run and generated 15+ million nodes.


For this assignment, I prioritized speed since my grade depended on having a working program.

The minimum number of moves I commented in were from my professor, I don't know how he got those numbers so feel free to take them with a grain of salt.
Last edited on
The challenge is still on the table. Can you make a better algorithm for solving the sliding puzzle game?

Not a challenge that appeals to me. I'm obstinate and obdurate that way.

I have enough other challenges to pique my interest. One is improving my understanding of C++20/23.
I couldn’t solve those things as a kid, mostly because I had no interest in them, alas. Those kinds of puzzles have always seemed to me like a version of picking up the kids toys — cleaning up a mess with no purpose. I suppose a little thought would get me there, but my eyes honestly gloss over just looking at the suggested problems.

...I have so little thought space left...
(Semi-) different reasons, same result. Little to no interest in this A* "challenge".
Algorithms was my one weakness when I did my CS degree too many moons ago to count. I only just 'scraped' the 'Into to Algorithms' course in year 2 and was strongly advised not to take the 'Advanced Algorithms' course in year 3. I did a networking course instead which was great.
school based algorithms are kinda frustrating ... about 3/4 of what you cover isn't useful. Like 'memorize the name and approach for 10 different flavors of bubble sort and how they differ before learning how it is really done'. I get that the background is useful for big-O, how not to do stuff, and how to think about the problem various ways, but I am a stand on the shoulders of giants kinda guy. Show me the good stuff, and we can build off that instead, maybe improve it or cover a dozen useful things instead of stuff that has no practical value. Its like how calc teachers force you to learn that derpy division derivative formula when you can invert and multiply 10 times easier and faster.

If I had a dollar for all the worthless stuff we did with trees, I would have retired out of college.

the sliding puzzle is a little interesting (I can't deny this). But I know better than to try to beat something thats been done to death. That sort of thing takes years of head-desk time. Is there an actual application for the cod if someone did come up with a better mousetrap?
Last edited on
Its like how calc teachers force you to learn that derpy division derivative formula when you can invert and multiply 10 times easier and faster.


That's what I used to try to do. But it would come back with big red crosses and unintelligible red squiggles all over.......
Registered users can post here. Sign in or register to post.