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!
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).
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.
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.
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:
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:
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:
The artificial life simulation, as it was, would not have been possible without these free assets:
- Ant model – https://www.turbosquid.com/FullPreview/Index.cfm/ID/856094
- Fungi models – https://assetstore.unity.com/packages/3d/vegetation/pbr-mushroom-pack-lite-56263
- Ground texture – https://assetstore.unity.com/packages/2d/textures-materials/floors/grounds-materials-sample-photoscanned-55437
- Foliage – https://assetstore.unity.com/packages/3d/vegetation/yughues-free-stylized-foliages-13392