This is Part 3 of my A* Pathfinding!
Part 2: Reading and Displaying Boards of Tiles
Time to work on the A* algorithm! I had this explained to me from policy almanac: http://www.policyalmanac.org/games/aStarTutorial.htm. It should be about the same everywhere, although other sites discuss it more in terms of nodes and graph theoryish stuff.
Taking on this algorithm is the scariest part of the project–there’s a lot of data to handle, and I’m not too familiar with all of it. Luckily, the site describes the steps pretty clearly, and I should be able to make a clearish outline.
Given map, start, destination
1. Add start to open list
2. For each reachable square:
– add to open list
– signify that start is ‘parent’
– compute F score
3. Remove start from open list, add start to close list
Process then repeats more or less, with a couple changes.
1. Remove A from open list and add A to closed list, where A is tile with lowest F score on open list
2. For each reachable square from A not in closed list:
– add to open list if not already in
– compute F score if it doesn’t exist
– compute G score using A otherwise, and replace old G score if new one is lower
– change parent to A if new F score is used
3. Cycle back to first step
Terminate at step one once A is the destination. The shortest path is found by tracing all the parents back to start.
There are a couple details that are dependent on the model. For my grid, reachable squares are adjacent up/down/left/right and not diagonals. Also, F score is computed through F = G + H.
G = movement cost from start to tile, one per tile walked
H = distance from tile to destination
= |row of dest – row of tile| + |column of dest – column of tile|
For those new to A*, the calculation of distance, H, is one of the most variable parts of the A* formula. For example, I couuuuld use the standard distance metric of root(x^2 + y^2), but since we’re walking tiles I’ll choose not to.
Back when I was a math major I was learning of different “metrics”, and there was a class of them called d_p, where ||x|| = (x1^p + … + xn^p)^(1/p), and they defined some complicated spaces called L_p spaces. Thought it was totally useless. But now I see that my “distance” is d_1 on two dimensions, and the standard distance is d_2. Maybe for different tile arrangements (hexagon, more dimensions, etc), other distances could be used?
Anyway. My computation of H is easier than all that.
Once I’ve found the shortest path, I’ll return a path struct, containing an array of tiles (starting at start and finishing at destination), and an integer for the length of the array.
One extra paramenter I’m taking in is an integer determining what tiles are walkable. I may change the implementation later but it’s good to have it. For example, “0” means I can walk tiles labeled “0”. But maybe I’ll have tiles labeled “1” that “0” can’t walk through, but if I want to bypass that I can change the parameter to “1” to indicate that.
Once I can output paths, I’ll work on a function to turn it into a highlight array, as well as update the drawing function to handle it.
The moment I start, it becomes glaringly obvious I’m going to need a buttload of arrays to store my lists. Some of these are 2d integer arrays, but some data has to be stored in 2d point arrays when I need to store (x,y) values. This involves creating the point struct.
– tiles, original array that is inputed
– closed & open, each spot is 1 or 0 for whether it is closed (or open)
– gScore & hScore, containing gScore or hScore
– fScore, sum of gScore and hScore. This was added in later because I figured it’s better to precalculate this value than risk having to calculate the same value multiple times.
– parents, indicating the parent of the tile
– path, the array that is returned. This is a 1d array.
Here are the additional functions that I ended up writing to ease creating structs. A lot of these are pretty standard when working with tiles, so I’ve written those before and doing them again isn’t too hard.
– pt to generate a point with given values. Since everything is in integers, so will the point’s x and y values.
– blank2d to generate a 2d integer array filled with 0’s
– point2d to generate a 2d array of empty points
– neighbors to generate a path containing the 4 adjacent tiles of a point
– valid to return whether given point is on board
– reachable to determine whether a tile is walkable under a filter. This part will be modified once more tiles are introduced.
– g and h functions to calculate respective scores
– updateF to update fScore when g or h is changed
– newParent to change a point in the parent array. This is a function because the old point (if it exists) needs to be freed every time.
Implementing all the functions wasn’t too difficult. The one major compiler error I ran into was a segmentation fault, as usual. The lldb debugger wasn’t telling me which line it was occuring on for some reason, so I ended up narrowing it down through commenting out code and using printf to make checkpoints. As it turns out, it was because I tried to access points in the closed array before I checked that these points were actually valid. With that figured out, everything compiles nicely.
A little bit of testing on various boards reveals that my path isn’t always optimal. Dammit! I always fear errors after a successful compile the most, since they are a lot harder to pin down. In this case, I made the right guess as to the problem in one–the portion of the code that changes the parent if something is already in the open list but has a lower G score via the new A tile. I had a less than symbol pointing the wrong way (facepalm), an easy fix.
Without any further noticeable errors and a pretty much instant run time on a 15×15 grid of numbers, all that is left to do is to make a draw function that highlights our path. To increase support for highlighting in general (say I want to highlight two different paths, etc), I’m going to convert the path into a 2d integer array, with 0’s where there are no highlights.
pathToArray is pretty easy to write, and along with that, I updated drawBoard function to handle the highlight array by modulating the color of the highlight with the tile (each of r,g,b are 0-255, so multiply them and divide by 255 once)
And with that, my A* project is complete!
Most important functions:
– boardToArray reads a file of 1’s and 0’s
– shortestPath finds the shortest path given a board and two tiles
– drawBoard turns a board and highlights into a .ppm image
The most prominent changes I would make if I worked further:
– incorporate the list struct into my project. Notably, I currently find the next open tile to work with by searching every single tile, which is inefficient. Instead, I can track the tiles by just adding coordinates to a list, and only check that list.
– output a different image format. Unlike lists, this is a skill I haven’t actually learned yet. Nobody really uses ppm files, and I’m pretty sure their file size is bigger than they could be.
The more I thought about it, the less it made sense to search every tile. I ended up adding a plist struct (list of points), and replaced numOpen with openList, a list that I can search through for open tiles. The most annoying part now is that I need to duplicate points when I place them into the list, since freeing of the current point A and freeing of the list is handled separately. If I could read my own code a lot faster or started with a list implementation this problem could be easily fixed. This is also reveals the advantage of languages that handle memory allocation automatically, since this would not happen.
Read my next post for the source code and some pretty pictures: A* Pathfinding Source Code