People pathing

[Brendon]

I'm working on an XNA game called Atom Zombie Smasher. It's a light strategy game played from the top-down view. In a densely-packed village, highly-infectious zombies are dropped in, and it's up to the player to smush the zombies before they gobble up everyone.

The people AI was kept simple: zombies run toward humans, and humans run away from zombies. Everything seemed to be going pretty smoothly, but that kinda stopped when I placed some buildings into the map. People were now bonking straight into buildings and looking pretty braindead.

I needed a pathfinding system to steer my people around buildings. I did some research on A-Star pathing, and after a few false starts, I had an ugly first pathfinding prototype up and running.

At the four corners of each building, I placed a "Pathfinding Node." The person's pathfinder brain then worked as such:
1. Person receives a Final Destination.
2. If Person had direct line-of-sight to Final Destination, then just move to the Final Destination. If not, then...
3. Query "what Pathfinding Nodes does this person currently have line-of-sight to?"
4. From this sub-list of Pathfinding Nodes, find out which one is closest to the Final Destination.
5. Move to this Pathfinding Node.
6. Once the Person arrives at the Pathfinding Node, return to Step 2 and do it all over again.

Surprisingly enough, this was not a complete disaster. In simple map layouts, people were nicely moving around buildings. But, in more elaborate map layouts, the pathfinder fell apart.

If a person had line-of-sight to a Pathfinding Node, but not to the Destination, the person would of course move to the Pathfinding Node. However, this resulted in situations where person would sometimes walk right past the Destination, seemingly completely oblivious. Secondly, buildings were destructable. If a building was destroyed while a person was en-route to one of the building's Pathfinding Nodes, the person wouldn't "realize" it until he arrived at the node.

So, the solution I'm using now is simply having the person re-evaluate his pathfinding once every 3-4 seconds. This solved the issue of the person mistakenly walking past the destination, and people also handled destroyed buildings better.

I'm fairly certain this approach is much more expensive than it should be. Ideally, I'd like to only re-evaluate the person's pathing only at key events instead of just every few seconds. At any rate, the results are looking pretty good and framerate has been a pretty steady 55, so I'm O-K with how it has turned out.

[Paul Jeffries]

Interesting post. I find it a little odd that you mention A* specifically, though, since the process you describe isn't an A* algorithm; in fact if I was feeling fussy (which I always am) I would feel bound to point out that it isn't really a true pathfinding algorithm either, since it's not hard to imagine a situation where your people end up running into dead ends and getting stuck there (or at least running backwards and forwards between two nodes). I suggest that using a more A*-like algorithm that calculates the whole path might save you processing time in the long run since you'd only need to run it once (until you reach the destination or unless you hit an unforseen obstacle). Then again it all depends on how large and complicated your maps are, how many units you'll have pathfinding at once... etc. etc.

[Brendon]

I agree - there are many ways to break what I currently have. And, as I should've mentioned, I'm definitely not using A* for pathfinding; I was inspired by A* and used it as a jumping point to making a quick 'n dirty way for my people to not bump into buildings.

There are limitations to the game's current pathing, so the design works with (around) these limitations. When a level is populated with buildings, every building is kept a certain distance away from other buildings. This ensures every building is a plain rectangle (no wacky L-shapes or horseshoe shapes here) and prevents making any dead ends. I'm fine with rectangle buildings, so this hasn't turned out to be an issue.

With that being said, what I'm doing only works with the ultra-simple setups I currently have. A* would be necessary for anything even slightly more complex.

[Goran]

I think it's better this way, KISS. As for people getting stuck in dead ends well, that's what happens when you're in panic as there's twenty zombies chasing you. :)