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

[zomboid123]

5 minutes ago, MXXIV said:

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

 

You can, you just have to add a window first.

[MXXIV]

2 minutes ago, zomboid123 said:

You can, you just have to add a window first.

How can you do that?

[zomboid123]

Use the move furniture tool to grab a window from a house and add it to your player made window frame. The tooltip is bugged so make sure you have both a hammer and a crowbar on your person when you do it.

[BoogieMan]

If the pathfinding isn't terribly resource intensive, what about making each zombie, or each group, calculate if there is more than one path to the desired destination and select one of the paths randomly?

 

-This way their behavior isn't 100% predictable (best possible route at all times)

-More difficult to exploit

-Disguises their clever pathfinding skills somewhat (adds immersion)

-Adds a random factor, which can surprise the player

-Increases chance of getting surrounded if you're not careful

-Less predictable horde gatherings since they don't all always choose the same thing

[EnigmaGrey]

2 hours ago, BoogieMan said:

If the pathfinding isn't terribly resource intensive, what about making each zombie, or each group, calculate if there is more than one path to the desired destination and select one of the paths randomly?

 

-This way their behavior isn't 100% predictable (best possible route at all times)

-More difficult to exploit

-Disguises their clever pathfinding skills somewhat (adds immersion)

-Adds a random factor, which can surprise the player

-Increases chance of getting surrounded if you're not careful

-Less predictable horde gatherings since they don't all always choose the same thing

Because pathfinding is already resource intensive, as is . . .

[Jab]

Sounds like the algorithm for path detection is pretty straight-forward, and while I agree with zombies being a bit too predictable in some cases, I feel that the speed, and dexterity, along with the ability to stay up-right, are too constant. Having these kinds of variables would dither the paths, creating somewhat of a random, and variant result, which would seem to prevent zombies with the current algorithm from not being able to reach the player, while giving a less predictable (zombie farming) result. You could use a range offset and recalculate at varying times. Some zombies could be deaf. Others could have short sight, or poor depth perception, and move into different places.

 

Not every zombie would need to be unique, however, variants could actually help both sides of what TIS's algorithm is, and what the OP wants to see.

[RoboMat]

I think we need some kind of boids simulation. Not because it works well for swarms, but because the name fits perfectly.

 

\o/

[EnigmaGrey]

20 minutes ago, Jab said:

Sounds like the algorithm for path detection is pretty straight-forward, and while I agree with zombies being a bit too predictable in some cases, I feel that the speed, and dexterity, along with the ability to stay up-right, are too constant. Having these kinds of variables would dither the paths, creating somewhat of a random, and variant result, which would seem to prevent zombies with the current algorithm from not being able to reach the player, while giving a less predictable (zombie farming) result. You could use a range offset and recalculate at varying times. Some zombies could be deaf. Others could have short sight, or poor depth perception, and move into different places.

 

Not every zombie would need to be unique, however, variants could actually help both sides of what TIS's algorithm is, and what the OP wants to see.

Yes, let's make it even more complex. You know, for the edge cases that actually notice . . .

 

7 minutes ago, RoboMat said:

I think we need some kind of boids simulation. Not because it works well for swarms, but because the name fits perfectly.

 

\o/

Little did they know . . .

[RoboMat]

The devs should call it Dijstarboids just to f*** with people

 

Also:

From all the pathfinding code I have written so far, A* is by far the only pathfinding code I have written.

[MXXIV]

6 minutes ago, EnigmaGrey said:

Yes, let's make it even more complex.

46 minutes ago, EnigmaGrey said:

Because pathfinding is already resource intensive, as is . . .

Come on, it's a 2D game. Minecraft does the same in 3D just fine and there are some games who have realistic physics apart of million critters using A* to attack players. Performance might be a problem, might be not. I wouldn't dare to claim this without having some benchmarks that it's pathfinding what slows the game.

 

It's truth that the game eats almost 2 full cores of my CPU even when it's running in the background and it's truth that the A* has almost no recursion limit. That might be a problem.

 

[EnigmaGrey]

*Sighs* The "It's 2D so it's simple" argument, really?

[RoboMat]

12 minutes ago, MXXIV said:

Come on, it's a 2D game. Minecraft does the same in 3D just fine and there are some games who have realistic physics apart of million critters using A* to attack players. Performance might be a problem, might be not. I wouldn't dare to claim this without having some benchmarks that it's pathfinding what slows the game.

 

It's truth that the game eats almost 2 full cores of my CPU even when it's running in the background and it's truth that the A* has almost no recursion limit. That might be a problem.

 

 

Comparing apples and oranges here. How many entities does Minecraft compute in one chunk? How many of those are actively doing pathfinding? Now compare those numbers to the zombies PZ is simulating. Now ask yourself how many of the NPCs in Minecraft do boid-like behavior. Now compare those numbers to the zombies PZ is simulating. Now ask yourself how many of the NPCs in Minecraft are doing complex behavior (knocking on doors, crawling through windows, getting distracted by stuff, punching walls). Now compare those numbers to the the zombies PZ is simulating ... I guess you get the idea.

 

Pathfinding can be a huge bottleneck even in modern games (and still is in many games). I'd say PZ is closer to a Strategy game when it comes to pathfinding. Huge number of actors, large map and very long paths. You can't do that without some tricks and hacks. It has nothing to do with the A* algorithm itself. If you read about pathfinding in general and educate yourself on the problems that come with it you will see that PZ and Minecraft have more or less completely different goals for their pathfinding.

 

TLDR: I am impressed with the zombie simulation that is going on in PZ.

 

Edited March 10, 2016 by RoboMat

[MXXIV]

1 minute ago, EnigmaGrey said:

*Sighs* The "It's 2D so it's simple" argument, really?

Yeah, probably and definitely better than no argument at all. I wonder where does all that negative attitude of yours coming from. If you're so sure there's something wrong with what I say, be a man and say what it is rather than just challenging me (or whatever is your post's message). The thing is 2D might be not be simple or might be but it must always be possible to make it simpler than 3D. That's just a matter of degrees of freedom.

 

lemmy101 explained some of the challenges regarding zombie patfinding but it's not really that other games don't have them, I just decided not to bring it up on him since he really doesn't seem to like to discuss this anymore and instead of asking him I can just look in the code anyway saving everyone's time. Until I look how it actually works I of course can't be sure. But I feel like I have full right to speculate without being perceived negatively.

[RoboMat]

Also last time I checked A* doesn't require recursion. Even if it would, it is up to you to implement a limit.

Edited March 10, 2016 by RoboMat

[RoboMat]

Just now, MXXIV said:

I wonder where does all that negative attitude of yours coming from.

 

If I had to guess it's because the "it's 2d" argument is used most often by people who have no clue about programming games.

[MXXIV]

4 minutes ago, RoboMat said:

people who have no clue about programming games

This is still just more negativity instead some nice explanation or some google terms I can use to improve my education. Seems I better unsubscribe of this thread because this debate is just spamming the forum and no benefit to me...

 

Edit: apparently it's not possible to ignore your own threads.

Edited March 10, 2016 by MXXIV

[RoboMat]

Well I didn't say you don't have no clue ... !? I just answered your question as to why your comment sparked some negative vibes. It's just a hollow argument. It's for example like saying "why can't this plane go to space? This spaceship can do it too".

 

If you really want to educate yourself on A* I'd recommend http://theory.stanford.edu/~amitp/GameProgramming/

[BoogieMan]

1 hour ago, EnigmaGrey said:

Because pathfinding is already resource intensive, as is . . .

For the moment let's ignore potential resource hit, also that most gaming PCs these days have more cores than are typically used at their limit by most games, let me ask this: How difficult would it be implement such a system? It could be limited by designing it to not to seek more than 2 or 3 paths at most, and to give up on extra paths if the search goes on for a certain period of time without success, or if the target location is below and/or above a certain threshold. Maybe it could even be just another option that could be set with the warning it uses more resources.

 

1 hour ago, EnigmaGrey said:

Yes, let's make it even more complex. You know, for the edge cases that actually notice . . .

 

Little did they know . . .

 

Edge Case doesn't really apply, it's easy to notice this behavior. They always seem to pick the best route to where they want to go, even if there is no plausible way to explain how they know the best route in advance. The people I personally know who have played the game have all commented on it, often in their first few hours of playing. Just being gamers for many years and even decades gives you a certain sense that picks up on such things. In most games it's not really an issue.. But Project Zomboid really isn't like most games.

 

 

To address the thread as a whole, people don't need to get so defensive about it. Most of the time when people offer feedback or even criticize something, especially when you can tell they put some thought in the post, is because they care. Half the purpose of early access, betas and the like is to get feedback. Far to often feedback threads here end up with this overly defensive approach to refuting someone's suggestion or idea.

Edited March 11, 2016 by BoogieMan

[Jab]

I thought up a solution, but people want to discuss being right and wrong.

[MXXIV]

28 minutes ago, Jab said:

I thought up a solution, but people want to discuss being right and wrong.

I didn't want to discuss right and wrong but RoboMat and EnigmaGrey decided to shut-down anything I (and apparently others) say on this matter as wrong. I disapprove such attitude which unfortunately stirs unpleasant discussion and usually misses the point anyway. I even had very specific ideas myself and wanted to start another thread about actual constructive suggestion, but what's the point? lemmy101 said there's no time for it (I respect this, I'm sure there are other problems) and several others decided that in that case any debate on this should not even start. Too bad for me I guess.

 

If there was more programmers concerned about this issue, I'd like to look into what lemmy101 proposed - try to understand and solve the issue in our way. I work in programming department which means I don't have time or will to go into it alone, team would be nice.

Edited March 11, 2016 by MXXIV

[Jab]

2 hours ago, MXXIV said:

I didn't want to discuss right and wrong but RoboMat and EnigmaGrey decided to shut-down anything I (and apparently others) say on this matter as wrong. I disapprove such attitude which unfortunately stirs unpleasant discussion and usually misses the point anyway. I even had very specific ideas myself and wanted to start another thread about actual constructive suggestion, but what's the point? lemmy101 said there's no time for it (I respect this, I'm sure there are other problems) and several others decided that in that case any debate on this should not even start. Too bad for me I guess.

 

If there was more programmers concerned about this issue, I'd like to look into what lemmy101 proposed - try to understand and solve the issue in our way. I work in programming department which means I don't have time or will to go into it alone, team would be nice.

 

Many people have and will continue to disagree with me on my ideas to make things better.

 

I see the nature of development like this: We all have an ability to share our vision. Sometimes, it take a few puzzles to solve to show the full picture, and sometimes, when I take the time to sit down and solve these puzzles, I see a picture that I don't recognize. I put the time and effort into that puzzle and solved it, yet it's not what I was originally going for, but I can share that knowledge and experience with others to craft their own ideas, and maybe make something useful out of it.

 

Maybe your path-finding isn't the solution. A lot of these people on these forums (from what I've seen), are used to ideas being constantly thrown at them. Their opinions can be harsh, but even then they are still useful to some degree. 

 

Then do what I do. Prove it works. Make a mod. Try it out yourself, even if it's code that doesn't touch the game's code. 

 

Can't do it in Lua? Do it in Java. There is a way.

 

The best constructive gestures are examples.

 

Make sure that if you want to invest time into this, you will do it for your enjoyment and benefit first. If you enjoy it, someone else will.

 

Just a tip from someone who has dealt with this same situation many times over the course of the past decade. 

[BoogieMan]

37 minutes ago, Jab said:

 

Many people have and will continue to disagree with me on my ideas to make things better.

 

I see the nature of development like this: We all have an ability to share our vision. Sometimes, it take a few puzzles to solve to show the full picture, and sometimes, when I take the time to sit down and solve these puzzles, I see a picture that I don't recognize. I put the time and effort into that puzzle and solved it, yet it's not what I was originally going for, but I can share that knowledge and experience with others to craft their own ideas, and maybe make something useful out of it.

 

Maybe your path-finding isn't the solution. A lot of these people on these forums (from what I've seen), are used to ideas being constantly thrown at them. Their opinions can be harsh, but even then they are still useful to some degree. 

 

Then do what I do. Prove it works. Make a mod. Try it out yourself, even if it's code that doesn't touch the game's code. 

 

Can't do it in Lua? Do it in Java. There is a way.

 

The best constructive gestures are examples.

 

Make sure that if you want to invest time into this, you will do it for your enjoyment and benefit first. If you enjoy it, someone else will.

 

Just a tip from someone who has dealt with this same situation many times over the course of the past decade. 

 

Is it possible for a mod to change the in-game pathfinding?

[Jab]

33 minutes ago, BoogieMan said:

 

Is it possible for a mod to change the in-game pathfinding?

 

Java Mod, most likely.

[EnigmaGrey]

You guys can discuss theoretical pathfinding in in GD, separate from a suggestion for PZ.