Pathfinding on a wrappable map
Author
I'm in the process of writing a civ-like strategy game and am wondering how to implement the pathfinding routine for units that cross-over the 'international dateline' on a map that wraps around from east to west. My first instinct is to use a second map something like:
..........
........
........
........
......
........
........
..........
becomes:
..........
........
........
........
......
........
........
..........
and then re-map the results onto the first using an offset.
Has anyone ever encountered this problem or tackled it a different way ?
Edited by - Decker on June 24, 2001 5:43:58 PM
Actually, it's quite easy, it just requires a quick change in your map accessing functions. Basically, you index the map like you normally would, but if the x is greater than the maximum extent you wrap it over. So, for example, a function like so:
Edited by - The Senshi on June 24, 2001 6:14:35 PM
int GetTile(int x, int y){ return Map[x][y];} Would become: int GetTile(int x, int y){ while( x < 0) x += Width; while( y < 0) y += Height; while( x > Width) x -= Width; while( y > Height) y -= Height; return Map[x][y];} Edited by - The Senshi on June 24, 2001 6:14:35 PM
Author
Sorry the ASCII art sucked.Thx for the reply - though this works fine for displaying/updating the map it won''t work for pathfinding as the goto routine doesn''t understand the wrapping concept, hence my lame attemp at chopping the map in two and re-arranging it - i can''t see any other way of implementing it.
Perhaps you could tell us how your current pathfinding works? If it''s a traditional graph theory type thing (A*, Dijkstra, breadth-first, etc), then it''s a trivial modification. If it''s some sort of ''direct-route'' system, then it''s gonna be a bit more complicated.
Then it''s trivial.
There is a part of the algorithm where you come to generate a set of ''neighbouring'' nodes that are adjacent to the one you are currently examining. Those nodes then get shoved on the Open list. The code might look something like:
All you change is how it decides where these new codes come from. In the above example, it uses a square map, and it picks the 8 adjacent locations. However, if you''re at the edge of the map, you need a special case. So it becomes something like:
All you do, is add basic checking when it comes to generating your neigbouring nodes.
There is a part of the algorithm where you come to generate a set of ''neighbouring'' nodes that are adjacent to the one you are currently examining. Those nodes then get shoved on the Open list. The code might look something like:
addNodeToOpen(x-1, y-1); // node to the NWaddNodeToOpen(x, y-1); // node to the NaddNodeToOpen(x+1, y-1); // node to the NEaddNodeToOpen(x-1, y); // node to the WaddNodeToOpen(x+1, y); // node to the E... etc... All you change is how it decides where these new codes come from. In the above example, it uses a square map, and it picks the 8 adjacent locations. However, if you''re at the edge of the map, you need a special case. So it becomes something like:
if (x > 0) addNode(x-1, y-1); // node to the NWelse addNode(MAP_WIDTH, y-1); // node 1 north on the east sideaddNode(x, y-1); // node to the Nif (x < MAP_WIDTH) addNode(x+1, y-1); // node to the NEelse addNode(1, y-1); // the node 1 north on the west side...etc... All you do, is add basic checking when it comes to generating your neigbouring nodes.
Author
Thanks , i never thought of that believe it or not - programming can stifle the imagination sometimes 
I''ll give it a try
I''ll give it a try
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement