ramadash Posted September 10, 2006 Share Posted September 10, 2006 hello, I am implementing a star algo in autoit, and I was looking for some suggestions (mostly speed-related). I would also like any suggestion on what to use for open list, use an array and redim it everytime? and I would like to make this an UDF eventually but im not sure wich functions to provide / not provide, and wich options should be "hard coded' and wich should be changed by the user. I did not start to make the algo yet i just have my node list so far and scanning for unwalkable areas. Yep im really looking for ideas! and also if anyone want to have a look at this code and make suggestions, im far from the best scripter so I always like new tips to improve my scripting here is the code so far btw, does anyone ever tryed to do this? expandcollapse popup#include <ARRAY.AU3> Opt ( "CaretCoordMode" , 2 ) opt ( "ColorMode" , 1 ) opt ( "MouseCoordMode" , 2 ) opt ( "PixelCoordMode" , 2 ) global const $NodeParams = 6;total params for each nodes global $X_TotalNodes = 160, $Y_TotalNodes = 120 global $Screen_Height = 600, $Screen_Width = 800, $UnwalkableColor = 2197206, $UnwalkableSearchStep = 10 _ ,$X_LeftNode = 0 , $Y_TopNode = 0 , $X_RightNode = $Screen_Width , $Y_BottomNode = $Screen_Height ;the default 4 values below generate node for the full screen, to generate nodes for a part of screen, use ChangeNodeBox() ;PARAMS: ; Walkable, F, G, H, Parent global enum $n_Walkable, $n_F, $n_G, $n_H, $n_Parent, $n_InitialPos ;return an array x,y func _GetNodeByPixel( $X, $Y ) return _ArrayCreate( round ( $X / ( $Screen_Width / $X_TotalNodes ) ) , round( $Y / ( $Screen_Height / $Y_TotalNodes ) ) ) EndFunc ;scan for walkable/unwalkable nodes func _SetNodeWalkable() local $stepX = $Screen_Width / $X_TotalNodes, $StepY = $Screen_Height / $Y_TotalNodes $timer = TimerStart() for $nX = Round( 0 + $X_LeftNode / $stepX ) to Round( $X_RightNode / $stepX ) for $nY = Round( $Y_TopNode / $StepY ) to Round( $Y_BottomNode / $StepY ) if PixelGetColor( $nX * $stepX + $stepX / 2 , $nY * $StepY + $StepY / 2 ) == $UnwalkableColor then $NodeList [ $nX ] [ $nY ] [ $n_Walkable ] = 1 Else $NodeList [ $nX ] [ $nY ] [ $n_Walkable ] = 0 EndIf Next Next MsgBox( 0, "", "Walkable flag set, time: " & TimerDiff( $timer ) ) EndFunc ;this is a custom function func _ChangeNodeBoxSearch() $timer = TimerStart() local $Left = 0, $Top = 0, $Right = 0, $Bottom = 0 ;set left for $x = 0 to 400 step 15 for $y = 0 to 600 step 15 if PixelGetColor( $x, $y ) == $UnwalkableColor Then $Left = $X ExitLoop 2 EndIf Next Next ;set top for $Y = 0 to 400 step 15 for $X = 0 to 800 step 15 if PixelGetColor( $x, $y ) == $UnwalkableColor then $Top = $Y ExitLoop 2 EndIf Next Next ;set right for $x = 800 to 400 step -15 for $y = 0 to 600 step 15 if PixelGetColor( $x, $y ) == $UnwalkableColor then $Right = $X ExitLoop 2 EndIf Next Next ;set bottom for $y = 600 to 200 step -15 for $x = 0 to 800 step 15 if PixelGetColor( $x, $y ) == $UnwalkableColor then $Bottom = $y ExitLoop 2 EndIf Next Next FileWriteLine( $LogFile, $Left & " " & $top & " " & $Right & " " & $Bottom ) _ChangeNodeBox( $Left, $top, $Right, $Bottom ) MsgBox( 0, "", "ChangeNodeBoxSearch, time: " & TimerDiff( $timer ) ) EndFunc ;change the edges of the area to generate nodes (full screen by default, but put it lower for better speed ) func _ChangeNodeBox( $Left, $Top, $Right, $Bottom ) $X_LeftNode = $Left $Y_TopNode = $top $X_RightNode = $Right $Y_BottomNode = $Bottom EndFunc ;dump the map according to the changes made by _ChangeNodeBox (dont dump the full screen) func _DumpMap ( $File ) local $currLine, $hFile = FileOpen ( $file, 2 ), $stepX = $Screen_Width / $X_TotalNodes, $StepY = $Screen_Height / $Y_TotalNodes for $y_log = Round( $Y_TopNode / $StepY ) to Round( $Y_BottomNode / $StepY ) $currLine = "" for $x_log = Round( 0 + $X_LeftNode / $stepX ) to Round( $X_RightNode / $stepX ) if $NodeList [ $x_log ] [ $y_log ] [ $n_Walkable ] then $currLine &= "..." Else $currLine &= " " EndIf Next FileWriteLine( $file, $currLine ) FileWriteLine( $file, $currLine ) Next FileClose( $file ) EndFunc ;dump the full map even unnasigned nodes func _DumpMapFull ( $File ) local $currLine, $hFile = FileOpen ( $file, 2 ) for $y_log = 0 to $Y_TotalNodes - 1 $currLine = "" for $x_log = 0 to $X_TotalNodes - 1 if $NodeList [ $x_log ] [ $y_log ] [ $n_Walkable ] == true then $currLine &= "." Else $currLine &= " " EndIf Next FileWriteLine( $file, $currLine ) Next FileClose( $file ) EndFunc Link to comment Share on other sites More sharing options...
PsaltyDS Posted September 10, 2006 Share Posted September 10, 2006 hello, I am implementing a star algo in autoit, and I was looking for some suggestions (mostly speed-related). I would also like any suggestion on what to use for open list, use an array and redim it everytime? and I would like to make this an UDF eventually but im not sure wich functions to provide / not provide, and wich options should be "hard coded' and wich should be changed by the user.I did not start to make the algo yet i just have my node list so far and scanning for unwalkable areas. Yep im really looking for ideas! and also if anyone want to have a look at this code and make suggestions, im far from the best scripter so I always like new tips to improve my scriptinghere is the code so farbtw, does anyone ever tryed to do this?Ermmm... perhaps you could define "star algo"? I did write a function to take a list of node ID pairs, each pair defining a segment, and determine if any loop was formed: Determining Trees With AutoIT Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law Link to comment Share on other sites More sharing options...
nfwu Posted September 10, 2006 Share Posted September 10, 2006 (edited) A* (a-star) Algorithm.Here are some good resources:(Mostly game dev involved)http://gpwiki.org/index.php/A_starhttp://www.policyalmanac.org/games/aStarTutorial.htmhttp://ai-depot.com/Tutorial/PathFinding.htmlhttp://en.wikipedia.org/wiki/A-star_search_algorithm#) Edited September 10, 2006 by nfwu TwitterOut of date stuff:Scripts: Sudoku Solver | Webserver | 3D library (Pure AutoIt) | Wood's GadgetsUDFs: _WoodUniqueID() | _DialogEditIni() | _Console*() | _GetIPConfigData() | _URLEncode/Decode() Link to comment Share on other sites More sharing options...
PsaltyDS Posted September 10, 2006 Share Posted September 10, 2006 A* (a-star) Algorithm.Here are some good resources:(Mostly game dev involved)http://gpwiki.org/index.php/A_starhttp://www.policyalmanac.org/games/aStarTutorial.htmhttp://ai-depot.com/Tutorial/PathFinding.htmlhttp://en.wikipedia.org/wiki/A-star_search_algorithm#)Cool. Thanks for refs. I've learned my new thing for today... going back to bed! Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law Link to comment Share on other sites More sharing options...
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