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.
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
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.
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.
