I'm developing a real time, tile-based RTS. This is an example map:
This map consists of 4 regions with 256 tiles each. Blue tiles represent obstacles. Units can move in the standard eight directions. Units are bound to tiles; one tile can hold one unit.
These are some examples of the ideal paths I'm looking for. Typical A* stuff:
My question is: Is a navigation mesh applicable to a tile-based RTS? I've only seen navigation maps used in games where units are free-moving and not bound to a grid of tiles. What would the navigation mesh look like on this particular map? An example image would be excellent.
Answer
Yes, navigation meshes are still applicable to tile based games. Although, they would primarily be used as a optimization. For example, I've converted the lower left of your image to use a navigation mesh:
In this case, each green square would be a navigation node. As you can see, this drastically reduces the number of nodes that A* needs to process. Units can then simply path to the center of each of these nodes.
The generation of these nodes is a different issue. It can be complex deciding how to form the nodes. There's a few questions on the site where you might find some ideas on how you'd like to implement that:
Subdividing a polygon into boxes of varying size
Identifying quad patterns in a two-dimensional array
This navigation mesh can also essentially be used as a "first pass" path finding. If a path is found through the navigation mesh, you know that a path exists. This is a faster test to see if two points are connected.
No comments:
Post a Comment