# VBForums UtilityBank > UtilityBank - Tutorials >  A* Algorithm

## dday9

*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:


```
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:


```
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:


```
F = G + H
```

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.

 :Alien Frog:  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:


```
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:


```
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:


```
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:


```
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:


```
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

----------

