Summary
I’ve been working on this game called Battlefield One and it has a very simple algorithm for computing the next move that an enemy unit will take in order to reach it’s goal. The algorithm used searched all 6 surrounding hex and eliminates illegal hex points (off the grid or occupied by a unit). Then it computes the distance from each grid point to the destination and takes the shortest one. In this blog post, I’m going to put in some obstacles in the game and demonstrate the flaw in the algorithm I chose. Then I’m going to demonstrate how to use the A* algorithm to work on a hex grid instead of an 8-way or 4-way square matrix.
Adding Mountains
First, I painted a mountain hex in Photoshop. You can make up any hex terrain you wish, but I just went to Google Maps and copied some of the Rockey mountains onto the clipboard and then pasted it into a hex block and erased to match the hex shape:
Then I turned off the green hex shape layer and saved my hex-shaped mountain terrain as a mountain.png file:
Fortunately, I had planned on having many terrain types, so I coded the DrawTerrain method to contain a switch for each terrain picture to render. If you look at the code at GitHub you’ll see there are 4 grass terrains (I added some variety) and a new “mountains_01.png” terrain file type.
Next I modified the GameMap object to include a new “Blocked” property. If the terrain is equal to 6 (representing a mountain terrain type), then Blocked returns true, otherwise it’s false.
The FindAdjacentCells(x,y) method inside the GameBoard object was modified to use this Blocked property. This method will return all cells that are on the map board but not mountain cells. There are several unit tests that check different conditions (edge of map, corner of map, near mountains and in the middle).
Now to setup a test board to test the blocked cells:
This is a 7 by 6 cell gameboard with a German unit on cell 0,3 a city on cell 6,3 a spare allied unit in the lower right corner (to keep the game from ending with a German win). Finally, I put a line of mountains blocking the German unit from reaching the city. With the simple straight line algorithm of navigation, the German unit will go to the wall and toggle between cells 2,3 and 2,2.
The A* Algorithm
Next searched for an A* algorithm that I could adapt. I ended up using this web site to explain the details and I wrote the entire thing from the ground up:
The A* algorithm uses two lists to contain search nodes. The open list and the closed list. I created an object that represented one search node and called it AStartNode. This node needs to contain the F, G and H variables as described in the beginner guide (I set those to integers). The F variable is nothing more than G + H, so I just made a getter that adds G and H and returns the result as F. The next variables I needed was the X,Y coordinate of the cell that this node will represent and finally the location of the cell that was searched from (called Source). The constructor for the AStarNode just stores the values in the getters and then it computes the distance to the destination (which is an approximation of the distance as the crow flies).
Next, I created a list to contain AStarNodes. This generic list class is called AStarNodeList (yeah, not creative, but obvious). Instances of this list becomes the open and closed lists. That means that I can put all the methods I need inside this list to manipulate the nodes being processed. The FindSmallestNode() method is very useful. It finds the node with the lowest F value and returns it (after it removes it from the list). This is where I will grab the smallest node and find all it’s surrounding nodes and then push it on the closed list. I created a Contains() method to be used when I get surrounding nodes and I want to not save the ones that are already in the closed list. I created a GetNode(x,y) so I can read the nodes off the list in order to build the way point list (the goal of this whole exercise).
Next is an object called ShortestPath. This object is what does the work of putting the first node on the open list, then calling the FindPath() method which will recursively find the smallest node and find it’s neighbors until it runs into the destination point. I put in an iterations counter and made sure I exited if it hit 50. This max might need to be incremented if the map size is larger (you’ll know if the unit goes almost to its destination and stops). I wanted to make sure I didn’t get an infinite loop while I’m testing.
There is a method called GetWayPoint(x,y) inside the ShortestPath object. This is used by the game to get the next way point. Basically, to ensure that I can provide backwards compatibility, I just made my CollectGermanMovementData() method call this method first. This method will check to see if the WayPoint list has any nodes. If not, then a null is returned and CollectGermanMovementData() will grab the coordinates using the old fashioned direct calculation method (because lCoordinates will be null). If the first way point variable is equal to the unit x,y coordinates, then it is removed and the next coordinates are returned (but not removed from the list). The reason this is left on the list is in case the unit runs into an allied or even a German unit and is temporarily blocked. For now, it will stop and attack (if Allied unit) and continue on its way when it is no longer blocked. In the future, I’ll make it recompute the path (if it’s just going around and not attacking). Baby steps.
How to Build Something This Complicated
This algorithm is a bit complicated and there is a lot going on. So I create a visio document with the test map fully numbered. Then I plotted the F, G and H numbers for the first iteration:
I also put arrows on the diagram to point to the previous cell. Then I put a breakpoint in my AStarNode object and I ran the program. The first AStarNode was node 0,3. Then 0,2. That’s when I checked to make sure that G=1, H=6 and F=7 (the red numbers in the corners of each cell). Then I checked the next cell, which turned out to be cell 0,4, and so on. On the next iteration, things got a bit complex so I added Log4Net to my application, spit out the node being worked on and listed the nodes that were pushed onto the open list. Eventually, I was able to walk through the log file and see the order that the algorithm was using to walk toward the goal of cell 6,3.
The last task of this project was to make sure the list was read back into the way point list. You have to walk the list backwards because the AStarNode contains the x,y coordinates for the previous node. A simple while loop walked this back to the starting point and I just inserted it backwards into the WayPoint list, leaving the starting point out of the list (since the GetNextWaypoint() method takes care of that anyway.
Get the Code
You can go to my GitHub account and download the zipped up version of this project (Click Here). Assuming you have Visual Studio 2012 or better, you should be able to re-build the project and make this work. If you want to run the sample as shown in this blog post, you can go to the HomeController.cs file and change the GameData.InitializeGame(1) to a 3. Then go to the GameBoard.cs file (in the core project) and at the top is a TestMode boolean variable that you should set to true. Then run the game and you’ll see the map pictured earlier in this post. You can just click the next phase button and watch the German unit navigate to the city on the right side of the map. If you want to dig through the code, you can un-comment the log4net logging inside the ShortestPath.cs file and run the program, then look at the log file (which will be located in c:logs.
Last, you should take a look at how the non-A* algorithm failed. You can do that by going to the GameClass.cs file. Search for the SetEnemyStrategy() method and you’ll see two places where the ComputePath() method is called. Comment these two lines and run the program. You’ll see the German unit walk right up to the mountains and get stuck going back and forth.