Trouble implementing A* [Solved]

[Shaggy]

Ahhh, I understand. Now I feel really stupid that it took me this long to realize that.

I've done the changes you said, as well as one other thing I noticed. I was updating the CurrentX and CurrentY, but not feeding that back into the tempnode, and therefore not feeding it back into AddNeighbors correctly.

Now that that is fixed, It adds 6,6 and 7,7 (When path-finding from 5,5 to 10,10) and then gets stuck in a loop.

http://pastebin.com/kaSSLEBU

[Omnomnom]

It's useful to use the debugger in visual studio to step through code one line at a time and check what the values of variables and the contents of the open and closed lists are at any point. That's the best way to figure out what's going on and when it goes wrong. For example I think if you try this on the current code you will find the nodes added to the open list by the first AddNeighbours call all have the same X and Y value (which is wrong)

The reason for this is you are only instantiating one Node object at the start of the method:

Dim TempNode As New Node

You then add this single instance to the open list multiple times (one for each neighbor). This worked before but now that Node is a class it's a reference type so when you add TempNode to the open list it adds a reference, not the object itself. For each neighbor you are adding a reference to the same object.

A fix is to put the 'Dim TempNode As New Node' line after:

If Not (Y + intY) < 0 Then

That way you at least get a new TempNode object for each neighbor.

Another thing. You've added a check in AddNeighbour to see if the node is already in the open list. It just sets InList = True. But IIRC the A* algorithm requires you update an existing node's G value if the new calculated value is lower than the existing one. Fortunately you've already done all the hard work so I think it's just a matter of a few alterations:

Code: [Select]

'check the closed list first
For Each Node In ClosedList
    If Node.Self.X = TempNode.Self.X And Node.Self.Y = TempNode.Self.Y Then
        InList = True
    End If
Next

'only check the open list if it wasn't in the closed list
If Not InList
   For Each Node In OpenList
      If Node.Self.X = TempNode.Self.X And Node.Self.Y = TempNode.Self.Y Then
         'if the new node info (path from this parent) has a lower G cost than the
         'existing node info (path from some other parent) then update the
         'node info in the open list to come from us (our path is shorter/better)
         If TempNode.G < Node.G then
            InList = True
            Node.G = TempNode.G
            Node.H = TempNode.H
            Node.F  = TempNode.F
            Node.Parent = ThisNode  'this is new parent
         End If
      End If
   Next
End-If

After that I suspect it might work, I can't see any other problems (not that means anything, it took me about three weeks to implement A* all the time being unable to spot a dozen or so problems)

[Shaggy]

It's useful to use the debugger in visual studio to step through code one line at a time and check what the values of variables and the contents of the open and closed lists are at any point. That's the best way to figure out what's going on and when it goes wrong. For example I think if you try this on the current code you will find the nodes added to the open list by the first AddNeighbours call all have the same X and Y value (which is wrong)

I still need to learn to use the debugger better. I kind of understand it, but I basically just use breakpoints to track things.

After that I suspect it might work, I can't see any other problems (not that means anything, it took me about three weeks to implement A* all the time being unable to spot a dozen or so problems)

And that makes me feel a bit better. When I first started writing this implementation I thought I had a good understanding of the algorithm. But I've realized there were a few key things I was missing. Getting closer, though.

Still stuck in a loop somewhere. Do you have any tips or articles I could read about how to use the debugger more efficiently? Here's the code now, though it's pretty much exactly what you said. Just added some comments in there.

http://pastebin.com/jDmKBQA7

[requerent]

There are a few things to nitpick. I would recommend writing more output-- What are you g, f and h values when you get stuck in the loop? Put write statements everywhere and see what's going. If you're still having trouble post your output.

[Shaggy]

Good idea. By doing that, I found out that it's not selecting the lownode correctly. When path-finding from 5,5 to 10,10 it selects 4,6 as the first lownode, when it should be 6,6.

I tried making it loop through all the nodes until there were no changes made, but it's come to the same solution. Any ideas what I'm doing wrong here?

4,6 scores (G,H,F) as (14, 100, 114) where 6,6 is (14,80,94) yet it selects 4,6 as the lowest.

Code: [Select]


LowNode.F = 999999

Dim bChanged As Boolean = True 'tracks if there was a change or not

                Do While bChanged = True 'cycle through until you make NO changes.

                    bChanged = False

                    For Each Node In OpenList

                        If Node.F < LowNode.F Then
                            Write(2, 2, Node.F, ConsoleColor.Cyan)
                            Write(2, 4, "vs", ConsoleColor.Yellow)
                            Write(2, 8, LowNode.F, ConsoleColor.Cyan)
                            LowNode = Node
                            bChanged = True
                            Console.ReadKey()
                            Console.Clear()
                        End If

                    Next

                Loop


                Console.Clear()

                Write(2, 2, "Low Node", ConsoleColor.Yellow)

                With LowNode

                    Write(4, 4, "X:", ConsoleColor.Yellow)
                    Write(5, 4, "Y:", ConsoleColor.Yellow)
                    Write(6, 4, "G:", ConsoleColor.Yellow)
                    Write(7, 4, "H:", ConsoleColor.Yellow)
                    Write(8, 4, "F:", ConsoleColor.Yellow)

                    Write(4, 7, .Self.X, ConsoleColor.Cyan)
                    Write(5, 7, .Self.Y, ConsoleColor.Cyan)
                    Write(6, 7, .G, ConsoleColor.Cyan)
                    Write(7, 7, .H, ConsoleColor.Cyan)
                    Write(8, 7, .F, ConsoleColor.Cyan)

                    Console.ReadKey()
                    Console.Clear()
                End With

[Omnomnom]

Your lowest-hunting code works. It turns out the reason it's saying 4,6 is the lowest F value node in the open list is because it really is. I stepped through the code in the debugger and noticed AddNeigbhours only adds the first four neighbours to the OpenList:

(4,4), (4,5), (4,6), (5,4)

WTF. So I ran through it again and found the reason is it sets InList to True for the 5th node (which is 5,5), but doesn't reset InList when it checks the rest of the neighbours (5,6), (6,4), (6,5), (6,6), so none of them are added to the open list.

If you set InList to false at the start of each loop it will fix this. You can also skip the (5,5) case just for purity:

Code: [Select]

For intX = -1 To 1
   For intY = -1 To 1
      'skip intX=0,intY=0, it's always self, never a neighbour
      If intX = 0 and intY = 0 Then
         Continue For
      End-If
      'start by assuming a neighbour is not in the list until it is found
      InList = False

This is one of those bugs I mentioned about being hard to spot.

Another even harder bug to spot is in the Path() method itself:

At the end of the processing for a node you set CurrentX and CurrentY.
CurrentX = LowNode.Self.X;
CurrentY = LowNode.Self.Y;

For the next node processing you then instantiate a new tempnode using CurrentX and currentY.

Code: [Select]

With TempNode
     .Clear()
     .Self.X = CurrentX
     .Self.Y = CurrentY
End With

You need to also set the G value of the node too. Eg with something like a new variable CurrentG (or you could set TempNode = LowNode somehow rather than making a new node?). The reason you need the G value to be set is that AddNeighbours needs it (for the parent's G value).

I wouldn't have figured that out just by looking at the code itself. It would take me days to even have a chance of stumbling on it. I only found it again through debugging because once I reached GetScore for the first valid neighbour of 6,6 I noticed hovered over Parent.G and noticed it was set to 0 and I knew (6,6).G should have been 14 not zero. So then it was a matter of figuring out why. Was it being reset or was it not being set at all? I debugged through line by line again slowly to find that it wasn't being set. Stepping through code can be tedious, but it is reliable at tracking down the source of problems. Almost any problem can be tracked this way.

-----

This 5 minute video looks like it explains debugging in visual studio with VB (I haven't heard the speech though as I have no sound here):
http://www.youtube.com/watch?v=Uk-a7qVa36c

For more detailed stuff (much of which I don't know) there are tutorials on using the VS debugger here:
http://msdn.microsoft.com/en-us/library/ms172744(v=vs.110).aspx

What I do is pretty much what the video shows. I just set a breakpoint and when the program hits the breakpoint I use Step Over (F8) to step to the next line. You can keep hitting F8 to run through the whole program one line at a time, each line it pauses. If you are over a method call then Step Into (F10) will step into that method. At any point if you hover over variables in the code it will show you what the values are at the current time of the paused program. There is also an autos window that automatically lists variables in the current scope and their values (rather than having to hover over them).

[Shaggy]

Awhh, yeah! It's working! And (as far as I can tell anyway) its decently quick. I'm sure there's places it could be sped up, but for now I'm just excited it's working. Thank you all so much for all your help!

This 5 minute video looks like it explains debugging in visual studio with VB (I haven't heard the speech though as I have no sound here):
http://www.youtube.com/watch?v=Uk-a7qVa36c

For more detailed stuff (much of which I don't know) there are tutorials on using the VS debugger here:
http://msdn.microsoft.com/en-us/library/ms172744(v=vs.110).aspx

What I do is pretty much what the video shows. I just set a breakpoint and when the program hits the breakpoint I use Step Over (F8) to step to the next line. You can keep hitting F8 to run through the whole program one line at a time, each line it pauses. If you are over a method call then Step Into (F10) will step into that method. At any point if you hover over variables in the code it will show you what the values are at the current time of the paused program. There is also an autos window that automatically lists variables in the current scope and their values (rather than having to hover over them).

Ahh. See, I used breakpoints, but I didn't realize there was a Step Over or Step Into command. That'll be very helpful, thanks! Here's the (working!!) code I've got now.

http://pastebin.com/vtyS0ntH