Jump to content
Sign in to follow this  
ramadash

A* autoit implementation

Recommended Posts

ramadash

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?

#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

Share this post


Link to post
Share on other sites
PsaltyDS

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?

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

:P


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

Share this post


Link to post
Share on other sites
nfwu
PsaltyDS

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

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  

×