Jump to content

Replace A* with a simpler and more zombie-like algorithm


MXXIV

Recommended Posts

Currently, zombies use A* algorithm to seek their path. This is how A* works:

 

path.gif

From this post

Being a recursive algorithm A* can be rather expensive, but not much on modern machines. But the problem is it's too smart for zombies. I documented nice case of zombie being just way too smart.

This happened on railroad station.

As you can see the zombie walked quite bit to find a door and bang on it. That zombie wasn't aware of me! It heard sound inside the railroad station. I let it through and then killed it, as many others.

MW4KSwy.png

Also the A* is optimized over low distances, leading to probably too stupid behaviour in some cases. Behold my A* zombie grinder:

grinder1.png.4a154a7d5683dab8bb4037c75b6

Zombies actually take no fall damage from first floor so all this does is generate a lot of crawlers. This is caused by the fact that zombies no longer use A* when very close to you. Same effect can be observed with transparent fences - zombies close will engage you, those far away will find a way around.

 

The nasty thing is that A* makes any obstructions virtually useless. As long as perimeter is not 100% secure, zombies will allways immediatelly find the best path to get inside. This, on other side, motivates for creating tower defense style defenses (eg. let them fall of stairs).

astar.png

Edited by MXXIV
Link to comment
Share on other sites

This is totally intended behaviour! The zombies are supposed to retain some basic pathfinding skills, but also be dumb and make mistakes. The zombies are working as intended. Some things in their behaviour will probably be tweaked going forward, but pathfinding.. probably not.

If you don't want them to find you, break line-of-sight. It's the only way. (Of course, the only way to be sure is to nuke them from orbit, but we can't do that, so.)

Link to comment
Share on other sites

I do not really care whether it's intended or not. The problem is this totally breaks any kind of defense and encourages building sky fortresses. As long as there's a one single entry to your base, all zombies will immediately go to that entry (eg. door). Instead, they should bang on the walls, walk around and eventually find the entry.

Currently, if player protects his base entry with a maze, zombies will immediately find a way through, which is not realistic at all. Similarly wall perimeter with occasional holes does not increase area defense at all, because zombies immediately find way through the wall.

Link to comment
Share on other sites

Zombies choosing to jump over railing instead to comimg close enough to bite you? Does not look like intended IMO.

I've actually found both of those places MXXIV posted on screenshots above and found that zombie behaviour odd as well.

Link to comment
Share on other sites

2 hours ago, MXXIV said:

I do not really care whether it's intended or not. The problem is this totally breaks any kind of defense and encourages building sky fortresses. As long as there's a one single entry to your base, all zombies will immediately go to that entry (eg. door). Instead, they should bang on the walls, walk around and eventually find the entry.

Currently, if player protects his base entry with a maze, zombies will immediately find a way through, which is not realistic at all. Similarly wall perimeter with occasional holes does not increase area defense at all, because zombies immediately find way through the wall.

I'm pretty sure the part about them immediately going to the entry way (the door) is only true if they actually spot you from all the way inside the base. Same with the maze, in order for them to do what you're saying, they would have to spot you at the solution point of the maze. Which either makes it a very poor maze, or a see through maze that allows them to figure out point of entry anyway.

"Currently, if player protects his base entry with a maze, zombies will immediately find a way through, which is not realistic at all."

It's hard to argue realism in a zombie survival game, the way in which this would be poor AI, depends on the supposed intelligence levels of the zombies, which may not be the same as you see elsewhere. The AI is reasonable enough if you make the assumption that the zombies are intelligent enough to know that a wall is not a viable point of entry.

53 minutes ago, Geras said:

Zombies choosing to jump over railing instead to comimg close enough to bite you? Does not look like intended IMO.

I've actually found both of those places MXXIV posted on screenshots above and found that zombie behaviour odd as well.


I imagine in those cases, it's a genuine glitch rather than working as intended. Whether that be an issue with AI or map, but to replace an entire AI algorthim due to glitches seems to be using a shotgun for a scalpel job.

Link to comment
Share on other sites

I don't really follow your example with the railroad station. You say it wasn't aware of you, but in your pictures you're clearly just the other side of a see-through chain-link fence. That the zombie walked around the perimeter until it found a way through seems perfectly reasonable to me. You're also saying that the pathfinding is simultaneously too good and too stupid. If you want less smart zombies, why is not taking the direct line path (even if it involves falling off a balcony) not reasonable? Do you want them clever enough to pathfind or not?

(note: I don't code any of this myself, so I don't actually know much about how it works under the bonnet.)

Link to comment
Share on other sites

35 minutes ago, CaptainBinky said:

You say it wasn't aware of you, but in your pictures you're clearly just the other side of a see-through chain-link fence.

You can tell that the zed wasn't aggro'd to him, it would have turned towards the fence. Instead it just walked straight to the entrance and then got aggro'd, as the animation suggests.

 

The big issue here is not whether it is working as intended or not, it is that the zed will make a beeline for the quickest way, which is supportable by building a maze and watching zed navigate it instantly.

There should be a degree of stupidity in the zed's aggression to walk straight into the sound and then need to discover a way around it. You can shoot zeds from across the river in Knob Creek and the zed will go on a journey to walk all the way around the end of the creek and down the opposing bank to get you.

Of course, I'll say I haven't been in many situations that show this, so I can't say it's the most immersion breaking thing that I've seen. But I think adding some kind of 'discovery' to the pathfinding would make stealth and zed mazes more rewarding.

 

Edited by Kim Jong Un
Link to comment
Share on other sites

I get your frustration, but we've had this discussion with people numerous (read a ton of) times and it never occurs to anyone why we chose a complicated pathfinding algorithm for brainless zombies in the first place when a more realistic zombie behaviour would take about 1/10th the time to code. (note this is a custom engine - we had to MAKE A* pathfinding support from scratch in the engine)

Quite simply we've tried non A*  and more naturally TWD looking 'walk straight at things', we've tried lowing the range zombies are capable of pathfinding and all manner of other things,  and guess what:  We'd be currently sitting at 30% on the Steam Store Page and called that awful broken easy game with broken zombies that never ever chase you.

Thus, again, the Zombie AI pathfinding is the way it is after 4-5 years of development because every other way its ever been tried has resulted in a completely broken game with no threat. It turns out that if you portray zombies completely 100% without any pathfinding skills they are not plausible enemies. Zombies thumping on doors is a quintisential zombie / zomboid thing, but how does a zombie zero in on a door over a wall in the first place if they don't pathfind through that door? There must be some residual concept of a door or they would just walk toward the wall and start thumping that. A wall with a shut door along it would be more or less completely zombie proof as the chance of a zombie walking to the door without stimuli would be practically zero.

Thus we allowed the residual obstacle avoidance instincts in the brain still to function in our canon. 

I'm sure we'll experiment in future at ways of improving this and you're welcome to try yourself in a mod but the truth is even if we lower the pathfinding range a tad, or in cases where the pathfinding bugs out, it stops a zombie from pathfinding from outside a building through a door, through the interior and up a flight of stairs, which is the only possible way being seen through a window upstairs could ever result in those zombies being a threat, it can result in complete zombie inability to get to the player in situations you'd expect TWD/Romero zombies to pile through a door en mass. 
 

The player would be 100% safe upstairs in every building in the game, even with 50 zombies right outside. Even moreso, its probably just being inside a building would be enough to render you completely safe.

This stacked up against the issues you've posted is no contest at all. Gameplay > Realism unless Gameplay = Realsm.

Link to comment
Share on other sites

These situations are rare, indeed. The problem is intricate and I'm sure finding the perfect balance between "realistic" pathfinding and easy peasy Zeds is nearly impossible.

Just want to point out, that I had similar observations which were annoying from a immersion point of view.

d85NtPn.png

I was working in the blue zone. Zeds in the yellow area hear me and are instantly making a bee line along the red arrows to my position, again and again.

That makes Zombies look quite magical. And there we have it: Dragons already in the game - disguised as undead humanoids.

That's a path of nearly 20 times the distance of a straight line between us. Surely a 100+ recursions of A*. Is there a recursion limit at all?

 

Link to comment
Share on other sites

In some cases, I've noticed odd behaviors with zombies and doors. For example, one time at the north warehouse on the highway in Muld, I had just went into the warehouse from the cafeteria area of the warehouse. I took just enough steps inside to "unload" the area outside the warehouse's top most end. When I came back less than 15 seconds later, zombies had migrated to the door, which of course got me killed. I was pretty mad at the time so I did not post about it, because I can't post angry, it just ruins any kind of legitimacy I may have because that anger comes out in my wording. In hindsight, what I imagine happened wasn't the path finding itself so much as the placement and migration ticking at a bad time, it made it feel pretty ridiculous. Since then, I've encountered very few situations where this has occurs, but it does seem to happen, but I don't think its a bug, just frustrating one shot occurrences that seems to occur with larger buildings.

Link to comment
Share on other sites

6 hours ago, Leoquent said:

These situations are rare, indeed. The problem is intricate and I'm sure finding the perfect balance between "realistic" pathfinding and easy peasy Zeds is nearly impossible.

Just want to point out, that I had similar observations which were annoying from a immersion point of view.

d85NtPn.png

I was working in the blue zone. Zeds in the yellow area hear me and are instantly making a bee line along the red arrows to my position, again and again.

That makes Zombies look quite magical. And there we have it: Dragons already in the game - disguised as undead humanoids.

That's a path of nearly 20 times the distance of a straight line between us. Surely a 100+ recursions of A*. Is there a recursion limit at all?

 

 

This is the first I have ever heard of A* (so I have self identified myself as not an expert on this!)

 

But, IMO in this situation it would make sense for a zombie to walk directly towards you first before finding its way around the fence. IMO the zombie wouldn't realize immediately that it can't walk through a chain-link fence. It can see its prey on the other side and would be drawn straight towards it. Once it hits the fence and blunders about for a bit, it might figure out that it can walk around the fence and eventually get to you. But initially it would try to reach you through the fence. I think it would be great for gameplay if the zombies began to pile up on the other side of the fence. TWD style at the prison. It would give you a feeling of claustrophobia and a sense that you are surrounded with no escape. Instead of hundreds of zombies piling up against the fence and forming a horde trying to get to you, the few that were originally there find there way to you and you are easily able to dispatch their small numbers.

 

I have found one spot on the map where this does work. I think its because the path around the fence is too far. I started building a base here: http://pzmap.crash-override.net/#0.7707722654046587,0.16546367926042965,79.49684720339079.

 

It was fun to have the number of zombies outside the fence slowly grow until there were dozens on the other side of the fence. I wish I took pics...

 

I have no idea how difficult it would be to code this, but what if the zombies fumbled around trying to get to you instead of going straight around the obstacle. Eventually one would figure it out and it would attract the others to follow it? They'd hear that one zombie groaning away as it got closer to you and that stimulus would cause most of them to follow? That way you get the best of both worlds? On one hand the zombies don't appear super intelligent, on the other hand you still get hordes of zombies relentlessly finding their way to the player?

Edited by CaptKaspar
Link to comment
Share on other sites

19 hours ago, lemmy101 said:

I get your frustration, but we've had this discussion with people numerous (read a ton of) times and it never occurs to anyone why we chose a complicated pathfinding algorithm for brainless zombies in the first place when a more realistic zombie behaviour would take about 1/10th the time to code. (note this is a custom engine - we had to MAKE A* pathfinding support from scratch in the engine)

Quite simply we've tried non A*  and more naturally TWD looking 'walk straight at things', we've tried lowing the range zombies are capable of pathfinding and all manner of other things,  and guess what:  We'd be currently sitting at 30% on the Steam Store Page and called that awful broken easy game with broken zombies that never ever chase you.

Thus, again, the Zombie AI pathfinding is the way it is after 4-5 years of development because every other way its ever been tried has resulted in a completely broken game with no threat. It turns out that if you portray zombies completely 100% without any pathfinding skills they are not plausible enemies. Zombies thumping on doors is a quintisential zombie / zomboid thing, but how does a zombie zero in on a door over a wall in the first place if they don't pathfind through that door? There must be some residual concept of a door or they would just walk toward the wall and start thumping that. A wall with a shut door along it would be more or less completely zombie proof as the chance of a zombie walking to the door without stimuli would be practically zero.

Thus we allowed the residual obstacle avoidance instincts in the brain still to function in our canon. 

I'm sure we'll experiment in future at ways of improving this and you're welcome to try yourself in a mod but the truth is even if we lower the pathfinding range a tad, or in cases where the pathfinding bugs out, it stops a zombie from pathfinding from outside a building through a door, through the interior and up a flight of stairs, which is the only possible way being seen through a window upstairs could ever result in those zombies being a threat, it can result in complete zombie inability to get to the player in situations you'd expect TWD/Romero zombies to pile through a door en mass. 
 

The player would be 100% safe upstairs in every building in the game, even with 50 zombies right outside. Even moreso, its probably just being inside a building would be enough to render you completely safe.

This stacked up against the issues you've posted is no contest at all. Gameplay > Realism unless Gameplay = Realsm.

 

Link to comment
Share on other sites

36 minutes ago, lemmy101 said:

This stacked up against the issues you've posted is no contest at all. Gameplay > Realism unless Gameplay = Realsm.

No offense but this can be just summed up to "I give up for now". I think the issue with this whole thread is that I didn't suggest anything better than what we currently have. I'll think about it.

 

Also I'm not entirely sure why did you quote self. I mean, it kind of implies we didn't read your post the first time...

Link to comment
Share on other sites

2 minutes ago, MXXIV said:

No offense but this can be just summed up to "I give up for now". I think the issue with this whole thread is that I didn't suggest anything better than what we currently have. I'll think about it.

 

Also I'm not entirely sure why did you quote self. I mean, it kind of implies we didn't read your post the first time...

No, the summation is "This is the best solution available."

 

Have a warning point and reflect on our "be lovely" rules.

Link to comment
Share on other sites

1 minute ago, MXXIV said:

No offense but this can be just summed up to "I give up for now". I think the issue with this whole thread is that I didn't suggest anything better than what we currently have. I'll think about it.

 

Also I'm not entirely sure why did you quote self. I mean, it kind of implies we didn't read your post the first time...



I think you need to relax. I'm not so keen on the whole "be lovely" hugbox thing, but you're being really abrasive for no reason at all. I wouldn't fault Lemmy for telling you to love it or shove it at this point.

Link to comment
Share on other sites

1 hour ago, MXXIV said:

No offense but this can be just summed up to "I give up for now". I think the issue with this whole thread is that I didn't suggest anything better than what we currently have. I'll think about it.

 

No offence but it appears that a few select people are waiting for something called NPCs, and something called a new animation system, and something called Creative, and something called ad nauseum, so yes 'I give up for now' fixing this problem the occasional person brings up and complains about but in the grand scheme of things is about 100th on our list of 'things people get angry about'

 

Quote

Also I'm not entirely sure why did you quote self. I mean, it kind of implies we didn't read your post the first time...

 

Well exactly, so did the reply I quoted, where immediately after me explaining the reasons its the way it is and how it has to stay that way, then I'm kind of lectured on my 'giving up' by someone who doesn't even know the name of the bloody algorithm used let alone the complexity involved in getting more realistic zombie pathfinding. There's a bloody gulf of difference between 'I think they should walk there' and a pathfinding algorithm opprerating. Nowhere am I saying 'if there's a fence walk around it pls'.

 

I've working on the game for 5 years and it's remotely possible I've been through exactly the same thought process you have in the past, and being a game dev with a lot of experience and 5 years on the game it's possible we may have explored options already. In fact I say exactly that. It's also remotely possible that I've had to explain this not only in this thread but in countless threads in the past, and each and every time I'm responded to like people don't believe me or I fell off the turnip truck and should 'just make the zombies go up there instead of down there'. So I reply and explain the situation, yet again, why it has to be that way, and people immediately reply with 'oh well I think it should work like this' and 'why doesn't it just do that' and explicitly go over the exact stuff I said we can't do or is not as simple as a layman would make out. So I requote my post to make sure it's seen (instead of repeating myself) and then get accused of passive aggressive requoting. For every penis ham thread...

 

Here's the challenge. Get modding that lovely new pathfinding system (or lack of it) and keep the zombies a threat and the game over 5fps and I'll put it into the game in a heartbeat. Until then this is going in my 'can't answer another one of these threads pls someone quote the last time' - good day ;) 

Link to comment
Share on other sites

Yup - one small case in point on the complications involved:  Most pathfinding algorithms work on a grid of 'blocked' and 'non blocked' squares. So that square is 'wall' and that square is 'floor'. 

 

PZ doesn't work this way, as it has walls inbetween squares that are otherwise unblocked, that are accessible from one or more sides but not others. You can walk up alongside the left hand side of a wall as well as the right hand side of that same wall on adjacent squares, and most pathfinding algorithms are suited to a situation where that also implicitly proves that you can walk between those squares, but we have a wall there and have to check for doors or windows etc etc and have situations where 'that square is blocked if you're going north but not if you are gong east'. 

 

We've had to do significant system bending to make A* work comfortably with the PZ map and it's pretty much removed possibility of using a lot of the A* optimizations. So when you see a pathfinding thing on a website that works on a grid and think 'hey that may work for zomboid' there are countless hidden factors that make things more difficult or make certain systems completely unusable.

Link to comment
Share on other sites

3 hours ago, lemmy101 said:

someone who doesn't even know the name of the bloody algorithm used

 

7 minutes ago, lemmy101 said:

We've had to do significant system bending to make A* work with the PZ map

Now I am confused. Is Project Zomboid using A* or other algorithm?

Link to comment
Share on other sites

Wow, now I feel guilty that I dared to post my observations after your statement.

I'm no Expert of A* either (like CaptKaspar).

I have basic knowledge of recursive programming and have heard of A* before.. but that's it. So maybe half of my post was technically bullshit.. ^^

 

I never underestimated your efforts and endless thought-processes about this (or other) topics.

Sorry, if my post (especially or additionally) made you feel upset, Lemmy.

 

Nonetheless, this is a place for PZ-Feedback, so maybe I shouldn't be feeling too guilty!?

 

I didn't know, that Zombie behaviour is moddable. That is very interesting. I have no experience with modding/LUA, but I will have a closer look at that. Maybe it will be as fruitless, but next time I can talk less stoopid things about this special topic.. ;-)

 

Edited by Leoquent
Link to comment
Share on other sites

Okay, so now that this topic has calmed down I had a question about an inconsistency with the pathfinding AI: A zombie will always stop to break a window, I can be shouting at them through a broken window 1 tile over and they will still prefer to bang their head on the unbroken window, yet the same is not true of player built walls... As was pointed out earlier in this thread they will easily find their way through a maze of player built walls which would in theory make building a bunch of window frames and boarding them up far superior to just plain walls.

What is it with windows that overides their pathfinding AI and why is that not applied to player built walls?

Link to comment
Share on other sites

5 hours ago, zomboid123 said:

building a bunch of window frames and boarding them up

I wanted to do exactly that but you can't barricade your own window frames. At least I certainly couldn't.

 

5 hours ago, zomboid123 said:

 What is it with windows that overides their pathfinding AI

My guess is that windows are considered empty space by the pathfinder (like fences). So the zombie picks path that goes through unbroken window because broken/unbroken makes no difference for it.

Link to comment
Share on other sites

Guest
This topic is now closed to further replies.
×
×
  • Create New...