Sign in to follow this  
Followers 0
ramadash

A* autoit implementation

4 posts in this topic

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



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

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  
Followers 0