Depth First Search AI Mostly Functional

[RoBoMon]

I have been researching AI search algorithms lately, trying to find a way to make a component for a Bot I am playing with, I actually think I have a pretty good handle on the Depth First search algorithm idea, I am trying to implement, my problem is basically, coming up with the logic that actually takes the searching and actually moves the Avatar to the next block for searching.

I have a method for moving to the next unvisited neighbor, the problem I am having is defining a simple way to loop logic for returning to a previous node (several steps back in depth) and then finding the next unvisited node that is a neighbor of THAT node.

NOTE, this code is not yet "Executable" in that it is in it's planning stages, and I am trying to map out the logic, prior to testing. Does anyone have any insight on what logic I can use to have the Avatar move in a recursive manner, and or, perhaps change the point at which I am doing the actual movement?

Here is my Code so far...

expandcollapse popup

#include <Array.au3>
#include <ImageSearch.au3>
#include <GUIConstants.au3>

;Declare two empty lists: Open and Closed, a list to hold room data, and our ID counter
Global $aOpenList[1], $aClosedList[1], $aRoomData[1][4], $iIDCounter = 0

Func _DepthFirstSearch($iCurrentVID)

    Dim $aNeighborData
    $aRoomData[$iCurrentVID][0] = 1;Marks current room visited field
    _ArrayPop($aOpenList)
    $aNeighborData = _GetNeighborData(); Search for Neighbors and returns array of neighbor data    
    If $aNeighborData[0] Then;Checks for a neighbor to the North
        $iIDCounter += 1;increment ID
        _CreateNode($iIDCounter, $iCurrentVID, "S")
    EndIf
    If $aNeighborData[3] Then;Checks for a neighbor to the East
        $iIDCounter += 1;increment ID
        _CreateNode($iIDCounter, $iCurrentVID, "W")
    EndIf
    If $aNeighborData[6] Then;Checks for a neighbor to the South
        $iIDCounter += 1;increment ID
        _CreateNode($iIDCounter, $iCurrentVID, "N")
    EndIf
    If $aNeighborData[9] Then;Checks for a neighbor to the West
        $iIDCounter += 1;increment ID
        _CreateNode($iIDCounter, $iCurrentVID, "E")
    EndIf
    
    $aClosedList = _ArrayAdd($aClosedList, $iCurrentVID)
    _MoveNext($iCurrentVID,$aOpenList[0])
EndFunc

Func _CreateNode($iChildID,$iParentID,$sParentDir)
    $aRoomData[$iChildID][1] = $iParentID;set New Nodes ParentID to Current ID
    $aRoomData[$iChildID][2] = $sParentDir;set Direction of New Node to Parent Node
    $aOpenList = _ArrayAdd($aOpenList, $iChildID);Add New Node to Open List 
EndFunc


Func _GetNeighborData()
    Dim $bFoundSelf, $iMyX, $iMyY, $bN, $iNx, $iNy, $bS, $iSx, $iSy, $bE, $iEx, $iEy, $bW, $iWx, $iWy, $aNeighborData[15]
;Locate Self on Map
    $bFoundSelf = _ImageSearch(@ScriptDir & "\images\VMSelf.bmp",1,$iMyX,$iMyY,50);finds image of self on map
    If NOT $bFoundSelf Then
        $bFoundSelf = _ImageSearch(@ScriptDir & "\images\RLSelf.bmp",1,$iMyX,$iMyY,50);finds alt image of self on map
    EndIf
    
    $bN = _ImageSearchArea(@ScriptDir & "\Map\HDoor.bmp",1,$iMyX-20,$iMyY-20,$iMyX+20,$iMyY,$iNx, $iNy,40);finds a Horizontal Doorway, North of your point on map
    $bS = _ImageSearchArea(@ScriptDir & "\Map\HDoor.bmp",1,$iMyX-20,$iMyY,$iMyX+20,$iMyY+20,$iSx, $iSy,40);finds a Horizontal Doorway, South of your point on map
    $bW = _ImageSearchArea(@ScriptDir & "\Map\VDoor.bmp",1,$iMyX-20,$iMyY-20,$iMyX,$iMyY+20,$iWx, $iWy,40);finds a Verticle Doorway, West of your point on map
    $bE = _ImageSearchArea(@ScriptDir & "\Map\VDoor.bmp",1,$iMyX,$iMyY-20,$iMyX+20,$iMyY+20,$iEx, $iEy,40);finds a Verticle Doorway, East of your point on map
    
;Tooltip("Found Self: (" & $iMyX & "," &$iMyY&") N:("&$iNx&","&$iNy&") S:("&$iSx&","&$iSy&") E:("&$iEx&","&$iEy&") W:("&$iWx&","&$iWy&")",0,0,"Get Neighbors Results:")
    Sleep(10)
    
    $aNeighborData[0] = $bN
    $aNeighborData[1] = $iNx
    $aNeighborData[2] = $iNy
    $aNeighborData[3] = $bS
    $aNeighborData[4] = $iSx
    $aNeighborData[5] = $iSy
    $aNeighborData[6] = $bW
    $aNeighborData[7] = $iWx
    $aNeighborData[8] = $iWy
    $aNeighborData[9] = $bE
    $aNeighborData[10] = $iEx
    $aNeighborData[11] = $iEy
    $aNeighborData[12] = $bFoundSelf
    $aNeighborData[13] = $iMyX
    $aNeighborData[14] = $iMyY
    
    Return $aNeighborData
EndFunc

#cs
This next function is the area where my brain starts to die.
I am trying to figure out the actual navigation
that goes along with the search and discovery.

I got the easy part... if the next item on the
Open List is a neighbor just move there, I can't
figure out the logic I should write in order to backtrack
#ce


Func _MoveNext($iThisVID,$iNextVID)
    Dim $bFound = False, $iClosedCounter = 0, $aCurNavList[1]

    While NOT $bFound
        Select
            Case $aRoomData[$iThisVID][1] = $iNextVID
                MsgBox(0, "", "Go North")
            ;Enter the code to execute a North Move Here...
                $bFound = True
            Case $aRoomData[$iThisVID][2] = $iNextVID
                MsgBox(0, "", "Go East")
            ;Enter the code to execute an East Move Here...
                $bFound = True
            Case $aRoomData[$iThisVID][3] = $iNextVID
                MsgBox(0, "", "Go South")
            ;Enter the code to execute a South Move Here...
                $bFound = True
            Case $aRoomData[$iThisVID][4] = $iNextVID
                MsgBox(0, "", "Go West")
            ;Enter the code to execute a West Move Here...
                $bFound = True
            Case Else
                MsgBox(0, "", "FindPath!")
                While NOT $bFound
                ;Since we aren't next to the neighbor figure out which consecutive steps to go...
                ; i imagine some looping and backtracking, The data I have to work with are:
                ;Parent ID
                ;Parent Direction
                ;Has current cell been visited before
                ;At each step of backtracking I can check Neigbors until i find it... 
                ;(similar to the above Select Statement)
                ;each node upon creation, I also mark if each node has been visited, This is where
                ;my brain ceases to grasp a solution, I have come up with partial solutions, that
                ;really don't do what i am looking for there has to be a simple algorithim I can implement
                ; similar to the Se;ect Case above that recurses somehow?
                WEnd
        EndSelect
    WEnd
EndFunc

Func Main()

    $aOpenList = _ArrayAdd($aOpenList,$iIDCounter); Starting point to Open List
    
    _DepthFirstSearch(0); do a depth first search on Starting Point and find neighbors to add to the list...
    
    While NOT _ArrayToString($aOpenList,"|") = "";As long as nodes exist in the Open List... 
        _DepthFirstSearch($aOpenList[UBound($aOpenList)-1]); Do Depth First search of most recently added node
    WEnd
EndFunc

Main();Do It

[Linux]

hi!

see this post:

http://www.autoitscript.com/forum/index.php?showtopic=74041