A* autoit implementation

[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?

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

[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

[nfwu]

A* (a-star) Algorithm.

Here are some good resources:

(Mostly game dev involved)

http://gpwiki.org/index.php/A_star

http://www.policyalmanac.org/games/aStarTutorial.htm

http://ai-depot.com/Tutorial/PathFinding.html

http://en.wikipedia.org/wiki/A-star_search_algorithm

#)

Edited September 10, 2006 by nfwu

[PsaltyDS]

A* (a-star) Algorithm.

Here are some good resources:

(Mostly game dev involved)

http://gpwiki.org/index.php/A_star

http://www.policyalmanac.org/games/aStarTutorial.htm

http://ai-depot.com/Tutorial/PathFinding.html

http://en.wikipedia.org/wiki/A-star_search_algorithm

#)

Cool. Thanks for refs. I've learned my new thing for today... going back to bed!