Overview

  • My ant colony is Orange in the video
  • AI is contained in a DLL which is loaded and used by the Arena program and pitted against other AIs. When the Arena requests orders from the DLL, they must be given in less than 1ms
  • Ants have limited view distance. Any updates and changes from the Arena map passed to the DLL must be handled in less than 1ms. Every time your program goes over the time limit, one of your ants is killed as punishment
  • Implemented A* pathfinding to find shortest possible paths to enemies and food, and used priority queues to handle path requests from the ants.
  • Used a Finite State Machine
  • Used mutexes for thread safety when updating the arena states, setting objectives, and handling path requests

Ant Types

Development  &  Strategy

The factor of the project that constantly loomed over was the strict time requirement any time my DLL interacted with the main program. Giving orders to ants turned out to be pretty quick, as the most complex thing they needed to do was find the nearest entity. Path requests proved to be the bottleneck, so I took some steps to ensure that pathfinding was fast as possible. 

First, I had ants do any "thinking" and requests for order first, and then any time that remained would be spent granting path requests based on a priority queue of requests. Within the pathfinder itself, any A* data was encoded into the map (g, h, f costs), and a binary min heap was used to maintain the open list so I could quickly find the next node to check. A sample of the pathfinding code is included below.

For my Colony strategy, I decided that maintaining a ratio of workers, scouts, and soldiers based on the overall situation of the colony would be an effective way to maximize the value of each ant. The colony as a whole would try and position itself as close to the largest amount of food as possible in order to maximize resource gain. Soldiers would attack enemies closest to workers and queens in order to defend the colony, and would go on the offensive if the colony was safe. Workers find and "claim" food that is the most efficient to get in terms of distance to the food and to the queen. The ratios of each type of ant are adjusted based on current resources, information on the enemy, and sudden death status (where food stops respawning).

What Went Well

  • Significant time was spent planning out the overall class hierarchy and interaction up front, which prevented huge amounts of refactoring and rework down the line
  • Researching how to handle interactions between the DLL and main program progresses quickly, allowing me to begin development soon.
  • The AI technique was very easy to tweak and balance

What Went Wrong

  • Some debugging visualization was not developed until relatively late in the project. As a result they were not as robust and useful as they could have been during development

What I Learned

  • When developing AI, ensure that any debugging and conveyance tools are developed ASAP - the initial time investment will definitely pay off when debugging later in the project.
  • Ensure that your AIs abilities are flexible to allow for faster iteration, balancing, and adaption.

Code Sample - AStar.cpp