Instead of constraining the solution to a grid, I think a general graph-based approach should be used.

The basic algorithm consists of grouping nodes into sets such that no set shares more than a single edge with another set. 'Grow' random groups by selecting a node and adding it to the group, then adding it's neighbors, then the second-level neighbors, etc. Growing stops when a group would contain more than a certain number of nodes, would contain nodes that are too different (ie positional nodes span a great distance), or when a group would share two edges with another group. Once growing has stopped for all groups, start the process again with any ungrouped nodes and repeat the whole process until all nodes are grouped. Once that is complete, you need to calculate the cost of going from one edge in a group to each other edge in that group. Now, to find a path, simply use the edges of the groups as your A* nodes, which will find a high-level path. If you store the cost for moving from edge to edge properly (using the least costly value possible, since A* requires never overestimating), then the group-edge to group-edge path will still be the optimal path, and you never had to search the inside of the group. You could treat all edge nodes as a single edge, or if you require full precision, you can use all the edge nodes and still skip the internal nodes.

Really, in A*, what matters are the links/edges, and you're making a group of links/edges and using the links/edges in the new 'high level' graph instead of the more numerous ones in the original graph.

Hey, that was actually really clever Extrarius. Did you come up with that yourself, or is it an old and tested solution?
It sounds terribly fast, and would give good paths too.

I came up with the idea independantly, though I'm sure others have done so as well. I've yet to actually implement it, so I can't say how much speed improvement it gives, but theoretically it should be quite a bit.
It's basically the same as what NotAYakk posted, but generalized to arbitrary graphs. I've read similar ideas about heirarchial pathfinding in quite a few books, but I've never seen it explained quite that way (and I'm not entirely sure I'm explaining it correctly =-)

Quote: and you never had to search the inside of the group. You could treat all edge nodes as a single edge, or if you require full precision, you can use all the edge nodes and still skip the internal nodes.

Extrarius, I don't see where you are storing the "path from edge X to edge Y" within your node-clusters?


Knowing how long the shortest path is is one thing, but making a sprite move around the screen requires the exact path it will follow.

And storing the paths explicitly seems overly expensive -- the storage requirements for that could easily blow up. (in the grid case, a NxN area has 16N^2 edge-to-edge paths of max length N^2 -- up to O(N^4) storage requirements!)

That is why my algorithm has multiple "levels" of clustering. Paths between nodes that are far away should "step up" into higher level node-clusters and cross more terrain in fewer steps.

While "no node-cluster shares more than a single edge with another node-cluster" seems useful, I don't see how it is practical. Given a reasonably arbitrary graph, how do you generate your node-clusters such that they have this property?

(Note that my solution has no requirement for "at most one edge between adjacent node-clusters". It would be nice to guarantee, but it seems expensive.)

Two professors at my university (I'm actually working under both at the moment) wrote a paper on this topic a few years ago.

Check it out, I don't know if it's what you want but it sure sounds like it

Quote: Original post by NotAYakk
[...]Knowing how long the shortest path is is one thing, but making a sprite move around the screen requires the exact path it will follow.[...]

It is trivial and very very fast to calculate pats from edge to edge in realtime as they are needed using A*. First you calculate the path using the group edges and store that, then as your sprite reaches one edge and needs to move to the next, you find the path between those two edges (which should be short since groups are limited in size) and store that. Despite having to still calculate the entire path from start to end if the full path is travelled, this algorithm provides an easy way to break it up over a period of time without having to sacrifice seemingly-instant response along the correct path. Another benefit is that only parts of a path actually reached are calculated, so that if character state changes such as a goal causing the destination to change, the latter part of the path was never computed and thus didn't cost anything.

Quote: Original post by Extrarius

Quote: Original post by NotAYakk
[...]Knowing how long the shortest path is is one thing, but making a sprite move around the screen requires the exact path it will follow.[...]

It is trivial and very very fast to calculate pats from edge to edge in realtime as they are needed using A*.

Ah! Sorry, when you said "and you never had to search the inside of the group", I thought you meant "never" not "later, when you actually need the information".

Thanks, just didn't understand that bit of your post.

averisk, cute article.

The existence of an O(N^(3/2)) pre-processing time and space algorithm that grants O(lg(N)) performance at run-time seems nice. Althougth the "within a factor of at most 2" is a bit of a downer. (Arikati et al).

Quote: Original post by Extrarius
I came up with the idea independantly, though I'm sure others have done so as well.

What you have described Extrarius sounds very much like a method to contruct cliques in the graph structure. Such constructions arise in solutions to a number of graph theory problems and there are well established algorithms for finding cliques. You might find it beneficial to any pathfinding implementation to take a look at what has been done before in this area.

Cheers,

Timkin

Quote: Original post by NotAYakk
[...]Ah! Sorry, when you said "and you never had to search the inside of the group", I thought you meant "never" not "later, when you actually need the information".[...]

Hrrm, that must have been leftover from a previous version of the idea - if you form the groups such that getting from any node to any other inside a group is just moving in a straight line, you literally don't need to pathfind inside the group, though you might need to reform groups if obstacles appear

Quote: Original post by Timkin
[...]What you have described Extrarius sounds very much like a method to contruct cliques in the graph structure. Such constructions arise in solutions to a number of graph theory problems and there are well established algorithms for finding cliques. You might find it beneficial to any pathfinding implementation to take a look at what has been done before in this area.[...]

Yes, looking into the mathematics behind something is definitely a good idea =-) Like I said, I've never gotten to a point where I was going to implement pathfinding or I'd certainly have looked into it. In fact, I probably will now anyways since you've handed over a keyword