Hey, I am in the process of writing a small game, up until now I have never ventured into AI before apart from your standard A* for Pathfinding. The game in question does not require any amazing AI as I am only going to be having zombies which adhere to the following rules: 1) Run at the enemy based on line of sight. 2) Attack enemy 3) Call nearby friend zombies for help once spotted an enemy 4) Roam around when no enemies are near Now I was wondering what the best way to approach this is and if there are any articles around that are basic enough for what I need. I was thinking of something like a finite state machine, would this be a good model to base the zombies on? One area that I am a bit unsure about is how to make the zombies roam around realistically and how to ensure they don’t end up walking into each other, we did cover a few flocking algorithms whilst I was at University but ideally I don’t want to implement something that’s too hardcore, I already have a lot of stuff on the physics/graphics/game play side to be doing so I just want to create a system that does what I need nothing more. And besides since when were zombies remotely intelligent  Any help appreciated.

How about just making them move in straight lines and change course when they hit or get close to stuff, or switch to attack mode when they sense an enemy? Also, if they attack whenever they see an enemy, won't the actual nature of their roaming behavior be (mostly) unseen.

hmm yes the roaming will rarly be seen I suppose, these were my thoughts

Have a state machine for the zombies with different modes that supports free roamings, attack, die, call for help. (free roaming could be moving in a random vector for a random time or until a collision is detected, then update the random vector/random time)

I was thinking I will probably end up implementing flocking for the zombie movement, and when they go to attack mode have a leader (who is closest to the player), the leader is then in-charge of running directly towards the player whilst the flocking should take care of the rest, once within a certain distance I could have the zombies simply attack the player. If the leader is killed the next nearest zombie to the player is promoted to the new leader.

Having hundreds of zombies with flocking and checking collisions for each could be a pain, I could perhaps keep them sorted by position that way only check with the nearest zombies, but if there is a swarm of zombies around the player this could be quite expensive :S

50 zombies all clumped together
1 -> collision check * 50 for each = 2500 collision checks, and its expontential for each new zombie that gets added... not good. Unless I keep a limit e.g 8 nearest which would mean 50*8 = 400 but it would cause some visual artifacts where zombies were walking thru each other when clumped together.

Please can somebody tell me if I am along the right lines or if there are any issues you can forsee by doing this or anything I havnt considered?

Quote: Original post by reaper93

I was thinking I will probably end up implementing flocking for the zombie movement, and when they go to attack mode have a leader (who is closest to the player), the leader is then in-charge of running directly towards the player whilst the flocking should take care of the rest, once within a certain distance I could have the zombies simply attack the player. If the leader is killed the next nearest zombie to the player is promoted to the new leader.

If you implement flocking anyway, I wouldn't take care for a leader or such kind. This would only bring more complexity into the thing.
If zombies who can see the player move a bit to the player, the center of the zombie-swarm will move towards the player, the other zombies will move to the center, and that way more zombies will see the player and move to the player. Resulting in the player being swarmed, surrounded by zombies.

all zombies behave the same, brain-dead, having no leader. I like that. :)

so each zombie should try to follow the flocking rules:
1) keep some distance from your closest neighbor (collision prevention)
2) keep distance from world obstacles (collision prevention)
3) move to player if you see him
4) move the same direction other zombies in your neighborhood are facing
5) align your speed to the other zombies close to you

probably i would take 3-5 in one simple weighted moving direction vector.
(the closer a neighbor is, the more take care for it's moving direction)

also the player should have the weight of say 10 zombies to keep the zombie swarm heading to him.

On your "expensiveness of 50 zombies" problem.

The first optimisation is to bring it down to 50! rather than 50*50.
To do this, when you iterate through the zombies to check collision, start each sub loop advanced by one, so:

for (int i = 0; i < numberofzombies; i++)
{
for (int i2 = i+1; i < numberofzombies; i2++)
{
Checkforcollision(zombie, zombie[i2]);
}
}

So, each zombie starts checking collisions from the next one in the list. It doesn't have to check with the one before it, because that one already checked that pair when it was it's turn to go through the loop.

More advanced would be to do some broad phase collision detection. Grid based (where you add each object to a grid, and then iterate through the grid only checking for collisions between objects in adjacent squares) and Sweep and Prune (Where you built a 1dimensional list of all the objects in the game and only check between objects with overlapping left and right edges) are two simple ways to bring it down greatly.
Just by using sweepandprune in one dimension I can handle 700 enemies bunched up colliding with each other.

Quote: Original post by CIJolly
On your "expensiveness of 50 zombies" problem.

The first optimisation is to bring it down to 50! rather than 50*50.

50!=50*49*48*...*3*2*1 is a much larger number than 50*50. What you probably meant was "50 choose 2", which is 50*49/2.

You're correct. I meant 49+48+47...etc, which is what my loop should do.The last zombie wont have to check any collisions, the first will check 49.

Curious, if you have a sea of zombies, would you need to worry about collision detection between them? Does the player have the ability to see all the zombies at once? If performance is an issue I wouldn't worry about the zombies that the camera can't see.

i had a zombie swarm game once, what i did for zombies out of range was to eliminate them from any updates completely. This meant the zombies didn't move if they couldn't be seen, hence no reason to check for collision.
(I guess this depends on your gameplay, I only wanted the player to be concerned with zombies nearby and had no reason to worry about what a zombie four blocks down the road was up to)

Of course if somehow the player managed to 'interest' all 200+ zombies into one place there could be slow down.

CIJolly has the right idea though if you really want to keep all your zombies activated. I recently looking into cell partitioning and it's ideal for checking vast amounts of wandering objects against each other.

Stealing from zombie movies, zombies could sometimes moan when they notice prey.

This moan attracts other zombies to the location near where the moan is, and induces them to sometimes let out a lesser moan.

Zombies tend to move to the greater of the moans they hear when they are idling.

You could also give your zombies limited time 'smell' based tracking. Ie, when you move, you leave a trail of 'smell' behind you. Zombies who find that track can follow it with a certain degree of reliability. This allows Zombies to 'run to the last location where they saw you' then 'try to follow the smell until they find you' -- an AI that isn't omniscient, and yet cannot be reliably fooled by 'running around 2 corners'.

This also provides a method for sleeping zombies to wake up and jump out of air ducts (as you get near, the zombie smells you, and then attacks), and could even be expanded into a sub-explicit game mechanic (why do zombies follow you so much worse outdoors? The wind!).