A* is one of the searching algorithms that is very vastly used for path finding when devloping games. Although, different views for it, it is one of the most effecient algorithms. In the next section i will briefly explain some related concepts. We will also have a look at some of its deficiencies and problem areas in the coming articles:
A* is a directed algorithm that us used to find the shortest path to the destination very qickly. It is primarily used for MAP terrains. One of the key points why it boasts of its effeciency is its ability to backtrack to find alternative paths to the destination node.
Having said that: Lets understand some comcepts-
MAP: A map is an area which holds both the origin and the destination to which the path is to be found. It might be made of squares, hexagons, trees etc. This is the boundary within which A* is to operate.
Nodes: These are the data structures that hold the position infiormation. For eg, if we need to go from one point to another on a given MAP, we will have a origin node that will store the position coordinates and other position information of the object and also a destination node that wil store the position information to the point to be reached.
Distance: Distance between Origin and Destination Nodes
Cost: Time taken to reach from Origin node to Destination Node.
Since a Node stores all the position information, it is defined with 2 attributes:
- Goal: This is represented by “g” notation. This is the cost of getting from the Origin node to an Intermediary Node that is identified as one of the nodes in the Path. There is always a single path to this intermediary node as this node is always knows.
- Heuristic: This is expressed by “h” notation and is the cost of getting from the intermediary node to the Destination Node. There can always be more than one paths to get to the destination node. The A* algorithm is primarily used to find the shortest path with the Heuristic value as low as possible.
- Fitness: This is expressed by “f” notation as follows:
(f) = (g)+(h)
The lower the value of “f” the efficient and short the path is.
A* maintains 2 lists to store nodes:
Open List: This data structure consists of all the node that have not yet been explored by the algorithm.
Closed Lists: This data structure consists of the explored nodes.
Explored Nodes: These are the nodes for which the algorithm has calculated the f,g,h values for every node connected to this node.
Why maintaining these lists is important?
Since now we know that A* can backtrack to any node to find an alternative path, so ti is important to keep track of the nodes that have already been explored.
More to come in next article..
A* Efficiency Calculation
Problem Areas
