Pathfinding using mipmapping

This topic is 4316 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I am interested in expanding the capabilities of my A* pathfinding to use a "mipmapped" version of my terrain for speedier searches over long distances. I fully understand the concepts behind it, I just don't understand how to exactly go about the actual mipmapping of the terrain, how to reduce the resolution of the terrain without losing vital pathfinding data. Does anyone know a good resource that describes how to mipmap the terrain and what specific info, flags, etc. need to be calculated in order to reduce the "resolution" of the terrain grid? Thanks, Jake

Share on other sites
I think that by definition, you lose data this way, just as you lose data when applying it to graphics. As to what data you choose to sacrifice, that's up to you, and depends on what data you're actually using.

Share on other sites
Well, at this point all I care about is whether the terrain is "walkable" or not. What I'm wondering, I guess, is whether there is a clever way to reduce the resolution of the terrain grid, thus saving time on A*. It might involve modifying the A* algorithm to account for extra data attached to the reduced grid squares that preserves the informoation of the higher resolution.

But maybe this isn't possible, I don't know.

One suggestion I'm reserving as a fallback is to consider a low resolution square blocked if it contains any high res. square that are blocked. Then you just handle the blocked low res. squares at the higher level when they are encountered.

Any thoughts or other suggestions?

Share on other sites
I would give all the tiles info on which sides are connected (3+2+1 bit, only a byte extra data). That way the pathfinding wouldn't need to explore the complicated low level tiles, but it would still be able to create working paths.

Share on other sites
You can visualise a terrain mipmap as a heirarchy of tesselations of diminishing resolution (larger tiles). You can create this either by starting with a fine tesselation (high resolution) and simplifying this, or creating individual tesselations of appropriate resolution from your height data. The latter is probably easier to manage because you can easily sample any given tesselation to produce a regular grid of height data.

As for incorporating lost information. By definition, a mipmap has a lower information content for each successive decrease in resolution. You're going to have to sacrifice some information. How you choose to handle this is up to you. I can think of some very elaborate methods, but honestly, simple ideas will suffice. Basically, all you need to do is come up with a single measure that indicates for any given tile at the next finest resolution covered by the current tile, how likely it is to be impassable... and average this for the current tile over the tiles it covers from the next finest resolution. Your pathing algorithm should then take this into account in its cost function for paths.

Most mipmapping (as you're probably aware) is done by averaging... that's a little harder when dealing with triangular tesselations... but certainly not impossible. Since you can presumably do this offline, you can use any manner of algorithm to achieve it. As an esoteric one, you might consider taking a 2D fourier transform of your height data, filtering it, resample it on a coarser grid and then transforming it back with an inverse transform, then tesselating that surface... or if working with tesselations, take the 3D transform of the surface normals, filter it, resample it and inverse transform it.

Cheers,

Timkin

Share on other sites
Well you could use it instead to as an early cap out of whether there is a path or not. But a texture map is not going to work, the way to do it is with basically a subdivision of cubes.

Like a quadtree/octree. At the most abstract level you have 4 quads, Moving from one quad to another is possible if you can move from quad a to quad b at any point on the border.

And then dividing the quad up into 4 more quads and applying the same thing.

The difficulty is in generating the tree, generally speaking it will be best to start out at the finest level you want.

Share on other sites
I think I would agree with dawidjoubert on that.
If you're looking for how to speed up your A* over huge landscapes... I think you'll have a much easier time solving the problem by early-exclusion (quad-tree) than by actually decreasing the resolution (mipmapping).

As you said, you're looking for a faster way to do it. Not specifically mipmapping, right?

But I believe this way would require some pre-processing of the game map. You'd have to generate the quadtree when you load the map, and perhaps you don't want to do that? Perhaps you have some reason to want to handle it all in realtime?

If so, then go for finding a way to decrease the resolution. Several approaches to this pops up in my head, but from a first look I believe I would personally try to solve this by means of quadtree-ing.

Share on other sites
So what you want to do is to find the shortest path with
less resoulution.

Ill guess that the mimmap should contain if there is a path
trough the mipmap pixle, not what kind of path.

If you have fex. 4x4 pixels and you want to reduce it to one,
you should see if the 4x4 pixels are walkable: can i go from north
to south, can i go from east to west and so on...
then store this result as your new pixel.

This way, when you do the search on the mipmap, you will know
that there IS a path trough that pixel, but not what the path
is...

averaging or adding the 4x4 pixels could give false results, but
this logical test should make you a good mipmap to search...

Later you have to search inside 4x4 pixels, but this can be done
when you get there...

-andy

Share on other sites
A KxK area has K^2 cells, but only 4K edge-walls.

Thus, the space of (edge of KxK region, edge of KxK region) is of size 16 K^2 -- only 16 times larger than the number of cells.

For a given KxK area, define the "edge map" to be a map from "any two cells at the edge of the KxK area" to "distance to travel from the first cell to the second".

Now, take a 2Kx2K area for which the 4 sub-KxK areas have "edge maps".

You can build a 2Kx2K "edge map" using the A* algorithm for each pair of outer cells and the sub-KxK "edge maps".

If you start with 2x2 areas and work your way up to nxn areas, there are lg(n) layers. Each layer requires roughly 16 distances per cell, so the total memory requirement for such a "A* mip-map" would be 16 n^2 (1+lg(n)). Considering that you have n^2 cells, this isn't that expensive.

When finding a path between any two points in your "A* mip-maped" space, you only have to consider paths that are along the highest KxK block that does not contain either your "current" or "end" location and that your "possible path node" has an end on.

Once you have determined the minimium distance, you have to deconstruct the mip-maped routes and do "small-scale A*" on each block to figure out the ideal path.

At each level, you have 4 sub-cells with "edge maps", the knowledge that you won't be leaving the 4 sub-cells, and a start and destination edge. There is no guarantee the path isn't psychotic, but at least you know the total cost of the path, and the start/end points, to start with. :)

I believe such an algorithm gives the ideal path, faster than naive A*, but it requires far more pre-computation.

Interestingly enough, one benefit of this algorithm is that you quickly know the total distance and the "overall" route faster than the route details. In theory the rest of the route could be calculated as time progresses and the unit moves towards it's destination.

Really simple situation:

Space:
--x--xx--x------

x is blocked
- is not blocked
diagonal movement is not allowed.

Top left block:
---x

Numbering the edge blocks with 1 starting at the top left, clockwise, the edge-map is:
1,1: 1
1,2: 2
1,3: N
1,4: 2
2,2: 1
2,3: N
2,4: 3
3,3: N
3,4: N
4,4: 1

X,Y is the cost to move from outside the 2x2 block, into location X, then move within the 2x2 block to location Y.

N means "no path".

Next block:
x-x-

Valid paths:
2,2: 1
2,3: 2
3,3: 1

x---

Valid paths:
2,2: 1
2,3: 2
2,4: 3
3,3: 1
3,4: 2
4,4: 1

----

1,1: 1
1,2: 2
1,3: 3
1,4: 2
etc

Using these, you can build the entire 4x4 block's "edge map" (it has 256 entries).

And using 4 4x4 block's "edge maps", you can build a 8x8 "edge map" (which would have 1024 entries).

If you are at the edge of any of the 8x8 terrain, you can find out what the cost of moving to any other edge of the 8x8 block by a simple lookup in a table.

Now, I may be on crack -- I am not an expert at this -- but it seems to me that this is accurate, fast, not ridiculously memory expensive, and not insanly hard to do the pre-calculation.

Deleted

Share on other sites
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.

Share on other sites
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.

Share on other sites
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 =-)

Share on other sites
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.)

Share on other sites
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

Share on other sites
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.

Share on other sites
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).

Share on other sites
Quote:
 Original post by ExtrariusI 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

Share on other sites
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