🔒 Locked

path finding question - refrasing

Started by cyberia_2ooo Jan 29, 2003 at 8:03 AM 13 replies 600+ views

Original Post

Jan 29, 2003 at 8:03 AM

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

cyberia_2ooo

Author

cyberia_2ooo

Jan 29, 2003 at 8:27 AM

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

FxMazter

Jan 29, 2003 at 1:54 PM

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~

cyberia_2ooo

Author

cyberia_2ooo

Jan 30, 2003 at 7:00 AM

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

Paradigm Shifter

145

Paradigm Shifter

Jan 30, 2003 at 7:14 AM

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.

cyberia_2ooo

Author

cyberia_2ooo

Jan 30, 2003 at 7:31 AM

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

Paradigm Shifter

145

Paradigm Shifter

Jan 30, 2003 at 7:43 AM

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

cyberia_2ooo

Author

cyberia_2ooo

Jan 30, 2003 at 2:47 PM

have no problem with trig, my problem is finding the turning points, i have no idea how to that...

Thunder_Hawk

Jan 30, 2003 at 3:31 PM

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 -- ¦þ
______________________________

Thunder_Hawk

Jan 30, 2003 at 3:54 PM

How many directions have you got?

Thunder_Hawk

Jan 30, 2003 at 4:13 PM

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 -- ¦þ
______________________________

Thunder_Hawk

Jan 30, 2003 at 5:26 PM

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

cyberia_2ooo

Author

cyberia_2ooo

Jan 31, 2003 at 6:00 AM

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

cyberia_2ooo

Author

cyberia_2ooo

Jan 31, 2003 at 6:43 AM

Thunder_Hawk

Feb 1, 2003 at 5:02 PM

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 -- ¦þ
______________________________

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.