Jump to content

Pathing Optimization [New Question...]


malu05
 Share

Recommended Posts

Hey, im currently working on a pathing UDF for one of my projects.

Im using a Dijkstra like algorithm for the traveling. So to get that working I need the points and I need their connections.

My current "network waypoint" system is like this:

WayPointNr,X,Y,Z,CONN[$nr],...

The CONN[$nr] is all the other waypoints that the waypoint is connected to...

Here is an example:

WP123=  -6196.13720703125x  378.242065429688x   391.027069091797y   122z    124
WP124=  -6194.107421875x    378.781951904297x   391.594482421875y   123z    125
WP125=  -6192.0712890625x   379.323638916016x   392.103485107422y   124z    126
WP126=  -6190.0419921875x   379.863525390625x   392.736999511719y   125z    127
WP127=  -6188.0126953125x   380.403411865234x   393.381072998047y   126z    128

WP124 is connected to 123 and 125.

The letters XYZ is my seperators used for splitting.

That is no problem at all, the problem is when I record the points. Lets say I have a certain speed and it records every 2 feet. This offcause require autoIT to record a path and be ready to add the next one within 2 feet's travel time. And since the points have a connection tolerance of 3 yards it must be recorded within that time.

When I want to record my pathing I have to check up my current position contra all the other points to see if there are any that are close enough to make a connection (3 feet).

When doing that with 1000 points is no problem, autoIT is fast enough to look through them all, calculate the distance and point out the ones that are within 3 feet. But when I near myself 2000 points to check, the down time is longer than the time it takes to set one point and therefore connections are dropping, like seen here:

WP1413= -5932.357421875x    -71.7599258422852x  383.203063964844y   1412z1414
WP1414= -5933.65576171875x  -74.8892440795898x  384.072021484375y   1413
WP1415= -5935.35107421875x  -77.9134674072266x  385.077697753906y   1416        
WP1416= -5937.384765625x    -80.472770690918x   386.123870849609y   1415
WP1417= -5939.18798828125x  -83.331657409668x   387.329650878906y;this point have no connections... =(
WP1418= -5940.58154296875x  -86.5255966186523x  388.476745605469y

So instead of checking against all points at the same time I wanted to check up on like the 200 closest points then updating that "closest" list every 10 sec's or so.

Now the problem is that updating this "closest" list will still take too long and so that every 10sec there will be a connection drop.

Any suggestions on how to solve this problem?

Edited by malu05

[center][u]WoW Machinima Tool[/u] (Tool for Machinima Artists) [/center]

Link to comment
Share on other sites

Hey, im currently working on a pathing UDF for one of my projects.

Im using a Dijkstra like algorithm for the traveling. So to get that working I need the points and I need their connections.

My current "network waypoint" system is like this:

WayPointNr,X,Y,Z,CONN[$nr],...

The CONN[$nr] is all the other waypoints that the waypoint is connected to...

Here is an example:

WP123=  -6196.13720703125x  378.242065429688x   391.027069091797y   122z    124
WP124=  -6194.107421875x    378.781951904297x   391.594482421875y   123z    125
WP125=  -6192.0712890625x   379.323638916016x   392.103485107422y   124z    126
WP126=  -6190.0419921875x   379.863525390625x   392.736999511719y   125z    127
WP127=  -6188.0126953125x   380.403411865234x   393.381072998047y   126z    128

WP124 is connected to 123 and 125.

The letters XYZ is my seperators used for splitting.

That is no problem at all, the problem is when I record the points. Lets say I have a certain speed and it records every 2 feet. This offcause require autoIT to record a path and be ready to add the next one within 2 feet's travel time. And since the points have a connection tolerance of 3 yards it must be recorded within that time.

When I want to record my pathing I have to check up my current position contra all the other points to see if there are any that are close enough to make a connection (3 feet).

When doing that with 1000 points is no problem, autoIT is fast enough to look through them all, calculate the distance and point out the ones that are within 3 feet. But when I near myself 2000 points to check, the down time is longer than the time it takes to set one point and therefore connections are dropping, like seen here:

WP1413= -5932.357421875x    -71.7599258422852x  383.203063964844y   1412z1414
WP1414= -5933.65576171875x  -74.8892440795898x  384.072021484375y   1413
WP1415= -5935.35107421875x  -77.9134674072266x  385.077697753906y   1416        
WP1416= -5937.384765625x    -80.472770690918x   386.123870849609y   1415
WP1417= -5939.18798828125x  -83.331657409668x   387.329650878906y;this point have no connections... =(
WP1418= -5940.58154296875x  -86.5255966186523x  388.476745605469y

So instead of checking against all points at the same time I wanted to check up on like the 200 closest points then updating that "closest" list every 10 sec's or so.

Now the problem is that updating this "closest" list will still take too long and so that every 10sec there will be a connection drop.

Any suggestions on how to solve this problem?

Big picture first: AutoIt is an interpreted scripting language. It is surprisingly fast for such a tight little run-time module, but it will never be as fast as a true compiled language like C++. If you really need top number crunching performance, AutoIt is not the right tool.

That said, your string storage with "... letters XYZ is my seperators used for splitting" is going to make it much slower than it could be. Make that a 2D array and access will be much faster:

; 2D array of way points:
; [0][0] = Count
; [n][0] = x
; [n][1] = y
; [n][2] = z
; [n][3] thru [n][10] = up to 8 connected way point indexes (null for unused connections)
Global $avWayPoints[2000][11]

; Set a typical wap point's data
$avWayPoints[125][0] = -6192.0712890625
$avWayPoints[125][1] = 379.323638916016
$avWayPoints[125][2] = 392.103485107422
$avWayPoints[125][3] = 124
$avWayPoints[125][4] = 126

; Retrieve data for a way point
$iWP = 125
$sMsg = "Way point index " & $iWP & ":  X = " & $avWayPoints[$iWP][0] & ", Y = " & _
        $avWayPoints[$iWP][1] & ", Z = " & $avWayPoints[$iWP][2] & @LF
For $n = 3 To 10
    If $avWayPoints[$iWP][$n] = "" Then ExitLoop
    $sMsg &= "Connection " & $n - 2 & ":  " & $avWayPoints[$iWP][$n] & @LF
Next
ConsoleWrite($sMsg)

:mellow:

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
Link to comment
Share on other sites

Big picture first: AutoIt is an interpreted scripting language. It is surprisingly fast for such a tight little run-time module, but it will never be as fast as a true compiled language like C++. If you really need top number crunching performance, AutoIt is not the right tool.

That said, your string storage with "... letters XYZ is my seperators used for splitting" is going to make it much slower than it could be. Make that a 2D array and access will be much faster:

; 2D array of way points:
; [0][0] = Count
; [n][0] = x
; [n][1] = y
; [n][2] = z
; [n][3] thru [n][10] = up to 8 connected way point indexes (null for unused connections)
Global $avWayPoints[2000][11]

; Set a typical wap point's data
$avWayPoints[125][0] = -6192.0712890625
$avWayPoints[125][1] = 379.323638916016
$avWayPoints[125][2] = 392.103485107422
$avWayPoints[125][3] = 124
$avWayPoints[125][4] = 126

; Retrieve data for a way point
$iWP = 125
$sMsg = "Way point index " & $iWP & ":  X = " & $avWayPoints[$iWP][0] & ", Y = " & _
        $avWayPoints[$iWP][1] & ", Z = " & $avWayPoints[$iWP][2] & @LF
For $n = 3 To 10
    If $avWayPoints[$iWP][$n] = "" Then ExitLoop
    $sMsg &= "Connection " & $n - 2 & ":  " & $avWayPoints[$iWP][$n] & @LF
Next
ConsoleWrite($sMsg)

:mellow:

About the language, its 100% for the chalange... its fun to see how much you can push out of this. Limitations is a charm imo.

I think I might have pointed it out wrong. Its only the "file" format that uses the separators.

When I load a profile all the points are put into variables so it does it all in the memory.

Here is a example of my connection code:

func _AddCurToList()
local $PathConnections[1000] ;Max Connections 
local $AddConnections 
local $NOADD = 0
    $WaypointNR = $WaypointNR + 1
    $GetPosX = _MemoryRead("0x" & hex($memoryx), $DllInformation, 'float')  ;GetX
    $GetPosY = _MemoryRead("0x" & hex($memoryy), $DllInformation, 'float')  ;GetY
    $GetPosZ = _MemoryRead("0x" & hex($memoryz), $DllInformation, 'float')  ;GetZ
    _report("Waypoint: "&floor($GetPosX)&","&floor($GetPosY)&","&floor($GetPosZ) & " added.")
if IniRead($CurProfile,"Waypoints", "WP" & 1,"notfound") = "notfound" Then ;Check if there are any waypoints in the data file. If not there is no connections to be made.
    $AddConnections = "" ;No connections
Else
    local $connections = 0
    local $count = 1
    local $checker = 0
    while $checker = 0
        $i = $count
            $dx = $GetPosX-$WPX[$i];X
            $dy = $GetPosY-$WPY[$i];Y
            $dz = $GetPosz-$WPZ[$i];Z
            $NPCDistancelist[$i] = sqrt($dx*$dx + $dy*$dy + $dz*$dz)
            if $NPCDistancelist[$i] < 3.5 Then ;Distance Connection Threshold...
                if $NPCDistancelist[$i] < 2 Then ;IF The point are within 2 feet of last point there is no need to add a new one. 
                    $NOADD = 1 
                    $WaypointNR = $WaypointNR - 1 ;Substract the waypoint we though we were going to add....
                    ExitLoop
                EndIf
                $connections = $connections + 1 ;NR Of ConnectionsCalc
                $PathConnections[$connections] = $i ;What it connects to
                $PathConnections[0] = $connections ;NR Of Connections
                
            EndIf
            $count = $count + 1
            if $WaypointNR = $count then $checker = 1
    WEnd    

if $NOADD = 1  Then

Else
For $i = 1 to $PathConnections[0] Step +1
    if $PathConnections[0] - $i = 0 Then ;Don't Add a seperator if it is the last connection.
        $AddConnections = $AddConnections & $PathConnections[$i]
        $WPbraker = IniRead($CurProfile,"Waypoints", "WP" & $PathConnections[$i],"notfound")
        IniWrite($CurProfile, "Waypoints", "WP" & _ 
        $PathConnections[$i], $WPbraker & "z" & $WaypointNR)
    Else
        $AddConnections = $AddConnections & $PathConnections[$i] & "z"
        $WPbraker = IniRead($CurProfile,"Waypoints", "WP" & $PathConnections[$i],"notfound")
        IniWrite($CurProfile, "Waypoints", "WP" & _ 
        $PathConnections[$i], $WPbraker & "z" & $WaypointNR) ;UPDATE FILE
    EndIf
Next
EndIf
EndIf           
if $NOADD = 1  Then     
;nothing, this point should not be added.
Else        
    ;WRITE TO MEMORY.. This could also be a 2D array^^
    $WPX[$WaypointNR] = $GetPosX
    $WPY[$WaypointNR] = $GetPosY
    $WPZ[$WaypointNR] = $GetPosZ
    ;PUT IN FILE
    IniWrite($CurProfile, "Waypoints", "WP" & _ 
    $WaypointNR, $GetPosX&"x"&$GetPosY&"x"&$GetPosZ _
    & "y        " & $AddConnections)
EndIf
$NOADD = 0

GUICtrlSetData($UIConnection,$PathConnections[0])
GUICtrlSetData($UIWaypointCount,$WaypointNR)
Endfunc

[center][u]WoW Machinima Tool[/u] (Tool for Machinima Artists) [/center]

Link to comment
Share on other sites

found out what caused the hangup....

if IniRead($CurProfile,"Waypoints", "WP" & $count,"notfound") = "notfound" then $checker = 1

replaced with

if $WaypointNR = $count then $checker = 1

Now I can go beyond 10000 connections...

Much much better.

[center][u]WoW Machinima Tool[/u] (Tool for Machinima Artists) [/center]

Link to comment
Share on other sites

found out what caused the hangup....

if IniRead($CurProfile,"Waypoints", "WP" & $count,"notfound") = "notfound" then $checker = 1

replaced with

if $WaypointNR = $count then $checker = 1

Now I can go beyond 10000 connections...

Much much better.

An INI file is a poor choice for this function, but if you got it working... go with it until it breaks.

:mellow:

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
Link to comment
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
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...