Simple pathfinding algorithmn

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

Recommended Posts

I need help in looking for a simple pathfinding algorithmn that moves a sprite from 1 end of a chessboard to a certain square and the chessboard has no obstacles whatsoever.I've thought of using the A* algorithmn,but seems like it takes into account any obstacles which makes it more complicated and slow.So i was wondering is there a simpler algorithmn which i can use?

Share on other sites
You want breadth-first search, my son. It searches the children of the parent, then their children and so on. Very simple.

Share on other sites
If there are actually no obstacles, you don't need intelligent pathfinding at all. If the target is to the northeast, north, or northwest of you, go north. If the target is to the southeast, south, or southwest of you, go south. If the target is to the west, go west. If the target is to the east, go east. Bingo.

Share on other sites
Quote:
 Original post by SneftelIf there are actually no obstacles, you don't need intelligent pathfinding at all. If the target is to the northeast, north, or northwest of you, go north. If the target is to the southeast, south, or southwest of you, go south. If the target is to the west, go west. If the target is to the east, go east. Bingo.

If the target is 30 degrees of you,how do you implement the math to start going 30 degrees towards the target on a 8 X 8 chessboard?

Share on other sites
Quote:
Original post by Moose6912
Quote:
 Original post by SneftelIf there are actually no obstacles, you don't need intelligent pathfinding at all. If the target is to the northeast, north, or northwest of you, go north. If the target is to the southeast, south, or southwest of you, go south. If the target is to the west, go west. If the target is to the east, go east. Bingo.

If the target is 30 degrees of you,how do you implement the math to start going 30 degrees towards the target on a 8 X 8 chessboard?
If you are restricted to moving from square to square, then my algorithm will do that just fine. If you can move any direction you want (including weird diagonals that take you between rather than into squares) then it's even easier; simply point yourself towards the target and go forwards.

In retrospect, I see what the confusion may be. Just to make it clear: this decision process is applied after each one-square move. That is, you decide what direction to move in, move one square in that direction, and then you repeat the process, choosing a (possibly) different direction to move in.

[Edited by - Sneftel on September 12, 2004 11:35:39 PM]

Share on other sites
Can you move diagonally or not, because if you can't, just going up and the right works perfectly fine.

Sneftel beat me to it...

Share on other sites
Yup,the target can only move diagonally.Like how the bishop moves on a chessboard,only diagonally.

Share on other sites
Then you just need to modify the algorithm slightly: if the target is north, northwest, or west, go one space northwest. If it's south, southeast, or east, go one space southeast. If it's northeast, go one space northeast. If it's southwest, go one space southwest. Rinse, repeat.

Share on other sites

while ((TargX!=CurX) AND (TargY!=CurY))
{ // loop steps til current coords are target coords
dx = TargX-CurX;
dy = TargY-CurY;

if (dx>0) NewX=CurX+1;
else if (dx0) NewY=CurY+1;
else if (dy<0) NewY=CurY-1;
}

I used something like this more than 25 years ago for various games .

If you want a cleaner linear stepping pattern look at the basic Bresenham line-draw algorithm (do a web search)....

Share on other sites
Original post by Anonymous Poster

while ((TargX!=CurX) AND (TargY!=CurY))
{ // loop steps til current coords are target coords
dx = TargX-CurX;
dy = TargY-CurY;

if (dx>0) NewX=CurX+1;
else if (dx0) NewY=CurY+1;
else if (dy0) NewX=CurX+1;
else if (dx0) NewY=CurY+1;
else if (dy<0) NewY=CurY-1;
}

• Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 12
• 10
• 9
• 15
• 22