Well, i'm attempting to implement a* for the first time ever. I'm working in a map that is 100x100, and haven't yet added checks for walkablility. When i run the pathfinding routine it works fine, assuming the path it's looking for is directly to the right ONLY. heh. If i try to go up or down it goes into some sort of infinate loop, and if i try to go to the right, it displays a path of 2 squares to the right. Well, without further ado, here's the pathfinding code... (oh, and so no one thinks i didn't calculate .F for the tiles, .F is a function, and does the calculation itself)

Public Function FindPath(path() As clsCoordinates, unit As clsUnit, targX As Integer, targY As Integer) As clsCoordinates()
'Stop
Dim comptile As clsTile
Dim openlist As New Collection
Dim closedlist As New Collection
Dim curtile As New clsTile
Dim tilesquare(9) As clsTile
Dim tempG As Integer
Dim x As Integer
Dim y As Integer
Dim count As Integer
Dim found As Boolean
Dim lowestF As String
Dim pathcount As Integer
Dim results() As New clsCoordinates

Set curtile.Parent = curtile
curtile.x = unit.x / 32
curtile.y = unit.y / 32
curtile.G = 0
curtile.H = Abs(curtile.x - targX) + Abs(curtile.y - targY)
count = 0
openlist.Add curtile, curtile.x & "," & curtile.y
'On Error Resume Next
Do While found = False
    lowestF = ""
    count = 0
    For Each curtile In openlist
        If Not curtile Is Nothing Then
            If lowestF = "" Then
                lowestF = curtile.x & "," & curtile.y
            Else
                Set comptile = openlist.Item(lowestF)
                If curtile.F < comptile.F Then lowestF = curtile.x & "," & curtile.y
            End If
        End If
    Next curtile
    
    Set curtile = openlist(lowestF)
    openlist.Remove lowestF
    closedlist.Add curtile, lowestF
    For x = -1 To 1
        For y = -1 To 1
            count = count + 1
                If Abs(x) = Abs(y) Then tempG = 14 Else tempG = 10
                Set tilesquare(count) = New clsTile
                tilesquare(count).x = curtile.x + x
                tilesquare(count).y = curtile.y + y
                If IsIn(closedlist, tilesquare(count).x & "," & curtile.y) Then GoTo skip
                If IsIn(openlist, (tilesquare(count).x & "," & curtile.y)) Then
                    Set tilesquare(count) = openlist.Item(tilesquare(count).x & "," & curtile.y)
                    If tilesquare(count).G > curtile.G + tempG Then
                        Set tilesquare(count).Parent = curtile
                        tilesquare(count).G = curtile.G + tempG
                        tilesquare(count).H = Abs(tilesquare(count).x - targX) + Abs(tilesquare(count).y - targY)
                    End If
                Else
                    tilesquare(count).G = curtile.G + tempG
                    tilesquare(count).H = Abs(tilesquare(count).x - targX) + Abs(tilesquare(count).y - targY)
                    Set tilesquare(count).Parent = curtile
                    openlist.Add tilesquare(count), tilesquare(count).x & "," & tilesquare(count).y
                End If
skip:
        If tilesquare(count).x = targX And tilesquare(count).y = targY Then found = True
        Next y
    Next x
pathcount = pathcount + 1
Loop

ReDim path(pathcount)
Debug.Print pathcount
Set curtile = tilesquare(count)
For x = pathcount To 0 Step -1
    Set path(x) = New clsCoordinates
    path(x).x = curtile.x
    path(x).y = curtile.y
    Set curtile = curtile.Parent
Next x
End Function
  

Yes, i know some parts of it are hackish, (the whole passing in an array, among others) but i'll fix that later, right now i just want it to work... any suggestions? edit: Details [edited by - zendarva on August 16, 2003 6:51:24 AM]

perhaps u could give us a pseudo code implementaiton. Its difficult for me to follow ur VB implementation, as im only slightly familair with its syntax.

-ddn

Please only post code as a last resort. You are far more likely to get assistance if you post the algorithm your code implements. Thus, as the previous poster indicated, pseudo code is more readable and understandable by many of our readers.

Without going through your code, here are a couple of possibilities that usually cause this sort of problem.

Make sure that:
1) you have completely debugged the code you have written;
2) you use and remove the lowest cost node from your OPEN list at each iteration;
3) the path cost to each node from the root node is correct;
4) the heuristic is admissible (that is, it under estimates the actual cost of getting from a node to the goal);
5) when you create a new node, you verify that it doesn''t already exist in the OPEN list OR the CLOSED list.

If it''s none of these, then you probably need to look a little deeper at logical errors in your code.

Timkin