Overhaul of Infected AI

[annikk.exe]

The Infected AI engine has been praised for its virulence and aggression, however it is extremely messy and difficult to transport from one level to another.

Therefore I am going to overhaul it - I will use the experience I gained writing the first version to write a new version basically from scratch.

As is becoming usual for me whenever I start a complicated project, I am going to keep all my notes here in public.  I have no clue if others will actually benefit from this or not - hopefully you will - but apart from anything else it's a nice place to keep my notes that I can access from anywhere with an internet connection.  :>



Aims

• The engine must automatically learn about the level, without having to be told lots of different parameters manually by the programmer.
• The engine must be able to deal with levels where the number of asteroids in play changes over time.
• The engine must be equally at home conducting itself in a static level as in a dynamic level, with gravity or roids that are otherwise moving.
• The engine must be easily copy+pasteable from one level to another.
• The engine must deliver a similar level of deadliness to version 1
• The engine must be resilient, able to recover and ultimately take over the galaxy (if left alone) even when knocked all the way back to, say, 1 tree on one asteroid.
• The engine must be capable of controlling multiple AI factions, fighting against each other as well as the player.
• The engine must work fine alongside the Gravity Engine, but must not REQUIRE the gravity engine in order to function.
• The engine must be sufficiently lightweight (unlike version 1) that it can be run on a large number of asteroids without significant performance loss.

Concepts

• The engine will be run on a random asteroid each tick of the "While Running" loop.  The engine then carries out a series of checks for that asteroid.
• The checks determine the asteroid's state: how many trees, how many seeds, how many player seeds, etc.
• The asteroid will also make a list (array) of all a) friendly or empty asteroids, b) a list of enemy neighbouring asteroids or empty asteroids with enemy seedlings on them that are within its send distance.
• The asteroid will set a "metric" for itself based on its own status and the status of the neighbouring asteroids.  The metric is a list that is kept for all asteroids currently in play.  It is used in order to dynamically create a priority travel list for seeds.  An asteroid that can spare seedlings will send them to whichever neighbouring asteroid has the lowest metric.

In version 1 I kept different metrics for guarding the empire, colonising new asteroids, and building up a force ready to attack.  In this new version, I plan to combine all of these metrics into one.  Therefore, one metric array will be used per empire.

Here is my initial proposed scale of metrics:

0 = under attack
100 = asteroid that needs more trees for building
200 = gather point (ready to attack somewhere).


Suppose I'm an asteroid that has been selected for checking.  I have the same number of trees as my treecap, and I have 50 seedlings orbiting me, and I'm not under attack in any way.





I will now look around at all my "neighbours" - asteroids within my send distance - to see what they are up to.  One of them is a blank asteroid, so his metric is 100.  The only other asteroid in my range is fully built too, like me...however his metric is 101.  That means he must be within range of another asteroid that is blank.





Because the asteroid in the northeast has the lowest metric (100), I'll send my 50 seedlings to it, and set my own metric to be 100 + 1.

The seeds will build 4 trees, and 10 will be leftover.  Now the northeast asteroid is finished building, so it resets its metric to nil, ready to be re-evaluated on the next cycle.

On the next cycle when Fluffy is selected, Fluffy realises that now the lowest metric of any neighbour is 101.  So Fluffy sets to 102.

On the next cycle when the north-east asteroid is selected, it looks at Fluffy and sees that the metric there is 102. So it sets itself to 103.  It also notices that it has 10 seedlings orbiting, so it sends them to the next lowest metric...which is Fluffy.






...and then fluffy (102) sends them to the next asteroid (101)...

...which sends them to the asteroid with metric 100, which builds a tree with them.





This is the whole basis for how the engine works.  You can probably do your own thought experiments for what happens if an asteroid comes under attack (and sets its metric to 0).





Sorting out the behaviour of the gather point is the tricky part for me right now.  Especially in dynamic levels, whole sections of an empire might be seperated from one another.  I need to figure a way to let them operate independently of one another, so that orphan empires can still launch attacks and potentially bridge the gap with the other half of the empire.  I need to do this without introducing problems like every asteroid trying to be the gather point.


This will require some thought.

[annikk.exe]

Well, I've thought about it, and here's what I've come up with.

In order to allow seperated parts of empires (lets call them empire partitions from now on) to operate independently, the metric system must work independently for them.

The metrics for Under Attack and Need Construction Seeds work fine, but I was getting worried about the way they gather.  In version 1, I had assumed that there should always be just 1 gather point.

But actually, this is not so.  I have realised that it's actually not a bad idea to have multiple gather points.  You naturally would want to reinforce your front lines.

But there's a slight problem in that we don't want to split all of our seeds over all of the different frontline planets.  Why have 20 seeds on 6 planets when we could have 120 on one?

So what we do, is we make the rules for gather point promotion (ie the asteroid becoming a gather point with metric 200, ready to launch an attack) thusly:

Become a gather point if...

1.  I have at least one neighbouring asteroid that is owned by player 0 or an enemy faction and has at least 1 dyson tree or 1 defence tree or (checkedroid.Treecap * 10) enemy seedlings on it.
2.  None of my friendly neighbouring asteroids (within my send distance) are gather points.


These means that, in a straightforward front-line scenario, every other frontline planet becomes a gather point.
In the example above, that would mean our 120 seeds split themselves 40 on each frontline asteroid.  That's a fairly nice way to do it, that means that as the empire grows in strength it will launch attacks on multiple different points as each reaches the threshold of seeds where it judges it can capture a neighbouring enemy asteroid.

This approach is less single-minded than the original Infected AI, which would only allow a single gather point to exist at any one time.  But it also neatly avoids the problem of orphaned partitions with huge swarms of AI seeds that never attack because the gather point is in a different partition.  With this proposed new logic, a gather point would appear in that swarmy partition the moment any of its asteroids was within send distance of an enemy asteroid.



So this would still just use 1 array per empire.

If we wanted to have 2 or more different Infected AI factions that could fight each other as well as the player, here's how we would do that (in pseudo-code).

Code: [Select]

 Num of Factions = check number of asteroids and seeds for all factions to determine this number.

  metric = {}

  For aiplayer = 2, Num of Factions do

      metric[aiplayer] = {}     -- create a new row

    -- infected engine
    -- all arrays are now referred to as matrices
    -- for example, consider the following method of setting metric on an asteroid that needs seedlings to build more trees:

    if checkedroid.Owner == 0 or checkedroid.Owner == aiplayer and checkedroid:GetNumTrees() < checkedroid.TreeCap then
      metric[aiplayer][checkedroid] = 100
    end
  end

[annikk.exe]

Here's a diagram of how the metric network, works.

The numbers indicate what metric that asteroid has.  In this example, we assume that all the friendly asteroids have maximum trees and are contributing reinforcements for the gather point, rather than contributing seedlings towards defence and construction, which are much lower metric numbers and would thus over-ride the gathering behaviour.



This diagram shows how the gather points (the roids marked "200") would form on an "ideal" frontline.  Note how the asteroids nearby, and behind lines, contribute seeds toward their neighbours with the lowest gather metric, whilst setting their own metrics to be their lowest neighbour's, +1.


For a more realistic example, consider a smaller, typically shaped galaxy.



The metric configuration may have formed like this.  But, due to the way that the engine randomly selects asteroids for checking, the configuration might equally have looked like this:




Either configuration is valid for massing up a large number of seedlings prior to an attack.


The advantage of this approach is that it balances defense of the front line with gathering up to attack any weak links in the armour of the opposing.  Having multiple gather points on a large scale empire means attacks can erupt from multiple different points.



I will need to address the problem of what happens when an asteroid ready to send some reinforcing seedlings is met with the problem of the lowest metric being tied between two of its neighbours.
What is the best thing for the AI to do in that instance?

I think that, for maximum eye-candy and swarmyness, the best approach would be to have the AI split the its seedlings between the winning neighbours.  That way, asteroids with metric "201" who have a choice between two different "200" asteroids to contribute seedlings to, would send half to each of them.  I think that's probably what I want...

[annikk.exe]

Hmm, on second thoughts, maybe I don't need a matrix to store the metric data.  I think I can do it with just one array.

I would have to re-declare the array on each pass of the engine, and populate it with however many asteroids are in the game for that cycle... (and probably, only those asteroids with a radius greater than 1).
The metric would be calculated for the asteroid's CURRENT OWNER, and the code would need to check what surrounding asteroids belonged to the current owner.  Then their metrics could be examined, and a resultant metric for the checked asteroid derived thusly.

When an asteroid changes owner, its metric would need to be set to 500 or something that won't cause nearby asteroids to propogate anything or send any seeds.  The next time the asteroid is checked, its metric will be changed according to its newfound surroundings.

Metrics for any given asteroid must be re-checked on any given cycle.


Doing it this way would be good, I think.  The main way that it differs from version 1 is that in all its checks, it refers to the owner of the currently checked asteroid, rather than a specific empire number.  I believe multiple faction functionality should basically fall out of this naturally, provided I always make sure to refer to the Owner of checkedroid rather than a specific faction in all checks.

[annikk.exe]

How is the AI going to learn about the level?

In eight easy steps, this is how Infected AI v2 will operate:


1) The engine operates in a While loop, which runs through all of the engine code, activating different parts of it as deemed necessary by the environmental conditions in the level at that moment.

2) On each cycle of the While loop, it performs a number of steps.

3) First, it figures out how many asteroids there are on the map (up to a maximum of, say, 200).

Code: [Select]

numberofasteroids = -1

for i = 0, 200 do
  if GetAsteroid(i) ~= nil then
    if GetAsteroid(i):GetRadius() > 10 then
      numberofasteroids = numberofasteroids + 1
    end
  end
end

-- now the variable called "numberofasteroids" accurately represents the number of playable asteroids on the field.
4) Then, it selects one asteroid at random and performs additional checks on it.

Code: [Select]

checkedroid = GetAsteroid(math.random(0,numberofasteroids))

5) First, it checks what neighbours it has.  It stores this information in an array.

6) Then, it updates the metric based on its own state or the metric of any neighbours that have the same owner.

Metrics are as follows:
0 = Under attack
1, 2, 3 = a nearby friendly asteroid needs help.  This way!

100 = Need seeds to build trees
101, 102, 103 = a nearby asteroid needs trees for building.  This way!

200 = Gather point - I can see an enemy asteroid and none of my neighbours are gather points.
201, 202, 203 = a nearby asteroid is a gather point.  This way!



7) Then, the asteroid takes action (sometimes) based on its own status, and the metric of neighbouring asteroids.

Asteroids can take three different types of actions:
i) Build trees
ii) Send available seeds, splitting them between all neighbours with the same owner that share the lowest metric
iii) (If a gather point) Attack the weakest nearby enemy asteroid.


8) Finally, if an asteroid changes hands, a Function OnAsteroidTaken() sets its metric to something high and safe - above all the useful metric numbers, eg it might set it to 500.


That's the whole engine.


It rechecks the entire level on each iteration, so that means it can cope with levels where the number of asteroids changes over time.  Also, it will be able to cope with levels that have moving asteroids for the same reason.

It should work fine for different factions, they should fight each other without problems.  Different partitions from the same empire will be able to act independently.

If I stick to the design, the finished engine should be small and lightweight, hopefully just a few hundred lines.  Hopefully I can make it so that there aren't seperate parts for LevelSetup() and LevelLogic() so others can simply copy and paste the thing into their levels.  I should try to find ways to have the code for the engine be good for just a single iteration, so that it can be inserted into a While loop, rather than containing one itself.

I believe that the AI, knocked back to 1 tree on 1 asteroid, would set the metric for that asteroid to 100 and when it had 10 seedlings, plant another tree.  Then another and another until it had max trees.  Then I think that it would set its metric to 200, build up seedlings until it had enough to launch an attack on a nearby asteroid, and attack.  The attack would hopefully succeed, the metric for the new asteroid would be changed to 500 and then (if necessary) to 100 - trees would then be planted, with reinforcements coming from the original orphan asteroid (which still has metric 200, or if it's no longer in range of any enemy asteroids, it would change to 101) until the max was reached, then the metric would be changed to 201 (if the first asteroid was still gather point) or 200 (if not).  The massing up would continue and ultimately the AI would be capable of coming back to take over the galaxy.




Tomorrow, I get to coding.  :>

[annikk.exe]

Extra note:

The only array data that needs to be preserved between cycles is the Metric array.
Therefore, it seems unavoidable that this will need to be declared outwith the While loop.

I don't think there's anything else, so that's not too bad I guess.



Also..


Pay close attention during the creation of gather points/attackable paths array to make sure an owned asteroid with no trees and lots of enemy seeds doesn't flummox the AI!



Also...

Apparently math.sqrt is expensive on processing time.  So instead of checking distance like I normally would, here is how I will do it.

Assuming we have already selected a random asteroid to use as checkedroid:

Code: [Select]

numberofneighbours = 0

for i = 0,numberofasteroids do
  length = checkedroid.x - GetAsteroid(i).x
  height = checkedroid.y - GetAsteroid(i).y
  if (length * length) + (height * height) + GetAsteroid(i).Radius < (checkedroid.SendDistance)^2 then
    -- this asteroid is in range.  Add it to the neighbours list, and increment the neighbour count by one.
    numberofneighbours = numberofneighbours + 1
    neighbours[numberofneighbours] = GetAsteroid(i)
  end
end

[annikk.exe]

I couldn't resist and started writing it tonight.  :>

After this much preparation, the coding went fast...the thing is half written already!  It's looking very concise.  It's quite hard trying to conceptualise all the different states an asteroid could be in, but I've been practicing for it all day.
Anyway, going to pwn some n00bs in Starcraft for a bit.  I'll finish this tomorrow.  :>

[annikk.exe]

Written the entire metric network backend.  Now I'm writing the actions section.  :>

First version should be finished in an hour or so. :D

[Pilchard123]

Have you done any speed tests on the two different methods of distance checking? math.sqrt might be processor-heavy, but the other one might take longer for some reason.

[annikk.exe]

I did use one square root, in the end.  I might still find a way to take it out.  We'll see.

The engine is nearly complete.  The AI now has a (in theory) fully functional backend metric system, which should create a dynamic metric network regardless of what type of level there is.  I have added sufficient action abilities that it can colonise the galaxy now.  It doesn't attack yet.

I'm troubleshooting bugs with the way the metric system works.  It's an extremely tricky and subtle task, bugs manifest themselves only once the majority of the code is complete, and can be hard to pinpoint.  Fortunately the code is very neat and organised, and not excessive to the purpose, so it's a lot easier this time around.  :>

[annikk.exe]

I tested how it works with 2 different empires to control.
Seems to work good.  :>

Currently troubleshooting why gather points don't appear...

[Bonobo]

Whoooooooaaaaaa, olympic coding

[annikk.exe]

The best time to conquer the world is RIGHT NOW...


The AI is now smart about sending seeds to colonise blank asteroids.  It won't send 3, or 7... it will only ever send a minimum of 10 to a new asteroid, so that they can actually build a tree when they get there rather than sitting around going to waste.

The metric system works great for colonising and for responding to attacks.

However, there seems to be a bug at the moment where seedlings on a gather point will never move off it - even if an adjacent asteroid comes under attack!  Clearly this will not do.
The list of bugs with the building/colonising/defending code is growing shorter.. :>

[annikk.exe]

Gather points are flapping...  :/

The problems are getting pretty obscure now.

[Sniped50]

How long do you think it'll take until all the coding's done?

[annikk.exe]

How long do you think it'll take until all the coding's done?

For the AI engine, first draft will be done tonight - the only bit left to add now is the code that triggers a gather point to launch an attack.  That's very comfortable territory for me and I don't envisage any great problems.
I will be testing it a lot in the coming days, including on gravity maps.

So I guess the answer is... I don't know :P
It'll be done when it's done.


In the mean time, I have some awesome-tastic news:




The gather point flapping problem has been solved.  You can see now the green boxes indicate the spots where the AI are gathering up, having fully colonised the current partition galaxy.  The fact that it creates these multiple different gather points implies that it will work in seperate partions, although I haven't fully tested that yet of course.  :>

I also squashed a bug that (in very rare cases) was causing the AI to issue commands to the player's seedlings!

[Sniped50]

It'll be done when it's done.

That's probably one of the better responses I've heard of. It's almost as if you work for Valve...

I also squashed a bug that (in very rare cases) was causing the AI to issue commands to the player's seedlings!

Aw, did you have to? It would have been cool to just watch it all play out while simultaneously making you feel insignificant that the computer itself was doing a better job than you.

[annikk.exe]

Going to do an open beta for the AI.  If you have a map and want Infected AI you can just copy and paste into it, this will be your chance!


I will post 2 pieces of code.
The first must be inserted at the end of function LevelSetup().
The second must be placed inside a While Running loop (such that it will run repeatedly) inside function LevelSetup.

The only requirement is that you give player 2 (or above) ownership of 1 asteroid to begin with, and at least 10 seeds or 1 tree on the asteroid.  The AI should then automatically learn about your level and work immedietely.

[annikk.exe]

Now watching Infected Empire 2 battle against Infected Empire 3 :P


UPDATE

Empire 3 is winning!

UPDATE 2

Damn, there's a bug with single-asteroid partitions.  The metric spirals above 500 endlessly.  There aren't any nearby asteroids for it to be exchanging higher numbers with though.  Hmm...

UPDATE 3

Think I've fixed it...  testing...

UPDATE 4

Not fixed yet, but Empire 3 managed to win.  :>  Tried something else, testing it now.

UPDATE 5

Think I've got it this time.  Everything is showing Expected Behaviour.  :>  I haven't put any bells and whistles in this AI yet, like flower handling...but it seems to have colonising and attacking down really well.
Standby for release of v0.1 for beta..

UPDATE 6

Working - w00t !  Unfortunately, it sends seeds in dribs and drabs.  Slight change to make it only send an attack force once it has enough seeds to have a realistic chance of taking the roid.
Testing...

[annikk.exe]

First version should be finished in an hour or so. :D

Ah, the optimism of programmers.  :P

[annikk.exe]

Ok, all the behaviours seem to be correct now.
Trying it in a different map next.  :D

[annikk.exe]

In version 1 I kept different metrics for guarding the empire, colonising new asteroids, and building up a force ready to attack.  In this new version, I plan to combine all of these metrics into one.  Therefore, one metric array will be used per empire.

It's funny looking back at this now.  When I was actually coding the metric system, I realised that it would be possible to just use a single array to keep track of the metrics for all asteroids, and all empires.

The trick is that asteroids only take notice of neighbouring asteroids' metrics if they are owned by the same empire.  :>
I guess it makes things a bit more efficient.  Less data structures are needed, the code is less confusing, etc.


Also,

The asteroid will also make a list (array) of all a) friendly or empty asteroids, b) a list of enemy neighbouring asteroids or empty asteroids with enemy seedlings on them that are within its send distance.

This was one of the concepts listed in the first post in this thread.  But actually, I combined those 2 arrays into one as well.  It's called "neighbours", and it's simply a list which is created on each cycle of which asteroids are within the send distance of the one being checked.

The various seed-sending code in the "Actions" section takes care of whether a particular neighbour is a friend or an enemy.  This is a much simpler system than maintaining 2 different arrays.


The entire engine contains just 2 arrays: metric, and neighbours.

[annikk.exe]

Coding stopped for now due a depression. :<

I'll feel better tomorrow, hopefully..