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?

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

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.

Quote: Original post by Sneftel
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.

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?

Quote: Original post by Moose6912

Quote: Original post by Sneftel
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.

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]

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

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

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.

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

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;
}