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!

Ok, here is my suggestion:

1) make your waypoint list and connections.
2) Parse the waypoints and find islands. Either handplace the islands, or choose a huristic like "if you have a neighbor who is also my neighbor, then we are part of the same island". Nothing will work 100% perfectly, as you will always end up with some compromise. But the idea is to seperate waypoints out into rooms (like your ABC)
3) Make a pathing matrix for your rooms (ABC). Like a navmesh system the idea is that you want a matrix that represents "if I'm at A, what letter do i go to next if I'm headed towards Z". You precalculate all the shortest paths, and using that matrix you only have to worry about the next move from your current location. No more deep pathfinding.
4) Once you have the matrix from 3, you need a waypoint list that says "A3 connects to M4" So, when your matrix says "to get from A to Z, goto M next" you'd then look up, "A3 -> M4", so I have to path to A3.
5) Then you path inside your small list of nodes in room A using something like A* to quickly generate a path from your current closest waypoint towards A3.
6) once you are at M4, you look up "to get from M to Z, goto V" and repear 4-5 till you are in room Z.

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.

As was suggested earlier, you seem to be doing a lot of work reinventing the proverbial wheel. Hierarchical A* encompasses pretty much everything that you have covered. It is well used and well documented in plenty of places around the web.

As you mentioned later here, the key is to identify the areas as a whole but to know the costs from each entry point to each exit points in each area. That is your edge cost to traverse that "island". Then, you can simply glue the large sections together as part of your overall search. You only need pathfind across the individual areas when you get to them - thereby cutting down your search space significantly.

Quote:

Original post by InnocuousFox As was suggested earlier, you seem to be doing a lot of work reinventing the proverbial wheel. Hierarchical A* encompasses pretty much everything that you have covered. It is well used and well documented in plenty of places around the web. As you mentioned later here, the key is to identify the areas as a whole but to know the costs from each entry point to each exit points in each area. That is your edge cost to traverse that "island". Then, you can simply glue the large sections together as part of your overall search. You only need pathfind across the individual areas when you get to them - thereby cutting down your search space significantly.

I haven't really done my reading on Hierarchical A*, although I've done quite a few variations on A* myself. I'm wondering about the last part you said: assuming that the "areas" defined by waypoints are not trivially connected, would it make sense to do the fine-detail pathfinding from your current location to all of the exit nodes between the second and third waypoint?

It doubles your search area, but in return it would tend to find a better path through your current node by always looking ahead one area.

Really, it doesn't help at all. If you know that a path exists inside a section from one exit to another, you can calculate and store that information. You can then use that low-level information on the higher level searches as the edge calculation. The length of the paths inside each area is then counted in doing the area-to-area search.

The only advantage you can get is at your ultimate destination inside a final zone. You would want to calculate how far the destination node is from each exit. That way, it might bias from which zone you would want to approach the target one.