• Popular Now

• 11
• 9
• 10
• 9
• 11

Archived

This topic is now archived and is closed to further replies.

Pathfinding on a wrappable map

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

Recommended Posts

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

Share on other sites
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:

  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

Share on other sites
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.

Share on other sites
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.

Share on other sites
It is similiar to A* only theres no closed paths list.

Share on other sites
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:

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.