# Tile walking algorithm for already known set of walkable tile?

Suppose I already have a list of tile that specify which tile the character can move to, and these tiles are clustered around the character. If I want to produce a path (maybe not shortest, but just a short path) to the desired tile, how would I construct it with the given list of tiles? I was going to do an A* algorithm, however, thinking again, it will complicate my coding process. Therefore, is there a better way to find short path for known list of movable tile?

• Well you are precisely asking for A*. Given a set of connected tiles, A* produces a path, maybe not the shortest, but a short path. Commented May 19, 2012 at 12:21
• @SamHocevar if your heuristic is good enough (and you have to work hard for a bad heuristic) it is guaranteed to find the shortest.
– kaoD
Commented May 19, 2012 at 12:51

What you are looking for is in the domain of Graph Theory.

Firstly, I would make sure you have a solid understanding of how the depth-first search and breadth-first search work. Knowing how these algorithms, which means being able to work through a graph by hand. I came upon this page, which seemed to fit the bill for learning how the searches work.

From there it is time to move on to Dijkstra's algorithm, which improves on the earlier searches.

Once you have a thorough grasp of Dijkstra's algorithm, you will want to learn what a heuristic is. On that Wikipedia page only the first paragraph is necessary to read, the rest is a bonus.

As an aside: Alpha-beta pruning is mentioned on the heuristic page. AB pruning is an extension on the minimax algorithm. Both of these are a natural move forwards from searches, and the more basic graph theory, starting with minimax (mostly this)

From the basic heuristic, you will want to learn about admissible heuristics. This is the crucial concept, which, when applied to Dijkstra's algorithm, gives us your final answer: the A* search algorithm.

The A* algorithm is quite simple once you have the knowledge background.

• If a mod wants to clean this up that would be fantastic. The anti-spam prevention measures prevented me from posting the links as hyperlinks. You would think if you had the required reputation on another section of stack exchange it be ok to post hyperlinks Commented May 19, 2012 at 15:46
• Fixed the links. It's queued for peer review now, should be up soon. Commented May 19, 2012 at 16:47

Amit's A* : http://theory.stanford.edu/~amitp/GameProgramming/ , a great illustrated intro.