Jump to content
  • Advertisement
Sign in to follow this  
Axiverse

2D Distance Map

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement


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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!