Pathing Optimization [New Question...] (SOLVED!)

malu05 · November 5, 2008

Since my last pathing question I got into more performance trouble, however I really don't understand why, since the script is fairly small.

What this script does is that it places all the waypoints into a array.

Each waypoint have connections, and the goal of this script is to find out how to get to 28 "PathToPoint("28")" from 1 "$Nearest = 1".

Now in my head:

-look at a variable

-use the numbers in the variable

-if we have seen the number before then blacklist it (to avoid loops)

-if not check this next variable and get the numbers from that

-and so on...

..should not take more than a milli sec... also taking in consideration that there are only 28 points.

However on my computer it takes around 2 sec.

Can this be optimized or is there anything that causes bad loops or so?

Can be downloaded at: http://www.madx.dk/files/Paths.rar

or

#include <Array.au3>
dim $CurProfile = @ScriptDir & "\general.profile"
dim $SSM2data[9999][999], $m2data[9000][9], $dataokM2[9000], $WMOdata[9000][9], $dataokWMO[9000],$prev[9999],$vervar[999],$VarData[999][999],$closer[9999],$saved[9999], $Point[70][10]
dim $Nearest = 1
dim $begin, $MCINoffs, $MCNKoffs[9999], $Basevaluepointer, $countANA,$ConnectNR[19999],$p[2]

PathToPoint(28)

func PathToPoint($Goal)
;Load Process
local $predist
local $count = 1
local $checker = 0
    while $checker = 0
    $i = $count
    $WPbraker = IniRead($CurProfile,"Waypoints", "WP" & $i,"notfound")
    $WPbraker = stringsplit($WPbraker,"y",1)
    $POSITIONS = stringsplit($WPbraker[1],"x",1)
    $CONNECTION = stringsplit($WPbraker[2],"z",1)
    $Point[$i][1] = $POSITIONS[1] ;X Array Index for later use
    $Point[$i][2] = $POSITIONS[2] ;Y Array Index for later use
    $Point[$i][3] = $POSITIONS[3] ;Z Array Index for later use  
    For $ai = 1 to $CONNECTION[0] Step +1
        $Point[$i][4] = $CONNECTION[0] ;To get ConnectionCount Later On
        $Point[$i][$ai+4] = $CONNECTION[$ai] ;Each Connection
    Next
    $count = $count + 1
    if IniRead($CurProfile,"Waypoints", "WP" & $count,"notfound") = "notfound" then $checker = 1
    WEnd        
    
_ArrayDisplay($Point,"Waypoint List")



;Scan Proces,                           !!!!this is the one that is causing problems!!!!
$StepCount = 0
$Start = $Nearest
;goal = goal
local $LoopNR = 0;This number is to loop through the blacklist list.
$ConnectNR[$StepCount] = $Start ;This is the blacklist
$p[1] = $Start
$StepCount = 1
$CurStep = $Start ;Current Step in the Search
$MainPoints = 1 ;Nr Of Points To Look for connections from
$begin = TimerInit()
while $ConnectNR[$StepCount] not = $Goal
    For $ia = 1 to $MainPoints Step +1
        For $ib = 1 to $Point[$CurStep][4] step + 1; For 1 to The Ammount of Connections retrived in the Load Process
            $Pos = _ArraySearch ($ConnectNR, $Point[$CurStep][$ib+4], 0, 0, 0, True)
            If not @error Then
                ;nothing, this point have been blacklisted.
            Else
                $ConnectNR[$StepCount] = $Point[$CurStep][$ib+4] ;Add the point to the blacklist
                ;ConsoleWrite($P[UBound($P)-1] & @CRLF) ; For Realtime Update of Pathing Discovery
                _ArrayAdd($P,$P[1] & "->"&$Point[$CurStep][$ib+4])
                if $ConnectNR[$StepCount] = $Goal then 
                    $dif = TimerDiff($begin)
                    msgbox(1,"Success","Path Found in: " & ($dif/1000) & " Secs" &@crlf & " Path: " &$P[UBound($P)-1])
                    ConsoleWrite($dif & "Path Found in: " & ($dif/1000) & " Secs" &@crlf)
                    return $P[$ia]
                    ExitLoop
                EndIf
                $StepCount = $StepCount +1
            EndIf
        Next
        _ArrayDelete($P,1)
        $LoopNR = $LoopNR + 1
        $CurStep = $ConnectNR[$LoopNR]
    Next
    $MainPoints = UBound($P)-1
    sleep(1)

if $ConnectNR[$StepCount] = $Goal then 
                    ConsoleWrite($dif& "HURREY!!!" &@crlf)
                    return $P[$ia]
                    ExitLoop
                EndIf
WEnd

EndFunc

General.profile looks like this:

[Waypoints]
WP1=-8748.1025390625x-322.737762451172x79.5110015869141yz2
WP2=-8749.4931640625x-321.183197021484x79.0345077514648y1z3
WP3=-8751.3056640625x-319.926727294922x77.6662063598633y2z4
WP4=-8753.4375x-319.285034179688x76.7867126464844y3z5
WP5=-8755.455078125x-318.70166015625x76.3991012573242y4z6
WP6=-8757.6025390625x-318.141510009766x76.0448989868164y5z7
WP7=-8759.7529296875x-317.59375x75.702522277832y6z8
WP8=-8761.7880859375x-317.075347900391x75.3994903564453y7z9
WP9=-8763.9384765625x-316.527587890625x75.0260162353516y8z10
WP10=-8766.0888671875x-315.979827880859x74.6096267700195y9z11
WP11=-8768.123046875x-315.46142578125x74.0634078979492y10z12
WP12=-8770.158203125x-314.943023681641x73.2332916259766y11z13
WP13=-8772.3544921875x-314.631469726563x72.1579513549805y12z14
WP14=-8774.5546875x-314.340270996094x71.4350891113281y13z15
WP15=-8776.63671875x-314.064636230469x72.1432647705078y14z16
WP16=-8778.84375x-313.772491455078x72.8879699707031y15z17
WP17=-8781.0361328125x-313.482208251953x71.6955642700195y16z18
WP18=-8783.234375x-313.191192626953x71.1632995605469y17z19
WP19=-8785.44921875x-313.229736328125x70.9714126586914y18z20
WP20=-8787.537109375x-313.447723388672x70.7154388427734y19z21
WP21=-8789.63671875x-313.438507080078x70.5976257324219y20z22
WP22=-8791.85546875x-313.407867431641x70.5098342895508y21z23
WP23=-8794.0703125x-313.377258300781x70.4872360229492y22z24
WP24=-8796.2900390625x-313.346618652344x70.5365753173828y23z25
WP25=-8798.5087890625x-313.315979003906x70.4905853271484y24z26
WP26=-8800.6083984375x-313.286987304688x70.4997787475586y25z27
WP27=-8802.8271484375x-313.256317138672x70.4899673461914y26z28
WP28=-8805.0458984375x-313.225677490234x70.5292587280273y27

Edited November 5, 2008 by malu05

malu05 · November 5, 2008

ahh.. seems like to be the array search since it searches $ConnectNR[19999], meaning that there are 19998 empty spots.

malu05 · November 5, 2008

yes...

That fixed it...

Maybe I should do a "for" instead of array search... would be faster afaik.

#include <Array.au3>
dim $CurProfile = @ScriptDir & "\general.profile"
dim $SSM2data[9999][999], $m2data[9000][9], $dataokM2[9000], $WMOdata[9000][9], $dataokWMO[9000],$prev[9999],$vervar[999],$VarData[999][999],$closer[9999],$saved[9999], $Point[70][10]
dim $Nearest = 1
dim $begin, $MCINoffs, $MCNKoffs[9999], $Basevaluepointer, $countANA,$ConnectNR[1],$p[2]

PathToPoint(28)

func PathToPoint($Goal)
;Load Process
local $predist
local $count = 1
local $checker = 0
    while $checker = 0
    $i = $count
    $WPbraker = IniRead($CurProfile,"Waypoints", "WP" & $i,"notfound")
    $WPbraker = stringsplit($WPbraker,"y",1)
    $POSITIONS = stringsplit($WPbraker[1],"x",1)
    $CONNECTION = stringsplit($WPbraker[2],"z",1)
    $Point[$i][1] = $POSITIONS[1] ;X Array Index for later use
    $Point[$i][2] = $POSITIONS[2] ;Y Array Index for later use
    $Point[$i][3] = $POSITIONS[3] ;Z Array Index for later use  
    For $ai = 1 to $CONNECTION[0] Step +1
        $Point[$i][4] = $CONNECTION[0] ;To get ConnectionCount Later On
        $Point[$i][$ai+4] = $CONNECTION[$ai] ;Each Connection
    Next
    $count = $count + 1
    if IniRead($CurProfile,"Waypoints", "WP" & $count,"notfound") = "notfound" then $checker = 1
    WEnd        
    
;_ArrayDisplay($Point,"Waypoint List")

;Scan Process   
$StepCount = 0
$Start = $Nearest
;goal = goal
local $LoopNR = 0;This number is to loop through the blacklist list.
$ConnectNR[$StepCount] = $Start ;This is the blacklist
$p[1] = $Start
$StepCount = 1
redim $ConnectNR[$stepcount+1]
$CurStep = $Start ;Current Step in the Search
$MainPoints = 1 ;Nr Of Points To Look for connections from
$begin = TimerInit()
while $ConnectNR[$StepCount] not = $Goal
    For $ia = 1 to $MainPoints Step +1
        For $ib = 1 to $Point[$CurStep][4] step + 1; For 1 to The Ammount of Connections retrived in the Load Process
            $Pos = _ArraySearch ($ConnectNR, $Point[$CurStep][$ib+4], 0, 0, 0, True)
                    ;nothing
            If not @error Then

                ;nothing, this point have been blacklisted.
            Else
                $ConnectNR[$StepCount] = $Point[$CurStep][$ib+4] ;Add the point to the blacklist
                ;ConsoleWrite($P[UBound($P)-1] & @CRLF) ; For Realtime Update of Pathing Discovery
                _ArrayAdd($P,$P[1] & "->"&$Point[$CurStep][$ib+4])
                if $ConnectNR[$StepCount] = $Goal then 
                    $dif = TimerDiff($begin)
                    msgbox(1,"Success","Path Found in: " & ($dif/1000) & " Secs" &@crlf & " Path: " &$P[UBound($P)-1])
                    ConsoleWrite($dif & "Path Found in: " & ($dif/1000) & " Secs" &@crlf)
                    return $P[$ia]
                    ExitLoop
                EndIf
                $StepCount = $StepCount +1
                redim $ConnectNR[$stepcount+1]
            EndIf
            ;Next
        Next
        _ArrayDelete($P,1)
        $LoopNR = $LoopNR + 1
        $CurStep = $ConnectNR[$LoopNR]
    Next
    $MainPoints = UBound($P)-1
    sleep(1)

if $ConnectNR[$StepCount] = $Goal then 
                    ConsoleWrite($dif& "HURREY!!!" &@crlf)
                    return $P[$ia]
                    ExitLoop
                EndIf
WEnd

EndFunc

Edited November 5, 2008 by malu05

senthor · November 5, 2008

the problem is you're using in total... wait...

$SSM2data[9999][999] means 10000*999 Subs, = 9990000

$m2data[9000][9] 9001*9 = 81009

$dataokM2[9000] = 9001

$WMOdata[9000][9] 9001*9 = 81009

$dataokWMO[9000] = 9001

$prev[9999] = 10000

$vervar[999] = 1000

$VarData[999][999] = 1000*999 = 999000

$closer[9999] = 10000

$saved[9999] = 10000

$Point[70][10] = 71 * 10 = 710

$MCNKoffs[9999] = 10000

$ConnectNR[19999] = 20000

$p[2] = 3

Means u have in total 11230733 Subscripts.

senthor

Sign In

Pathing Optimization [New Question...] (SOLVED!)

Recommended Posts

malu05

malu05

malu05

senthor

Create an account or sign in to comment

Create an account

Sign in

Browse

AutoIt Resources

Release

Beta