Posted on by Theo Butler

A Star Path Finding Comparison to AI Techniques

The A Star algorithm defined as “best-first, graph search algorithm that finds the least-cost path from a given initial node to one goal node (out of one or more possible goals)” (INAM, 2009). It is used throughout the games and AI industry for many different reasons, but mainly used for runtime pathfinding for NPC’s in games. Out of the possible methods for pathfinding this is used in most cases due to its guaranteed accuracy to find the shortest path on any map.

The algorithm takes a map and populates a grid with walkable, non-walkable, start and end nodes. These nodes will be able to hold information about themselves such as location, cost from the start (g-cost), cost to the end (h-cost) and their overall cost (f-cost). Then it generates two lists (open and closed), places the start location in the open list and sets that as the current node. From there, the program enters the main loop which is described in the following paragraph.

While the open list does not contain the end point, the program will test all the nodes around the current node and these will be added to the open list if they are not walls. As they are added their h-cost, g-cost and f-cost values will be calculated. To do this the program calculates h-cost in a direct route, the g-cost is calculated from the current shortest path to that node, and the f-cost is the sum of the two. Distances are found using 14 for diagonals, whereas a horizontal or vertical direction adds 10 to its distance. These values are used as approximations of the distance of one node to the next. Now the current node is processed, it is placed on the closed list. The loop then repeats by selecting the new current point from the lowest f-cost node on the open list. When the algorithm tests the nodes around the current it will update the scores of any nodes where the score is lower than its previous one.

Once the loop finishes, it generates the path by moving backwards from the end node by finding the lowest g-cost around the node and repeating until it reaches the start.

Genetic algorithms

“Genetic algorithms are randomized search algorithms that have been developed in an effort to imitate the mechanics of natural selection and natural genetics.” (Wilfried Roetzel, 2020) This means that for a pathfinding program a random path will be made and improved on eventually giving the best path for the maze given. This does take time for the iterations to complete and find their way towards the end goal. This would be excellent for a computer game because it can be used in both a static and dynamic state effectively to generate the path for an NPC.

Results

Here is an example of the guaranteed optimal path (pink) from the start (green) to the end (blue) point.

The algorithm had to check the central cavity before finding that the outer path was quickest.

Once the program was working, I set it to work on something a bit more difficult. From a computer generated maze the algorithm found the optimal path correctly.

Success after over a million iterations of the algorithm

The Genetic Algoythm did not do so well. By its nature it had to try very many paths.

In the middle of its search trying random possible paths.

Code

I wanted to have the map be dynamically allocated but also allow for easy addressing in an 2D array fashion. So I used an addressing overload of [ ].

class pointgrid
{
public:
	int width;
	int height;
	class point* gridarray;

	pointgrid(int, int);
	~pointgrid();

	point* <strong>operator[]</strong>(int x) { <strong>return &(gridarray[x * height])</strong>; } // overloading
};

pointgrid::pointgrid(int x, int y)
{
	height = y;
	width = x;
	gridarray = { <strong>new class point[(size_t)(width * height)]</strong> };
};

The main loop looks like this:

// while the endpoint is not in the greenlist
while (!isinalist(greenlist, endlocationx, endlocationy))  
{
	// this function iterates through the greenlist to find the point 
	// with the lowest currentscore.
	int lowestscoreindex = findlowestscore(greenlist);
	
	// changes the current position to the best case in the greenlist
	currentpositionx = greenlist[lowestscoreindex]->xy[0]; 
	currentpositiony = greenlist[lowestscoreindex]->xy[1];

	// moves the point currently working on into the tested list		
	testedlist.push_back(&grid[currentpositionx][currentpositiony]); 
		
	// changing it for visual referance in the out images		
	if (	grid[currentpositionx][currentpositiony].typeofsquare != 3 && 
		grid[currentpositionx][currentpositiony].typeofsquare != 2	)
	{
		grid[currentpositionx][currentpositiony].typeofsquare = 4; 
	}

	// removes the current point from the greenlist
	greenlist.erase(greenlist.begin()+ lowestscoreindex);

	// find the points around the current point that are a viable 
	// option to step to	
	findpointsaroundme8(testedlist, &greenlist, grid, currentpositionx, 
		currentpositiony, gridsizex, gridsizey, endlocationx, endlocationy);
		
	// test if greenlist is empty suggesting there is no path left to go down.
	if (greenlist.empty())
	{
		cout << "There are no solutions to " << filename;
	}
}