Hello everybody, first post, woohoo [attention] Hello World. Too much text? Scroll down for animation. If you don't like reading all this text you can scroll down for an animation. Though I don't know if it makes any sense without the text. [grin] Goal: Pathfinding in a HUGE world I've been thinking about pathfinding in huge worlds. I'd like to get some feedback on my approach which I believe can be enhanced (or is actually useless and should be replaced by a different one?). Approach: Waypoints I'm used to pathfinding with a net of waypoints thus my first approach is to place waypoints throughout the world. The waypoints will be placed in a way that there's a clear route between connected waypoints. Problem: too many calculations This, however, means that there are going to be a lot of waypoints and there will be awfully many (*) calculations when looking for the shortest way. Finding the shortest way, by the way, will be done by trying all paths shortest first, longest last and stopping once the current way reaches the goal. (*) I'm not going to spend my time on calculating any numbers (I tried to but I came up with too many variables) but I believe it's pretty many and rises faster than in proportion to the number of the waypoints. But: The shorter the route, the less calculations. That's what brought me to the following enhancement. Solution: LOD? To reduce the amount of calculations I thought about adding an LOD system. When a character searches for the way from easttown to westtown (see example map below) he will first look at it on a great scale (highlevel waypoints) and finds out that he should go through the forest, then over the bridge and finally through the desert. He doesn't plan to visit the lake and the volcano. Example Map referenced in the paragraph above - if you're scrolling down for the animation: scroll further. He then looks at how to reach the forest. This might involve the same principle on a smaller scale until he reaches the waypoints with a clear path to each other described above. Once there, he'll continue with the bridge and so on. In this case, easttown, westtown, forest, bridge, desert, lake and volcano would be the highlevel waypoints. I think this model is quite close to how we would do it in real life, isn't it? Problem: Not the shortest path? One problem that arises is that the found path is not the shortest one as all high level waypoints in the path must be visited. An example of this is in the animation: visiting the second highlevel waypoint is taking a curcuit. Solution, anybody? I think clever highlevel waypoint placement can reduce this problem, though you might end up with lots of highlevel waypoints then. Probably still less than the lowlevel waypoints anyway. Oh and for calculating the length of a path: During some kind of navigation compile the connections will be bundled with the length of the way connecting them if it differs from their distance. Animation visualizing my algorithm The character searches for a path from A to B. Green circles are high level waypoint, blue squares low level. The colored lines are connections (colored based on the waypoints they connect) and black lines are obstacles. Please comment on and critisize my pathfinding system as I'd like to improve it before programming it. Changes during design are easier after all. Thanks Mr. Wonko

Quote:Finding the shortest way, by the way, will be done by trying all paths shortest first, longest last and stopping once the current way reaches the goal.

I'm not sure I follow this - what do you mean by 'trying all paths'? And why not just use a graph search algorithm, such as Dijkstra or A*? (Apologies if I'm misunderstanding something here...)

As for hierarchical pathfinding, it is a known technique for accelerating pathfinding in complex environments. A Google search for 'hierarchical pathfinding' should lead you to some good references on the subject.

You might also consider looking into navigation meshes, as they have some significant advantages over waypoint systems.

Quote:Original post by mrwonko
Hello everybody

Hello!

Quote:Original post by mrwonko
Please comment on and critisize my pathfinding system as I'd like to improve it before programming it. Changes during design are easier after all.

I think you've got a good strategy - should work pretty well on large maps. The problem is how to divide low-level waypoints into higher groups (but easy if you design the maps to deal with this!).
The real test is to try it out in a game - as jyk says, navmeshes have advantages if you're working in 3D.

similar approach

Quote:Original post by jyk

Quote:Finding the shortest way, by the way, will be done by trying all paths shortest first, longest last and stopping once the current way reaches the goal.

I'm not sure I follow this - what do you mean by 'trying all paths'? And why not just use a graph search algorithm, such as Dijkstra or A*? (Apologies if I'm misunderstanding something here...)

I actually don't know all those path finding algorithm yet, I read about them a long time ago and my approach was something I remembered because I could understand it and it made sense to me. Also as I said I'm used to waypoints for pathfinding, I know them from Jedi Knight 2 and 3, Oblivion (from modding) and Gothic 3 (from the art book) for example. Crysis also uses them for indoor navigation, although outdoor navigation is automatically generated somehow, I guess a triangle mesh.

My approach works this way:
To begin, you create one path for every waypoint connected to the start waypoint. Then you always follow the shortest path, creating one path for every possibility on a junction while not revisiting waypoints already in that shortest path. On dead ends the path is deleted. This continues until you reach your destination.

Animation again, A to B, the black numbers are the lengths of the connections, colored numbers total path lengths. Sorry for the bad visibility of the yellow path.



For implementation I though about an std::multimap that maps the paths to their lengths, because it's already sorted and allows multiple entries per key. Well and that's where you end up with a lot of entries pretty fast, therefore I thought of that LOD model.

A problem I can see is that this algorithm will calculate every possible path if there is actually no connection, wasting many cpu cycles, especially on a huge world. But that would be a design bug I think as every place should be reachable or else an NPC shouldn't want to go there.

Thanks for the answers so far!

I just refreshed my memory on A* and found that my approach is similar in that the way to be tried is based on its length.
In A* the distance to the goal is also taken into consideration and instead of saving all paths it saves the waypoints (nodes) and how to get there fastest. Seems like that way fewer memory is used.

As it looks like many agree that A* is best I might just use it :D
It seems a little harder to implement but that's ok.

Although I have doubts about whether it's correct to just use the distance to the goal as H or if this might lead to non-ideal solutions?

And I can probably still use the high level waypoint idea. And it probably still has flaws.

I like the island idea (provided I understood it^^), you're talking about something like this? I added grey border nodes which are used to determine the islands.



In this case it seems easiest to me to calculate the length of the shortest path from a border node to every directly reachable other border node, those would be the highlevel waypoints then. Then each border node of the current island would be tried and the shortest path is chosen.
Problem: Which border node of the goal node's island is the right? the closest? not necessarily...

But this sounds like an overall improvement as all the high level wps that need to be visited would be visited anyway. And pathfinding in the same island does not include LOD at all. And an island could still have sub-islands. For example the map I provided might just be one island in a larger world.