Jump to content
Sign in to follow this  

Depth First Search AI Mostly Functional

Recommended Posts


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

#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
    $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")
    If $aNeighborData[3] Then;Checks for a neighbor to the East
        $iIDCounter += 1;increment ID
        _CreateNode($iIDCounter, $iCurrentVID, "W")
    If $aNeighborData[6] Then;Checks for a neighbor to the South
        $iIDCounter += 1;increment ID
        _CreateNode($iIDCounter, $iCurrentVID, "N")
    If $aNeighborData[9] Then;Checks for a neighbor to the West
        $iIDCounter += 1;increment ID
        _CreateNode($iIDCounter, $iCurrentVID, "E")
    $aClosedList = _ArrayAdd($aClosedList, $iCurrentVID)

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 

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
    $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:")
    $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

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

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

    While NOT $bFound
            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?

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

Main();Do It

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  


Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.