I have an FPS I'm working on and I've already written some bots that can solve paths using waypoints and A*. I also have a decent system that moves them in real time through these paths, and reevaluates their situation every so often to see if better paths exist. I even hacked together a small state machine to make them chase and attack. My problem is short-term pathing. If their goal (the player, for instance) is "easier" to get to than their next waypoint, they chase him directly. The problem with this is that they tend to walk through each other. I have two questions: 1. What is a good (i.e., fast) way to prevent them from walking into each other? 2. Once they avoid walking into each other, how can I make them find a new path around each other without resorting back to using the waypoints? For instance, say two bots are running directly to their goal (an enemy). They realize that they'd run into each other, from the solution to my first question. How can I have them go around each other (making sure that they don't clip walls)? Thanks!

One solution is to use steering behaviors.

See Craig W. Reynold's webpage for examples.

Basically what you do is steer toward your next waypoint, while avoiding other dynamic obstacles / walls. You can check each n frames if your target destination is still accessible (if another dynamic object overlaps it). With such system you should be able to solve around 99% of your problems.

Hope this helps,

Eric

Thanks Eric!

I was already using a similar algorithm to have my characters turn while move, I guess I just have to adjust the direction of movement vector. However, I don't see how I'm going to avoid straying from the path to avoid world geometry. Most/all of our levels are in-doors, and the sphere checking described in the article would not work with our rooms. My best guess is to have each path have a width that the NPC would be free to roam within. The width would be assigned such that it is as wide as it can be without crossing level geometry. Is this a decent way to do it, or am I missing the boat?

Thanks

Your agents can use the wall avoidance steering behavior to avoid collisions with walls...

If you download the binaries that accompany my book and run the demos (Raven & steering behaviors) you'll see what I mean.

hi,

i know almost nothing about game programming but since i had an idea i figured i'd post anyhow ...

is it possible, once a bot has a path in mind, to cover that path in "virtual walls" which don't affect this bot but affect all others ? that way, no new algorithm is needed : the other bots just see walls so they can't use that path ...

now suppose a path crosses another possible path, it would be necessary for a "virtual wall" to also save the step in time at which it will be used (so that if a bot crosses before the original bot gets there it's ok).

a problem with this (or maybe it isn't a problem) is that two bots can use the same path as long as they don't use it at exactly the same time ...

what do you think ?

cheers,

stephane.

Yep, as fup said, you need to avoid walls as well. Depending on your level layout, you might be ok to use some plain 2D top view walls.

Stephane, the problem with your technique is that it doesn't take into account things that are not AI controlled. I don't know if this could be a problem for Zoma, but a lot of FPS games these days include physical objects and vehicles, and both of them need to be avoided when following a path.