Game AI Assignment 2 (A* Code Demo)
Summary of Code
The software used for development was Unity 5.3.2f. It has scenes available to it, and can be thought of as “levels”. The code I wrote for the “first level” is a very simple “main menu” type scene. The scene displays a sprite image with text explaining controls to play the game. Pressing enter will enter the game, aka “level 2” aka the actual assignment. I thought that the best way to start would be to have a screen that explains the controls and features right off of the bat. The code for the main menu uses key down detection for the Enter key in order to progress to the other scene. Since this is a summary of the code, and not a comments of the code this will be very brief.
An 12 by 8 grid of tiles is available for the agent (seeker), or the subject (target) to move across and be positioned on, as long as a rock tile is not placed upon it prior to compile time. A rock can be added or removed via Unity’s game objects by simply copying the prefab’d object and placing it at a x,y location that is of integer only value. The agent (seeker) can be moved around using the WASD keys, and the subject (target) can be moved using the arrow keys. Each movement allows for movement in a one tile direction, north, south, east, west respectively.
The “x” key is used to toggle an overlay of numbers for the tiles to be displayed on the game screen itself. The “z” key is used to perform the Seek() code from Part A. The agent will seek out the target, using a very basic, and dumb algorithm that can only work 100% if there are no obstacles (rocks) in the way of the path. If a rock is in the way of the target, the agent will go as far as the rock, but stop moving and report with “Error: <x,y,z> is blocked! Ending seek”. The “Enter” key begins the A* algorithm, which is of course the meat and potatoes. Before going into detail to that, I’d like to note that during execution of the A* algorithm or the basic Seek() method the seeker and the target are unable to be moved via wasd or arrow keys. Also, another algorithm is unable to execute while another one is being executed. However, the “x” key overlay toggle is still able to be toggled. This is to help prevent errors since Seek() and the A* algorithms both run in their own respective threads.
There is a tick within the algorithms that pauses every 1 second per “movement” essentially. This variable’s value can be changed in the Agent.cs script file with the variable waitTime.
The A* algorithm code first does some initialization of the grass tiles. As the algorithm progresses and new tiles are examined per A* algorithm, the tiles have their colors changed to help indicate that they have been added to the closed list. Tiles on the open list are not highlighted on the screen however during execution. The code for this algorithm swaps sprites with a hidden game object and moves that game object in place where the agent is. This makes it look like the agent never moved, but in fact is moving to tile to tile to examine the tile. This is in part because the code was far easier to write to simply +/- based on relative current location of the object the agent script is attached to. And based on the game itself, (no box colliders, rigidbodies, and a method that prevents movement to blocked areas) — it’s actually okay to do.
When an agent moves to a tile, it examines the tiles north, south, east, and west of the agent, as long as those tiles exist, and if they are not blocked (aka, does not have a rock tile in that location as well, and is not outside of the arena of tiles) THEN the agent will calculate the heuristic value (H) based on the manhattan algorithm. This is to keep track of the number of times a move would be made to go to a position (G), and the parent tile the agent is currently on, in regards to the tiles it examines.
The sum of the G and H, known as F, is calculated on the fly with a separate class called tilesClass. This class actually stores the F, G, H, and P values as well as contains some methods for outputting the final path. Those tilesClass objects are stored in a 2D array based on the top left of the map being 0,0 (y,x) and the y values increase going south, and the x values increase going right.
As such, during execution of the A* method, the “gameGrid” 2D arrary containing the tilesClass objects is reset/initialized at the start of execution and those tiles have the appropriate values assigned upon needed examination only. After examining the neighboring tiles, those tiles are added to an open list through self made methods for adding and removing rather than using C#’s add/remove methods for Lists due to an excessive amount of incorrect adding/removing that I was wanting and expecting from the built in methods.
After the examination, and adding to the OpenList, the current tile the agent is on during the execution of the algorithm, is removed from the open list and added to the closed list (perhaps not entirely in that order) and the open list is examined to see which tilesClass object responds with the smallest F value to determine where to examine next. The agent doesn’t really know the best path to get to the target, so it has to use the A* algorithm and questions which path is the right path to take, one tile at a time (as per it should).
Once the algorithm examines and finds it’s way to the target, the parent of the target tile is examined backwards/recursively and a list is generated to determine the parent of the parent of the parent (etc) in order to determine it’s way back to the starting point of the agent. This list is then reversed via C#’s .Reverse() method for lists and the outcome is a list of tilesClass objects that lead the agent on the best A* calculated path to the target. At this point, the highlighted tiles have their colors reset, and the path to the target is then highlighted. The agent will then traverse the path 1 second at a time. Also, it should be noted that the algorithm examining the tiles pauses one second at a time as well.
This is due to the fact that the method that performs this algorithm was spawned a separate thread (Coroutine). The coroutine allows for pausing within it’s thread’s code due to the nature of Unity and Coroutines which is perhaps another lengthy explanation and subject not worth writing here.
Once the agent finishes walking the path calculated from the A* algorithm. The highlighted tiles remain and agent and target are free to walk around again.
Screenshots & Two A* Examples
Below is a map of the tile/nodes
(without any game objects such as the target, seeker, agent visible)
An example of one A* search is below:
1) Starting positions
2) After the algorithm has searched through the tiles (is on the last tile examination)
3) The redrawn path that the agent will take to the target as well as a screenshot of the agent walking down the path.
Below is the console log (with extra unity text removed) of that algorithm executing:
Part B (Option 1): A* Searching! Resetting gameGrid! | [001][002][003][004][005][006][007][008][009][010][011][012] | | [013][014][015][016][017][018][019][020][021][022][023][024] | | [025][026][027][028][029][030][031][032][033][034][035][036] | | [037][038][039][040][041][042][043][044][045][046][047][048] | | [049][050][051][052][053][054][055][056][057][058][059][060] | | [061][062][063][064][065][066][067][068][069][070][071][072] | | [073][074][075][076][077][078][079][080][081][082][083][084] | | [085][086][087][088][089][090][091][092][093][094][095][096] | | [097][098][099][100][101][102][103][104][105][106][107][108] | Done Resetting Game Grid! Added 52 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 52 now... New OpenList->East: Tile[53]: f: 5 g: 1 h: 4 p: 52 New OpenList->West: Tile[51]: f: 7 g: 1 h: 6 p: 52 New OpenList->North: Tile[40]: f: 7 g: 1 h: 6 p: 52 New OpenList->South: Tile[64]: f: 5 g: 1 h: 4 p: 52 Added 64 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 64 now... New OpenList->East: Tile[65]: f: 5 g: 2 h: 3 p: 64 New OpenList->West: Tile[63]: f: 7 g: 2 h: 5 p: 64 New OpenList->South: Tile[76]: f: 7 g: 2 h: 5 p: 64 Added 65 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 65 now... New OpenList->East: Tile[66]: f: 5 g: 3 h: 2 p: 65 New OpenList->South: Tile[77]: f: 7 g: 3 h: 4 p: 65 Added 66 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 66 now... New OpenList->North: Tile[54]: f: 7 g: 4 h: 3 p: 66 New OpenList->South: Tile[78]: f: 7 g: 4 h: 3 p: 66 Added 53 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 53 now... New OpenList->North: Tile[41]: f: 10 g: 5 h: 5 p: 53 Added 77 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 77 now... New OpenList->South: Tile[89]: f: 11 g: 6 h: 5 p: 77 Added 78 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 78 now... New OpenList->East: Tile[79]: f: 9 g: 7 h: 2 p: 78 New OpenList->South: Tile[90]: f: 11 g: 7 h: 4 p: 78 Added 40 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 40 now... New OpenList->West: Tile[39]: f: 15 g: 8 h: 7 p: 40 New OpenList->North: Tile[28]: f: 15 g: 8 h: 7 p: 40 Added 54 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 54 now... New OpenList->North: Tile[42]: f: 13 g: 9 h: 4 p: 54 Added 51 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 51 now... New OpenList->West: Tile[50]: f: 17 g: 10 h: 7 p: 51 Added 76 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 76 now... New OpenList->West: Tile[75]: f: 17 g: 11 h: 6 p: 76 New OpenList->South: Tile[88]: f: 17 g: 11 h: 6 p: 76 Added 63 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 63 now... New OpenList->West: Tile[62]: f: 18 g: 12 h: 6 p: 63 Added 79 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 79 now... New OpenList->East: Tile[80]: f: 14 g: 13 h: 1 p: 79 New OpenList->South: Tile[91]: f: 16 g: 13 h: 3 p: 79 Added 41 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 41 now... New OpenList->North: Tile[29]: f: 20 g: 14 h: 6 p: 41 Added 89 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 89 now... New OpenList->South: Tile[101]: f: 21 g: 15 h: 6 p: 89 Added 90 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 90 now... New OpenList->South: Tile[102]: f: 21 g: 16 h: 5 p: 90 Added 42 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 42 now... New OpenList->East: Tile[43]: f: 20 g: 17 h: 3 p: 42 New OpenList->North: Tile[30]: f: 22 g: 17 h: 5 p: 42 Added 80 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 80 now... New OpenList->East: Tile[81]: f: 20 g: 18 h: 2 p: 80 New OpenList->North: Tile[68]: f: 18 g: 18 h: 0 p: 80 New OpenList->South: Tile[92]: f: 20 g: 18 h: 2 p: 80 Final Path: 52,64,65,66,78,79,80,68 Using path to move to target now. All Done!
The second A* example uses a more direct and shorter path. The first tiles/nodes it examines end up being the tile with the smallest calculated F value. As such the analysis and actual path highlights are the same screenshot.
The agent then moves along that path, one tile at a time.
1) Starting positions:
2) The algorithm has searched through the following tiles (which also so happens to be the path screenshot that it takes).
3) The rest of the screenshots are simply the agent moving one tile at a time to the target.
4) Moving closer…
5) Moving closer…6) Moving closer…
7) Moving closer…8) All done!
Below is a console log output of the second A* example executing:
Part B (Option 1): A* Searching! Resetting gameGrid! | [001][002][003][004][005][006][007][008][009][010][011][012] | | [013][014][015][016][017][018][019][020][021][022][023][024] | | [025][026][027][028][029][030][031][032][033][034][035][036] | | [037][038][039][040][041][042][043][044][045][046][047][048] | | [049][050][051][052][053][054][055][056][057][058][059][060] | | [061][062][063][064][065][066][067][068][069][070][071][072] | | [073][074][075][076][077][078][079][080][081][082][083][084] | | [085][086][087][088][089][090][091][092][093][094][095][096] | | [097][098][099][100][101][102][103][104][105][106][107][108] | Done Resetting Game Grid! Added 54 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 54 now... New OpenList->West: Tile[53]: f: 6 g: 1 h: 5 p: 54 New OpenList->North: Tile[42]: f: 6 g: 1 h: 5 p: 54 New OpenList->South: Tile[66]: f: 4 g: 1 h: 3 p: 54 Added 66 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 66 now... New OpenList->West: Tile[65]: f: 6 g: 2 h: 4 p: 66 New OpenList->South: Tile[78]: f: 6 g: 2 h: 4 p: 66 Added 78 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 78 now... New OpenList->East: Tile[79]: f: 6 g: 3 h: 3 p: 78 New OpenList->West: Tile[77]: f: 8 g: 3 h: 5 p: 78 New OpenList->South: Tile[90]: f: 8 g: 3 h: 5 p: 78 Added 79 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 79 now... New OpenList->East: Tile[80]: f: 6 g: 4 h: 2 p: 79 New OpenList->South: Tile[91]: f: 8 g: 4 h: 4 p: 79 Added 80 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 80 now... New OpenList->East: Tile[81]: f: 6 g: 5 h: 1 p: 80 New OpenList->North: Tile[68]: f: 6 g: 5 h: 1 p: 80 New OpenList->South: Tile[92]: f: 8 g: 5 h: 3 p: 80 Added 68 to ClosedList. And removed this tile form OpenList. Checking neighbors of tile 68 now... New OpenList->East: Tile[69]: f: 6 g: 6 h: 0 p: 68 Final Path: 54,66,78,79,80,68,69 Using path to move to target now. All Done!
Lessons Learned
Since I had already studied the A* algorithm prior to beginning work on this assignment, I don’t feel I learned too much about the algorithm itself from the code itself. I did learn a lot about Unity, as well as it’s Sprites. I started prodding more with Unity and seeing what other little features and touches I could add to make the experience better for someone who was executing it. I’m still lacking in my ability to dynamically display text to the screen (Unity’s Canvas is extremely difficult to work with) — but I am improving also as a result in order to find other ways to display text (such as large sprite images for the main menu for example or the tile number overlay sprite)
I learned that A* is at the same time both very simplistic, but also very complex in terms of code. I’m sure libraries must exist for it, but hooking them into your game could be extremely difficult depending on the game you have and the engine being used. I suppose the same could be said about neural networks to some degree. For the game I set up, it works remarkably well. I was actually pretty surprised how well it worked.
The hardest part for me wasn’t the algorithm code’s logic, but to actually have everything prepared for the logic to finally be able to perform its calculations. For example, needing to set up a tile’s class to store individual tile’s attributes for F, G, H and P, knowing the position of the vectors, calculating the distance, dealing with some minor unity issues with positioning and so forth. Lots of many nuances were encountered, but once those were ironed out I was literally done before I realized I was done.
In terms of weakness, I believe at the moment there’s a lot of duplicate code that needs to be cleaned up. Obviously A* can only find the shortest path to one target at a time, so there are those limitations in place as well. If I wanted to create something like a “bullet hell” type game, I would be much better off with something like a neural network based algorithm I believe.
In terms of the assignment, I would have loved to include sprite walking animations as well as change the sprite in the direction it’s walking towards. I had the sprite sheets and began heading down the path in order to do so — but it ended up taking me far too much time and realized it would have to be something I pursue another time. I also wanted to create a sprite overlay of arrows similar to “Advanced Tactics” game’s movement arrows for units to show the path to be taken, but this too would require sprite sheet access and manipulation rather than the simple swapping of a single sprite that I did as a final touch for my version of the project.
In terms of using the algorithm again in the future — I believe I would focus more on the layout of the game, and how I want it to work as a game first, then build the A* algorithm behind it afterwards. This would likely make coding it a lot more easier. In my case it was very much like molding clay and shaping it one way, then another way and slowly molding it into the final version without a totally clear image of the final outcome.