Archived

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

A* Pathfinding & Tiles

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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
[s] = where u start
[e] = where u end

map :
[ ][ ][ ][ ][ ]
[ ][x][e][x][ ]
[ ][x][x][x][ ]
[ ][ ][x][x][ ]
[s][ ][ ][ ][ ]

i them make that into a array on ints and make walls say 255 and everything else 0 .. oh and i make s 255

[0][0][0][0][0]
[0][x][e][x][0]
[0][x][x][x][0]
[0][0][x][x][0]
[s][0][0][0][0]

then do the following
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..
so loop 1 results in

[0][0][0][0][0]
[0][x][e][x][0]
[0][x][x][x][0]
[1][1][x][x][0]
[s][1][0][0][0]

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 ..

[0][0][0][0][0]
[0][x][e][x][0]
[2][x][x][x][0]
[1][1][x][x][0]
[s][1][2][0][0]

[0][0][0][0][0]
[3][x][e][x][0]
[2][x][x][x][0]
[1][1][x][x][0]
[s][1][2][3][0]

[4][4][0][0][0]
[3][x][e][x][0]
[2][x][x][x][0]
[1][1][x][x][4]
[s][1][2][3][4]

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

sorry for the long example ;-)

good luck
Tim

Share this post


Link to post
Share on other sites
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

Share this post


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

Share this post


Link to post
Share on other sites
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?

Share this post


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

Share this post


Link to post
Share on other sites
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

Share this post


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

1 2 3
4 5 6
7 8 9

You can''t pretend that it looks like this:

1 2 3
4 5 6
7 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.

Share this post


Link to post
Share on other sites
Without trying to put anyone down, Wrathgame's algorithm is just Breadth-First Search (commonly abbreviated to BFS) and is one of the slowest of the pathfinding algorithms. Although it is guaranteed to find a path, if one exists, it doesn't make any use of extra information you provide about the map or the start/end points. This is why the A* algorithm is generally better, as it employs a heuristic (estimation function) to 'guess' which the best direction is. As a comparison using the example given, instead of generating a load of 1s, then searching them all to generate a load of 2s, then 3s and so on, it generates a load of 1s, then picks the best 1 to generate 2s, then picks the best 2 and generates 3s from it, etc. This tends to direct the search towards the target in a far more efficient manner, providing the heuristic is.

BFS is a good solution in a game where the number of nodes won't get too big. Examples are small maps (less than 20x20, I'd say) or maps that are generally tunnels rather than open spaces (Pacman as opposed to Command and Conquer). For other maps, something like A* is preferable, although slightly harder to code.

(PS: The choice of algorithm is actually irrelevant to Abaddon_db's problem. It will still generate 'broken' paths no matter whether you use BFS, DFS, A*, Dijkstra's, or any other pathfinding/node-based algorithm. The problem is that, for any given node, the list of candidate neighbouring nodes generated is wrong. This is because it's being treated like an offset grid, when in fact it needs to be treated more like a rotated grid, which is something Wrathgame did actually point out.)

Edited by - Kylotan on August 10, 2001 10:37:13 PM

Share this post


Link to post
Share on other sites