Monster pathfinding

Game Talk The Drawing Board
1

At the moment zeds don’t pathfind, just walk in straight lines and stumble around.

Is it more because performance or because they’re just supposed to be painfully dumb? Or maybe is it there to force them to rely on smell?
If just the performance, if I found a fast solution, would it get in?

For example, instead of making all zeds path to the target, do it all in reverse: path from all the targets to all the zeds. This way 300 zeds chasing 1 player would path just once (and just re-trace the paths 300 times, which wouldn’t be that much slower than pathing 300 straight lines).

Old pathfinding code was very naive - before I got to it, it not only used a vector for the open set (=linear time cost for every single iteration), but also did up to 7 times as many checks for furniture, terrain cost and vehicles as needed.
Now it uses a heap-based priority queue for open set (=logarithmic time per iteration) and doesn’t duplicate ter/furn/veh checks.

Even with many targets to find, the time of each “multi-pathfind” would be rather low. You can test current pathfinding by spawning ~20 NPCs, having them follow you and teleporting away. This reverse-pathfinding would, in most cases, be faster than 20 NPCs pathing to the other end of the map.

Having zombies pathfind to visible targets would stop them from getting clogged up in the cars and turning them into mosh-pits. For some added dumbness, zombies might disregard (fully or partially) pathing around passable-but-slow terrain (rubble, small furniture).

Some very cool behaviors can be created with simple manipulation of pathfinding. For example, swarming around when close to the target (achieved by manipulating the results around the target), avoiding light, avoiding open spaces, avoiding being seen by the player, forming a tight horde or loose pack etc.

So, are zombies supposed to be brainless or were they brainless because technical limitations?

2

I think i read somewhere that absent of something guiding them (which i am not sure is implemented yet) they are suposed to be painfully stupid.

3

It’s a bit of both IIRC. A lot of the pathfinding code is really old code, and as such isn’t the best. But zombies are also supposed to be rather stupid.

Ideally a rework would be able to handle these things:

  1. Monsters of varying levels of intelligence, ranging through ‘NPC’, ‘sub-human’, ‘animal’, ‘bug’, and ‘dumb as a brick’.
  2. Allow for monsters to override patching for others with new orders. This is already done by the brain blob and the thriller in very basic fashions, for example, but we’d also like to eventually extend it to the zombie master and somewhat the necromancer as well.
  3. Various types of pathfinding from different senses, including sight, sound, and smell, as well as a way to weight one type of pathfinding over another (so that wolves and dogs could depend on smell more than sight, for example).
  4. The ability to somewhat maintain your goals if you have to bash something out of the road (maybe for a time based on intelligence?).
  5. Z-level scalability (as I’m sure you are aware :P).
  6. Form mobs. What we don’t want to do is to have the 300 zeds chasing you form a nice orderly line for the player to clobber them down one at a time. Zeds should form big howling mobs while they chase you around.
4
  1. I’m pretty sure this would be quite simple. I plan to move the entire pathfinding code away from map to a separate class, where each kind of pathfinder would have its own instance. Important for future fliers, climbers, door openers etc.
    Stupid creatures could have only limited plans, heavy heuristics, coarse map instead of nice grid etc.
  2. Ideally this would be handled in planning phase rather than pathfinding itself. A coordinator-based pathfinding sounds like an interesting idea too, though.
  3. This one would be hard, unless other senses granted awareness of map in some way. Like, smell-sight and echolocation. Otherwise it would just be used to pick a different target.
  4. NPCs already do this - they should even understand degrees of toughness of the target to bash (a bit roughly at the moment).
  5. That may be a performance hurdle (especially fliers). Might require some greediness and simplification. Still, Dwarf Fortress did it, so we can do it too.
  6. I have some ideas, like penalizing turns, semi-random choices, alternative paths when current one is blocked etc. If all else fails, there’s always that cool research paper on crowd flow algorithm at http://grail.cs.washington.edu/projects/crowd-flows/
    Implementing that crowd flow algorithm could be quite a bit of work, but the interesting kind of work instead of code monkeying (like the part of z-level update I’m working on right now).
5

This makes me think of smart zombies, that wield sticks or pipes, open doors, have perfect pathfinding, run faster (to open the door for other zombies) and try to dodge.

Edit for spellcheck. Also, just by reading your stuff I know that, if you do it, it’ll be awesome.

6

It would be interesting from a tactics and survival point of view if there was some kind of zombie that could act as a ‘leader’ to other nearby zombies. perhaps sending the brute around the other side of a house to cut you off while blocking your way back with shockers, etc. i realize that would likely require a lot of new AI code, but if would be fun to never know if you were the hunter or the hunted until its almost too late. this is the kind of situation for why you would always carry High-explosives >:}

7

That’s pretty much exactly what we want to eventually have zombie masters and possibly necros start to do. :stuck_out_tongue:

8

That’s pretty much exactly what we want to eventually have zombie masters and possibly necros start to do. :P[/quote]

ah, well ok then

9

“Zombie master laughs maniacally”

The zombies stole all of your onions