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

Acknowledgements

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

Advertisements

Process scheduler assignment

Uni, University & Life (Legacy)

This is a fairly quick and fun (for me, at least) blogpost about something I have to consider for a university assignment.

The assignment revolves around developing a scheduler in C++ that could theoretically be applied as a process scheduling algorithm for an operating system. We were given a code spec to conform to, which consists of class and functions definitions for a integer Stack, Queue and Scheduler. The assignment mandates that we make all three paradigms operational (no surprise). Implementing the first two things was easy, but building a scheduler requires a lot of thinking. Thanks to the specification and the assignment briefing, we are shown that the scheduler operates with 10 priority levels (0 – lowest, 10 – highest) and it bares some relation (inheritance) to the Queue functionality.

You might be thinking: “Woah there Khalid, lot more thinking? Processing tasks based on priority levels is easy ’cause you just select the highest priority items first and go from there…”. Well in theory, that is an easy concept to understand. BUT with that specific approach, you could experience one of the most breaking problems in scheduling.

Blocking.

Blocking (which is the phenomenon where low priority tasks are ‘blocked’ from being processed by high priority tasks) could effectively break the integrity of a system that is supposed to take on more and more tasks whilst operating (like our process scheduler). Whilst those low priority tasks are supposed to be… well… low priority, they are not irrelevant and will need processing eventually. Even in scenarios where tasks are not added during operation (schedulers that have a predefined task list to complete), sequentially processing items from highest to lowest could result in the lower ones never being touched (at least until after an unreasonable amount of  time) since there could be a huge amount of set items!

Imagine we have a system that has a million high priority tasks but just one low priority task. If the scheduler is processing sequentially, it will take a huge amount of time to reach that one low priority task. Surely, there has to be a better way?

With the use of some more processing power, there is. But you’re gonna have to wait to find out! I’m currently having an interesting time trying to select an appropriate method. I’ll likely report my findings after the assessment is submitted (because I do not want to give the answer away).