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

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.

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?

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.

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

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.

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.

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

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