Hello, this is my doubt: I have a screen of a RPG, the char is located in a grid x*y squares where the values are 0=empty, tha char can pass trough here; 1 = can`t pass. Every square represents a portion of the screen where the character can walk. So, my problem is that I'm trying to make the char to walk from one point to another choosing the shortest path, like in Age of Empires where you select a char and click where you want it to go, but with my screen and paths system. So, how could I do it?, because I have not the minimun idea! Thank very much!

google for A*, or Dijkstra Algorithm.. maybe that will help you.

I would recommend A* since that is the best path finding algorithm out there. Dijkstra's Algorithm is slower and only good for pre-calculating the shortest path from all nodes in the grid.

A* on Wiki:

http://en.wikipedia.org/wiki/A_star

Quote: Original post by Eldritch
I would recommend A* since that is the best path finding algorithm out there. Dijkstra's Algorithm is slower and only good for pre-calculating the shortest path from all nodes in the grid.

It depends. A* is really just a modification of Dijkstra's shortest path algorithm. If you need to solve some pretty straightforward paths between two nodes (like following road that only curves a bit, or avoiding a few obstacles), A* is much more efficient. If you've got something more like a maze, where you may have to go off in the opposite direction before finding your way to the destination, Dijkstra is just as good if not better.

if your x,y grid is small enough and static, you can use disjktra when you save the map to compute all possible shortest paths and store them in a matrix the same size as your map, where each x,y entry indicates the next node you need to step to go from your position x to a desired position y.

Have fun!

Thank you all! I will search about these algorithms in google and at the wikipedia (thanks Eldritch!).
If I have more news I will notice you.
Sincerely