I was playing with Quadtrees, and I found a perfect path-search algorithm. There are some details to iron out, and probably some optimizations -- so I'm wondering if anyone recognizes it, so I don't have to do the grunt work myself. :) First, define a Path to be: ((source, dest), (hint, hint_cost), cost) Hint: the next step to take to find the path. Hint_Cost: the cost of getting to the hint location. Cost: the total cost of getting to the destination. Source: where you start. Dest: where you want to go. So the size of a Path is 2 counters and 3 locations. Now build a heiarchy of 2^N x 2^N squares, N from 0 up to large enough for your map. Each 2^N square looks like this:

/----------------\ 
|       .        |   
|       .        |   
|       .        |   
|       .        |   
|................|   
|       .        |   
|       .        |   
|       .        |   
|       .        |   
\----------------/

There is a total 4*2^N edge length, and 2*2^N of internal seam length. The 2^N square owns a Path from any of the seam/edge sections any of the seam/edge sections (36*4^N total paths). Note that there are 4^N nodes in a 2^N square, so this means a 2^N square has 36 Paths per node. The Hint for the Paths of a 2^N square is the next edge or seam you hit when going to the destination from the source. Example:

/------------D---\ 
|    ***6*       |   
9**  *  .*       |   
| *  * *5* ***   |   
| *  * *.  * *   |   
|.8..7.4...2.1...|   
| *  * *. ** *   |   
| **** *. *  *   |   
|      *3** **   |   
|       .   *    |   
\-----------S----/

S is the source D is the destination 1 is the Hint for the first path. 2 is the Hint for going from 1 to D 3 is the Hint for going from 2 to D ... To get from S to D, you first: A> Figure out how to get from S to 1. B> Figure out how to get from 1 to D. To figure out how to get from S to 1, you simply fall down to the 2^(N-1) square and solve it there. Not only is the length of the S to 1 route known, but you also know it won't leave the 2^(N-1) square. Sometimes the hint isn't within this 2^(N-1) box, but rather outside. You can detect these by doing a check at the 2^(N+1) level, and see if the path is shorter there. At 2^0, the problem turns into nothing more than the cost of crossing the square, and there are no sub-squares. Between 2^0 terminating, and the Path getting shorter, (unless we have a negative-cost node), the recursion will eventually terminate. I think this describes an O(total route length), times a factor logorithmic in 2^N (for a 2^N x 2^N surface), way of solving the entire path details of "get from one part of an edge to another part of an edge of a 2^N square to a 2^N square". The next step is to figure out an effecient way to go from a point inside a 2^N x 2^N square to an edge of the square. I think I can manage that in O((2^N)^2 lg(2^N)) time. I'd like to do better. Then, given two collections of "(edge, current cost)", and appropriate sorting of the Path information, I think I can manage at least O((2^N)^2 * log(2^N)) esque perfect pathing between them. Sad: I was hoping for O(path length)... As a bonus, "extra exterior edge sections" in the form of teleporters, elevators or ramps can be worked into this algorithm. The 'extra exterior edges' of the sub-squares of a square just have to be treated like internal seams. Building the data for the pathing will take a significant amount of time, but after you are done you only need to store 36*log(map width)*number of nodes Paths -- ie, for a 1 million by 1 million map, that's 360 Paths per node on the map. The bound on the amount of memory needed to build the dataset fails horribly if we try to do full 3D pathing: this algorithm really doesn't work above 2 D. So, I suspect this gives us, for two points K units apart on the map, O(K^2 lg(K)) to figure out the cost of getting from one point to the other, then O(path length lg(K)) cost to figure out the exact path. I'd love for this to fall down to O(K lg(K)) to figure out the cost as well. Hmm... Building the Path data could be tricky. I think the trick is to build it internally for each 2^N square, then integrate and check for shortcuts, propogating the dirty flag -- but that could get messy. Or we could just use Floyd-Warshall to do the entire map at once in time cubic in the number of nodes (which is expensive), but only linear space -- Floyd-Warshall won't produce the hint, but figuring out the Hint isn't that hard given the Costs (O(2^2N) for a 2^N square, or quadratic in the number of map nodes -- cheaper than Floyd-Warshall). ... So: Have you seen this algorithm before? It isn't A* -- there is no heuristic function, but instead we have a large hard-to-calculate data structure which cache's the distance information. Know any tricks/thoughts to solve the remaining problems? Did I make any errors that would make my attempt at an algorithm not work? I should do the work to ensure that my back-of-the-napkin estimates of execution time are accurate. Edit: cleaned up some details. [Edited by - NotAYakk on June 8, 2007 5:11:38 PM]

How do you check the length of a path at the 2^(N+1) level? Also I'm not entirely clear on where the nodes and edges are.

This looks a lot like hierarchical pathfinding A*, except I think there are some pieces missing and some assumptions that don't work.

At the N+1 level -- the algorithm is the same. You have a map from (source, destination) to (hint, hint_cost, cost), which provides you the cost and the next step that is ideal. If the ideal route is inside the N-level node, the N+1 level will tell you.

..

A 2^N square has (2^N by 2^N) nodes: each cartesian coordinate in the 2^N square is a node. By "node" I mean "smallest pathing element" -- in a tile game, that would be a tile. In a continuous game, it would be the pathing grain-size.

The "edge sections" of a 2^N square are the (graph-theoretic) edges connecting the nodes on the surface of the 2^N square to nodes outside of the 2^N square. They are also sections of the "edge" of the 2^N square, hence "edge section".

The "fold sections" of a 2^N square are the (graph-theoretic) edges connecting the contained 2^(N-1) sub-squares between each other. If you folded the 2^N square into half twice, the folds are where you would tend to naturally fold. They are the edges of the sub-squares that aren't also edges of the square. :)

  edge    |   \.//----------------\           -|       .        |           ||       .        |<--- edge  ||       .        |           ||       .        |           ||................|           | 2^N distance|       .  /^\   |           || fold->.   |    |           ||       .  fold  |<--- edge  ||       .        |           |\----------------/           -    /^\      |    edge|----------------|   2^N distance

The trick is that the complete information to get from any of the edges or folds to any of the other edges are folds is encoded in the pre-calculated data.

It isn't A*: there is no heuristic function, which is what makes A* different than a completely blind search.

A*, or an A* like algorithm, might be needed to get from (interior) to (edge) of a 2^N graph. So maybe this ends up being A* in the end. :)

But I think I can get a sufficiently accurate list of "cost to get to the edges of a graph" at the 2^N level in O((2^N)^2) time and O(2^N) space without using A*. Do this at both ends, and you can stitch them together in 36 4^N steps (or O((2^N)^2))).

2^N is at most twice the distance between the source and dest -- so I have O(distance^2) time and O(distance) space to hook together arbitrary points, and I never call a heuristic function... (note that this might require a post-process of O(path length) to find the details of the path -- two points 2 units apart could have a path that is a million units long -- this algorithm separates calculating the cost to get to the destination and the details actual path: but it does let you calculate the path piece-meal, and avoid having to do the entire path to figure out the first step).

What I'm looking for is ways to improve this quadratic score, or otherwise improve the algorithm, or get a name for it.

The pre-work building the 2^N squares doesn't store an approximation of the cost: it has to pre-solve all of the (edge|fold)-to-(edge|fold) paths. This is hard (as noted, O(nodes^3) time O(nodes(?)) space is one solution).

So I don't think this is quite A* -- but maybe it is equivalent to hierarchical A* in some way (or maybe just inferior!). Do you have a link to a good description of hierarchical A*

Am I making sense? :)

I think I sort of see what this is; I've sometimes thought about something similiar but then I usually come up with a reason why what I'm thinking wouldn't actually work as well as I wanted.

The terminology gets a bit confusing because of the confusion between different graphs and representations that are involved. Edges can either mean a link between nodes, or the sides of a tile, or in this case both meanings simultaneously. This makes the drawing a bit hard to interpret, even with the edges labeled, since the actual pathing nodes could be either the squares or the intersections of lines. I think in this case the pathing nodes are the squares, correct?

Then in the actual algorithm, the important elements are the edges between pathing nodes. We can represent the data structure used by this algorithm, or at least by one layer, by creating a graph with one node for each fold within a square and one node for each edge. The nodes created from folds and edges of a single square are fully connected. All of the edges in this graph are called paths, and contain the data as described in your first post. Is this accurate?

I think this is hierarchical A*, which is faster than A* but the paths found can be suboptimal. There's an article called "Near Optimal Hierarchical Path-Finding" you can google for. Actually that article only uses a limited number of hierarchies combined with A* searches, and I'm still not entirely sure how your method could always work, let alone how it would find optimal paths. What if there are walls going across entire squares?

[Edited by - Vorpy on June 8, 2007 11:06:51 PM]

If I understood your notation and explanation correctly, I believe the answer is 'yes, this algorithm already exists'. Unfortunately I cannot recall the name of the algorithm (I could probably find out) but it has already been applied (at least in comparitively similar problems). I first came across it when searching for partitions of temporally sequenced data that were optimal with respect to a cost measure. In that application, you built up the optimal partition over a 1D data set of length N by a recursive search of partitions of length N-1, which were in turn devised in terms of N-2 partitions. The optimal partitioning scheme for the entire data set was then an optimal combination of this heirarchical structure.

In your case you're searching in a 2D space and the cutpoints for the segments represent nodes in a graph. Conceptually its the same problem... the implementation is just a little more complex and taxing on your processor! ;)

If you're interested, I should be able to track down the algorithm name.

Cheers,

Timkin

Ah yes, heiarchical A* doesn't guarantee optimal paths. So this is not heirarchical A* -- this algorithm guarantees optimal paths. It does not attempt to find an approximation.

"tiles" are "nodes", if we are talking about a tile-based game.

The "edge sections" of a 2^N square are the "edges" of the "nodes" that leave the 2^N square.

So for a 2^0 square (aka, 1x1), the "edge sections" are simply the exits out of the single node within the square. There are no folds in this case.

For a 2^1 square (aka, 2x2), the "edge sections" are the outer edges:

abcde12fg34hijkl

So if the 2^1 square is nodes 123 and 4, the letters are all of the adjacent nodes. If we have Manhattan movement only, the connections (1b)(2c)(2f)(4h)(4k)(3j)(3g)(1e) are the edge sections of that 2^1 square.

If we have diagonal movement, you add in the diagonal connections.

The fold sections are the connections (12)(24)(34)(13) if we have Manhattan movement only (once again, the folds get more expensive if we have diagonal movement).

2^2 sections get larger.

...

The trick to go from an internal point to an internal point is:
Start with a "edge section" cost map for getting from an internal point to a 2^N square's edge sections.

You can expand it to a 2^(N+1) edge section cost map in O(2^(N+1)*2^(N)) = O((2^N)^2) time by simply examining all of the costs from the 2^N edges sections to the 2^(N+1) edge sections, and recording the cheapest solution for each 2^(N+1) edge section.

The cost for going from 2^0 to 2^K is thus
O( sum(i=0 to K) (2^i)^2 ).
=
O( (2^K)^2 * sum(i = 0 to K) (1/2)^i )
<=
O( (2^K)^2 * 2 )
=
O( (2^K)^2 )
=
O( width^2 )
quadratic in the size of the region we need (interior point) to (exterior) cost map for.

To path from one arbitrary point to another, we simply inflate to the point that our two points are in adjacent (2^N) square in a (2^(N+1)) square. Then use the 2^(N+1) square Path data to link them (another O(x^2) search) -- and voila, you can find the exact cost to go from one arbitrary point to another in O(x^2) time, where x is the distance between them, and you will have enough way-points that you can work out the actual path from one point to the other in O(path-length) time.

I could see this being much easier in one dimension! It took a bit of massaging to work out what data we need to cache in the Path data, and figure out how to use it.