One of the ideas often presented for speeding up A* in large environments (I'm thinking a tile-based RTS specifically) is to perform the search on different scales. Basically the idea is you divide the map up into large sections - maybe a 64x64 grid covering the whole 2048x2048 map. You do A* on this scale first, then at each end of the path you do A* on the fullly detailed grid to find a short path from the start-point to the first large-scale node and from the last large-scale node to the end-point. I hope this kind of makes sense? While this sounds really nice in theory, how is the large-scale grid generated? How can you know which of it's nodes can be used - it's unlikely such a large chunk of the map will ever be totally blocked or totally clear?

Rather than using a grid, consider using a node map.

The node map can be LOD'd much more easily than a grid. You can weight the links between the nodes with different travel times, based on the complexity of the fine route, intervening terrain, whatever. Interpolating this course position to your standard a* routes gives you your fine-scale position.

Use a spatial division system to ensure that what you can see is always at the appropriate level for routefinding/planning. Stuff you can't see can use the coarse node map and get interpolated back.

I don't quite get it. You're saying a node might be like a 10x10 section of the map, and I precalculate which of its neighbours can be reached directly?

Forget the grid map. The hierarchical model is not gonna get you any significant benefit at all if all you do is quantize the map along grid lines.

Think about why the hierarchical model exists - it's so that you can use the top level map to quickly rule out large parts of the underlying map. Therefore that top level map needs to usefully represent the interconnectivity of distinct areas. It should be delineated by large obstacles or choke points. It is unlikely to help you at all if you do not have large obstacles or choke points.

So to design that top level map, you'd either get your map designers to designate specific regions of the map, or you'd perhaps perform some sort of choke point analysis on it, or something like that.

That does make some sense. I'll leave this for now until I come back to work on this again - then be back with more questions no doubt!

Thanks.

Quote: Original post by Kylotan
Forget the grid map. The hierarchical model is not gonna get you any significant benefit at all if all you do is quantize the map along grid lines.

This hierarchical model is called image pyramids, and used for fast lookups in image processing. The idea is that you effectively mipmap the whole map to different levels based on connection possibilities. First you have to find the shortest path on the highest level. Then by processing the next level, only those maps have to be searched that were found by the previous level. This can be done by 'reading' other nodes as blocked while doing the search. Please note that each mipmap node must contain the 4 or 8 possible connection informations in the form of a vector. (aka. bitmap) The mipmaps can be generated with logical operations by masking together the edges or a 2x2 tile on mipmapping.

This way large chunks of blocked and large chunks of walkable but detouring terrain can be skipped. The only requirement is the recalculation of each mipmap tile if an underlying real map tile changes. This can be N*8 operations if for an N level mipmap and a 8 way connected grid.

Viktor

Not a problem for static terrain but when the terrain starts to change ur have a problem.

Also if new buildings create choke points it is a problem. A way to resolve this is to forget the tile method entirely.

Like they did in C&C Generals, this eliminates most of the problems but creates the problem that you can't create a blockade.

Just cluster fully connected areas together into nodes.

Tell me if Im nuts, but instead of using a large grid, what about dividing the 'walkable' area of your map into a serie of convex polygon? Im sure there exist good algo to do that, probably beggining by a delaunay's triangulation...

Those would become your nodes, adjacent polygons gets connected, and it would identify chokepoints easily as the smallest nodes.