# 2D Distance Map

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

## Recommended Posts

I'm working on a 2D RTS game, and I've been thinking about ways to handle unit-terrain collision. I've come up with this method, which I think is a little innovative. Basically on every tile I calculate how far it is from the nearest non-walkable tile, and store that number. So when moving units units can only walk on tiles which are at least their radius away from a non-walkable tile. And thoughts on this method? My questions are, how would I go about generating this distance map in less than O(n^2), and also I want to do hierarchical A*, but the nodes will be different for units of different sizes. Any thoughts on that? Thanks.

##### Share on other sites

The obvious way to not have to do O(N^2) depends on what limits you know will exist on the size of the moving objects. If you know that you wont have any objects larger than R (its radius in tiles) then for each tile on the map you only have to test a box/circle around it to R+1 (radius plus one from the tiles center) as any furtehr wont matter for that tile.

If you have large objects in relation to tile size then you may want a prebuilt list of offsets for a circle pattern (of the max R+1 size) to optimize the testing. Besides being more accurate than a square pattern you can also order that list to be an expanding set of (near) concentric tile offsets which you can stop early on the first offset position that collides (you already would have found the interference radius so there is no point seraching further out from that tile...).

There will probably be endcases at the edge of the map which you would handle depending on how your mechachanic processed the edges, The circle culling system I mention above will work with no extra if-then edge testing as long as the edge of the map is a layer one deep of impassible tiles.

1. 1
2. 2
Rutin
15
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633725
• Total Posts
3013559
×