easy web builder

Ant AI

Homework assigned at SMU guildhall intended to teach us AI basics and optimization. The goal of the assignment is to create an ant colony that can survive off the land and outlives other ant colonies.

Mobirise

In the above .gif, you will see two ant colonies trying to survive. My ants are the orange ones. There are a lot of moving components, but the important ones are these. To begin with, you have A queen, two farmers, two soldiers, and a scout. Each unit eats a certain amount of food per turn. Every ant also has an opportunity to act, turning a turn. After 30 microseconds, any ants that are still deciding to act, their colony will be penalized. Once ready, all actions are performed at the same time and are adjudicated. Some actions that you can take are, move, dig, pick up, and attack, and each unit has it's specialty focusing on one of the actions. The game is essentially an RTS, and we are attempting to make a power colony to beat other colonies.


I wanted to focus on having a good foundation in pathfinding. I started with Dijkstra's algorithm, as well as creating debug functions to draw out the pattern. Because we were using a square grid, I could make the data representation relatively easy and compact. I used a 2D array of NodeRecords, which is a struct that contains the current position, the index of the parent node within the 2D array, the order the ant took to get to the tile, the cost so far, a heuristic if any, and an enum to state if the node is in the open list or the closed list.

Mobirise

Next, for the open list, I created my own templated MinHeap. I made sure the pop function just got the top of the list, making it instant, hence making the push function the longest.

Mobirise

Gains that I achieved are from the index of the parent node, and the enum for which list the node is in. Instead of newing off NodeRecords when I need them, I decided to new off the size of an entire map of nodes. Yes, this is a wase of memory, but it keeps all the nodes compact, meaning it is cache hot. Next, I use an enum to determine if a node is in the open or closed list. Usually, In Dijsktr's algorithm, you have to keep track of both lists so that you can query if a tile is in either one. However, since I am already storing my nodes in a compact container, I can add a flag to it, rather than making two more containers. On top of that, I know which list they are in instantly, rather than taking time to search for them.

Mobirise

After ensuring that the Dijstr's algorithm worked, I copied the function and created an A* function. The only thing I had to change between the two algorithms is the calculation of the priority value, and the checks for the open and closed list. The priority value now equals the cost so far, plus a heuristic to get to the goal. However, since we are on a uniform map, we have a slight issue with the algorithm's fill. As the algorithm picks potential nodes to search, the nodes around are just as likely to be picked vs. the new node because of the priority value. What we want are nodes that direct us towards our goal quicker, rather than nodes that go away. So for my heuristic, I add not just the manhattan distance, but also a small octile distance as well. This means that nodes that are farther away will have a slightly significant value, vs. the more direct nodes. The direct nodes will have a small change in value, but not enough to ruin the fastest path.

Mobirise

Postmortem

At the end of the assignment, this was all that was needed to beat the entry-level Ant Colony. However, going back over this algorithm in this new API, I realize how important it is to know your foundations. Once I had a well-structured system, I could manipulate the algorithm ever so slightly to find better or smarter routes, just through planning alone with no decision making. I was able to gather resources at extreme rates that I could starve out the other colony. The only other plan I added was making my warrior ants attack anyone who came near my ants.