Temple of The Roguelike Forums
Development => Programming => Topic started by: Shaggy on October 04, 2012, 11:16:52 PM
-
So I've begun working on my AI now that I've got the dungeon generator working. My first issue is in implementing the A* algorithm for path-finding. Before, I tried using a djikstra map of sorts but I couldn't get that to work quite right either.
I've got some code that I think should work, but it's getting stuck in a loop somewhere and I've been unsuccessful finding it with the debugger. If anyone would be willing to take a look at my code and figure out where I may have made a mistake I would be grateful. Also, if you could tell me a 'better' way to do this, as I'm sure my way is a bit off.
http://pastebin.com/bZjPPShJ
EDIT :: Code fixed, see page 2.
-
My a* algorithm has a check for whether a node has already been "visited," which I didn't see in your code. I.E. if you are looking at neighbors you do not want to create a new node for a location that already has a node and cost associated with it. Instead, you want to check if a new path coming from currentx, currenty is shorter than the old path through that node.
It may be that I just don't see your check.
-
That is a very long A* implementation. I would recommend breaking up your A* to help differentiate between distinguished states, the heuristic, your priority queue, and the algorithm itself. Any one of these places could result in infinite looping. A correct A* implementation will work the same regardless of what else is going on in your program. Let me know if you'd want some ideas for that.
Anyhow- your problem is here--
Sub GetScores(TargetX As Integer, TargetY As Integer)
Dim dx, dy As Integer
dx = NodeX - ParentX
dy = NodeY - ParentY
If dx = 1 And dy <> NodeY Then
G = 14
ElseIf dx = -1 And dy <> NodeY Then
G = 14
Else
G = 10
End If
dx = Math.Abs(TargetX - NodeX)
dy = Math.Abs(TargetY - NodeY)
H = (dx + dy) * 10
F = G + H
End Sub
A* needs to aggregate the path cost. That is, whenever a Node is expanded and its children's F value are evaluated, you need to ADD the parent's cost path to the child's path cost (The path cost is the G value). You're only evaluating the path cost from your current position to its neighbor's positions. The G value should be the actual non-heuristic cost of reaching the child node from the start node.
Your G values are being assigned the cost of moving to the next child, not the entire path cost.
Image courtesy of somebody else-
(http://www.cs.nott.ac.uk/~gxk/courses/g5aiai/003blindsearches/images/ucs001.jpg)
The path cost from S to A is 1. The path cost from A to G, however, is 11, even though the cost from moving from A to G is only 10. It's more accurate to say that we're moving from S to G through A.
-
cleaned up my code a bit, and fixed the distance issue. However, it's still stuck in a loop. I think it may have something to do with the computer seeming to think that 5 - 5 = 5.
http://mroedesigns.webs.com/what.png
Here's the new code
http://pastebin.com/JinsdWLk
-
A few problems I see.
1) Nothing is ever removed from the open list. When you process a node it should be removed from the open list and placed in the closed list.
2) AddNeighbors should skip over neighbours that are in the close list. Closed nodes are done, never to be edited again.
3) In AddNeighbours if a neighbour node is already in the open list then you need to use that node. Don't create a new Node instance. Each tile should have at most 1 node instance.
This tutorial is really useful. It's good to run through it on paper a few times. In particular you seem to be missing steps 4,5 and 6
http://www.policyalmanac.org/games/aStarTutorial.htm
-
Interesting.
-
That article helped, and I can tell I'm getting closer. It's not stuck in a loop anymore, though it's far from working correctly. My ClosedList output at the end starts off decent, but gets way off. By the time I decided to stop writing them down, it was at position 0,7 when trying to go from 5,5 to 10,10. Oh yeah, and that was it's 14th step.
Anyway, I've gotta go through and figure out whats going on, but I need to head to bed. I appreciate all your help so far! If you want to take a look, here's how the code looks now.
http://pastebin.com/fP4WcAQ5
-
That article is unnecessarily verbose. I imagine it causing more confusion than clarity.
I can't read VB very well, but I noticed another issue.
Private Structure Node
Dim NodeX, NodeY As Integer 'the location of this node
Dim ParentX, ParentY As Integer 'the location of this nodes parent
Dim ParentG As Integer 'the G score of the parent cell
Dim F, G, H As Integer
If Not OpenList.Contains(TempNode) _
And Not ClosedList.Contains(TempNode) Then _
OpenList.Add(TempNode)
These two don't work together. The OpenList and ClosedList shouldn't store nodes, they should store states. In a purely positional A-Star search, each state is described solely by a position, (x,y).
Nodes are wrappers to store states in a search-graph. Parents and path-cost and heuristic values are NOT a part of the state, but we put them in a node to make a meaningfully connected graph. ClosedList.contains(someNode) is including the parentx, parenty, F, G and H values as a single value-type in the comparison for duplicate values. This is not correct. You'll end up duplicating states with different F,G,H and parent values.
The Node should simply be a wrapper to the state with a pointer (reference data-type) to the parent. That's why node should be a class and state should be a struct. IE-
Structure State
dim x,y as integer
Class Node
dim parent as Node
dim self as State
dim F, G, H as Integer
' no clue if this is proper syntax or not
To help you out- you may want to consider using a PriorityQueue and a Set (in the form of a Hash or Dictionary). I found a straightforward VBasic priority queue implementation - http://www.vb-helper.com/howto_net_generic_priority_queue.html (though you should implement it as a heap instead of lists, but whatever--VB might automagically optimize stuff or something).
Now, instead of putting nodes into your openList, you just put states. Your closedList can then be a dictionary, where the state is a key and the Node is a value. If the key doesn't exist, then we know the state has never been discovered (and in order of constant-time!).
When it's time to pop the best state off the openList, you can easily fetch the Node by passing the state into the dictionary.
Anyhow, good luck.
-
If Not OpenList.Contains(TempNode) _
And Not ClosedList.Contains(TempNode) Then _
OpenList.Add(TempNode)
These two don't work together. The OpenList and ClosedList shouldn't store nodes, they should store states. In a purely positional A-Star search, each state is described solely by a position, (x,y).
They aren't sharing nodes. It's just making sure that the described node isn't already in either list, ensuring it hasn't already been examined.
-
If Not OpenList.Contains(TempNode) _
And Not ClosedList.Contains(TempNode) Then _
OpenList.Add(TempNode)
These two don't work together. The OpenList and ClosedList shouldn't store nodes, they should store states. In a purely positional A-Star search, each state is described solely by a position, (x,y).
They aren't sharing nodes. It's just making sure that the described node isn't already in either list, ensuring it hasn't already been examined.
I think you misunderstood me. I'm saying that the Node structure you've defined will NOT behave as you expect when using list.contains.
Your node structure is a value type that stores NodeX, NodeY, ParentX, ParentY, F, G, and H values. ALL of these values are compared when checking to see if a given node is in the list or not. It just isn't going to work if you use Nodes instead of States- F,G,H and parent state are NOT a part of any given state! The state is purely positional (x,y). There shouldn't be any other data compared to see if it exists. You must make a distinction between Nodes (a reference-type class) and States (a value-type structure).
-
Eh, this is what I did for my A*:
https://github.com/st33d/red-rogue/blob/master/src/com/robotacid/ai/MapGraph.as
It's uses some optimisation hacks based on some shortcuts I realised you could take in the representation of the closed and open lists. It also defaults to a metaheurisic path if the steps limit is reached, perfect path finding over large distances isn't essential for close combat.
The function that does the magic is getPathTo()
-
Ahh I see, that does make more sense. I changed it up to work how you advised, keeping the states as a separate part of the node and comparing that value to check for duplicates. I also added a lot of commenting to make sure you know how each method is supposed to work. It's still stuck in an infinite loop somewhere. I'm pretty sure it's outside of the addneighbors sub, but I could be wrong.
http://pastebin.com/rMnshBh8
-
Private Structure Node
Dim self As State 'the state of this node
Dim parent As State 'the location of this nodes parent
Your going to want to make the parent a Node. This will effectively make each node's path to the start state a linked-list. Which is important when you need to return the final path.
I did notice something else about your addNeighbors.
'in add neighbors
TempNode.GetScores(X, y)
TempNode.ParentG = TempNode.G
TempNode.GetScores(TargetX, TargetY)
'In get scores
If dx = 1 And dy <> self.y Then
G = 14 + ParentG
ElseIf dx = -1 And dy <> self.y Then
G = 14 + ParentG
Else
G = 10 + ParentG
TempNode in addNeighbor is never assigned a ParentG value before calling getScores. This means that it's G value is going to be 14 or 10. When TempNode call getScores a second time, the G value will be between 10-28. The G value should describe the ENTIRE path cost from any given state to the START state. Right now you're just fetching the parent (I may not have been clear on that)- you need the entire path cost.
To resolve this, you should make addNeighbors a sub-(routine?) of Node. AddNeighbors does not currently have the right amount of information to assign the proper G values.
You need to ensure that each node's path cost is the path to the start state-- to do that, you really want to have each Node reference a Parent Node. Take look at the example below.
Private Structure
dim x,y as Integer
private Class Node
dim parent As Node
dim self As State
dim F,G,H As Integer
sub getScores(Goal As State)
Dim dx, dy As Integer
dx = self.x - parent.self.x
dy = self.y - parent.self.y
If dx <> 0 And dy <> 0
G = 14 + parent.G
Else
G = 10 + parent.G
End If
dx = Math.Abs(self.x - Goal.x)
dy = Math.Abs(self.y - Goal.y)
H = (dx+dy)*10
F = G + H
sub getNeighbors()
Dim tempNode As New Node
for intx = -1 To 1
for inty = -1 To 1
If Not (self.x + intx) < 0 Then
If Not (self.y + inty) < Then
TempNode.self.x = X + intx
TempNode.self.y = y + inty
TempNode.parent = self 'IMPORTANT!!!
TempNode.GetScores()
'.... ETC
Hope that helps.
-
Private Structure Node
Dim self As State 'the state of this node
Dim parent As State 'the location of this nodes parent
Your going to want to make the parent a Node. This will effectively make each node's path to the start state a linked-list. Which is important when you need to return the final path.
It's impossible to make parent a node. In VB a structure can't have a refrence to itself. Hence why it's just a state.
I did notice something else about your addNeighbors.
'in add neighbors
TempNode.GetScores(X, Y) ' <- This is the location of the parent node.
TempNode.ParentG = TempNode.G
TempNode.GetScores(TargetX, TargetY)
'In get scores
If dx = 1 And dy <> self.y Then
G = 14 + ParentG
ElseIf dx = -1 And dy <> self.y Then
G = 14 + ParentG
Else
G = 10 + ParentG
TempNode in addNeighbor is never assigned a ParentG value before calling getScores.
It uses getscore the first time to get the parent scores, then assigns that as the parent G. Then it uses getscore to get the rest of the scores for that actual cell.
'get the scores of the parent
TempNode.GetScores(X, Y)
'assign the parents G score
TempNode.ParentG = TempNode.G
'get this nodes scores
TempNode.GetScores(TargetX, TargetY)
X,Y is the location of the cell you're looking for neigbors around (IE, the parent cell); and TargetX, TargetY is the location of the cell that is currently being worked with.
-
Private Structure Node
Dim self As State 'the state of this node
Dim parent As State 'the location of this nodes parent
Your going to want to make the parent a Node. This will effectively make each node's path to the start state a linked-list. Which is important when you need to return the final path.
It's impossible to make parent a node. In VB a structure can't have a refrence to itself. Hence why it's just a state.
For the Node, don't use a Structure, use a Class. There are two different types of objects in VB, Classes and Structures. Classes are reference type and structures are value type.
If you had twelve variables all assigned a reference type value, changing one of them would change ALL of them. Whereas with a struct that is not the case. You can nest class objects within the same class, whereas you cannot with structures. It isn't absolutely necessary to use a class, but it will greatly simplify the process.
I did notice something else about your addNeighbors.
'in add neighbors
TempNode.GetScores(X, Y) ' <- This is the location of the parent node.
TempNode.ParentG = TempNode.G
TempNode.GetScores(TargetX, TargetY)
'In get scores
If dx = 1 And dy <> self.y Then
G = 14 + ParentG
ElseIf dx = -1 And dy <> self.y Then
G = 14 + ParentG
Else
G = 10 + ParentG
TempNode in addNeighbor is never assigned a ParentG value before calling getScores.
It uses getscore the first time to get the parent scores, then assigns that as the parent G. Then it uses getscore to get the rest of the scores for that actual cell.
It won't work out that way. And here is why--
Public Sub AddNeighbors(X As Integer, y As Integer, TargetX As Integer, TargetY As Integer)
You're passing states to this sub-routine. There is no-preexisting G value anywhere in there. When you create the tempNode around the X,y state, it's G value is either 10 or 14, not the aggregate cost of getting to that state. There's absolutely no way your sub-routine can know what the G value of X,y is without passing a node.
[a][b][c][d][e][f][g][h][i] : Nodes
[S][1][1][1][1][1][1][1][1] : Path costAssuming we start at 'a' and our goal is 'i', what is the path cost of moving from 'd' to 'e'? The COST of moving is 1, the PATH COST is 4. It's the entire path from 'a' to 'd' + the cost of going from 'd' to 'e'. Does that make sense? Unless you pass a G value (or preferably a node) into your addNeighbors, your tempNode cannot know its own path cost.
'get the scores of the parent
TempNode.GetScores(X, Y)
'assign the parents G score
TempNode.ParentG = TempNode.G
'get this nodes scores
TempNode.GetScores(TargetX, TargetY)
X,Y is the location of the cell you're looking for neigbors around (IE, the parent cell); and TargetX, TargetY is the location of the cell that is currently being worked with.
Same as above. Your tempNode is calling getScores without a previously stored parentG value. It'll only evaluate its own path-cost at 10 or 14.
-
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
-
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:
'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)
-
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
-
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.
-
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.
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
-
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:
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.
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 (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).
-
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 (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