Archived

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

Decker

Pathfinding on a wrappable map

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 NW
addNodeToOpen(x, y-1); // node to the N
addNodeToOpen(x+1, y-1); // node to the NE
addNodeToOpen(x-1, y); // node to the W
addNodeToOpen(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 NW
else
addNode(MAP_WIDTH, y-1); // node 1 north on the east side

addNode(x, y-1); // node to the N

if (x < MAP_WIDTH)
addNode(x+1, y-1); // node to the NE
else
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.

Share this post


Link to post
Share on other sites
Thanks , i never thought of that believe it or not - programming can stifle the imagination sometimes I''ll give it a try

Share this post


Link to post
Share on other sites