-
A* Algorithm
Description
The A* algorithm, pronounced “a star”, is an advanced path finding algorithm that uses heuristics to try and determine the most optimal path between two locations. Because of the performance and accuracy of the A* algorithm, it is most often used in computer science.
Broad Explanation
The A* algorithm works by adding a location to a collection based on if the location has the lowest cost of adding both actual cost of moving from the starting point to the given location and the estimated cost of moving from the given location to the final destination.
Steps
There will be two collections that will be used throughout the A* algorithm. One collection represents all “open” locations while the other represents all “closed” locations. There will also be a numeric value used throughout the A* algorithm that represents the “F” cost.
- Add the starting location to the "open" collection.
- Repeat until either:
- The final destination is added to the "closed" collection.
- The "open" collection is empty.
- During the repetition:
- Get the location with the lowest F cost from the "open" collection.
- Remove the location from the "opened" collection and add it to the "closed" collection.
- Add all surrounding location to the "open" collection if:
- The surrounding location is not on the "closed" collection.
- The surrounding location is not a "blocked" location.
- Make the location found in step 3a the "parent" of all the surrounding nodes. If the surrounding location was already added to the "open" collection, then only change the "parent" if the location found in step 3a has a better score.
Detailed Steps
Initial Setup
The initial setup for the A* Algorithm is to declare 2 collections for the “open” and “closed” collections. The “open” collection is declared as a KeyValue collection where the Key represents the added location and the Value represents the “parent” location. The “closed” collection is declared as a dynamically sized collection to hold the final representation of the path.
The following is a Visual Basic .NET representation of the initial setup:
Code:
Dim opened As New Dictionary(Of Point, Point) From {{startLocation, Nothing}}
Dim closed As New List(Of Point)
Iterating Through Locations
The next step of repetition is to use a Do/Until loop to iterate until either the final destination is added to the “closed” collection or “open” collection is empty. If the former condition is met then this means that there was a successful path was found, whereas if the latter condition is met then this means that there was not a successful path found.
The following is a Visual Basic .NET representation of setting up the Do/Until loop:
Code:
Do Until closed.IndexOf(endLocation) <> -1 OrElse opened.Count = 0
Loop
Inside the Iteration
Calculating the F Cost
The first step in iteration is to get the location from the “open” collection with the lowest F cost. The following equation determines the F cost for a given location:
Where:
- G = Actual cost of moving from the starting point to the given location.
- H = Estimated cost of moving from the given location to the final destination.
To calculate the G cost, simply assign a cost of 10 to each horizontal and vertical movement and a cost of 14.14 to each diagonal movement from the starting point to the given location.
:afrog: TIP: It is easier and still accurate enough to round the diagonal cost of 14.14 down to the nearest whole number of 14. While for smaller grids the increase in performance is minimal, when there are larger grids the increase in performance is noticeably faster.
The following is a Visual Basic .NET representation of creating a Function to calculate the G cost:
Code:
Private Function CalculateG(ByVal startLocation As Point, ByVal currentLocation As Point) As Integer
Dim g As Integer = 0
Dim offsetX, offsetY As Integer
Do Until currentLocation = startLocation
offsetX = 0
offsetY = 0
If currentLocation.X <> startLocation.X AndAlso currentLocation.Y <> startLocation.Y
g += 14
offsetX = If(currentLocation.X < startLocation.X, 1, -1)
offsetY = If(currentLocation.X < startLocation.X, 1, -1)
ElseIf currentLocation.X <> startLocation.X Then
g += 10
offsetX = If(currentLocation.X < startLocation.X, 1, -1)
Else
g += 10
offsetY = If(currentLocation.X < startLocation.X, 1, -1)
End If
currentLocation.Offset(offsetX, offsetY)
Loop
Return g
End Function
To calculate the H cost, take the number of movements from the current location to the final destination and multiply it by 10.
The following is a Visual Basic .NET representation of creating a Function to calculate the H cost:
Code:
Private Function CalculateH(ByVal endLocation As Point, ByVal currentLocation As Point) As Integer
Return (Math.Abs(endLocation.X - currentLocation.X) + Math.Abs(endLocation.Y - currentLocation.Y)) * 10
End Function
With the CalculateG and CalculateH Functions, we are now able to calculate the F cost by simply adding the two together.
Getting the F Cost
To get the location from the “open” collection with the lowest F cost, query the “open” collection to retrieve the location with the lowest F cost. If the programming language supports inline functions or some variant, sort the “open” collection by the lowest F cost and get the first location from the collection. If the programming language does not support inline functions, then iterated through the “open” collection and assign a variable equal to the current location if the location that was iterated on just prior has a lower F score.
The following is a Visual Basic .NET representation of using LINQ to query the collection:
Code:
lowestScore = opened.Keys.OrderBy(Function(p) CalculateG(startLocation, p) + CalculateH(endLocation, p)).First()
The following is a Visual Basic .NET representation of iterating through the collection:
Code:
Dim ptLowestScore As Point = opened.Keys.First()
Dim intLowestScore As Integer = CalculateG(startLocation, ptLowestScore) + CalculateH(endLocation, ptLowestScore)
Dim currentScore As Integer
For Each key As Point In opened.Keys
currentScore = CalculateG(startLocation, ptLowestScore) + CalculateH(endLocation, ptLowestScore)
If currentScore < intLowestScore Then
ptLowestScore = key
intLowestScore = currentScore
End If
Next
Optionally Changing the Parent of Surrounding Locations
One of the conditions in step 3d is if the surrounding location is already in the “open” collection to change the parent if the new parent would have a better score, using the G cost as the measurement of score.
The following is a Visual Basic .NET representation of add all of the valid surrounding locations and optionally changing the parent location if the surrounding nodes is already in the “open” collection and the new parent would have a lower G score:
Code:
For x As integer = lowestScore.X - 1 To lowestScore.X + 1
For y As Integer = lowestScore.Y - 1 To lowestScore.Y + 1
If x > 0 AndAlso x < grid.GetUpperBound(0) AndAlso y > 0 AndAlso y < grid.GetUpperBound(1) AndAlso grid(x, y) <> New Point(-1, -1) AndAlso Not closed.Contains(grid(x, y)) Then
Dim surroundingLocation As Point = grid(x, y)
If opened.ContainsKey(surroundingLocation) Then
If CalculateG(startLocation, lowestScore) < CalculateG(startLocation, opened.Item(surroundingLocation)) Then
opened.Item(surroundingLocation) = lowestScore
End If
Else
opened.Add(surroundingLocation, lowestScore)
End If
End If
Next
Next
:duck: NOTE: In this code example, I use the point with X equaling -1 and Y equaling -1 to signify that it is a “blocked” node.
Final Implementation
The following link is to the Visual Basic .NET codebank that contains a functional A* algorithm: http://www.vbforums.com/showthread.p...5-A*-Algorithm
