I stumbled upon this guy’s site, and found this here path demo: http://bodytag.org/path1/
Very interesting pathfinding demo. You can probably get the Java Source from him is you ask.
Check it out!
It’s freaking awesome!!! :!: :!: :!: :!: :!: :!: :!: 
That algorithm (based on the visual and the fact that it is vision based) is relatively straight forward to create. A few raycasts from your current position (and potential waypoints) fanning out starting in the direction of the goal and you find the shortest open path by taking a greedy approach with a distance metric. So kind of like A* but you’re building your graph on the fly.
Sturestone implemented something like this in Unity.
I figured it wasn’t overly complex, but was commenting on it as an interesting way of testing your code .
I can see it easily spiraling downward into hundreds of racycasts a frame depending on the game environment and number of actors. Therefore I would still prefer a prebuilt nodegraph/navmesh for real game situations.
It would have some use in some situations, such as when the environment is very dynamic. A boulder falls from the sky blocking your path, an RPG blows a hole in the wall next to you creating a shortcut, etc. Situations that a static non weighted nodegraph might not be able to account for.
I’ve seen this example before and its very interesting. Although as mentioned above, this quickly becomes very expensive when dealing with complex 3D environments.
If I was doing a 2D game, this would probably be a good shortcut, but otherwise no. I’m therefore not including this technique in the upcoming version of Path although I am bringing navmeshes, waypoint networks and cell networks this time.
Well I don’t know about hundreds of raycasts per frame, maybe a very naive version. I think you could do this in the low tens of raycasts per frame max and probably on average around 5. Basically investigate one link per frame and have your bot follow the best estimated path so far. Plus since you are building a graph (or could build a graph) you only have to do this the first time your character enters an area on the way to another, once you have the graph you’ll already know the shortest path the next time your bot needs a route.
per bot…
Then you’re calculating for static geometry anyhow, and might as well have pre-calculated the node graph ahead of time instead of wasting CPU cycles on it. Also your ‘Already been here’ code better be spot on, or else you could end up with a node graph which has a density that is a magnitude higher than the resolution of your movement updates. Oh noes where’s that memory leak coming from!
True, although with proper tolerances “already been here” code should be relatively simple (it’s not like there’s any measurement error). However the node graph could still be used with a dynamic world as long as you set up a mechanism in which you can remove/mark nodes as the world changes.
For example the case of a path now blocked by a boulder. Last time you were there the path was open, so next time you go somewhere nearby your algorithm would plan a route through the boulder. Once you get there you see Oh, it’s not clear anymore, update the graph and replan. It would give your bot more human-like behavior anyway.
I’m glad my post has generated such enthusiasm!