Dynamic Pathfinding

My personal way of finding routes on large maps, would be to chunk them into smaller maps...

Say you had a map of 10k x 10k tiles (not unreasonable in mmorpg), obviously you don't want to run an A* algo over the whole thing.

So first, break it into 100x100 sections, each of which you flag as either "passable" or "impassable" (A simplication, I realise). If you want to be more advanced, you can ask "Can I get from (x,y) to (x+1,y) ?"

Anyway, you can then run the A* on this map without any problems. Then use A* for each segment, using the entire block as a target (i.e. anywhere will do), starting from the beginning.

You can do this as you go along, updating it for any obstacles found en-route.

I'd really advise that you don't have too many blockages, otherwise things could get awkward.

Of course, unlike A*, this route won't always be the best, but it won't be too bad either (hopefully).

Each of your sub-map A* searches needs to be limited to a route of a maximum length (say 250, seeing as you are searching a 100x100 area, otherwise if it's totally blocked it could blow up into using a stupid amount of memory.

Mark

Thanks, that idea, and some stuff I found on the internet, will give me something to think about.

Make your map sparsely populated with blockages (i.e. there's 'always' a simple path through) and have special cases/tests for known bottlenecks?
Obviously depends on the map and your generation methods...

Unfortunately, I don't make the maps, nor am I responsible for who or what is blocking any bottlenecks, and even more unfortunate, sometimes there IS only that one tree across a river connecting the two shores.

Some general background...

The problem you are dealing with is typically called (surprisingly enough!) replanning. The detection of an obstacle on a planned path is the result of execution monitoring: testing each state before an action is executed to ensure that the action will succeed. In this case, when on the bridge in front of the 'barrier', testing that the agent can pass the barrier and finding that it cannot (so it cannot execute the rest of its plan). Thus, the plan has failed and replanning must commence.

Within the AI community, if you did not generate a conditional plan (i.e., an action to execute in each possible state... of which one is the domain with the blocked path) then you must expend effort to find a correction to the current plan. This can either be done by repairing the current plan (finding a minimal set of actions that deviate from the old plan around the obstacle and back onto the plan) or preparing a new plan from the current state to the goal.

If you happen to have stored the previous search tree used to find the current plan, then you can use this as a starting point for repairing or replacing the old plan. The D* algorithm (Dynamic A*) by Stenz (see below) would solve your problem for you... but might be more computationally expensive than you are prepared to pay. Certainly give it a go and test the solution quality vs the cost.

Your backtracking method should work, since it will find the closest branch node in the tree that contained the optimal path and a suboptimal path. However, there are no guarantees that this suboptimal path is still viable. Hence, it might pay for your agent to sit in front of the obstacle for a few frames while it tries to generate a plan to go around. If it happens that in this time the obstacle clears (because it was only a temporary obstacle... like another agent crossing the bridge) then it can simply resume its original plan.

There are plenty of other strategies you could employ and there is a HUGE amount of literature out there on replanning that is appropriate to your problem... particularly from the robotics community. I suggest you start with the Stenz paper and check out Google and Citeseer.

Here's the Stenz reference:

@article{Stenz95,         author = "Stenz, A.",         title = "The {F}ocused {D}* {A}lgorithm for {R]eal-{T}ime {R}eplanning",         journal = "International Joint Conference on Artificial Intelligence (IJCAI)",         year = 1995        }

I hope this helps!

Cheers,

Timkin

So what you're saying is to have the agent backtrack a bit, wait, then see if the obstacle cleared before going ahead and replanning anything. Sounds good. Anything that saves me from having to do ANY additional pathfinding is my savior.

Hi,

Games usually (at least the ones I worked on) use steering to avoid dynamical entities. Steering is only a set of forces that drags your character around. The next node (A*) you're trying to reach will be one of these forces, and the obstacles you're trying to avoid will also be contained in these forces. As you can guess, the next node will be pulling your agent towards it, while the obstacles should push the agent in the other way.

Check out C. W. Reynolds' website for more information on steering.

Hope this helps

Eric

Re: Steering.

If you do go this route, you may want to look at the Counter Strike bot GDC presentation from last year. They took an approach I hope to explore at some point; build a path, then follow it loosely.

From the videos with the presentation, it looked very interesting. It is also one of the better visualizations of a pathing system I have seen.

If you have a fast connection, check out:
http://www.gdconf.com/archives/2004/booth_michael.zip

Its a hundred meg download, so be warned.

The one arguement against steering that it (without augmentation) doesn't handle obstacles which totally obstruct a path. When this happens, the local pathing/steering may fail to find a way around the obstacle. Hopefully, it fails instead of running in place.

At this point, you would typically 'repath' (from the AIs current position, to the goal. Unfortunately, as the pathing system doesn't know about the obstacle, an identical path to the one which just failed is created, even though there may be a longer but unobstructed path.

Steering definitely does work, but I would argue that it (A* + steering) isn't a complete solution to a static navigation space with dynamic obstacles. It constrains the type of obstacles to only ones small enough , or in large sparse space, that steering can handle them.

** sorry, I just realised I just misread the original post, I'll still post my reply, just in case it might be useful to someone **

Indeed, "static" dynamic obstacles that blocks the way are harder to avoid.

If the AI is friendly to the player, one option could be to let the AI go as far as it can, and when ever the agent gets stuck he could notify the user with a sound and/or graphics... queue your actions and wait until the path is free.

I don't know how efficient it might be, but each unit could hold a list of nodes it want to avoid, and take care of avoiding these nodes while using A*... it would force the NPC to pick another way. Combined with your idea of sub sections of paths, I think it could give good results.

Cheers

Quote:

Original post by TSwitch So what you're saying is to have the agent backtrack a bit, wait, then see if the obstacle cleared before going ahead and replanning anything.

No, that's not quite what I was saying. I was suggesting that once your agent identifies an obstruction lying across its path, it stops and starts computing a correction to its plan (either a new plan or sufficient steps spliced into the old plan to tak it around the obstacle). If during the time it spends performing the computation (which would presumably be spread out over a few frames... maybe even a dozen or two) the obstruction clears, then he can abandon his pathing search and go back to his original plan. You could even work this into the game play. Have the agent issue an emote of some form (like a curse at another player who is blocking their path: 'GET OUT OF MY WAY YOU FURRY LUMP'; perhaps some protestations: 'Damn, I'm going to have to go around this immovable pile of dwarf!') That way, in the time it takes to say this and play a short animation, you've had maybe 20 frames over which you can spread some pathing computation. If during that time the obstacle clears, then you play another short emote... perhaps something like 'Aaahh, that's the way ninny' and the agent keeps on walking along its path.

Hiding computation behind NPC emotions and actions is a good way to district the player from those annoying little moments where you need to pause the flow of the game to throw in some extra computation.

Cheers,

Timkin

The only problem would be if the agent has already started on the bridge. Then it, too, is an obstacle, to the other PC. If that PC doesn't move, then there's going to be a few seconds where we get into a stand-off. I might even piss off the PC, which isn't a good thing.

I'm trying to make the agents kowtow to the PCs, lest I get an angry mob with virtual pitchforks on the forum reporting them for blocking or whatever. I can't have that, because these agents are supposed to be regarded as humans (the same reason I can't have them repeating the same phrases over and over) and if I tell them "Hey, those aren't real people, give them a break." it'll be all over and the surprise is ruined and I've failed.

I guess I could spill a little bit about these agents. My plan is to have them start out as level 1 characters and level themselves up, fighting, harvesting, mining, whatever, and eventually they'll be really high level and I'll send them out into the PK areas where they'll be really formidable foes. Hopefully. And they'll have earned all of the armor and weapons and potions they use.

Quote:

Original post by TSwitch The only problem would be if the agent has already started on the bridge. Then it, too, is an obstacle, to the other PC. If that PC doesn't move, then there's going to be a few seconds where we get into a stand-off.

This shouldn't be a problem. Test the nature of the obstacle. If it is a player character, then enforce backtracking to the last known state that had an alternative branch emmitting from it in the search tree. Take this alternative route just one move. This equates to 'getting out of the way'. In the bridge example, this would be the state just prior to entering the bridge. Take a path to the left or right and move far enough so that the agent isn't blocking the entrance to the bridge. Once in that state you can start searching for a new path... or perhaps watch to see if the other agent moves off the bridge.

Timkin