Pathfinding

I don’t know how old this argument is or if we have already solved it but this seems like an interesting article about waypoints vs navigation meshs HERE


"Oh," I hear you say, "but I can just add more links to my waypoint graph to smooth everything out! I'll connect all the nodes in the whole town if I know an NPC can walk between them in a straight line."

"But that gives you exponential explosion," I reply ... "You're talking about 40 or 50 extra links in this example alone. The number of connections you'll need between all the nodes approaches O(N^2) as the size of the area increases."

"OK," I hear you say, "In that case, I'll just mark each area between any set of 3 mutually adjacent waypoints as 'open' so I know my AIs can walk anywhere in that area."

"That makes a polygon ... and you've just created a navigation mesh," say I

The problem isn't really solved because, it depends on the scope of the project. Navigation meshes aren't simple to implement and require quite a bit of work to get up and running. Waypoint graphs are fairly simple to implement and good for smaller projects or ones where AI developer is inexperienced.



Almost any (minus 1 or 2 genres) 5 star game ought to use navigation meshes. There is really no reason not to if you have the skill and the budget.

Are there any good tutorials on how to even write AI pathfinding?

Unfortunately I have not used navigation meshes myself and do not have many ready links to related resources. But here are some links I have saved:



A* Pathfinding for Beginners

Terrain Reasoning for 3d Action Games (PDF)



I also made a little A* implementation with BinaryHeaps myself which is available on the jme-demos google code page.

Hi there,



a few days ago I run into the problem of pathfinding in a RTS( real time strategy) and implemented a simple A* with a little optimization - I just merged a Heap and a HashMap to have a PriorityQueue, thats fast and a fast contains-function.

The really good thing is that the A* implementation doesn't depend on a 2D grid, but can handle every graph, thats represented as an adjacency list

After testing it in my RTS I first was very happy about how good the paths looked. But then after creating a larger map I was shocked. Selecting multiple Units ( 5 for example ) and sending them from one end of the map to another just took more than 3 seconds to calculate the path.

First I tried to just reduce the node count of my graph and it worked well. I now have 512x512 heightmap and a 128x128 file, where the graph is saved. Thats ok for the moment, but I don't want to have the accuracy of my pathfinding to depend on the size of the map.

So there was an idea (thats not implemented yet):

Why not make different layers in the graph. For example 2 - you have one detailed graph for finding short pathes and you have one "interstate graph" for finding long pathes. So if you have a short distance to go just let A* work on the detailed graph. But if you have a long distance to go, find the closest point (or the closest edge) of the "interstate graph" from your position and from the target position.

Compute the best path from your position to the closest interstate-enter-position with A* on the detailed graph and the best path from the closest interstate-exit-position to the target with A*. Then just compute the best path on the interstate-network from interstate-enter-postition to interstate-exit-postition and you have a full valid path from position to target.



Of course the resulting path won't be the shortest in a mathematic sense - but I think you can get to really good solutions if your interstate-network is good.



PS:

Is it possible to get confirmed by email when somebody answers my post?

Its my second post here and I'm registred since yesterday

Sorry for my bad english



mfG

BrainNode

@first post:

i use an optimization to achieve the same result using a standard a* algorithm. it goes like:

use a*. then see if you can simply skip nodes because node a can reach node c,d,e and so on in a direct line. this avoids the "go in an 45

so. Jme have any support for Navigation mashes or this A*? (I'm totally new to AI pathfinding) or those have to be implemented from scratch?

They would need to be implemented from scratch. There are a couple java libraries out in the ether, but from what I've seen they are either not free or not well suported.



A* itself is relatively easy to implement.



Implementing a solid framework for your AI and generating navmeshes is quite an undertaking if you've not done it before. That said, if you want to, just start reading… AIGamedev.com has everything you'll need.

thx! ;D

I have ported greg snooks navigation mesh algorithm and demo to jme.

If anybody is interrested I can share the source. the demo shows basic path finding (o smoothing, no rotations of entities)

that would be interesting can u post source or maybe upload a jar

ghoust said:

If anybody is interrested I can share the source. the demo shows basic path finding (o smoothing, no rotations of entities)

Sounds interessting... would be nice if you could share it.

I've got a realy good book about Game AI, and it do talk about this kind of problem. On a game i don't remember the name they did like this:



Short Path, a straight line path to the destination, so the unity starts walking as soon as it is comanded to move.

Long Path, the thing that takes 3 seconds to compute.

Merge Path, a path betwen where the agent is RIGHT NOW (after following the shortpath) to some point of the Long Path, so it would stop the straightline path, and go to the correct direction.



the only bad side of this, is if you make it do something like this:



     3
 ########
 # ###  #
 # #2#  #
 ### ####
    1



if # stands for not walkeable
if 1 stands for starting position
if 2 stands for short path destination
if 3 stands for long path destination

as you comand it to move, if the long path takes too long to compute, the AI will walk from 1 and reach 2, what is realy bad, as when the Merge Path is computed, the agent will have to backtrack to 1 and then go to 3, he will look silly!

also, the Short Path could be computed on the "Simplified Graph", so it would look less silly.

I'll package the source and bin example. and provide a link (perhaps mid week)

Here’s the source: http://www.3d-inferno.com/Jme/navigation_src.zip A webstart demo is packaged herehttp://www.3d-inferno.com/Jme/navigation.jnlp, but my webserver does not support jnlp files so you have to download the file and start it manually… I have only tested the webstart demo on windows (though mac & linux jars are present)

ghoust said:

Here's the source: http://www.3d-inferno.com/Jme/navigation_src.zip A webstart demo is packaged herehttp://www.3d-inferno.com/Jme/navigation.jnlp, but my webserver does not support jnlp files so you have to download the file and start it manually.. I have only tested the webstart demo on windows (though mac & linux jars are present)


i don't seem to be able to save the jnlp but i have the source thx will be a huge help

jnlp webstart should be working now…

Hi guys!

Do you know some A* implementation for JME3 please? :wink:



Thanks a lot!

Feel free to take the source and port it over to jme3. Or wait half a year or more until I have done it. :wink:

Where is A* implementation for JME2?