Is there any competent Zombie AI?

[Outcast]

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


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.

Ah thank you for the clarification! I see what you mean now with the grid based system and it does sound like a good idea. Where would I start though if I have never done such a system before? Would it be possible to do an AI system like you did with the overlap of obstacles with no overlap checks this way you mean then? Not sure exactly how that would work?

Also when it comes to movable barricades, how would a grid based system work in that case? Do you think it would be possible to use a grid based system and still use Box2D for movable objects?

[MuddyMole]

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.

[Outcast]

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

Hmm sorry but I don't understand this, what do you mean by background collision mask and that those runtimes support it? All this is all completely new to me My biggest issue though is that this sounds good in theory to me, but I have no clue where to start if I actually wanted to try to implement something like this and what objects and extension I need (if any) etc (I assume I need to use the array object?), is there any tutorials or examples out there on how to do this?

[MuddyMole]

The collision mask feature allows you to test any pixel to see if it is an obstacle:



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:
https://1drv.ms/u/s!Atq7cUIJ7uexnzbQ...W-pqL?e=BgIaoK
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).

[Outcast]

Quote

Oh, I had no idea there was such a thing as Collision Mask. So if I understand it correctly you "assign" some pixels a value of 0-2 and then you can test against those pixels? How do you assign those pixels though if you say have an active object that is a wall, how to assign the pixels at that wall to be an obstacle? (EDIT: Ah I think I saw where you did write them as 1:s now over the backrops in your example)

Also "ladder" is that just a term for something that is not either empty or an obstacle? It does not have anything to do with actual "ladders"? So in my case for example I could have solid walls as obstacle "1" and destructable doors and windows as "ladders" "2"?

About performance etc, perhaps it would be easiest to just do simple overlaps for the things that are on the screen yes. I am not exactly sure how perormance heavy things can get, I mean we still talk about a low res 2D game (?) and I will be targeting the PC market. I have no plan to make this for mobile or other more performance sensitive devices. But then again, I don't know if things still could get heavy.

Btw, do you have any idea how you would go about tackling zombie to zombie interaction? Of course as it is now with a system like this all the zombies can "clump togheter" in one spot on top of another so I need to have some way to check so they don't walk over each other. I was thinking about something like assigning an ID to all the zombies and then if two zombies collide the one with the lower ID will stop and the other one will move until they no longer collide if something like that would work and be a good method ? Then again while just thinking on it I can imagine all sorts of bugs with that though if there is like a big group of zombies with high IDs around a group of lower zombie IDs, then they would never get out of that group surrounding them.. hmm maybe not such a good method

[MuddyMole]

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.

[Outcast]

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.

Ah thanks I think I get it. So in performance from slowest to fastest when checking collisions would it be actives -> backdrops -> collision masks? The thing I don't get though is if collision masks is so much faster than backrops why are not all backrops automatically made into collision masks on runtime since backdrops are static and never move?

If I went with the Box2D way do you think I still could benefit from using Collision Masks?

I am thinking if it would potentially be possible to have the same logic you had in your example with turning the zombies when detecting walls, but by using physics shapes and apply force in a direction to make the zombies turn and behave in roughly the same way, but with physics and all the benefits that come with that with automatic "collisions" between bodies so they dont overlap..? Or do you think there would have to be a completely different way to approach it?

[Volnaiskra]

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

[Outcast]

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

Yes that would also be a way to minimize bugs! But honestly I am quite inclined to go with Box2D to get the zombie to zombie collision thing kind of sorted by itself, and nice physics when it comes to moving objects around never hurt.. the only problem then would be to have them still navigate around obstacles in a way that is acceptable like in the example by muddy mole.

[casleziro]

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: https://www.youtube.com/watch?v=bqtqltqcQhw

And I believe there is a fusion extension called "Flocking" that implements this here (not sure about obstacle avoidance): https://www.andersriggelsen.dk/mmf2_extensions.php