Pathfinding System

[D4RK_G4ND4LF]

Finally I succeeded in making a pathfinding system which does not only find a random path but rather the shortest path possible.

The problem that I'm having now is performance. Every time I run it it lags.
Edit:
Buffered some things and improved performance for every run after the first by 10 times but it still lags :S
A faster function for checking if a straight line is not blocked would be nice but every time I try to access the buffered values in that loop it just stops working (operation limit probably).

I'm working on fixing that now and while I'm doing that everyone may have fun with it.
If you've got some ideas to improve it tell me.

It's pretty easy to use with GUI although it is written in JASS (no vJASS)
All one has to do is this:

• Custom script: call InitPathing()

• Test
  • Events
    • Unit - A unit Is issued an order targeting a point
  • Conditions
    • ((Triggering unit) is A ground unit) Equal to True
  • Actions
    • Custom script: set udg_i = FindPath(GetUnitX(GetTriggerUnit()), GetUnitY(GetTriggerUnit()), GetOrderPointX(), GetOrderPointY())
    • Set d = (Load i of 0 from Path)
    • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
      • If - Conditions
        • d Less than 100000.00
      • Then - Actions
        • Game - Display to (All players) the text: (The distance is: + (String(d)))
        • Trigger - Run TraceBack <gen> (checking conditions)
      • Else - Actions

• TraceBack
  • Events
  • Conditions
    • i Not equal to -1
  • Actions
    • Set i2 = (Load i of 4 from Path)
    • Set loc = (Point((Load i of 1 from Path), (Load i of 2 from Path)))
    • Set loc2 = (Point((Load i2 of 1 from Path), (Load i2 of 2 from Path)))
    • Lightning - Create a Drain Mana lightning effect from source loc to target loc2
    • Custom script: call RemoveLocation(udg_loc)
    • Custom script: call RemoveLocation(udg_loc2)
    • Set i = i2
    • Trigger - Run (This trigger) (checking conditions)

This will create a line of lightnings showing the path a unit will take when it is issued to walk somewhere.

Here's the code and a testmap.

function isPathable takes real x, real y returns boolean
    call SetItemPosition(udg_pitem, x, y)
    return GetWidgetX(udg_pitem)==x and GetWidgetY(udg_pitem)==y
endfunction

function isLinePathable takes real x1, real y1, real x2, real y2 returns boolean
    local real dx = x2 - x1
    local real dy = y2 - y1
    local real d = SquareRoot(dx*dx + dy*dy)
    local real s = 0.0
    set dx = dx/d*32.0
    set dy = dy/d*32.0
    loop
        exitwhen s>=d
        set x1 = x1 + dx
        set y1 = y1 + dy
        if not isPathable(x1, y1) then
            return false
        endif
        set s = s + 32.0
    endloop
    return true
endfunction

function visitOtherNodes takes nothing returns nothing
    local real x
    local real y
    local real d
    local boolean b
    local integer i = 0
    local integer n = LoadInteger(udg_Path, 0, 0)
    loop
        exitwhen i>=n
        if i!=udg_i then
            set x = LoadReal(udg_Path, 1, i) - udg_x
            set y = LoadReal(udg_Path, 2, i) - udg_y
            set d = SquareRoot(x*x + y*y) + LoadReal(udg_Path, 0, udg_i)
            if d < LoadReal(udg_Path, 0, i) then
                set x = x + udg_x
                set y = y + udg_y

                if i!=n-1 and udg_i!=n-1 and HaveSavedBoolean(udg_Node, i, udg_i) then
                    set b = LoadBoolean(udg_Node, i, udg_i)
                else
                    set b = isLinePathable(x, y, udg_x, udg_y)
                    call SaveBoolean(udg_Node, i, udg_i, b)
                    call SaveBoolean(udg_Node, udg_i, i, b)
                endif

                if b then
                    call SaveReal(udg_Path, 0, i, d)
                    call SaveInteger(udg_Path, 4, i, udg_i)
                    call SaveInteger(udg_Path, 3, udg_n, i)
                    set udg_n = udg_n + 1
                endif
            endif
        endif
        set i = i + 1
    endloop
endfunction

function FindPath takes real x1, real y1, real x2, real y2 returns integer
    local real x
    local real y
    local boolean b
    local integer n = LoadInteger(udg_Path, 0, 0)
    local integer i = 0

    call SaveReal(udg_Path, 1, -1, x1)
    call SaveReal(udg_Path, 2, -1, y1)
    call SaveReal(udg_Path, 1, n, x2)
    call SaveReal(udg_Path, 2, n, y2)
    set n = n + 1
    call SaveInteger(udg_Path, 0, 0, n)

    set i = 0
    loop
        exitwhen i>=n
        call SaveReal(udg_Path, 0, i, 12345678.0)
        set i = i + 1
    endloop

    set udg_n = 0
    set i = 0
    loop
        exitwhen i>=n
        set x = LoadReal(udg_Path, 1, i)
        set y = LoadReal(udg_Path, 2, i)
        if isLinePathable(x, y, x1, y1) then
            call SaveInteger(udg_Path, 3, udg_n, i)
            call SaveInteger(udg_Path, 4, i, -1)
            set x = x - x1
            set y = y - y1
            call SaveReal(udg_Path, 0, i, SquareRoot(x*x + y*y))
            set udg_n = udg_n + 1
        endif
        set i = i + 1
    endloop

    set i = 0
    loop
        exitwhen i>=udg_n
        set udg_i = LoadInteger(udg_Path, 3, i)
        set udg_x = LoadReal(udg_Path, 1, udg_i)
        set udg_y = LoadReal(udg_Path, 2, udg_i)
        call ExecuteFunc("visitOtherNodes")
        set i = i + 1
    endloop

    set n = n - 1
    call SaveInteger(udg_Path, 0, 0, n)
    call SetItemVisible(udg_pitem, false)
    return n
endfunction

function isEdge takes integer x, integer y returns boolean
    if LoadBoolean(udg_Path, x, y) then
        if LoadBoolean(udg_Path, x+32, y) then
            if LoadBoolean(udg_Path, x, y+32) and not LoadBoolean(udg_Path, x+32, y+32) then
                return true
            endif
            if LoadBoolean(udg_Path, x, y-32) and not LoadBoolean(udg_Path, x+32, y-32) then
                return true
            endif
        endif
        if LoadBoolean(udg_Path, x-32, y) then
            if LoadBoolean(udg_Path, x, y+32) and not LoadBoolean(udg_Path, x-32, y+32) then
                return true
            endif
            if LoadBoolean(udg_Path, x, y-32) and not LoadBoolean(udg_Path, x-32, y-32) then
                return true
            endif
        endif
    endif
    return false
endfunction

function initNodeLine takes nothing returns nothing
    local integer y = R2I(GetRectMinY(bj_mapInitialPlayableArea)) + 16
    local integer Y = R2I(GetRectMaxY(bj_mapInitialPlayableArea))
    local integer n = LoadInteger(udg_Path, 0, 0)
    loop
        exitwhen y>=Y
        if isEdge(udg_xi, y) then
            call SaveReal(udg_Path, 1, n, udg_xi) 
            call SaveReal(udg_Path, 2, n, y)
            set n = n + 1
        else
        endif
        set y = y + 32
    endloop
    call SaveInteger(udg_Path, 0, 0, n)
endfunction

function initPathLine takes nothing returns nothing
    local integer y = R2I(GetRectMinY(bj_mapInitialPlayableArea)) + 16
    local integer Y = R2I(GetRectMaxY(bj_mapInitialPlayableArea))
    loop
        exitwhen y>=Y
        call SaveBoolean(udg_Path, udg_xi, y, isPathable(udg_xi, y))
        set y = y + 32
    endloop
endfunction

function InitPathing takes nothing returns nothing
    local integer X = R2I(GetRectMaxX(bj_mapInitialPlayableArea))
    set udg_Path = InitHashtable()
    set udg_Node = InitHashtable()
    if udg_pitem == null then
        set udg_pitem = CreateItem('ches', 0.0, 0.0)
    endif
    call SetItemInvulnerable(udg_pitem, true)

    set udg_xi = R2I(GetRectMinX(bj_mapInitialPlayableArea)) + 16
    loop
        exitwhen udg_xi>=X
        call ExecuteFunc("initPathLine")
        set udg_xi = udg_xi + 32
    endloop

    call SaveInteger(udg_Path, 0, 0, 0)
    set udg_xi = R2I(GetRectMinX(bj_mapInitialPlayableArea)) + 16
    loop
        exitwhen udg_xi>=X
        call ExecuteFunc("initNodeLine")
        set udg_xi = udg_xi + 32
    endloop

    call SetItemVisible(udg_pitem, false)
endfunction

 

[Pharaoh_]

Ah, nice, this is actually how RPGs work, the objects in the game find the shortest path possible, which also counts every obstacle in the possible way.

 

[Nestharus]

This looks like breadth first, which is bad.


Also your IsPathable is buggy...

See the comments in this pathable library to see why yours bugs: http://www.hiveworkshop.com/forums/jass-functions-413/snippet-pathable-199131/


Do A* Path Finding algorithm. Also use an optimal binary heap where you work with the nodes directly =).


Here is code for optimal binary heap for path finding

globals
    private integer hs=0              //size of heap
    private real array hv             //heap node value
endglobals

//insert value into heap
private function INS takes real v returns nothing
    //allocate heap node
    local integer i=hs+1        //heap node
    local integer p=i/2         //parent
    set hs=i
    
    //loop from bottom up until the inserted value is greater than its parent
    loop
        exitwhen 0==p or hv<=v
        set hv[i]=hv
        set i=p
        set p=p/2
    endloop
    
    //put inserted value into found hv
    set hv[i]=v
endfunction

//remove a value from heap
private function REM takes nothing returns nothing
    local integer l         //left
    local integer r         //right
    local integer i=1       //heap node
    local real v=hv[hs]     //value of replacing heap node (last)
	set hv[hs]=0
    set hs=hs-1             //decrease size of heap
    
    //bubble moved node down
    loop
        set l=i*2       //left
        set r=l+1       //right
        
        //exitwhen at bottom or both children greater than value
        exitwhen (0==hv[l] or v<=hv[l]) and (0==hv[r] or v<=hv[r])
        
        if (0==hv[r] or (0!=hv[l] and hv[l]<hv[r])) then      //move left up
            set hv[i]=hv[l]
            set i=l
        else                                        //move right up
            set hv[i]=hv[r]
            set i=r
        endif
    endloop
    set hv[i]=v
endfunction

Also, it's possible that you will rarely have 2 nodes that have the same distance to the goal, so you could probably get away with < instead of <=. <= is much, much slower than <, so only use <= if you expect a lot of nodes of the same value ; P.


You will always want to read from hv[1]. Once read from hv[1], remove it from the heap. I don't even think you need a hashtable for this =).

 

[watermelon_1234]

This is really neat! Unfortunately, it doesn't seem to take the unit's collision into account.

 

[D4RK_G4ND4LF]

Also your IsPathable is buggy...

See the comments in this pathable library to see why yours bugs: http://www.hiveworkshop.com/forums/jass-functions-413/snippet-pathable-199131/

ah cmon...
I can't believe you never read my comments on isPathable functions

1. I need performance
2. The cases where it might bug are so rare that it's easier to edit the map than changing the code

Collision size definitely is a problem but covering that would make it even slower

Do A* Path Finding algorithm. Also use an optimal binary heap where you work with the nodes directly =).

I don't think that this would be much faster
I've got 200-1000 pathing checks for this one and A* pathing checks become close to infinite for big open regions

Here is code for optimal binary heap for path finding

you also know I don't use vJASS

thanks anyway

 

[Nestharus]

A* would be quite a lot more efficient... rather than branching out in all directions, it would only branch to the shortest directions.

On an unblocked path, the A* pathing algorithm looked at the exact path (no other nodes).



In the worst cases, A* would do the same as breadth-first.



Also, you can easily modify the vjass to be jass >.>. Move the globals into GUI and then put udg in front of them and you're done, lol.

 

[D4RK_G4ND4LF]

A* would be quite a lot more efficient... rather than branching out in all directions, it would only branch to the shortest directions.

On an unblocked path, the A* pathing algorithm looked at the exact path (no other nodes).

In the worst cases, A* would do the same as breadth-first.

I can buffer the results of my algorithm so the only thing I have to do is spread new lines for the start and end nodes towards all edges if I run it a second time
I can't imagine a way of doing that for A*
but I don't think these algorithms are comparable anyway

A* should be faster for short paths so a combination of both algorithms might be best

Also, you can easily modify the vjass to be jass >.>. Move the globals into GUI and then put udg in front of them and you're done, lol.

I appreciate it that you don't force me to use vJASS


I am quite sure that there is an algorithm which suits best for this task but I didn't find it yet and I guess I will have similar issues so I better solve them first and maybe it will be good enough so I don't have to think further
There are other tasks to do