Original Post
I have a 2d tiled map that I would like to create an abstracted movement graph for. The purpose is to be able to make fast checks on movement distance and accessibility between any 2 points in the map.
Performance of recomputing the graph is important, because I actually have multiple maps, one for each different agent type. I want to recompute the graphs every 10 seconds perhaps.
I am trying to decide between different options for building the graph.
I know of these:
1. Region map. Created via flood fill.
Plus: should be easy to implement.
Plus: not too costly.
- regions can be large and irregular in size, so is most useful for accessibility checks. Not so useful for determining movement distance between points.
2. Sector/region map (AI Game Programming Wisdom 4, p. 203)
It divides the map into quadratic sectors first, then does flood fill to divide these into regions.
Plus: Regions are smaller and so more useful for distance checks.
- Dividing the map into sectors means I have to copy a lot of data from the tile map representation (a multidimensional byte array) into smaller byte arrays before I can perform flood fill.
- The regions can still be irregular, making them less useful for distance checks.
3. Navigation mesh
The map is divided into regions which have line of sight between neighbouring centers.
I have found this brief description on how to do this from a tiled map:
http://www.gamedev.net/community/forums/topic.asp?topic_id=524802
Plus: Regions are very regular. This makes them very accurate for distance checks.
- Doing a flood fill from every tile could be very costly...
So, do you know of other ways? Or have any comments/experience?
[Edited by - comfy chair on January 5, 2011 2:23:13 PM]
Performance of recomputing the graph is important, because I actually have multiple maps, one for each different agent type. I want to recompute the graphs every 10 seconds perhaps.
I am trying to decide between different options for building the graph.
I know of these:
1. Region map. Created via flood fill.
Plus: should be easy to implement.
Plus: not too costly.
- regions can be large and irregular in size, so is most useful for accessibility checks. Not so useful for determining movement distance between points.
2. Sector/region map (AI Game Programming Wisdom 4, p. 203)
It divides the map into quadratic sectors first, then does flood fill to divide these into regions.
Plus: Regions are smaller and so more useful for distance checks.
- Dividing the map into sectors means I have to copy a lot of data from the tile map representation (a multidimensional byte array) into smaller byte arrays before I can perform flood fill.
- The regions can still be irregular, making them less useful for distance checks.
3. Navigation mesh
The map is divided into regions which have line of sight between neighbouring centers.
I have found this brief description on how to do this from a tiled map:
http://www.gamedev.net/community/forums/topic.asp?topic_id=524802
Plus: Regions are very regular. This makes them very accurate for distance checks.
- Doing a flood fill from every tile could be very costly...
So, do you know of other ways? Or have any comments/experience?
[Edited by - comfy chair on January 5, 2011 2:23:13 PM]