Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Sam Hocevar May 19 '12 at 12:21
3  
@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 May 19 '12 at 12:51

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
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 –  Tanner May 19 '12 at 15:46
    
Fixed the links. It's queued for peer review now, should be up soon. –  William 'MindWorX' Mariager May 19 '12 at 16:47

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.