A* (A Star) Pathfinding help
A* (A Star) Pathfinding help
A* (A Star) Pathfinding help
A* (A Star) Pathfinding help
A* (A Star) Pathfinding help
A* (A Star) Pathfinding help A* (A Star) Pathfinding help A* (A Star) Pathfinding help A* (A Star) Pathfinding help A* (A Star) Pathfinding help A* (A Star) Pathfinding help A* (A Star) Pathfinding help A* (A Star) Pathfinding help
A* (A Star) Pathfinding help A* (A Star) Pathfinding help
A* (A Star) Pathfinding help
Go Back  Xtreme Visual Basic Talk > > > A* (A Star) Pathfinding help


Reply
 
Thread Tools Display Modes
  #1  
Old 03-14-2012, 07:40 PM
Waxara Waxara is offline
Newcomer
 
Join Date: Mar 2012
Posts: 2
Default A* (A Star) Pathfinding help


Greetings. I am having some issues with writing an A* path-finding routine for a grid based game. The game allows for movement to any of the 8 squares surrounding the currently occupied one.

The A* routine is supposed to pick-out the shortest (or one of the shortest) paths possible from point A to point B on the grid while avoiding obstacles that can't be moved upon such as lakes and mountains.

The code works great if the 2 points are right next to eachother, but the second that there is 1 or more squares between them the code just endlessly loops in its search adding new squares to search. Below I have attached the code I have written so far. If you have any questions please let me know.


The Map itself is stored as 1's and 0's in an array (4999 by 4999) 1 representing unable to be walked on, 0 walkable.

Code:
Module AStarAlgorithms
    Public Structure Node
        Dim XCoord As Integer
        Dim YCoord As Integer
        Dim Cost As Integer
        Dim XParent As Integer
        Dim YParent As Integer
        Dim FValue As Integer

        ' Dim State As String
    End Structure

    Const StraightCost As Integer = 10
    Const DiagCost As Integer = 14
    Public ClosedList As New ArrayList
    Public OpenList As New ArrayList

    Public GoalReached As Boolean = False
    Public GoalNode As Node
    Public PathToFollow As New ArrayList


    Public Sub PathSearch(ByRef XStartCoord As Integer, ByRef YStartCoord As Integer, ByRef XGoalCoord As Integer, ByRef YGoalCoord As Integer)
        Dim CurrentNode As New Node
        Dim WasClosed As Boolean = False
        Dim XHerDistance As Integer
        Dim YHerDistance As Integer
        Dim Heuristic As Integer
        Dim IsClosed As Boolean = False

        GoalNode.XCoord = XGoalCoord
        GoalNode.YCoord = YGoalCoord
        ClosedList.Clear()
        OpenList.Clear()

        CurrentNode.XCoord = XStartCoord
        CurrentNode.YCoord = YStartCoord
        CurrentNode.Cost = 0

        XHerDistance = Math.Abs(CurrentNode.XCoord - XGoalCoord)
        YHerDistance = Math.Abs(CurrentNode.YCoord - YGoalCoord)
        If XHerDistance > YHerDistance Then
            Heuristic = DiagCost * YHerDistance + StraightCost * (XHerDistance - YHerDistance)
        Else
            Heuristic = DiagCost * XHerDistance + StraightCost * (YHerDistance - XHerDistance)
        End If
        CurrentNode.FValue = Heuristic

        OpenList.Add(CurrentNode)


        Do While OpenList.Count > 0
            'set current node to something random and high for comparison
            CurrentNode.XCoord = 99
            CurrentNode.YCoord = 99
            CurrentNode.Cost = 99999
            CurrentNode.FValue = 999999999
            'Select the node on the openlist with the lowest F Value
            For Each TempNode As Node In OpenList
                If TempNode.FValue < CurrentNode.FValue Then CurrentNode = TempNode
            Next
            'Move Current Node from open list to closed list
            ClosedList.Add(CurrentNode)
            OpenList.Remove(CurrentNode)
            If GoalReached = True Then Exit Do
            'Test East 
            Testing(CurrentNode, 1, 0, XGoalCoord, YGoalCoord)
            'Test North East
            Testing(CurrentNode, 1, 1, XGoalCoord, YGoalCoord)
            'Test North
            Testing(CurrentNode, 0, 1, XGoalCoord, YGoalCoord)
            'Test North West
            Testing(CurrentNode, -1, 1, XGoalCoord, YGoalCoord)
            'Test West
            Testing(CurrentNode, -1, 0, XGoalCoord, YGoalCoord)
            'Test South west
            Testing(CurrentNode, -1, -1, XGoalCoord, YGoalCoord)
            'Test South
            Testing(CurrentNode, 0, -1, XGoalCoord, YGoalCoord)
            'Test South East
            Testing(CurrentNode, 1, -1, XGoalCoord, YGoalCoord)
        Loop
        Dim Direction1 As String = Nothing
        Dim Direction2 As String = Nothing
        Dim UD As String
        If GoalReached = True Then
            CurrentNode = GoalNode
            Do While CurrentNode.XParent <> Nothing And CurrentNode.YParent <> Nothing
                If CurrentNode.XCoord - CurrentNode.XParent = 1 Then
                    Direction2 = "E"
                ElseIf CurrentNode.XCoord - CurrentNode.XParent = -1 Then
                    Direction2 = "W"
                End If
                If CurrentNode.YCoord - CurrentNode.YParent = 1 Then
                    Direction1 = "N"
                ElseIf CurrentNode.YCoord - CurrentNode.YParent = -1 Then
                    Direction1 = "S"
                End If
                UD = Direction1 + Direction2
                PathToFollow.Add(UD)
                For Each PathNode As Node In ClosedList
                    If PathNode.XCoord = CurrentNode.XParent And PathNode.YCoord = CurrentNode.YParent Then
                        CurrentNode = PathNode
                    End If
                Next
            Loop
'This is just for testing purposes
            For Each Path In PathToFollow
                MessageBox.Show(Path)
            Next
'End testing purposes block
        Else
            MessageBox.Show("No path found")
        End If
        
    End Sub

    Public Sub Testing(ByRef CurrentNode As Node, ByRef XMod As Integer, ByRef YMod As Integer, ByRef XGoal As Integer, ByRef YGoal As Integer)
        Dim TestNode As New Node
        Dim MovementCost As Integer
        Dim XHerDistance As Integer
        Dim YHerDistance As Integer
        Dim Heuristic As Integer
        If XMod <> 0 And YMod <> 0 Then
            'Diagonal Movement detected
            MovementCost = DiagCost
        Else
            'Horizontal or vertical Movement only
            MovementCost = StraightCost
        End If

        XHerDistance = Math.Abs((CurrentNode.XCoord + XMod) - XGoal)
        YHerDistance = Math.Abs((CurrentNode.YCoord + YMod) - YGoal)
        If XHerDistance > YHerDistance Then
            Heuristic = DiagCost * YHerDistance + StraightCost * (XHerDistance - YHerDistance)
        Else
            Heuristic = DiagCost * XHerDistance + StraightCost * (YHerDistance - XHerDistance)
        End If

        'Test if we can walk on the Node, If we can't exit sub otherwise continue on
        If MapData(CurrentNode.XCoord + XMod, CurrentNode.YCoord + YMod) = 1 Then
            Exit Sub
        End If
        'Is this node the goal? If is Flag that the goal has been found so that path can be constructed.
        If CurrentNode.XCoord + XMod = XGoal And CurrentNode.YCoord + YMod = YGoal Then
            GoalNode.XParent = CurrentNode.XCoord
            GoalNode.YParent = CurrentNode.YCoord
            GoalReached = True
            Exit Sub
        End If
        'Is this node on the closed list?
        For Each ClosedNode As Node In ClosedList
            If ClosedNode.XCoord = CurrentNode.XCoord + XMod And ClosedNode.YCoord = CurrentNode.YCoord + YMod Then
                'Check to see if the cost is better, if so lower cost, reopen node with new F Value
                If ClosedNode.Cost < CurrentNode.Cost + MovementCost Then
                    ClosedList.Remove(ClosedNode)
                    ClosedNode.Cost = CurrentNode.Cost + MovementCost
                    ClosedNode.XParent = CurrentNode.XCoord
                    ClosedNode.YParent = CurrentNode.YCoord
                    ClosedNode.FValue = MovementCost + Heuristic
                    OpenList.Add(ClosedNode)
                    Exit Sub
                End If
            End If
        Next
        'None of the above? Congrats on a new node!!!
        TestNode.XCoord = CurrentNode.XCoord + XMod
        TestNode.YCoord = CurrentNode.YCoord + YMod
        TestNode.Cost = CurrentNode.Cost + MovementCost
        TestNode.XParent = CurrentNode.XCoord
        TestNode.YParent = CurrentNode.YCoord
        TestNode.FValue = MovementCost + Heuristic
        OpenList.Add(TestNode)
    End Sub
End Module
Reply With Quote
  #2  
Old 03-14-2012, 10:08 PM
passel's Avatar
passelA* (A Star) Pathfinding help passel is offline
Sinecure Expert

Super Moderator
* Guru *
 
Join Date: Jun 2003
Location: Upstate New York, usa
Posts: 8,026
Default

Do you understand how the search is suppose to work?
Have you set a breakpoint in the code and stepped through the logic line by line to watch what it is doing as it searches to see where it might be going astray.
Stepping the code line by line and watching what it does is usually more helpful than printing debug statements or poping up message boxes.
You can examine values, change values, and often make code changes while you're stepping through the code to fix logic errors as you find them.
__________________
There Is An Island Of Opportunity In The Middle of Every Difficulty.
Miss That, Though, And You're Pretty Much Doomed.
Reply With Quote
  #3  
Old 03-15-2012, 01:06 PM
Qua's Avatar
QuaA* (A Star) Pathfinding help Qua is offline
Impetuous & volatile

* Expert *
 
Join Date: Apr 2005
Posts: 2,177
Default

A* is a simple search algorithm. I'm gonna be honest with you now, and it is not discourage you in any way, but your current code is a mess and it contains several bugs / wrong code. I started a write-up to point out where you had gone wrong and what you would need to do to fix it, but I think starting from scratch might be easier.

There are a few concepts in the A* search algorithm. The cost/score values are crucial to A*. There are 3 score values that you need to compute for every node that you evaluate:
  • g-score: This is how long there is from start to your current node. This indicates how long you have to travel to get to your current point.
  • h-score: This is how long there is form your current node to goal. This is computed using a heuristic/guessing algorithm of your choice. Common ones are Manhatten og straight line euclidean distance.
  • f_score: This is the sum of g_score + h_score for you current node. This is your estimate for the total path length if you choose to go along the current node.

I suggest you take starting point in Wikipedia's pseudocode. The code is pretty straight forward, and you can reuse a lot of what you have already. The important thing is that you keep track of score, that you have a function to give you the neighbors of your current node and finally that you do not exit the first loop before your have found your goal node or that you have explored all paths.

I will be happy to help you further along the way if you have more problems.
__________________
Reading is the foundation for all knowledge - Unknown.
Reply With Quote
  #4  
Old 03-17-2012, 12:17 AM
Waxara Waxara is offline
Newcomer
 
Join Date: Mar 2012
Posts: 2
Default

Quote:
Originally Posted by passel View Post
Do you understand how the search is suppose to work?
Have you set a breakpoint in the code and stepped through the logic line by line to watch what it is doing as it searches to see where it might be going astray.
Stepping the code line by line and watching what it does is usually more helpful than printing debug statements or poping up message boxes.
You can examine values, change values, and often make code changes while you're stepping through the code to fix logic errors as you find them.
Yes, or well I thought I understood it completely at the time. Turns out I either somehow missed on the pages I spent a couple days reading that I had to compare to the open list as well as the closed list. I had done a few runs stepping through the code and the code was executing as I had expected, only after I set the code to break after a good number of searches rather than examining the code on the first few nodes did I discover the problem. Works as intended now.




Quote:
Originally Posted by Qua View Post
A* is a simple search algorithm. I'm gonna be honest with you now, and it is not discourage you in any way, but your current code is a mess and it contains several bugs / wrong code. I started a write-up to point out where you had gone wrong and what you would need to do to fix it, but I think starting from scratch might be easier.

There are a few concepts in the A* search algorithm. The cost/score values are crucial to A*. There are 3 score values that you need to compute for every node that you evaluate:
  • g-score: This is how long there is from start to your current node. This indicates how long you have to travel to get to your current point.
  • h-score: This is how long there is form your current node to goal. This is computed using a heuristic/guessing algorithm of your choice. Common ones are Manhatten og straight line euclidean distance.
  • f_score: This is the sum of g_score + h_score for you current node. This is your estimate for the total path length if you choose to go along the current node.

I suggest you take starting point in Wikipedia's pseudocode. The code is pretty straight forward, and you can reuse a lot of what you have already. The important thing is that you keep track of score, that you have a function to give you the neighbors of your current node and finally that you do not exit the first loop before your have found your goal node or that you have explored all paths.

I will be happy to help you further along the way if you have more problems.
If you are referring to the following as wrong code/bugs:
Code:
If ClosedNode.Cost < CurrentNode.Cost + MovementCost
I realized the next day I needed "<" to be ">" instead and have since corrected that,
and
Code:
ClosedNode.FValue = MovementCost + Heuristic
was supposed to read
Code:
ClosedNode.FValue = CurrentNode.Cost + MovementCost + Heuristic
but in my many tamperings to figure out what was wrong that was one of the things I changed and I did not realized I had not changed it back before copying my code.

As I said above those the code now works, or at least seems to work reliably in the 2 dozen or so tests I've thrown at it. If there are other errors/bugs that I may have missed I defiantly would not mind pointers as to where they may reside.

As for messy I'm not really sure how I can make it neater at current, coding is a light hobby though I get better with every program I write. I'm sure in a month or so I'll be able to make it even neater, but now that I've gotten it working I'll take a day breather from it then go back see what I can do about rewriting and neatening it up.
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump

Advertisement:





Free Publications
The ASP.NET 2.0 Anthology
101 Essential Tips, Tricks & Hacks - Free 156 Page Preview. Learn the most practical features and best approaches for ASP.NET.
subscribe
Programmers Heaven C# School Book -Free 338 Page eBook
The Programmers Heaven C# School book covers the .NET framework and the C# language.
subscribe
Build Your Own ASP.NET 3.5 Web Site Using C# & VB, 3rd Edition - Free 219 Page Preview!
This comprehensive step-by-step guide will help get your database-driven ASP.NET web site up and running in no time..
subscribe
A* (A Star) Pathfinding help
A* (A Star) Pathfinding help
A* (A Star) Pathfinding help A* (A Star) Pathfinding help
A* (A Star) Pathfinding help
A* (A Star) Pathfinding help
A* (A Star) Pathfinding help A* (A Star) Pathfinding help A* (A Star) Pathfinding help A* (A Star) Pathfinding help A* (A Star) Pathfinding help A* (A Star) Pathfinding help A* (A Star) Pathfinding help
A* (A Star) Pathfinding help
A* (A Star) Pathfinding help
 
A* (A Star) Pathfinding help
A* (A Star) Pathfinding help
 
-->