Is there any competent Zombie AI?

Hi Outcast.

Yes I have dont a lot of AI in the past....and there is an easy way to do it...But remember AI is always designed around the need of the game (ISO, 3D, 2D, Top Down, etc etc)

Instead of using collision detection (IE: the slide-around-it thing you mention) you can use a much older method, but one that still works perfectly.

All you do is to map out your ground area and the obstacles, and simply save it as a binary.
So as an example....Here is a 9 by 3 play area:

123456789
000000000----1
000010000----2
000000000----3

What you would then do is to keep track of your zombie and what area it is in.
So in the above example, lets say your zombie is at position 3,2 then he ( X ) would be here:

123456789
000000000----1
00X010000----2
000000000----3

When your zombie gets to 3,3, he will be next to the obstacle, so you can then give him a random direction to move (up or down) to get around it. You then move the zombie in that direction and so avoid the obstacle.

Yes it does mean you have to add a few variables (counters) to your game, but once you have it working, then you will find that your zombie can home-in on the player and totally avoid the obstacles without a problem.

If you want I can make you a very simple example to help you...but I may have to post it tomorrow as im busy today.

I'm in the process of making AI for my game, so I'm also very interested in seeing what suggestions people have. I think environment navigation is just one part of the problem (albeit probably the most fundamental part). Even for a dumb enemy like a zombie, I think you probably need to factor in quite a lot of things before they feel believable (ie. the zombies seem dumb rather than the game seeming dumb). Here are some I think would be useful:

-keep track of distance to player and only chase player if at a reasonable distance
-keep track of line of sight and only chase player if appropriate
-detect holes/inaccessible terrain in between player and enemy and don't bother chasing if player can't actually be reached.
-if enemy has a 'frenzied' state when chasing player, include some sort of cooldown timer so that enemy isn't frenzied forever
-include some basic geometry/algebra in chasing routine so that enemy doesn't just run to where player is but to where player is likely going (eg. if enemy is at 9o'clock and player is at 3o'clock but moving south, enemy should move not east but southeast)
-include some basic record of enemy's recent movement patterns, so that if they have been going around in circles or bouncing between two points for a long time, they'll try something new to break out of the pattern*
-include some occasional check to see if enemy is stuck in a wall or glitching out some other way, with some strategy for fixing them up (eg. moving them X pixels away from the wall until they get unstuck)
-some kind of randomised 'personality type' or some such thing that tries to make different enemies behave slightly differently, so that the player doesn't end up being like the Pied Piper with a conga line of automatons following him around all in exactly the same way

* Here's an issue I recently found that I hadn't expected at the planning stage, but that became immediately apparent once testing began (I imagine many more issues like it will surface eventually). Some of my enemies can jump onto ceilings and move on them. So I had their movement set like this:
-they move along a ceiling until they get to an edge
-once at the edge, they test to see if they can safely drop down to a nearby ledge
-if not, they turn around.

But then you get a situation like this where the enemy gets stuck in a loop on a ceiling, because it only checks for dropping points when it's at an edge, but the only safe dropping point occurs away from the edges:

Please login to see this picture.

So my solution was to keep track of how many times it hits ceiling edges consecutively, and force it to look for a dropping point once it hits a certain amount of them:

Please login to see this picture.

What you're talking about is "collision avoidance" (that's the proper term to google), as opposed to true pathfinding.
Dex's method seems like it should work.

Alternatively, I remember seeing an example many years back, that used two detectors positioned in front of the zombie, at roughly 2 and 10 o'clock positions.
If only the 10 o'clock (left) detector overlaps an obstacle, rotate to the right (clockwise).
If only the 2 o'clock (right) detector overlaps an obstacle, rotate to the left (anti-clockwise).
If both detectors overlap an obstacle, pick a direction (clockwise or anticlockwise) and keep rotating in that direction until not overlapping a backdrop.
If neither detectors overlap an obstacle, rotate towards the player character.

It's very simple, but it does work - although it requires a bit of fine-tuning to get the best results.

I couldn't find the original file or forum post any more (might have been on The Daily Click?), so I've just put together a quick example to demonstrate the principle.

Please login to see this link.
(arrow keys to move the player)

Obviously that's just the collision avoidance part - you still need to add in line-of-sight calculation (loads of example on the forums) and some behavioural states (searching, chasing, going to last known position, etc).

Quote from Outcast

One other area I am a little worried about is how performance heavy AI could potentially become, especially if having like 100 zombies. I even toyed with the idea of wanting to have the whole map be active and "moving" in real time all the time, so like zombies that are way far away from you are still moving around, I like that sort of persistance in games where not everything is just happening right around the player and everything else is "freezed" or just an "illusion", even if it is in practice "pointless" in a way. But I imagine that would make it even more performance heavy.

I've been very concerned with this too, especially since overlap checks are so expensive. I've been mindful of performance/efficiency since the beginning, and so far I've been relieved to see that performance is very acceptable. I only check for collisions only every 2nd tick or so, and only basic collisions (eg. is a hole or wall present, is enemy on a slope); only if a hole or wall has been found do I check detailed collisions (how wide is the hole, how tall is the wall, must enemy adjust for slope etc.).

If you have the whole map active, I'm sure you can somehow simplify the AI for those zombies that are off-screen or far away from the player - maybe check them less often, or use basic XY calculations rather than actual overlap checks, and of course skip any animation/rotation stuff for zombies that aren't currently visible. I'm sure this is what many AAA games do - especially open-world ones. I'm pretty sure I've taken advantage of this recently when playing Borderlands 3: some enemy had glitched and disappeared - stuck in geometry or whatever - so I moved as far as I could to the other end of the room. When I came back, he was fixed...I'm assuming it's because his AI routines changed when I was far away, and were perhaps more forgiving of collisions, allowing him to return to where he was meant to be.

Yes, fine collision checks are slow. On the other hand, bounding box collision detection should not be computationally expensive at all, so try disabling fine collision detection in the object properties.

Alternatively, there are two other routes you could go:

You could make the game grid-based, so collisions can be detected simply by looking up values from an array - Dex has suggested one way of doing that, but actually almost any method that works using the built in collision detection could be adapted to use an array instead (including the example I posted above).

You could make the game polygon-based, so collisions can be detected by calculating the intersections of lines. The maths is a bit more involved, but polygonal maps lend themselves really well to much more efficient pathfinding, line-of-sight checks, shadow-casting, etc and allow a more "free form" level design than is possible with a grid, so there are a lot of added bonuses.

By "grid-based", I don't mean that the actual movement has to be grid-based - only that the map is grid-based. That way, a two-dimensional array can easily be used to label a grid space as either walkable or an obstacle. With a little more work, you could also implement simple shapes such as circles and 45 degree angled walls, to give you slightly more fine control. In terms of creating the graphics, designing maps, saving and loading map data etc, a grid-based system will be much easier as well. This is the way I would go, in your particular case, since it's also good for stuff like destructible terrain and movable barricades etc, which I'd guess you might want to include.

By "polygon-based", I don't mean 3D, although the vast majority of 3D games are polygon-based, and so very often use polygons in their pathfinding etc, because most of the groundwork is therefore already done. All I mean is that obstacles are defined only as a list of vertex (corner) positions, and the outline that they form - collisions can be tested for using just maths (involves intersecting line segments). This would be massively more work (to be honest, don't even bother unless you're very confident with geometry and vector maths), but would give the best looking and performing results - if you can avoid bugs...

Please login to see this picture.
On the left is a polygon-based pathfinding system I made (but never quite managed to iron out all the bugs in). The example on the right was designed as a polygon-based field-of-vision display, like in "Commandos : Behind Enemy Lines", but it could easily be used for lighting/shadows too. In both, the shape of the obstacles is defined only by a long string of successive vertex coordinates, stored in a list or an alterable string - the visible lines and numbered nodes are only there for debugging purposes, and are not used in any of the calculations at all.

Box2D is likely to be far more computationally expensive than any other alternative.

Oh, and there's also the background collision mask on those runtimes that support it. That should be very fast as all it's doing is reading 2-bits of data (although you do need to calculate the position to test). It's basically the same as using 1x1 pixel detectors, but probably a little faster. Destructible terrain is easy, but for movable objects (eg. crates that can be pushed around) you'd still need actives and normal collision detection as well.

And yes, if you've got a large map and huge numbers of zombies, there's nothing wrong with using a less accurate but more efficient method for the zombies that are out of sight. If you were using the array based method I suggested, you could easily have the zombies that are too far away to be visible using a simple and very fast grid-based movement (jumping whole tiles in one step), and then have them switch to pixel-perfect movement once they get closer to the player.

The collision mask feature allows you to test any pixel to see if it is an obstacle:
Please login to see this picture.
Please login to see this picture.

From the help file:

"Value of collision mask. This function asks for two parameters : X and Y position of the pixel to test. It returns 2 if the given pixel is located over a ladder, 1 if the given pixel is located over an obstacle and 0 if the pixel is located on a free area."

"Collision Mask
Is Obstacle tests the collision mask for the presence of an obstacle at the given X and Y coordinates. This condition is true when the coordinates lay over an obstacle.
Is Ladder tests the collision mask for the presence of a ladder at the given X and Y coordinates. This condition is true when the coordinates lay over a ladder."

I don't believe it's supported in all runtimes though, as I think in some runtimes backdrops are handled more like actives.

Yes, you will need an array, but no other extensions. Personally, I would create a tile-based level editor for making the maps (it'll save you loads of time in the long run), and have it save maps as array files - and you can store the collision information in the same array.

My previous example, but converted to use an array instead:
Please login to see this link.
If you're not going to have a *huge* number of zombies on screen at once, I'd probably use whatever method gives the best looking results, even if it's quite heavy in terms of performance - and then focus on trying to make the movement of the zombies that are further away as efficient as possible (probably grid-based).

The collision mask is very much integrated into CF2.5. When you create a backdrop or quick backdrop, or when you use the "add to backdrop" action of an active object, you can choose to make it either "obstacle", "platform" or "ladder". Obstacles are used by all the built-in movements (and the "overlapping a backdrop" condition), while platforms and ladders are only used by the built-in platform movement. The way CF2.5 works behind the scenes, is that it creates a big map of the frame, called the "collision mask", and uses it to store the backdrop type of every pixel (obstacle, platform, ladder or empty). If you've got a lot of objects whose shape and position never changes (ie. backdrops), then using a mask makes collision detection much faster than it would be if you were to individually check for collisions with each one, so that's why Clickteam did it.

Unfortunately, I think you've hit the nail on the head at the end there. By far the most difficult thing is going to be keeping the zombies from overlapping - it's massively more complicated than it might seem, and a good reason why you *might* need a physics extension.

In terms of zombie/zombie interaction, Maybe a bit of randomisation would help prevent zombies being trapped or in perpetual loops (if randomisation would be acceptable for your game type) . For example:

Every so often, randomly swap IDs of two zombies.
Every so often, randomly pick a zombie and give him a new, random target to walk to (thus potentially moving him away from a traffic jam)
Every so often, temporarily disable collision checks for one zombie, allowing him to move through other zombies.

You could perhaps apply some basic heuristics to this kind of thing. For example, periodically record the x and y values of each zombie. Then occasionally compare the last, say, 4 records; if the x and y values haven't changed much in that time, assume that the zombie is likely stuck somehow, and give him one of the 'rule-breaking' behaviours I listed above

Would it be feasible to use something similar to boids to handle zombie groups? Only without the flock "cohesion" effect?

There's a video here about the concept with info in the description: Please login to see this link.

And I believe there is a fusion extension called "Flocking" that implements this here (not sure about obstacle avoidance): Please login to see this link.