Still a work in progress... but I have enough to show off for feedback.
Video description:
[font="arial, sans-serif"]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.
This algorithm (blacklist) is not a replacement for static navigation meshes (as a whitelist), but a compliment for speed and increased performance.[/font]
[font="arial, sans-serif"][/font]
[media]
(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.)
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 ?
Yes, you could implement some sort of steering mechanism, but this is not necessary.
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"]
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.
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.
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.
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?
