Trouble implementing A* [Solved]

[Shaggy]

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.

[kraflab]

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.

[requerent]

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

Code: [Select]

      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-


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.

[Shaggy]

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

[Omnomnom]

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

[MisterMoxxie]

Interesting.

[Shaggy]

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

[requerent]

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.

Code: [Select]

    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

Code: [Select]

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-

Code: [Select]

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.

[Shaggy]

Code: [Select]

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.

[requerent]

Code: [Select]

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).

[st33d]

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()

[Shaggy]

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

[requerent]

Code: [Select]

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.

Code: [Select]

'in add neighbors
            TempNode.GetScores(X, y)
            TempNode.ParentG = TempNode.G
            TempNode.GetScores(TargetX, TargetY)


Code: [Select]

'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.

Code: [Select]

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.

[Shaggy]

Code: [Select]

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.

Code: [Select]

'in add neighbors
            TempNode.GetScores(X, Y) ' <- This is the location of the parent node.
            TempNode.ParentG = TempNode.G
            TempNode.GetScores(TargetX, TargetY)


Code: [Select]

'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.

Code: [Select]

'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.

[requerent]

Code: [Select]

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.

Code: [Select]

'in add neighbors
            TempNode.GetScores(X, Y) ' <- This is the location of the parent node.
            TempNode.ParentG = TempNode.G
            TempNode.GetScores(TargetX, TargetY)


Code: [Select]

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

Code: [Select]

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.

Code: [Select]

[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.

Code: [Select]

'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.