(A*) Pathfinding

(A*) Pathfinding

Only for up,down,left,right

Anyways, I'm not sure, I've checked some examples, but, will it be like this?:

Point StartTile;
Point EndTile;
List<Point> CheckedPoints;
List<Point> UncheckedPoints;

So, I will add the StartTile to UncheckedPoints.

I'll cycle through UncheckedPoints, and add the (Up, Down, Left, Right) tiles to UncheckedPoints, if it's not in CheckedPoints. And remove the point I just checked, and add it to CheckedPoints.

I'll do the same until I get to EndTile in UncheckedPoints, then what?

1 What if I can't get to the EndTile, will it cycle on forever? How can I prevent this?

2 If I can't get to the EndTile, is there a way to get the closest tile to the EndTile?

3 How can I get the list of tiles from StartTile to EndTile? Keeping a long list for each cycle will take loads of memory, right?

Solution

1 What if I can't get to the EndTile, will it cycle on forever? How can I prevent this?

No, the algorithm should only run, as long as there are UncheckedPoints. You can abort, once it reachs EndTile, but that is not necessary.

And you must never add a point to UncheckedPoints that is already contained in CheckedPoints

2 If I can't get to the EndTile, is there a way to get the closest tile to the EndTile?

Yes, since you store all visited ppints in CheckedPoints, you can choose the closest point among them.

3 How can I get the list of tiles from StartTile to EndTile? Keeping a long list for each cycle will take loads of memory, right?

You can store for each point, from which point it was visited.

This will double the needed memory, but it will not be "loads of memory", since you already have to store all visited points anyways, to avoid running in loops.

You might want to look at Dijkstra's algorithm on a grid (not on a graph), which is simpler. A* is only an optimization to not explore all the titles in a kind of random order, but to first explore the titles that are closest to the end tile.