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

Link to comment

Share on other sites

malu05

Link to comment

Share on other sites

malu05

Link to comment

Share on other sites

senthor

Link to comment

Share on other sites

Create an account or sign in to comment

Create an account

Sign in

Recently Browsing 0 members

Browse

AutoIt Resources

Release

Beta