Enemy Interactions; Or How I Learned To Stop Worrying And Love The A*Star

In the last devlog, I talked about my intentions to have this devlog focused on completing Enemy Movement and Interactions. That's still, essentially, what this devlog is about, but some complications sprang up along the way. In my last devlog, I demonstrated the node-based movement system. It works quite well for the player, but at the start of this week, I had no idea how I was going to get it to make it's own decisions about how to move a particular enemy. At first, I tried a random number generator, assigning a different number to up, down, left and right.

The random number generator worked reasonably well, but this fairly simple AI was just as likely to stand still and stare at a wall as it was to make any real progress towards the center of the map, and the Generator the player is trying to protect!

It was at this point, I decided to use A*Star Pathfinding. The class already had a functional A*Star that had been provided by our Lecturer in one of our Practicals, and I was already using the PathNode code provided as part of the A*Star to manage the nodes, so it shouldn't be that hard to add it in, right? Wrong. Very, very wrong.

One of the big problems was that the A*Star we'd been provided was intended for continuous movement, not stopping and starting at specific intervals, at specific timings. This wasn't going to work with Static Vs UndeAAd, a turn-based game with lots of stopping and starting at specific intervals, at specific timings! I could have, in hindsight, decided to just go with the random number generator and have a very simple AI, but it lacked the threat that created any kind of urgency. A player could simply ignore enemies that were too far away because the AI would just keep bumping in to walls, or going backwards. I ended up deciding that if the A*Star provided to the class wasn't going to work for Static, I'd just have to create my own!... Mostly!

The way an A*Star works is using an algorithm that gives each location a weight based on how far the Enemy is away from the target destination, and if the Enemy has already stepped on that space. It does this using two lists, an open list (Which contains nearby spaces it hasn't stepped on yet, and spaces adjacent to spaces it has recently been on), and a closed list (Spaces it's already been on, or spaces that it can't go through). The Enemy checks the weighting of each space in it's open list, looks at the square with the lowest weighting, and if it can go there, it does. If it can't go there, it checks if there's a Player there or a Generator there, and decides how to act accordingly.

How does the Enemy work out the weighting for each space though? Each space has three values; 'G' which is how many times the node has been stepped on, 'H' which is how many nodes of movement it would take to reach the center, and 'F' which is the total of 'G + H'. Given that Static takes place on an 11x11 grid, that's 121 nodes, each with their own 'G' and 'H'! The 'F' is calculated by the Enemy at the point when it's making it's decision on where to go.

In the first iteration of my A*Star, the Enemy did all of the calculations itself, from 'G' to 'H' to 'F'. This proved problematic, as the Enemy (whilst using them to navigate) has no concept of the PathNodes as a measure of distance. It simply didn't know how to think of the PathNodes as a measure of distance, or the connections between them, and I lack the programming prowess to teach it. This proved a blessing in disguise. The second iteration of my A*Star involved modifying the PathNodes to keep track of their own 'G' and 'H' values, allowing me to manually set the 'H' values for each node on the grid.  At last, the Enemy could understand the concept of Nodes as distances.

At this point, the Enemy is now able to use A*Star Pathfinding to walk around walls towards the ultimate goal of chomping down on that Generator! The added benefit of the node keeping track of both 'G' and 'H' is that with sufficient foot traffic, it creates a psuedo-random number generator, that still encourages traffic to move towards the center of the map, as the 'G' value climbs higher and higher!

Next Week; Presentation and Graphics (Goodbye, little blue and green fellows!)

References;

A*Star Algorithm obtained from Johann Fradj's Article; "Introduction to A*Pathfinding", <https://www.raywenderlich.com/3016-introduction-to-a-pathfinding> Accessed 17/09/2020