#### Archived

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

# path finding question - refrasing

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

## Recommended Posts

well... as i guessed the discription of my problem was too vauge (damn, i hope this is the right spelling of the word) anyway, i''ll try to refrase... i have square grid (just to be sure u understand me, i mean not a hexagonal one and not an isometric one... a simple grid) which represend a map.... no i have a path on this map... a path is a list of adjacent coordinets on the grid. not i have a certein unit that needs to follow the path... i want the unit, at any time to face the point it is going... how do i do it???? p.s. if you have any ideas for me about group movment that can be good for implimatation for strategy games, please tell me... but that''s not really important right now... it''s for later

##### Share on other sites
by the way, by my understanfing boids will do the work i want, but is it a good solution for RTS game?

##### Share on other sites
Hey... take a look at the A-star algorithm and apply it to your game

Anyway... if you want to make a simplier version do like this:

From the point of your character expand paths like a circle. First expand to each direction and check if its possible to walk on that tile, if not tha kill that path and don''t use it anymore.
When you checked each direction, you expand one more tile and check if that one is walkable, if not... then once again kill that path. Do this until you reach the position you want your object to walk to. And of course choose tha fastest way to get there. This is not a VERY good way of solving your problem, but it works... and it works better the less times you expand... since this could eat your memory if you do this too many times.

Well and as for the problem where your object face... its quite simple. Just check what the next tile of the chosen path is in.

Oh well, just want to say that I actually never tried this method but to mee it seems that it should work OK.

GL, hope this helps~

##### Share on other sites
i have a path....
i now want the unit to walk down that path...
i don''t know hot to make it face the direction it is going...

##### Share on other sites
Do you want it to face towards the final destination at all points along the path? You will need to do some trigonometry (sin, cos). Do you want it to face the direction it is about to move towards? You need to change the image depending upon the direction it is moving, i.e. map x,y velocity values to an orientation of the sprite; read up on vectors.

##### Share on other sites
checking the next tile is not a good solution...
because:
a. if lets the path is no a perfect diagnol and not a straghit line... it would be funny looking...
b. i have more thatn 8 direction pics... i want to use them all to make a more realistic rotating

##### Share on other sites
So trigonometry it is then. You will also need to work out the "turning points" on the board (which isn''t going to be trivial) and orient yourself, using the angles you get back from the trig, towards each turning point. Using splines is another possibility.

I''d take a look at a few path-finding articles, there are some in the articles section of this site.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

##### Share on other sites
have no problem with trig, my problem is finding the turning points, i have no idea how to that...

##### Share on other sites
It just occured to me that this problem is similar in some ways to drawing a line between two points. Try googling for "Bresenham Line Algorithm" or "fast line algorithm" and see if anything inspires you.

______________________________

And the Phoenix shall rise from the ashes...

--Thunder_Hawk -- ¦þ
______________________________

##### Share on other sites
How many directions have you got?

##### Share on other sites
Here''s my idea...First once you have a path, divide it up into "checkpoints" and deal with each one separately. I''ll define a checkpoint as a point you can get to by going in a straight line without running into any obstructions. Next, determine at each tile, which direction (of the directions you have available) will lead you closest to your next checkpoint (i.e. project a ray in each direction from the current tile and see which one passes closest to the next checkpoint). You can do this all at once or reevaluate it each tile. I think that makes sense....hope it helps.

______________________________

And the Phoenix shall rise from the ashes...

--Thunder_Hawk -- ¦þ
______________________________

##### Share on other sites
Does that make any sense? I only ask because it seems, to me, to be a perfectly viable solution to your problem.

##### Share on other sites
actually, it does...
after i divde it to checkpoints (as you defined them) i have no problem choosing the direction image, i find the angle and divide it by 18 (i have 20 directions and 360/20=18) and the number i got is the index of the direction when 0 is facing right)

now what i am not sure is about how to devide to the checkpoints...

##### Share on other sites
actually, it does...
after i divde it to checkpoints (as you defined them) i have no problem choosing the direction image, i find the angle and divide it by 18 (i have 20 directions and 360/20=18) and the number i got is the index of the direction when 0 is facing right)

now what i am not sure is about how to devide to the checkpoints...

##### Share on other sites
If I''ve got your system right, it looks like the path you''ve determined only has right angle turns to go with your grid....

A quick (probably not the best) way to divide your path into checkpoints is to simply loop through using you current position and the next tile in line on your path and check if all tiles between them are ok to walk on. Pseudocode:

  TileCoords FindNextCheckpoint (TileCoords curPos, const TileCoords* path, int pathLength) {    bool done = false;    int index = 0;    do {        for (int i = curPos.y; i < path[index].y; i++) {            for (int j = curPos.x; j < path[index].x; j++) {                if (!IsTileWalkable(j, i)) done = true;            }        }        index++;    } while (!done && index < pathLength);    return path[index - 1];}

This isn''t the best because you obviously won''t walk on all of the tiles, just down the middle, but it really isn''t too bad to subdivide too much.

Hope that makes sense

______________________________

And the Phoenix shall rise from the ashes...

--Thunder_Hawk -- ¦þ
______________________________