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

Dissertation and Lorentz factor

Assignment: Y3 Dissertation, Uni

Ya boy Shark here about to spit mad equations at you!

Okay, maybe not like that. But now that the first milestone of my dissertation is past, I am feeling the need to talk about it a bit. This will be the first of a series of posts about what I’m doing.

An overview of the project

My dissertation title is “Relativity Simulation: Develop a physics-based game that utilises the principles of relativity, complete with GUI”.

The opportunity to study relativity on my third year project was something I could not turn down or substitute with another choice despite the depth of challenge in front of me. The impetus for the choice stems from my previous year’s team-based workshop assignment, which saw me developing the realistic gravitation physics behind our team’s game. With other aspects of the game put aside, the end resulted in a profound experience for me when I saw our little own Newtonian universe come to life. Now inspired to take on more advanced physics programming so that one day I can do it again more realistically and better, this project presents me with that opportunity to learn the physics I need with a hands-on project!

The first step of this journey was interpreting and narrowing down exactly what I want to do within the confines of the given title, since there is only so much I can do given the time constraints of the predetermined milestones and the time it will take me to digest everything I learn (something I hope these sort of blog posts will help me). My project aim is to create an educational and interactable simulation that demonstrates how relativity works and how everything changes when you alter relativistic (and by extension; applicable Newtonian) constants such as the speed of light, Planck’s or universal gravitational, which you need to do to complete game levels. Basically, you skew how all game objects interact because you’re basically altering how the virtual ‘universe’ is working. I’m hoping this can evolve into a fun game where you don’t interact with the objects themselves to complete the levels, and the player gets a visual idea of what relativity is without being bombarded with straight up equations, etc.

Milestone one saw me set out the aim and objectives, write my literature review and background research, and design the solution I’m working from (which will be a Windows OpenGL project). Right now, I do not have my game design specified since I am still in the process of researching relativity and deciding what aspects I am gonna use to build a game out of. Milestone two will ultimately have it though, which is due early-February. However, thanks to research I have done, I have indeed found an aspect of special relativity that I can potentially use as a game mechanic. So please, read on for part one in this journey to understand relativity!

But first, a bit of context

Actually, first we need a disclaimer: I possess up to A-level physics education, so please forgive any inaccuracies should there be any since I do not study physics as a part of my course. When I do study physics it is in my spare time – I’m trying my best!

Anyway. Relativity is perhaps one of the most important developments in physics in the 20th century, and today is a prime example of successfully-observed theoretical physics. It encompasses two related theories proposed by Albert Einstein that were built upon the results and findings of other physics such as Albert Michelson, Hendrik Lorentz, and Henri Poincaré. The two theories are special relativity (1905) and general relativity (1916). As stated before, special relativity (STR) will be the focus of this post since its within it that I found my potential ‘playing cards’ for this project. (Don’t worry about general relativity for now, since I will be posting about it closer to the next milestone once I’ve finished my research into it.)

So, STR! It describes the formerly-separate concepts of 3-dimensional space and 1-dimensional time as a 4-dimensional spacetime continuum, replaces the Newtonian Galilean transformations with Lorentz transformations (layman’s: a method of examining different perspectives of time, size and position in space), and states that the speed of light is an absolute constant.

Focusing specifically on the latter two tenants of STR, fixing the speed of light means only time, mass, and length change in calculations from now on. Hence we have consequences that you might of heard of, namely time dilation (event perceived at different times by observers at different velocities), relativistic mass (object’s mass increases with velocity), and length contraction (object’s length decreases with velocity). Each one is possible thanks to having a fixed reference (the speed of light as a constant) to calculate a velocity/light speed ratio with. This ratio is a part of the Lorentz factor, which is key to this idea of what I can make a game out of!

Beware, maths and formula ahead!

The Lorentz factor

The Lorentz factor is pretty much the key to calculating the most well known and visually-representable special relativistic effects. The factor arises from derivations of the Lorentz transformation that allows us to measure how time, mass, and length are affected by time dilation, relativistic mass, and length contraction respectively. The base factor is expressed as:

As aforementioned in the context, the factor relies on a ratio of comparing the velocity against the speed of light so that we know how time, relativistic mass, and length of an object changes when said object moves. The factor should return a value between 0 and 1, where 1 shows absolute lack of velocity. 0 would mean velocity is the same as the speed of light. We can then divide or multiple the factor by specific properties of an object to calculate relativistic values. Below shows three applications of this:

If you’re paying attention to the first two straight away, you might notice that if velocity is the same as the speed of light (299,792,457 metres per second), the result of the factor (as aformentioned, would be 0) would yield an error like “Math ERROR” on a scientific calculator or “#DIV/0” on Excel. This is normal (duh, you can’t divide by 0!), but there will be some additional relativistic explanations later for each specific case.

Time dilation

Starting with time dilation, I’ll be trying to explain these applications in a way that can be somewhat more easily digested that what you might find on Wikipedia (for example).

So, observer time is the time measured by an object that takes into account the relativistic effect of moving at extreme velocities (as opposed to “proper time”, which is time measured without any relativity taken into account). Suppose we have a stationary Shark named Wrex and an in-motion Shark named Princess travelling one-quarter the speed of light (0.25c or 74,948,114.5 m/s).  Let the proper time (from an independent clock) measure the time as 1PM (or 46,800 seconds from midnight).

My wonderful illustration

So we can see that at high velocities, Princess’ clock is no longer synchronized with Wrex’s observed time or the independent clock that provides us the proper time reference. The extra ~1,535 seconds or ~25.58 minutes is something no human can presently experience since we do not have any sort of vehicle that can propel us to the sorts of speed required to experience it. If we COULD reach the speed Princess is travelling, the subject would age slower since it would take them ~48,335 seconds to experience the same events a stationary observer does over 46,800 seconds. But let it be clear we do indeed ‘experience’ time dilation daily when we are at some sort of motion, although we ourselves cannot notice. To put this into perspective: the fastest thing the average human could experience, a commercial jet aircraft, would register an observer time of 46800.0000000157 seconds assuming velocity is the average jet speed of 885 kilometres per second or 245.833 m/s (source) and proper time is provided by the same clock used in the Wrex/Princess example. This is something only an atomic clock could register.

Relativistic mass

Relativistic mass (kilograms) is the measurement of “effective” mass that takes into account the increase in its inertial mass at high velocities, with inertial mass essentially being a parametre of mass that specifies it’s resistance to changes in motion. Using Lorentz factor, we can measure and prove that at higher velocities, the overall mass will increase. So now suppose we have a Shark named Benedict who has a “rest” mass of 50 kilograms and is travelling at one-quarter light-speed (0.25c or 74,948,114.5 m/s).

Another sick illustration (note: the final answer had an error, so I replaced it digitally)

So Benedict’s mass increased by 1.6397779494322 kilograms at 0.25c! One consequence of relativistic mass is that an object with a rest mass more than 0 cannot travel at the speed of light – as an object approaches c, the object’s energy and momentum increase without bounds. It is possible that you might have heard about this if you’ve ever looked into the challenges of deep-space travel within realistic and liveable time-frames.

Another interesting note is that we can calculate the relativistic mass of an object using its energy value, something possible thanks to Einstein’s famous equation that states mass and energy are equivalent:

Length contraction

Length contraction is the phenomenon of an object’s length being shortened in the direction of motion. Once again, we can use Lorentz factor to calculate this BUT formula is set out differently than in the last two uses, since we are calculating the contraction of the value in question and not the increase. So suppose we have a Shark named Louise who at rest (actual) length is 1.5 metres and is travelling at half-light speed (0.5c or 149,896,229 m/s).

The final sharktastic illustration!

So Louise became ~20cm shorter at half-light speed, but there is not much more to say about length contraction other than it is also known as Lorentz-FitzGerald contraction since it was postulated by George FitzGerald in 1889 and Hendrik Lorentz in 1892.

So, can we conclude this already?!

Yes, we can!

I think all three examples presented today can be invaluable in my game design, since what I need are mechanics that can be incorporated into the game that are both innovative (since there are very few relativity-based games out there) and representable. The latter is going to be a challenge, since in order to visualise any of these I need to scale the universe and its constants down to manageable levels. So constants such as the speed of light might be hundreds or even thousands of times smaller than actuality in order to make velocity/light speed ratios small so that changes to the effects can be noticeable on screen.

Anyway, that’s all folks! 😀 Hopefully this might be interesting for someone!

Supportive sources

Further reading…

Notes

  • All shark-based diagrams are free to use provided they are referenced to this blog
  • All equation images are free to use without reference!

SharktallicA: The Blog Reboot… Again?

Life, Uni

Well, hello there!

Shark here for another SHARKTASTIC blog reboot, but this time it’s all grown up and serious. Okay. Maybe not quite. I mean, I’m still the same old workaholic but I’m wanting to have a little tidy up here. This blog has been on hiatus since August, and a number of events have happened since then that have required my undivided attention. However, I’m back (hopefully)! 😀

So just prior to this post, I made almost all my ‘my life’ type posts private. Upon reflection, I believe some are a bit too personal for them to be readily out there. Plus they were quite cliche-y, TBH. All project posts are still public, although some of those projects are now terminated (see below). Going forward, I’m hoping to post more about projects, reviews, rants, and ramblings, but I will occasionally post stuff about life under the sarcastic and self-reflecting persona of Shark!

Now, let’s get into some Khalidonian updates!  Spoiler: “You don’t get spoilers ;)”

In regards to my work, I’ve pretty much dropped all projects for the foreseeable future to free up more me-time and allocate some of it towards self-studying. My Tholian Simulator game has been shelved indefinitely due to complexity and lack of time. Most of the planning phase was completed, so it is just a matter of dedicating time (when I have it) later on down the road. Path to 2265 Chapter 3 is postponed until next year since I’ve had not a lot of time to write creative stuff and I’m wanting to review over the rest beforehand (since re-reading it over, it feels like a 14 year old wrote it and there are so many typos). Everything else should be assumed to be cancelled. This freed time is partially channelled into University work; my notable works so far is my artificial life simulation coursework and my dissertation, which will both soon have their own posts since they’re both super cool!

Now in regards to my life, oh boy. This summer has been… interesting. As I tried to allude to, I’m not gonna try to post cliche stuff about being heartbroken, parental separation, and shit. I’ll just quickly summarise in saying that I approached each problem asking myself “What can I learn from this?”, and I believe I have the answers I need. I’m genuinely fine though, so no need to worry!

And yeah, that’s it really. I’ve joined a few societies at University, have good friends, and I’m now a student voice representative for my Faculty school and I’m really enjoying the role! I got some cool assignments and dissertation this year that will add immensely to my portfolio, and I still have some good project ideas for when the time is right!

As a wise Shark once said, “when life gives you lemons, put them in the fridge”.

Wait, what?

Alright. Fair enough. Shark out!

Snow in Treforest

Life, University & Life (Legacy)

It kind of took me by surprise. It has been about a decade (from what I remember) since it last snowed well in Wales – long enough to forget what snow even feels like. So, when I woke up to see that my street is now completely blanketed after a day or so of snowing, I couldn’t contain the urge to just walk and have some fun in it!

The result: one of the best days I have had in a while! I have previously talked about my love of the simple pleasure of being outside and walking, but combine that with this soft and pretty snow and I just didn’t want to not be in it! Throughout the day, I made four different voyages into the snow equalled a combined 20,500 steps (as per Google Fit). My legs are pretty tired to say the least, as fighting the fairly strong wind and the resistance of large piles of snow did take a little bit of a toll but every moment was worth it!

There are a few notable examples of fun or interesting things I did in the day – including spots of photography, banter with friends etc. But the one that left the biggest and most personal impression was this moment when I was walking alone past World of Groggs on my last trip of the day at around 2050 hours. Imagine a setting of this usually busy street now blanketed in vibrant-white snow and silent of human contamination. Where the force of the gentle wind becomes audible and snow creaks as you tread. For some random reason, I looked back when I was walking in this setting and realised how much devoid of human life this street now was. At first, the I got this deep feeling that I was truly alone for a second – like if I were to scream, no one would hear me. But when I turned back around, I realised how beautiful and calm my surrounds were. I could now enjoy this surrounding to the point where all scares and cares went straight out of me and walked home with a smile!

I think that moment will stick with me for a while. I hope to be out early tomorrow for a spot of photography. Hopefully my main camera’s battery won’t die early in the day again!

January has been hectic

Uni, University & Life (Legacy)

Where do I begin…

January has probably been the busiest month in my entire life. No kidding! Constant work, personal projects, assignments, and very little free time to myself. But I am happy to say I have enjoyed all of it!

Since December
Since my last life update last month, I have had two coursework results back from my Computer Graphics and Tool Development for Computer Games modules. The former was a 2D OpenGL scene demonstration where we had to sample OpenGL objects and techniques and demonstrate them – from Vector Array Objects to hierarchical modelling. The demo at the time went well, and I got 88% in the end! The latter was building a Python missile command game clone with the Pygame engine and developing a small physics simulator called “Marble Madness” with a lecturer-developed engine (PGE). I had 90% on that one. So I’m happy with my performance last term to say the least!

Computer Graphics
For the second term, this module now focuses on 3D rendering in OpenGL and 3D modelling with Autodesk 3DS Max. Things have continued to go well this term, and 3D modelling is actually more fun than I imagined! It has been useful for my group project in another module as well! The programming side is obviously interesting, but we are still in the opening weeks and have not done a lot of programming for OpenGL 3D yet.

Tool Development for Computer Games
Whilst I don’t have anything against Python, the module is a lot more interesting for me this term now that we are starting to do C# GUI programming with XAML. Whilst I have done a few WinForms projects before, WPF is something I have never touched before! The coursework looks like a nice challenge too, which is to build a game level designer for a tile-based game. We are given the game and its source code and have to build the designer based on the code ourselves!

Data Structures & Algorithms With Object Oriented Programming
This module recently had a coursework due on the 12th, which was the process scheduler assignment I talked about in a post back around late-December. Basically, we were given a public API to conform to and told to fill in the blanks in C++. My scheduler ended up being a multi-level queue with a custom algorithm that creates a cycle to prevent blocking (the act of higher priority items stopping lower priority items from being processed completely). The scheduler creates a cycle in which each level of priority (from 1 to 10) gets a certain amount of attention. Higher priorities get more attention than lower ones in the cycle, but the lowers still gets *some* attention rather than none.

Other than the coursework, this term has also taken up a slightly different theme. We are now covering different design and strategy patterns to OO programming. Whilst they certainly require a bit more thought to understand, one of the two we have learnt so far has already came in handy with my web work! The observer pattern, which states the relationship between a subject (essentially some hub) and its observers (dependencies like clients), is basically the same principle of the way I’m developing this small social network in PHP for my portfolio.

Professionalism: “Project FallingStar”
Once again, the largest and most impressive thing I am involved with at University. My team has made significant progress and whilst we are far from having a complete game, the game is looking rather beautiful already! Besides defacto leadership and physics programming, I have also undertaken tasks for 3D modelling and special effects for the game. Like the last time I wrote about this, I have some little peaks for you:

Personal projects
I have also made a fair bit of progress with personal things as well. My Star Trek fan site, Path to 2265, remains a top priority for me and many improvements in the back-office have been made. The website’s search engine programming has transformed into a mature, secure and robust platform that allows the website to provide intelligent and weighted search results, whilst also providing internal benefits by allowing pages to be more dynamic and use the website’s database more. I’ve also been working on actual front-end content as well with Chapter 2 being released within a month or so and several more ships added; Polaris has a completed database entry, DY-732 has its specs mostly ironed out, and an upcoming design is due for completion soon:

stage_4

The new (but still prototype) design – UESPA battleship SS Patterson (UESPA-57)

I have also resumed limited work on my old GeckoFX-based C# browser KAubersnek. I’ve been adding a few features over the weeks and will likely continue full development when I have some time.

Capture.PNG

KAubersnek in its current state

 

Anyway, that’s it for now!

 

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).

20171219_fallingstar.png

“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!