Algorithms and Ant Sex

Assignment: Y3 Artificial Intelligence

So, ya boi Shark here finished a really fun coursework last Friday!

The coursework was for one of my favourite modules – Artificial Intelligence for Game Developers. Since term started, we have looked at search algorithms, decision trees, artificial neural networks, fuzzy logic, finite automaton, evolutionary computing, clustering, and self-organising maps. We also briefed deep learning, although that’s for later in the academic year. Now, the coursework asked us to select appropriate (and reasonable, considering time restrictions) techniques from some of that pool for NPC navigation and artificial life simulation.

Please read on!

NPC navigation

My NPC navigation implementation was your standard A* search stuff. We were asked to come up with a solution to get from A to B on a map made up of different terrain types. The types – grass, marsh (slows you down), road (speeds you up), river, and mountain (both block) – were given to us. The A* algorithm is widely known for pathfinding and graph traversal, mainly because it’s basically a great extension of the popular Dijkstra’s algorithm with heuristic (educated guessing) guidance. To show informed choice, however, I did implement alternative algorithms to show the difference in operation:

  • Breadth-first search (BFS)
    • Only suitable for unweighted graphs
    • Imagining the graph is like a tree; simple concept of looking at all leaves on the same branch level before going deeper
  • Depth-first search (DFS)
    • Only suitable for unweighted graphs
    • Concept of going to the lowest branch first, then recursively going back up to explore leaves on the way
  • Dijkstra’s algorithm
    • Designed for weighted graph, but will act like BFS if all weights are equal

In theory, implementing A* is relatively straight forward – implement Dijkstra’s, then tack on some heuristic cost calculations. The solution is VC++ 2017 based, with the result being rendered in C++ console (there is no mark on aesthetic).

My heuristic – Manhattan distance

During development, I realised the core algorithm (the Dijkstra’s without heuristic) of the program was spitting out weird results that was only resolved by adding heuristic. Due to time constraints, I was not able to properly debug the issue before the deadline (but I did write and document the issues).

Artificial life simulation

This is where this assignment got REALLY interesting! For this second part, we were asked to come up with a life simulation game that shows agents (entities) interacting dynamically. I developed a fungi-ant simulation (that is not really accurate to real life, but fine for this assignment) that shows how both populations change and affect each other over time. My attack was developing the agents to be powered by a finite state machine, and specifically develop the ants with a genetic algorithm to facilitate the dynamic development of their population. I opted to do this part in Unity (2018.2).

My three agents are fungi, worker ants, and queen ants. The fungi simply replicates itself (stylised as one of four visually-different variants) via sporing, whilst also growing in size over time. The worker ants collect fungi via random selection and short-range sight and return them to the queen ant for the queen’s consumption. The queen ant, once well feed, will summon a worker selected via fitness proportionate selection to mate with.

This is what it looks like whilst running!

Finite-state machine

Finite-state machines (FSM) or finite automaton is the way of looking at computing where a machine operates with one state of operation at a time. Such a system is useful for the basic AI operation since it works by changing the state of an agent based on a specified and strict set of variables to look at. Each entity has its own FSM tailored to a generalised version of how they act.

One of my state diagrams (for worker ants)

Genetic algorithm

The ant population is influenced by a genetic algorithm designed to refine the performance of the ants over time as new generations are born. The process is triggered by the queen ant, who summons a selected mate via a pheromone when the queen ant is in a state of mating. The mate will return to the queen and some DNA splicing will begin!

Representation of DNA

Obviously, the DNA is generalised. Otherwise it would take forever to specify realistic genes and visualise them. So DNA is simply a collection of three variables acting as the ant’s “genes”; speed, sight, and hunger saturation. All three are floats and used fundamentally during the simulation of actions such as moving about or detecting things around the individual.

Fitness and mate selection

Fitness is a value we use to summarise the overall “quality” of the ant’s DNA. It is simply defined as f = (speed+ sight + hunger) / 3. We can use this to guide the queen’s selection of a mate so it’s not a total pseudorandom selection. I opted for roulette wheel selection. It operates by calculating the current ant population fitness (sum of all ant fitness or Σf) twice, but on the second time the ‘summing’ stops when a random threshold is reached. The iterative value used when looping the ant population is used to select a mate. In code, this looks like:

Splicing DNA

When an attracted worker arrives at the queen, DNA splicing will occur that creates some new DNA with a 50/50 chance splice of each of the three genes from the queen and the worker.  A random mutation may also occur when this happens, which for better or for worse will add some variance to the population. This looks like:

Note: the bool happened was added to quickfix a bug where multiple ants were being spawned before the queen’s FSM switched from the mating state to its idle/feeding state.
Extra context: mutationRate is ridiculously low (defined as 0.05f)

In conclusion, then…

…this has been a ballin’ coursework! The second part in particular was a joy to implement and I hope to continue on with it in the future. Maybe there will be a follow up post in a few months’ time? 😀

Oh, here’s a parting screenshot:

Hastily-assembled – you can tell I made because there’s an obligatory lens flare


The artificial life simulation, as it was, would not have been possible without these free assets:


An interesting term!

Uni, University & Life (Legacy)

As of last Friday, I’m now off university for a few weeks. I thought it might be neat if I make a post about what I have done these last few weeks for university, so here goes!

“Project FallingStar”
…is the single biggest thing I have been involved with this term. For the Professionalism module, we were put into groups (four, five (as it is for ours) or six people) and tasked with planning and building a 3D game from scratch whilst still learning the engine we have to use (Unity). I am pleased to say I have thoroughly enjoyed the project so far! The idea for our game is that the player builds modular space probes to send out on exploration and defence missions in the solar system. Despite initial doubts that our idea was too ambitious for a bunch of UNI students, our team (designated Team 1) is working well and our recent demo was well-received! My main contributions to the team have been physics programming (producing the gravity model) and leadership (defacto, since it was something that I naturally slipped into rather than being designated).


“A little peak” – credit to team member Luke Probert, who developed this splashscreen!

OpenGL coursework
This coursework was also fun. In the Computer Graphics module, we have been learning the basics of OpenGL and the assessment was to compile a 2D OpenGL scene that makes use of advanced OpenGL features (compared to just using immediate mode rendering) such as Vector Buffer Objects (and Vertex Array Objects), hierarchical modelling, and transformations. Whilst I have to wait for my grade, the demonstration I have to my lecturer was well-received!

Python + Pygame
This coursework was interesting ’cause I both did and did not enjoy it. The coursework was split into two tasks; building a missile command game clone with Pygame and then developing a small physics sim “Marble Madness” with a lecturer-created engine. Both tasks had their merits, which for me was mainly the fun of programming. What I did not like was that we could only develop the second part on Linux since the engine (PGE) is Linux-only. Whilst I have Linux at home nor is Linux THE problem, there is really only one computer lab in the university (where I work better at than home) that has Linux. This meant I could not always be guaranteed a computer since the lab was in high demand. I was even asked to leave for another class on two occassions, with can really be inconveniencing!

So yeah, that’s what I have been up to academically! In my spare time, I am continuing the development of Path to 2265 as another personal priority. I’ve recently made some huge underlying changes that I’ll be posting about this week!

Enjoy your day!