RoBoMon Posted June 4, 2008 Posted June 4, 2008 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 Posted June 19, 2008 Posted June 19, 2008 hi! see this post:http://www.autoitscript.com/forum/index.php?showtopic=74041 You can help! Donate to AutoIt! or, visit ClimatePREDICTION.netMy posts:Travian Bot Example (100+ servers) BETAHow to Host you code/app for free! (unlimited team number) (Public or Private)"Sir, we're surrounded!" "Excellent. We can attack in any direction!"
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now