Pathfinding on a wrappable map
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
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement