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)

// 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

Duthomhas (13195)

//----------------------------------------------------------------------------
// 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

Duthomhas (13195)

//----------------------------------------------------------------------------
// 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

Duthomhas (13195)

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

zapshe (1869)

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):

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

Duthomhas (13195)

That was an AI class?

Last edited on

zapshe (1869)

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

George PlusPlus (5700)

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.

Duthomhas (13195)

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.

Peter87 (11220)

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

George PlusPlus (5700)

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 pf A* is on my list, but way down the list. Waaaay down the list.

Registered users can post here. Sign in or register to post.

C++

Forum

Fox-Star Search Fun