Sign in to follow this  
rekindledphoenix

Pathing using Avoidance

Recommended Posts

Still a work in progress... but I have enough to show off for feedback.

[u]Video description:[/u]
[font="arial, sans-serif"][size="2"]This video demonstrates a circular method to calculate the quickest path to a target. There are absolutely no navigation meshes, as all of the calculations are done in dynamically using a collection of avoidance radii.

[i]This algorithm (blacklist) is not a replacement for static navigation meshes (as a whitelist), but a compliment for speed and increased performance.[/i][/size][/font]
[font="arial, sans-serif"][size="2"][/size][/font]
[media]http://www.youtube.com/watch?v=lg5n1z_Hsp4[/media]


Blog post describing the method
[url="http://rekindledsoftware.blogspot.com/2010/02/ai-path-finding.html"]http://rekindledsoft...th-finding.html[/url]

[i](Even though it's not shown in the video, this will work with long distances, but not yet with changes to terrain. The solution to that would be for the algorithm to utilize navMeshes up stairs, but use this method otherwise.)[/i]

Share this post


Link to post
Share on other sites
Ashaman73    13715
Your video looks cool. :)

But your algorithm seems to be not reliable. I.e. at 0:37 your algorithm was not able to determine a path. This happens often in your video. But when it is not reliable, a simple steering behavior could execute a similar task, couldn't it ? Does it only work on terrain or would it although work indoor ?

Share this post


Link to post
Share on other sites
Yes, you could implement some sort of steering mechanism, [i]but this is not necessary.[/i]

As demonstrated in the later part of the video, when the NPC white cube gets to a point where the boxes are blocking the direct path. The algorithm picks the nearest vector to either the left or the right and continues to recalculate the avoidance nodes. In addition, something which I should have demonstrated in the video, was the ability to change the calculated radius. Increasing the radius for which the nearest vector is calculated, may suit for better results in a broader area, but is much less accurate since there are less nodes per unit of measurement.
[color="#696969"][i]
Watch the last 20 seconds of the video and you will see there is ultimately nothing to stopping the NPC from reaching it's destination.[/i][/color]


As of this post, the algorithm does not work well with platforms, such as a multiple story house or inner walls. A good example would be inside a subway, where there is only one large mesh for the outer walls. To solve this dilemma, a regular navMesh (whitelist) will be integrated into this algorithm, and the NPC will use the classic meshes where available, and use this system for any other circumstance.

thanks for the comment, btw.

Share this post


Link to post
Share on other sites
pithlit    179
Let me see if I have this right: you define a bounding circle around your unit and then you sample points along its perimeter, ultimately choosing the point heuristically closest to the target for the placement of the next bounding circle. You then repeat until you have a point whose bounding circle contains the target.

Assuming I haven't butchered your idea too much with the above summary, I have a couple of questions.

1. It's unclear to me if your algorithm is complete; i.e. are you guaranteed to find a path if one exists? For example, does your method systematically recurse to consider all possible paths in the event that a direct path doesn't exist?

2. You claim this approach supports dynamic environments. What happens when a change to the environment invalidates your path. Do you re-plan from scratch?

More generally: why do you need to compute the search graph every time? Why not pre-process your map to build a graph of avoidance circles and simply repair it locally when there is a change to the environment. This approach will not only scale much better (longer paths, more units etc) but you will be able to create some kind of hierarchy on top of it to further speed up your pathfinding.

Share this post


Link to post
Share on other sites
Kian    239
I noticed an odd behavior at about 0:15 to 0:20. The path goes straight towards the boxes, paths to the side of the boxes, then goes for the sphere (it wasn't immediately obvious, but I take it the sphere is actually the target, not the origin?). This means that, even on otherwise identical terrain (not slanted to give a certain direction an advantage), the path is not the same when you reverse target and origin.

Does that mean that when the algorithm encounters wide obstacles, it'll run up to the obstacle before trying to find a way around? What about U shaped obstacles, would it run inside before following the edge out?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this