An easy to implement and low cost (low cost meaning it doesn’t use a lot resources like CPU or memory) path finding algorithm is the BLAH BLAH BLAH. Which will just head towards the target. If the target is up and to the left, it will move up and to the left. This does not give the appearance of being intelligent though in most cases. That is ok though! Common sidekick trick.
A*
One of the most common path finding algorithms that seems to work fast and with a minimal amount of resources is the A* (pronounced A-Star) algorithm. For this algorithm, we will need three values:
· Goal – The goal is the cost to get from the start node to this node. The cost in this definition does not refer to cpu or memory. Instead it is referring to how expensive it is to get to that point. Imagine that you are programming a tile based game where the map has a swamp in the middle. Lets say that each time you walk through a normal tile it will cost you a value of one. If you wish to walk through the swamp, it will cost you a value of two (because it is a swamp and you move a lot slower). You can also add in other types of squares, perhaps hills, and you can make them whatever cost you wish. The goal value is thus adding up the cost of each tile that you traveled on to get to where you are.
· Heuristic – This is our guess as to how much longer it will take to get to our goal. This can be done any way you see fit, but keep in mind that the closer that the heuristic is to the actual value, the better the algorithm will work. Often the Manhattan Distance (The change in the X value plus the change in the Y value) is used for the heuristic.
· Final – Final is our final guess as to how well the current path we are investigating is doing. Final is computed by adding the Goal value together with the Heuristic. Lower values of Final are better because lower values mean we think it is a shorter path.
We also need a few lists to keep track of the paths we are trying:
· Open list – the open list is a list of nodes that we can see but have not tested out yet.
· Closed list – the closed list is a list of nodes that we have tested out.
A node has been tested when we have looked at what the path would be for all the surrounding nodes.