[SNIPPET] Is Line Walkable

[AGD]

IsLineWalkable v1.0b


This simple snippet allows you to check if there are any unwalkable paths such as cliffs, mapboundary and other obstacles such as some doodads between two points.



Requires:
TerrainPathability

Script

library IsLineWalkable uses TerrainPathability/* v1.0b

     ________________
    |                |
    | Written by AGD |
    |________________|


    |=====|
    | API |
    |=====|

        function IsLineWalkable takes real x1, real y1, real x2, real y2 returns boolean
        - Checks if the line between points P1(x1, y1) and P2(x2, y2) does not contain any
          any unwalkable coordinates including some doodads, cliffs, mapboundary, and other similar stuffs

        function GetLastWalkableX takes nothing returns real
        - Returns the value of the x-coordinate of the last walkable terrain when using IsLineWalkable

        function GetLastWalkableY takes nothing returns real
        - Returns the value of the y-coordinate of the last walkable terrain when using IsLineWalkable

*/
    globals
        ///////////////////////////////////////////
        // The path walkability check distance   //
        // interval. Lower value increases       //
        // precision but may cost performance.   //
        // Suggested value limit (10.00 - 25.00) //
        ///////////////////////////////////////////
        private constant real checkInterval = 20.00
    endglobals

    //==============================================================================

    globals
        private real X = 0.00
        private real Y = 0.00
    endglobals

    function IsLineWalkable takes real x1, real y1, real x2, real y2 returns boolean
        local real dx = x2 - x1
        local real dy = y2 - y1
        local real angle
        local real x
        local real y
        if dx*dx + dy*dy < checkInterval*checkInterval then
            if not IsTerrainWalkable(x2, y2) then
                set X = TerrainPathability_X
                set Y = TerrainPathability_Y
                return false
            endif
        else
            set angle = Atan2(dy, dx)
            set x = checkInterval*Cos(angle)
            set y = checkInterval*Sin(angle)
            loop
                set x1 = x1 + x
                set y1 = y1 + y
                exitwhen x1 > x2 or y1 > y2
                if not IsTerrainWalkable(x1, y1) then
                    set X = TerrainPathability_X
                    set Y = TerrainPathability_Y
                    return false
                endif
            endloop
        endif
        set X = TerrainPathability_X
        set Y = TerrainPathability_Y
        return true
    endfunction

    function GetLastWalkableX takes nothing returns real
        return X
    endfunction

    function GetLastWalkableY takes nothing returns real
        return Y
    endfunction


endlibrary

Changelogs

v1.0b
- Replaced the variables IsLineWalkable_X/Y with the functions GetLastWalkableX/Y
- Fixed a bug regarding the values of GetLastWalkableX/Y not being updated if IsLineWalkable returns true
v1.0
- First Release

 

[Chaosy]

I can imagine it being useful, feels like functionality to check if a point is reachable would be a logical addition.
Not sure if that has been done elsewhere.

 

[AGD]

feels like functionality to check if a point is reachable would be a logical addition.

If I understood correctly, IsLineWalkable will return true if the point is reachable and false if not.

 

[FUJI]

After searching if theres any similar to this and surprisingly theres actually none.

Useful well made system. If only you made it compatible with vanilla ( but the TerrainPathability is strictly required so it would only make it complicated to do so especially coding that pathability ). Its pretty unique and nice idea, ( Hopefully vJass coders gonna use this ^^ )

 

[AGD]

After searching if theres any similar to this and surprisingly theres actually none.

But I thought I've seen something with similar title to this, I'm not sure though, I did not look carefully. I made this because I need this in my spell I couldn't also find one.

If only you made it compatible with vanilla

Do you hardly need a vanilla jass version?

 

[FUJI]

If you can but I think theres no need to. If you really want then do it so it will make your system friendly and also increases its usage.

 

[Chaosy]

@AGD
Your only checks pathing in a line, if it can be reached through other routes..?

I did not read the code, but I assume that is what it does.

 

[AGD]

Your only checks pathing in a line, if it can be reached through other routes..?

I understand now, perhaps I will include that in my updates if I can.

EDIT:
Updated to v1.0b
- Replaced the variables IsLineWalkable_X/Y with the functions GetLastWalkableX/Y
- Fixed a bug regarding the values of GetLastWalkableX/Y not being updated if IsLineWalkable returns true

feels like functionality to check if a point is reachable would be a logical addition.

I'm not sure if this is possible, take for example a very complex maze. In this case the system has to check every possible routes before it can tell if it's walkable. I'm not sure though.

 

[IcemanBo]

It's an useful wrapper around the patching check function, but it's too simple to write a linear search with a constant offset by your own I guess.
We could add it though to small code snipptets if you would like to.

 

[AGD]

We could add it though to small code snipptets if you would like to.

Its perfectly okay with me =). Btw, I'm thinking of having this combined with my BoundCoordinates so that instead of making sure that the unit's coordinates will be set within the map boundary, it will ensure that the unit's position will be set to a walkable terrain.

 

[IcemanBo]

As an code example you mean? If you would like to add it to the initial post we could then just move the whole post there. It can be default line check, and then also a code in combination with the other code if you want.

 

[AGD]

As an code example you mean? If you would like to add it to the initial post we could then just move the whole post there. It can be default line check, and then also a code in combination with the other code if you want.

I mean I think of having the two on a single library, not sure if its a good idea though.

 

[Zwiebelchen]

Bresenham Pathchecker is better because it actually checks on a per-cell basis (avoiding false positives for near-edge IsTerrainWalkable checks) and does not spam trigonometric functions.

 

[Veritas 117]

I've been thinking about making a blink-strike ability for my campaign but I didn't want it to be able to be exploited by blinking through blocked areas to reach enemies on the other side before you should be able to. This kind of thing would be perfect for that. Same can be said for a leap-type ability.

That being said it could be annoying if there is something like a barrel between your unit and the enemy that stops you from casting it..

 

[AGD]

Bresenham Pathchecker

But I thought I've seen something with similar title to this, I'm not sure though, I did not look carefully. I made this because I need this in my spell I couldn't also find one.

So this is that I've seen once. Now I remember looking for this kind resource, I couldn't believe it was just in the submission section all along.
Btw, I dont get the difference, isn't the method here also like checking a per cell basis?

 

[Zwiebelchen]

No, this one checks on a flat per-distance basis, which means you will end up checking the same cell twice or even three times, depending on the angle.

Also, the solution used here has no diagonal safety feature, which means depending on the angle and the pathing blockers, you might end up with a false positive (i.e. for the diagonal fence doodad).

 

[AGD]

I see, still you can just lessen the value of the distance interval check. However, the method you mentioned is better.

 

[AGD]

I think this can be graveyarded now. The above mentioned library Bresenham Pathchecker has a better implementation and indeed mine fails on near cliff edges no matter how small the distance check interval is.

 

[IcemanBo]

Alright, thanks for info. Just say if something new comes up.

Moving to grayeyard, see thread.