A* Pathfinding & Tiles
Author
Hi
I've been implementing the A* algothrim to my game, which is an Isometric Tile based RGP and I run into a problem. The pathfinding thinks that the map is based on squares which are tiled like in this picture :
www.icenet.fi/~tinot84/Kuva1.jpg
But because the map is tiled like this :
www.icenet.fi/~tinot84/kuva2.jpg
the pathfinding doesn't work. Is there any solution to this? I think I must move the path position back or front in every second line, but it also leaves empty spaces between pathes.
I'm using the A* algothrim staright from TANSTAAFLS book.
Thanks!
Edited by - Abaddon_db on August 3, 2001 7:03:51 PM
Edited by - Abaddon_db on August 3, 2001 7:05:48 PM
I haven''t seen the code you refer to, but I''m sure the method is pretty generic. There should be a function which checks the surrounding 8 tiles, and uses something like :
for (x = -1; x < 2; x++)
for (y = -1; y < 2; y++)
{
if (x == 0 && y == 0) continue;
// Otherwise add nodes to the list
}
(Yours might be unrolled). Isometric tiles aren''t quite this easy, your offsets will be different.
Understand?
"NPCs will be inherited from the basic Entity class. They will be fully independent, and carry out their own lives oblivious to the world around them ... that is, until you set them on fire ..." -- Merrick
"It is far easier for a camel to pass through the eye of a needle if it first passes through a blender" -- Damocles
for (x = -1; x < 2; x++)
for (y = -1; y < 2; y++)
{
if (x == 0 && y == 0) continue;
// Otherwise add nodes to the list
}
(Yours might be unrolled). Isometric tiles aren''t quite this easy, your offsets will be different.
Understand?
"It is far easier for a camel to pass through the eye of a needle if it first passes through a blender" -- Damocles
Hi,
in my game i use the following technique :
Note : your game is basically a grid but rotated 45*
[ ] = an empty block
[x] = a wall or something
= where u start<br>[e] = where u end<br><br>map :<br>[ ][ ][ ][ ][ ]<br>[ ][x][e][x][ ]<br>[ ][x][x][x][ ]<br>[ ][ ][x][x][ ]<br>[ ][ ][ ][ ]<br><br>i them make that into a array on ints and make walls say 255 and everything else 0 .. oh and i make s 255<br><br>[0][0][0][0][0]<br>[0][x][e][x][0]<br>[0][x][x][x][0]<br>[0][0][x][x][0]<br>[0][0][0][0]<br><br>then do the following<br>search surrounding 8 blocks to see if they are 0 (ie not been looked at) if they are 0 add to a list and set them to the number of positions from the start..<br>so loop 1 results in<br><br>[0][0][0][0][0]<br>[0][x][e][x][0]<br>[0][x][x][x][0]<br>[1][1][x][x][0]<br>[1][0][0][0]<br><br>and then for each of the items in the list i do the same .. adding their results to a temp new list and when they are all done do again on that new temp list and so on ..<br><br>[0][0][0][0][0]<br>[0][x][e][x][0]<br>[2][x][x][x][0]<br>[1][1][x][x][0]<br>[1][2][0][0]<br><br>[0][0][0][0][0]<br>[3][x][e][x][0]<br>[2][x][x][x][0]<br>[1][1][x][x][0]<br>[1][2][3][0]<br><br>[4][4][0][0][0]<br>[3][x][e][x][0]<br>[2][x][x][x][0]<br>[1][1][x][x][4]<br>[1][2][3][4]<br><br>at which point we get to e on the 5th attempt.. i then trace back from e the ajoining 4, then 3..2..1.. to find the path :-) works a treat<br><br>sorry for the long example ;-)<br><br>good luck<br>Tim
in my game i use the following technique :
Note : your game is basically a grid but rotated 45*
[ ] = an empty block
[x] = a wall or something
= where u start<br>[e] = where u end<br><br>map :<br>[ ][ ][ ][ ][ ]<br>[ ][x][e][x][ ]<br>[ ][x][x][x][ ]<br>[ ][ ][x][x][ ]<br>[ ][ ][ ][ ]<br><br>i them make that into a array on ints and make walls say 255 and everything else 0 .. oh and i make s 255<br><br>[0][0][0][0][0]<br>[0][x][e][x][0]<br>[0][x][x][x][0]<br>[0][0][x][x][0]<br>[0][0][0][0]<br><br>then do the following<br>search surrounding 8 blocks to see if they are 0 (ie not been looked at) if they are 0 add to a list and set them to the number of positions from the start..<br>so loop 1 results in<br><br>[0][0][0][0][0]<br>[0][x][e][x][0]<br>[0][x][x][x][0]<br>[1][1][x][x][0]<br>[1][0][0][0]<br><br>and then for each of the items in the list i do the same .. adding their results to a temp new list and when they are all done do again on that new temp list and so on ..<br><br>[0][0][0][0][0]<br>[0][x][e][x][0]<br>[2][x][x][x][0]<br>[1][1][x][x][0]<br>[1][2][0][0]<br><br>[0][0][0][0][0]<br>[3][x][e][x][0]<br>[2][x][x][x][0]<br>[1][1][x][x][0]<br>[1][2][3][0]<br><br>[4][4][0][0][0]<br>[3][x][e][x][0]<br>[2][x][x][x][0]<br>[1][1][x][x][4]<br>[1][2][3][4]<br><br>at which point we get to e on the 5th attempt.. i then trace back from e the ajoining 4, then 3..2..1.. to find the path :-) works a treat<br><br>sorry for the long example ;-)<br><br>good luck<br>Tim
Author
My program is just like that. But the problem is when the the tiles are moved to proper postions to make it seem like one big bitmap (I mean when every second line is moved half a tile left, see the difference between the pictures : kuva1,kuva2) the pathfinding doesn''t work.
When the A* calculates the map it thinks that the map looks like in picture kuva1. And when the code moves the tiles to their proper positions the path is broken and there are holes inside the path.
And also when I put some walls to the map between the path it doesn''t care because they are positioned different, like you see in kuva1,kuva2 .
I thought I wouldn''t care about the holes in the path (who cares if you skip one tile on your path), But it mustn''t skip the walls...
I hope you can help, cause my project has been hanging on this problem for a long time now...
Abaddon
When the A* calculates the map it thinks that the map looks like in picture kuva1. And when the code moves the tiles to their proper positions the path is broken and there are holes inside the path.
And also when I put some walls to the map between the path it doesn''t care because they are positioned different, like you see in kuva1,kuva2 .
I thought I wouldn''t care about the holes in the path (who cares if you skip one tile on your path), But it mustn''t skip the walls...
I hope you can help, cause my project has been hanging on this problem for a long time now...
Abaddon
You don''t need to virtually move any lines to make the pathfinding work. As you''ve pointed out, that can cause trouble rather than fix it. Perhaps the complication comes in how your tiles are references/numbered. Even so, there should be a well-defined formula for finding the neighboring nodes for any given tile, without you needing to ''pretend'' that the map is any other shape. A* doesn''t need your map to be any particular shape, or even tiled. I can''t tell you what the formula is, because I don''t know how you number your tiles. The only other awkward point could be the heuristic, but you''re implying that your heuristic is fine.
Author
I have an array named iTiles[x][y] where the tiles are stored with numbers (example Wall=1,Grass=0 etc) and I use the A* like Wrathgame showed. Is this enough information for you?
How do the numbers in your array correspond to the grid? If you are making paths that has ''holes'' in it, then you are obviously choosing the wrong neighboring nodes each time you come to generate them.
Author
I dont really understand what you mean by that question but if I have a grass tile in the upper left corner, the array looks like this :
iTiles[0][0]=0;
The A* doesn't make 'holes', but they appear when I draw the tiles so that every other line is moved left half tile. So if I have a straight path between Start and End, it will get holes when every other path marker moves left halftile. like this :
1. before drawing and how A* thinks it looks like :
SXXX
XPXX
XXPX
XXXE
2. After drawing and moving tiles :
SXXX
_XPXX
XXPX
_XXXE
(the mark _ means empty... It didnt't make a empty char to that place if I dont use that in there.)
You see? theres a hole between the Start and the first path marker. It would be allright if the path marker in the second line wouldn't move, but it has to move in order the map be drawn properly like isometric tiles should.
I think this is going way out of this galaxy...
Abaddon
Edited by - Abaddon_db on August 8, 2001 12:17:23 PM
iTiles[0][0]=0;
The A* doesn't make 'holes', but they appear when I draw the tiles so that every other line is moved left half tile. So if I have a straight path between Start and End, it will get holes when every other path marker moves left halftile. like this :
1. before drawing and how A* thinks it looks like :
SXXX
XPXX
XXPX
XXXE
2. After drawing and moving tiles :
SXXX
_XPXX
XXPX
_XXXE
(the mark _ means empty... It didnt't make a empty char to that place if I dont use that in there.)
You see? theres a hole between the Start and the first path marker. It would be allright if the path marker in the second line wouldn't move, but it has to move in order the map be drawn properly like isometric tiles should.
I think this is going way out of this galaxy...
Abaddon
Edited by - Abaddon_db on August 8, 2001 12:17:23 PM
It''s your A* that''s messed up. The A* algorithm has to work with the map in the way that it actually is, not in some distorted shape that makes it easier to think about. If your map looks like this:
You can''t pretend that it looks like this:
for the purposes of A* and then shift it back again when it comes to drawing. Because, in this case, A* could make a route that goes from 1 to 5 and then to 9, which are disjointed:
Which is I think what your problem is.
You need a slightly different system for generating the neighbor nodes on a diamond-shaped tile map compared to the one you need for a square-shaped tile map. For instance, in the example above, for square 5, you consider 2, 6, 7, and 8 for continuing paths, but not 1 and 9. (There may also be another couple of nodes you consider that don''t quite show on my 3x3 representation). Try drawing a small 10x10 diamond-tiled map on paper in the way you''d view it on screen, labelling each one with its coordinates (your array indices). Then from that, you should be able to work out the formulas for deciding which nodes are adjacent to a given node. (Right now, you seem to be using something similar to Merrick''s method, which is totally correct for square maps, but not for diamond ones.) Perhaps someone else can come and post the exact formulas you need, but it''s better if you do this yourself and work it out, because then you''ll understand why you cannot treat a diamond map like a square one.
1 2 3 4 5 6 7 8 9 You can''t pretend that it looks like this:
1 2 34 5 67 8 9 for the purposes of A* and then shift it back again when it comes to drawing. Because, in this case, A* could make a route that goes from 1 to 5 and then to 9, which are disjointed:
* 2 3 4 * 6 7 8 * Which is I think what your problem is.
You need a slightly different system for generating the neighbor nodes on a diamond-shaped tile map compared to the one you need for a square-shaped tile map. For instance, in the example above, for square 5, you consider 2, 6, 7, and 8 for continuing paths, but not 1 and 9. (There may also be another couple of nodes you consider that don''t quite show on my 3x3 representation). Try drawing a small 10x10 diamond-tiled map on paper in the way you''d view it on screen, labelling each one with its coordinates (your array indices). Then from that, you should be able to work out the formulas for deciding which nodes are adjacent to a given node. (Right now, you seem to be using something similar to Merrick''s method, which is totally correct for square maps, but not for diamond ones.) Perhaps someone else can come and post the exact formulas you need, but it''s better if you do this yourself and work it out, because then you''ll understand why you cannot treat a diamond map like a square one.
Wrathgame, that algo is great. I''ll have to test it out sometime. Maybe you should write an article on that, it would be a great help to the GameDev community.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement