[system] Pathing Algorithm System

// ==================================================================================
// Pathing Algorithm System - by Ammorth                                Feb 17, 2010
//    **Requires JassHelper (vJass) to compile**
//    Requires: LinkedList (by Ammorth, at wc3c)
//              LineSegment (by Ammorth, at wc3c)
//
// about:
//   Pathing Algorithm System (PAS) can be used to construct a set of "roads" and
//   generating paths through the nodes.  These paths can then be utilized to create
//   dynamic systems.  For example, the PASMovement and PASGPS libraries utilize the
//   paths generated from PAS to move units and provide a GPS-like arrow.
//
// Requirements:
//   - LinkedList (by Ammorth, at wc3c)
//   - LineSegment (by Ammorth, at wc3c)
//
// Installation:
//   - Create a new trigger called PAS
//   - Copy this code to the new trigger
//   
// Setup:
//   - Make sure the textmacro for the object merger line provides a unique rawcode id to your map
//     (aka, if 'pasn' conflicts with another unit in your map, change it to something else)
//   - Setup the node data (read Setting Up Nodes)
//
// Function List:
//   Node.add(integer id, real x, real y, string linkData, real size) -> PAS_Node *
//   Node.addRect(integer id, rect whichRect, string linkData, real size) -> PAS_Node *
//   PAS_Node[id] -> PAS_Node
//   PAS_Node.getNearest -> PAS_Node
//   PAS_Node.changeWeight(integer link, real weight) -> nothing
//   PAS_Node.changeWeightForNode(PAS_Node for, real weight) -> nothing
//   PAS_Node.setLinkEnabled(integer link, boolean enabled) -> nothing
//   PAS_Node.setLinkEnabledForNode(PAS_Node for, boolean enabled) -> nothing
//   PAS_GetPath(real startx, real starty, real endx, real endy) -> PAS_Path
//
//   * The PAS prefix isn't required for Node.add/.addRect as they are used within the PAS library exclusively
//
// Setting Up Nodes:
//   You can add nodes with 2 functions:
//
//     call Node.add(integer ID, real x, real y, string nodeData, real size)
//
//   or
//
//     call Node.addRect(integer ID, rect r, string nodeData, real size)
//
//   The only difference is one takes a rect and the other takes a cordinate.
//   I find laying out your nodes with rects and then using the rect method is much
//   easier than via cordinates.  Although, if someone would rather use cordinates
//   the option is there aswell.
//
//   Nodes should only be added in the specified location within the setup portion
//   of this script.  Any other location will cause errors!  Aswell, you cannot call
//   .add or .addRect outside of this PAS main library, so your hands are tied!
//
//   Integer ID is the node ID.  This is how you can tell each node apart.  Each ID
//   needs to be a unique, positive value from 1 to MAX_NODES and you must create a
//   node for each possible ID between 1 and MAX_NODES.  The easiest way to do this is
//   to start at 1 and work your way up.  MAX_NODES can then be changed to the last ID.
//   
//   The rect or cordinates specify the location of the node.  As you can seen in this
//   testmap, I have placed nodes at all the major intersections.
//
//   The nodeData string is by far the trickest to setup.  It contains all the data
//   required for each node, to generate the edges between nodes.  The format is as
//   follows:
//
//     "Node=Weight-Node=Weight-Node=Weight..."
//
//   Breaking this down to one Node we get:
//
//     "Node=Weight"
//
//   The "Node" is the ID number of the node we wish to create a link to
//   The "Weight" is a real value to multiply the distance between nodes by, to make
//   node links act as if they were longer or shorter.  Example:
//
//     "1-4=0.5-6=1.2"
//
//   Links this node to 1 (with a default weight), 4 (with a weight of 0.5) and 6 (with
//   a weight of 1.2)
//
//   The default weight for a node is 1.0.  As you can see from the example, leaving out
//   the "=Weight" part in the string gives it a deault weight of 1.0.  You can use a 
//   combination of nodes with weights and nodes without.
//
//   A weight of 1 is normal, a weight of 0 is as if the nodes were at the same point
//   and a weight of a very large number (think infinity) is if there was no link between
//   the nodes.  Weights are powerful as you can make roads that are used less-frequent
//   or more-frequent by increasing or decreasing their weight.  Keep in mind, a weight of
//   a large value still allows a unit to path through it, just only if no other paths with
//   less combined weight exist.  If you don't want units to path through, you can disable
//   a link after setup (check the PAS_Node struct section).
//
//   In short: "Node" is the ID of the node to link to
//             use "-" to separate nodes
//             if you want to add a weight, use "=Weight"
//
//   The real size is the radius of a node.  Some systems may use this to determine the
//   distance from a node or if a unit is at a node.  For example, PASMovement utilizes
//   node sizes to check for units at active nodes.  If a value below NODE_MIN_SIZE is
//   passed, the node will get the size NODE_DEFAULT_SIZE (both can be changed, although
//   there will be errors if NODE_MIN_SIZE <= 0.
//
//   Once you have setup your nodes.  You should take a look through all the constants
//   to make sure everything is set how you like it.  A quick breakdown for each value
//   can be found in the globals section
//
// The PAS_Node struct:
//   Within these structs, you can get access to their position, size, links, etc...
//   You can get a PAS_Node struct either via:
//
//     PAS_Node[id]
//
//   which will return the raw node for the specified ID number or:
//
//     PAS_Node.getNearest(x, y)
//
//   which will return the nearest node at the given point.
//
//   The data included in the PAS_Node struct is as follows:
//
//     real x
//     real y
//     unit marker
//     PAS_Node array links
//     real array linkLength
//     real array linkWeight
//     boolean array linkEnabled
//     integer linkSize
//     real nodeSize
//     integer id
//
//   x and y are the cordinates of the node.
//
//   marker is the dummy unit which is used to get nearby nodes/edges
//
//   links are the PAS_Nodes this node is linked to
//
//   linkLength is the weighted distance between the nodes, relative to this node
//
//   linkWeight is the weight between the nodes, relative to this node
//
//   linkEnabled is a boolean which is true if the link is enabled or false if disabled,
//   relative to this node
//
//   linkSize is the number of links this node links to
//
//   nodeSize is the size of the node, set by the Node.create() function
//
//   id is the unique id number of this node (which you also set in Node.create()
//
//   You usually only need to use .x, .y, .nodeSize and .id, but the others are there as well.
//   You shouldn't remove or kill the marker unit, or you won't be able to find nearby nodes
//   and edges.
//
//   You can use the following methods to change the weight of a link:
//
//     PAS_Node.changeWeight(integer i, real weight)
//
//   or
//
//     PAS_Node.changeWeightForNode(PAS_Node node, real weight)
//
//   The first one takes the link index while the second takes a node and will find the link
//   index for you, if it exists.
//
//   As well, you can use the following methods to enable or disable links:
//
//     PAS_Node.setLinkEnabled(integer i, boolean enabled)
//
//   or
//
//     PAS_Node.setLinkEnabledForNode(PAS_Node node, boolean enabled)
//
//   Again, the first method takes a link index while the second takes a node.
//
//   There are a few limitations to changing weights and enabling/disabling links.  You cannot 
//   change weights or disable links within the node setup function (changes will be over-written).
//   Any path that was generated before the change and is still being used by a system, will
//   not update or change paths to reflect changes.  Therefore, you could have units moving
//   between nodes which you have since disabled the links for.  You can't create links after
//   the system is initialized, but you can disable links you setup.  Keep this in mind when 
//   you setup your paths.
//
//   Also, keep in mind, links are local to the node they originate from.  Changing the weight
//   of the link from node A to B does not change the weight from node B to A.  Similarly,
//   disabling (or even creating a link at setup) from node A to B does not mean B to A changed
//   as well.
//   
// The PAS_Path struct:
//   The PAS_Path struct has a fair bit of data that can be used to do whatever you want.
//   It is not recommended to change any values of the PAS_Path struct other than calling
//   .destroy() once you are done.  You can get a PAS_Path struct using the following
//   funtion:
//
//     function PAS_GetPath takes real startx, real starty, real endx, real endy returns PAS_Path
//
//   The arguments should be self-explanitory.  The path generated will provide you with information
//   on how to traverse the nodes you set up, going from start to end.  From there, it is up to the
//   plugin to use the data to do whatever.
//
//   The data included in the PAS_Path struct is as follows:
//
//     Point start
//     Point end
//     Point nearStart
//     Point nearEnd
//     List nodes
//
//   All of the Point objects have both a real x and a real y component which are accessed
//   via:
//
//     Point.x
//
//   and
//
//     Point.y 
//
//   The start point and end point are the cordinates you passed to the PAS_GetPath function.
//   The nearStart is the nearest point on the nearest edge to your start point.  The nearEnd
//   is the nearest point on the nearest edge to the end point.  Think of these as entrance and
//   exit points.  To get into the paths from start.x and start.y, you need to go to nearStart.x
//   and nearStart.y.  Once you are there, you are on an edge, and can now move to the first node.
//   Once you get to the last node, nearEnd.x and nearEnd.y are the cordinated to the closest
//   point to your endpoint on the edge.  If you still don't get what I mean, you could most likely
//   ignore them.
//
//   nodes is a Linked List of all the nodes between .nearStart and .nearEnd.  The nodes are in
//   order from start to end, where .nodes.first is the first node and .nodes.last is the last node.
//   the nodes are stored as their raw values and not as their ID values.  So, you can cast link.data
//   directly into a PAS_Node using PAS_Node(link.data).  From there, you can access anything you want
//   about the node (.x, .y, .nodeSize, .id, etc...).  You will need to be familiar with how
//   LinkedList works to be able to read the nodes.
//
//   Once you are done with a path, call .destroy() on the path to clean it up.  This will remove all
//   points and the linkedlist aswell.
//
// Notes:
//   Although PAS has be re-designed and coded to be as fast as possible, PAS_GetPath is still an 
//   expensive function to call.  Therefore, if you find you need to move many units at once, use
//   a quick periodic timer or use .evaluate() to create new threads to run PAS_GetPath in.
//
// Changelog:
//
//  PAS 3.1
//   Added functionality for changing link weights after setup
//   Added functionality for enabling and disabling links after setup
//   Made objects private/read-only where applicable (mostly PAS_Node objects)
//   Added function lists to all the script and plugins
//   Added Object Merger macros to create units in the object editor
//   PASMove: Changed the plugin name from PASMovement to PASMove (shorter)
//   PASMoveSafety: Changed the plugin name from PASMovementSaftey to PASMoveSafety (shorter)
//   PASGPS: Added installation instruction about the custom model and changed the paths for the model
//   PASGPS: The system will now register arriving at the end even if you didn't take the recommended path
//
//  PAS 3.0
//   Complete re-write from PAS 2.40
//
// ==================================================================================
library PAS initializer onInit requires LinkedList, LineSegment
// ==================================================================================
//
//  Start Object Merger Line
//
// set the value inside the quotes to a unique rawcode that isn't used in your map
//! runtextmacro PAS_MARKER_ID("pasn")
//  
//  This will auto-generate a unit in the object editor as well as asign the global
//  PAS_MARKER_ID to the value here.
//
//  End Object Merger Line
//
// ==================================================================================
globals
// ==================================================================================
//  Start of Setup
//
//  Start of Constant Globals

// the maximum number of Nodes you have setup
    public constant integer MAX_NODES = 48 // cannot be larger than 8190
    
// the maximum number of Links a node can have
    public constant integer MAX_LINKS = 4 // limits the number of nodes to 8192/MAX_LINKS
        
// the minimum size a node can be.      
    public constant real NODE_MIN_SIZE = 32 // values less than this will get NODE_DEFAULT_SIZE
    
// the defualt size of a node, if the sized passed is less than the minimum size
    public constant real NODE_DEFAULT_SIZE = 128
    
// the test radius from a point to find near-by nodes with PAS_Node.getNearest()
    public constant real NODE_TEST_RANGE = 1024
    
// the test radius from a point to find an edge with PAS_Edge.getNearest()
// because edges can be long, and only the nodes can truely be found (units are placed at nodes)
// this number should be large enough to find a node on the nearest edge.
// aka, if the longest distance between 2 nodes is 1024, this should be slightly greater than 512
// which is half of the distance.  When the point is directly between the nodes, on the edge, 512
// will get both nodes of the edge.  Since it is hard for units to be directly on an edge (they deviate)
// it should be larger than 512, so a value of 640 may be better.  Try experimenting with finding the
// smallest value that provides no "dead-points" (can't find the nearest edge).  Remember, larger values
// of this will increase the calculations required as many nodes could be found if they are tight-together.
    public constant real LINK_TEST_RANGE = 2560
    
// while debugging, sometimes it is nice to see which nodes a generated path will visit.  Setting this
// to true will provide you with a print-out of the points passed and the nodes contained in the path        
    private constant boolean DEBUG_SHOW_PATHS = false // only works if Debug Mode is enabled in JassHelper
    
//
//  End of Constant Globals 
//
// ==================================================================================   
    endglobals

public keyword Node
private keyword Edge
private keyword add // haha! try using these methods outside of PAS now!
private keyword addRect
    private function SetupNodes takes nothing returns nothing
// ================================================================================== 
//
//  Start of Setting up Nodes 
//

        // nodes up to 28 are main roads, set their weight to 0.5 to use them more than back-roads
        call Node.addRect(1, gg_rct_Rect_001, "2=0.5-24=0.5", 128)
        call Node.addRect(2, gg_rct_Rect_002, "1=0.5-3=0.5-29", 128)
        call Node.addRect(3, gg_rct_Rect_003, "2=0.5-4=0.5-26=0.5", 128)
        call Node.addRect(4, gg_rct_Rect_004, "3=0.5-5=0.5", 128)
        call Node.addRect(5, gg_rct_Rect_005, "4=0.5-6=0.5-48", 128)
        call Node.addRect(6, gg_rct_Rect_006, "5=0.5-7=0.5-44", 128)
        call Node.addRect(7, gg_rct_Rect_007, "6=0.5-8=0.5-47", 128)
        call Node.addRect(8, gg_rct_Rect_008, "7=0.5-9=0.5-45", 128)
        call Node.addRect(9, gg_rct_Rect_009, "8=0.5-10=0.5", 128)
        call Node.addRect(10, gg_rct_Rect_010, "9=0.5-11=0.5", 128)
        call Node.addRect(11, gg_rct_Rect_011, "10=0.5-12=0.5", 128)
        call Node.addRect(12, gg_rct_Rect_012, "11=0.5-13=0.5", 128)
        call Node.addRect(13, gg_rct_Rect_013, "12=0.5-14=0.5", 128)
        call Node.addRect(14, gg_rct_Rect_014, "13=0.5-15=0.5-46", 128)
        call Node.addRect(15, gg_rct_Rect_015, "14=0.5-16=0.5", 128)
        call Node.addRect(16, gg_rct_Rect_016, "15=0.5-17=0.5-28=0.5", 128)
        call Node.addRect(17, gg_rct_Rect_017, "16=0.5-18=0.5", 128)
        call Node.addRect(18, gg_rct_Rect_018, "17=0.5-19=0.5-25=0.5", 128)
        call Node.addRect(19, gg_rct_Rect_019, "18=0.5-20=0.5-36", 128)
        call Node.addRect(20, gg_rct_Rect_020, "19=0.5-21=0.5", 128)
        call Node.addRect(21, gg_rct_Rect_021, "20=0.5-22=0.5", 128)
        call Node.addRect(22, gg_rct_Rect_022, "21=0.5-23=0.5", 128)
        call Node.addRect(23, gg_rct_Rect_023, "22=0.5-24=0.5-25=0.5", 128)
        call Node.addRect(24, gg_rct_Rect_024, "23=0.5-1=0.5-29", 128)
        call Node.addRect(25, gg_rct_Rect_025, "18=0.5-23=0.5-35-36", 128)
        call Node.addRect(26, gg_rct_Rect_026, "3=0.5-27=0.5-37", 128)
        call Node.addRect(27, gg_rct_Rect_027, "26=0.5-28=0.5-32", 128)
        call Node.addRect(28, gg_rct_Rect_028, "27=0.5-16=0.5-33-42", 128)
        
        call Node.addRect(29, gg_rct_Rect_029, "2-24-30", 64)
        call Node.addRect(30, gg_rct_Rect_030, "29-31-33", 64)
        call Node.addRect(31, gg_rct_Rect_031, "30-32", 64)
        call Node.addRect(32, gg_rct_Rect_032, "31-27", 64)
        call Node.addRect(33, gg_rct_Rect_033, "30-34-28", 64)
        call Node.addRect(34, gg_rct_Rect_034, "33-35", 64)
        call Node.addRect(35, gg_rct_Rect_035, "34-25", 64)
        call Node.addRect(36, gg_rct_Rect_036, "19-25", 64)
        call Node.addRect(37, gg_rct_Rect_037, "26-38", 64)
        call Node.addRect(38, gg_rct_Rect_038, "37-39", 64)
        call Node.addRect(39, gg_rct_Rect_039, "38-40", 64)
        call Node.addRect(40, gg_rct_Rect_040, "39-41", 64)
        call Node.addRect(41, gg_rct_Rect_041, "40-42-43", 64)
        call Node.addRect(42, gg_rct_Rect_042, "41-45-28", 64)
        call Node.addRect(43, gg_rct_Rect_043, "41-44", 64)
        call Node.addRect(44, gg_rct_Rect_044, "6-43", 64)
        call Node.addRect(45, gg_rct_Rect_045, "8-42-46", 64)
        call Node.addRect(46, gg_rct_Rect_046, "14-45", 64)
        call Node.addRect(47, gg_rct_Rect_047, "7-48", 64)
        call Node.addRect(48, gg_rct_Rect_048, "5-47", 64)
//
//  End of Setting up Nodes
//
//  End of Setup
//
// ==================================================================================      
    endfunction
    
    private function Error takes string msg returns nothing
        debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "PAS Error: "+msg)
    endfunction
    
    private function isNodeFunc takes nothing returns boolean
        return GetUnitTypeId(GetFilterUnit()) == MARKER_ID
    endfunction

//! textmacro PAS_MARKER_ID takes VALUE
//! external ObjectMerger w3u hfoo $VALUE$ uabi ACmi,Avul umdl .mdl ushu "" uaen "" utar "" umvs 0 umvt fly ucol 0 ufoo 0 uhom 1 uhpm 99999 uhpr 99999 upgr "" unam "PAS Marker"
    globals
        public constant integer MARKER_ID = '$VALUE$'
    endglobals
//! endtextmacro
    
    globals
        private constant hashtable storage = InitHashtable()
        private constant integer MAX_STRUCT = MAX_LINKS*MAX_NODES
        private constant integer getNode = -1
        private constant integer getLink = -2
        private constant group TempGroup = CreateGroup()
        private boolexpr isNode = null
    endglobals
    
    public struct Point // easier than having so many reals...
        real x
        real y
        
        static method create takes real x, real y returns thistype
            local thistype this = thistype.allocate()
            set .x = x
            set .y = y
            return this
        endmethod
    endstruct
    
    private type linkHelper extends Node array[MAX_LINKS]
    private type lengthHelper extends real array[MAX_LINKS]
    private type weightHelper extends real array[MAX_LINKS]
    private type enabledHelper extends boolean array[MAX_LINKS]
    
    private keyword xx
    private keyword xy
    private keyword xmarker
    private keyword xlinks
    private keyword xlinkWeight
    private keyword xlinkMulti
    private keyword xlinkSize
    private keyword xlinkEnabled
    private keyword xnodeSize
    private keyword xlinkData
    private keyword xid

    public struct Node
        real xx
        real xy
        unit xmarker
        linkHelper xlinks
        lengthHelper xlinkLength
        weightHelper xlinkWeight
        enabledHelper xlinkEnabled
        integer xlinkSize
        real xnodeSize
        string xlinkData
        
        integer xid
        
        private static thistype array nodes[MAX_NODES]
        
        static method operator[] takes integer id returns thistype
            return thistype.nodes[id]
        endmethod 
        
        //! textmacro PAS_ReadOnly takes NAME, TYPE
        method operator $NAME$ takes nothing returns $TYPE$
            return .x$NAME$
        endmethod
        //! endtextmacro
        
        //! runtextmacro PAS_ReadOnly("x", "real")
        //! runtextmacro PAS_ReadOnly("y", "real")
        //! runtextmacro PAS_ReadOnly("marker", "unit")
        //! runtextmacro PAS_ReadOnly("linkSize", "integer")
        //! runtextmacro PAS_ReadOnly("nodeSize", "real")
        //! runtextmacro PAS_ReadOnly("id", "integer")
        //! runtextmacro PAS_ReadOnly("links", "linkHelper")
        //! runtextmacro PAS_ReadOnly("linkLength", "lengthHelper")
        //! runtextmacro PAS_ReadOnly("linkWeight", "weightHelper")
        //! runtextmacro PAS_ReadOnly("linkEnabled", "enabledHelper")
        
        method changeWeight takes integer i, real weight returns nothing
            local PAS_Node for = .xlinks[i]
            set .xlinkLength[i] = SquareRoot((.xx-for.xx)*(.xx-for.xx)+(.xy-for.xy)*(.xy-for.xy)) * weight
            set .xlinkWeight[i] = weight
        endmethod
        
        method changeWeightForNode takes Node for, real weight returns nothing
            local integer i = 0
            loop
                exitwhen i >= .xlinkSize
                if .xlinks[i] == for then // right link
                    set .xlinkLength[i] = SquareRoot((.xx-for.xx)*(.xx-for.xx)+(.xy-for.xy)*(.xy-for.xy)) * weight
                    set .xlinkWeight[i] = weight
                    return
                endif
                set i = i + 1
            endloop
        endmethod
        
        method setLinkEnabled takes integer i, boolean enabled returns nothing
            set .xlinkEnabled[i] = enabled
        endmethod
        
        method setLinkEnabledForNode takes Node for, boolean enabled returns nothing
            local integer i = 0
            loop
                exitwhen i >= .xlinkSize
                if .xlinks[i] == for then // right link
                    set .xlinkEnabled[i] = enabled
                    return
                endif
                set i = i + 1
            endloop
        endmethod
                
        static method fromMarker takes unit u returns thistype
            return LoadInteger(storage, getNode, GetHandleId(u))
        endmethod

        static method getNearest takes real x, real y returns thistype
            local unit u = null
            local real dist = 999999
            local real curDist = 0
            local thistype closest
            local thistype cur
            call GroupEnumUnitsInRange(TempGroup, x, y, NODE_TEST_RANGE, isNode)
            loop
                set u = FirstOfGroup(TempGroup)
                exitwhen u == null
                set cur = thistype.fromMarker(u)
                set curDist = (cur.xx-x)*(cur.xx-x)+(cur.xy-y)*(cur.xy-y)
                if curDist < dist then
                    set closest = cur
                    set dist = curDist
                endif
                call GroupRemoveUnit(TempGroup, u)
            endloop
            set u = null
            return closest
        endmethod 
        
        private static method create takes nothing returns thistype
            call Error("I don't know how you called PAS_Node.create(), but don't!")
            return 0
        endmethod
                
        
        static method add takes integer id, real x, real y, string linkData, real size returns thistype
            local thistype this = thistype.allocate()
            static if DEBUG_MODE then
                if id < 1 then 
                    call Error("ID "+I2S(id)+" is not a valid Node ID!")
                elseif id > MAX_NODES then
                    call Error("ID "+I2S(id)+" exceeds MAX_NODES!")
                endif
                if linkData == "" then
                    call Error("Node "+I2S(id)+" has no Link data!")
                endif
            endif
            set .xx = x
            set .xy = y
            set .xid = id
            if size < NODE_MIN_SIZE then
                set size = NODE_DEFAULT_SIZE
            endif
            set .xmarker = CreateUnit(Player(15), MARKER_ID, .xx, .xy, 0)
            call SaveInteger(storage, getNode, GetHandleId(.xmarker), this)
            set .xnodeSize = size
            set .xlinkData = linkData
            set .xlinkSize = 0
            set .xlinks = linkHelper.create()
            set .xlinkLength = lengthHelper.create()
            set .xlinkWeight = weightHelper.create()
            set .xlinkEnabled = enabledHelper.create()
            set .nodes[id] = this
            return this
        endmethod
        
        static method addRect takes integer id, rect r, string linkData, real size returns thistype
            if r == null then
                call Error("Node "+I2S(id)+" received a null rect from its addRect method!")
                return 0
            endif
            return thistype.add(id, GetRectCenterX(r), GetRectCenterY(r), linkData, size)
        endmethod

    endstruct

    
    private struct NearEdge
        Edge e
        Point near
        real dist
        
        static method create takes Edge e, real x, real y, real dist returns thistype
            local thistype this = thistype.allocate()
            set .e = e
            set .near = Point.create(x, y)
            set .dist = dist
            return this
        endmethod
        
       method onDestroy takes nothing returns nothing
            if .near != 0 then
                call .near.destroy()
            endif
        endmethod
    endstruct
    
    private struct Edge 
        Node a
        Node b
        
        static method get takes Node a, Node b returns thistype
            if a.xid < b.xid then
                return LoadInteger(storage, getLink, a*MAX_NODES+b)
            else    
                return LoadInteger(storage, getLink, b*MAX_NODES+a)
            endif
        endmethod
        
        // create is duplicate safe, so you can't create the same link twice
        static method create takes Node a, Node b returns thistype
            local thistype this = thistype.get(a, b)
            if this == 0 then // link hasn't been created yet
                set this = thistype.allocate()
                if a.xid > b.xid then // make sure lowest is at a
                    set .a = b
                    set .b = a
                else
                    set .a = a
                    set .b = b
                endif
                call SaveInteger(storage, getLink, a*MAX_NODES+b, this)
            endif
            return this
        endmethod
        
        static method getNearest takes real x, real y returns NearEdge
            local integer array checked // 0 = no, 1 = yes
            local unit u = null
            local real dist = LINK_TEST_RANGE*LINK_TEST_RANGE+50 // amounts should never be longer than this
            local thistype shortest = 0
            local real shortx = 0
            local real shorty = 0
            local thistype cur = 0
            local integer i = 0
            local Node n = 0
            local location l = null
            local real tempx = 0
            local real tempy = 0
            local real tempdist = 0
            call GroupEnumUnitsInRange(TempGroup, x, y, LINK_TEST_RANGE, isNode) // gather all nodes nearby
            loop
                set u = FirstOfGroup(TempGroup) // loop through the nodes checking each link
                exitwhen u == null
                set n = Node.fromMarker(u) // get the node from the marker
                set i = 0
                loop
                    exitwhen i >= n.xlinkSize
                    if n.xlinkEnabled[i] then // don't check disabled links
                        set cur = thistype.get(n, n.xlinks[i])
                        if checked[cur] != 1 then // avoid checking the same edge multiple times
                            set checked[cur] = 1
                            set l = GetNearestPointOnSegment(cur.a.xx, cur.a.xy, cur.b.xx, cur.b.xy, x, y) // get the nearest point
                            set tempx = GetLocationX(l) // save the points to varaibles so we can reduce calls now as well 
                            set tempy = GetLocationY(l) // as pass them in the edge struct on the return.
                            set tempdist = (tempx-x)*(tempx-x)+(tempy-y)*(tempy-y) // we can square the distance at the end
                            if tempdist < dist then // nearest
                                set shortest = cur
                                set dist = tempdist
                                set shortx = tempx
                                set shorty = tempy
                            endif
                            call RemoveLocation(l)
                        endif
                    endif
                    set i = i + 1
                endloop
                call GroupRemoveUnit(TempGroup, u)
            endloop
            set l = null
            set u = null
            if shortest != 0 then
                return NearEdge.create(shortest, shortx, shorty, SquareRoot(dist))
            endif
            return 0
        endmethod
    endstruct
    
    private keyword setStart
    private keyword setEnd
    private keyword xcreate
    
    public struct Path
        List nodes
        Point start
        Point end
        Point nearStart
        Point nearEnd
        
        static method create takes nothing returns thistype
            call Error("PAS_Path.create() is private! Use PAS_GetPath()")
            return 0
        endmethod
        
        static method xcreate takes NearEdge start, NearEdge end, List n returns thistype
            local thistype this = thistype.allocate()
            set .nearStart = Point.create(start.near.x, start.near.y)
            set .nearEnd = Point.create(end.near.x, end.near.y)
            set .nodes = n
            set .start = 0
            set .end = 0
            return this
        endmethod
        
        method setStart takes real x, real y returns nothing
            if .start != 0 then
                call .start.destroy()
            endif
            set .start = Point.create(x, y)
        endmethod
        
        method setEnd takes real x, real y returns nothing
            if .end != 0 then
                call .end.destroy()
            endif
            set .end = Point.create(x, y)
        endmethod
        
        method onDestroy takes nothing returns nothing
            if .nodes != 0 then
                call .nodes.destroy()
            endif
            if .start != 0 then
                call .start.destroy()
            endif
            if .end != 0 then
                call .end.destroy()
            endif
            if .nearStart != 0 then
                call .nearStart.destroy()
            endif
            if .nearEnd != 0 then
                call .nearEnd.destroy()
            endif
        endmethod
    endstruct     
            

    private function AStar takes NearEdge start, NearEdge end returns Path
        local Node curNode = 0
        local Node curLink = 0
        local Node array from
        local Edge se = start.e
        local Edge ee = end.e
        local integer link = 0
        local integer array nodeStatus
        local real array fscore
        local real array gscore
        local List l = List.create()
        local Link tempLink
        // this version improves the routes as it takes into account the links as much as the noodes
        // we give each node in the link their g and f scores, based from the nearest point on the link.  from there we pick the best
        // node to start with and add the other to the list of open nodes
        set gscore[se.a] = SquareRoot((start.near.x-se.a.xx)*(start.near.x-se.a.xx)+(start.near.y-se.a.xy)*(start.near.y-se.a.xy))
        set gscore[se.b] = SquareRoot((start.near.x-se.b.xx)*(start.near.x-se.b.xx)+(start.near.y-se.b.xy)*(start.near.y-se.b.xy))

        set fscore[se.a] = gscore[se.a] + SquareRoot((se.a.xx-end.near.x)*(se.a.xx-end.near.x)+(se.a.xy-end.near.y)*(se.a.xy-end.near.y))
        set fscore[se.b] = gscore[se.b] + SquareRoot((se.b.xx-end.near.x)*(se.b.xx-end.near.x)+(se.b.xy-end.near.y)*(se.b.xy-end.near.y))

        if fscore[se.a] < fscore[se.b] then
            set curNode = se.a
            call Link.create(l, se.b)
            set nodeStatus[se.b] = 1
        else
            set curNode = se.b
            call Link.create(l, se.a)
            set nodeStatus[se.a] = 1
        endif
        loop
            // once we get to either end node, it will be the shortest path, as the best possible route is always taken
            exitwhen curNode == ee.a or curNode == ee.b
            if curNode == 0 then
                call l.destroy()
                return 0
            endif
            set nodeStatus[curNode] = 2
            set link = 0
            loop
                //Link Loop
                exitwhen link >= curNode.xlinkSize
                if curNode.xlinkEnabled[link] then
                    set curLink = curNode.xlinks[link]
                    if nodeStatus[curLink] == 0 then
                        set gscore[curLink] = curNode.xlinkLength[link] + gscore[curNode]
                        set fscore[curLink] = gscore[curLink] + SquareRoot((curLink.xx-end.near.x)*(curLink.xx-end.near.x)+(curLink.xy-end.near.y)*(curLink.xy-end.near.y))
                        set from[curLink] = curNode
                        set nodeStatus[curLink] = 1
                        
                        set tempLink = l.first
                        loop
                            if tempLink == 0 then
                                call Link.createLast(l, curLink)
                                exitwhen true
                            endif
                            if fscore[curLink] < fscore[tempLink.data] then
                                call tempLink.insertBefore(curLink)
                                exitwhen true
                            endif
                            set tempLink = tempLink.next                        
                        endloop
                    endif
                endif
                set link = link + 1
            endloop
            set curNode = l.first.data
            if l.first != 0 then
                call l.first.destroy()
            endif
        endloop
        // now l does double-duty
        call l.destroy()
        
        set l = List.create()
        loop
            exitwhen curNode == 0
            call Link.create(l, curNode)
            set curNode = from[curNode]
        endloop
        return Path.xcreate(start, end, l)
    endfunction
    
    public function GetPath takes real startx, real starty, real endx, real endy returns Path
        local NearEdge start = 0
        local NearEdge end = 0
        local Path p = 0
        debug local string msg
        debug local Link temp
        debug local boolean comma = false
        
        set start = Edge.getNearest(startx, starty)
        if start == 0 then // no nearby edge
            return 0
        endif 
        
        set end = Edge.getNearest(endx, endy)
        if end == 0 then // no nearby edge
            call start.destroy()
            return 0
        endif
        
        // need to check if start and end are the same edge, cause then we don't have to go to nodes
        if start.e == end.e then 
            set p = Path.xcreate(start, end, 0) // no nodes, don't need a path
        else
            set p = AStar(start, end)
            if p == 0 then // AStar couldn't find path
                call start.destroy()
                call end.destroy()
                call Error("Couldn't find path from "+R2S(startx)+", "+R2S(starty)+" to "+R2S(endx)+", "+R2S(endy))
                return 0
            endif
        endif
        call p.setStart(startx, starty)
        call p.setEnd(endx, endy)

        static if DEBUG_MODE then
            if DEBUG_SHOW_PATHS then
                set temp = p.nodes.first
                set msg = "GetPath("+R2S(startx)+","+R2S(starty)+","+R2S(endx)+","+R2S(endy)+")= ["
                loop
                    exitwhen temp == 0
                    if comma then
                        set msg = msg + ", "
                    else
                        set comma = true
                    endif
                    set msg = msg + "|cff00ff00"+I2S(Node(temp.data).xid)+"|r"
                    set temp = temp.next
                endloop
                set msg = msg + "]"
                call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, msg)
            endif
        endif
        
        call start.destroy()
        call end.destroy()
        return p
    endfunction

    private function LinkNodes takes nothing returns nothing
        local integer i = 1
        local Node to = 0
        local Node cur = 0
        local string temp = ""
        local real weight = 1.
        local integer si = 0
        local integer sa = 0
        local integer sl = 0
        local integer wi = 0
        local integer wa = 0
        loop
            exitwhen i > MAX_NODES
            set cur = Node[i]
            if cur != 0 then
                // calculate links
                set si = 1
                set sa = 0
                set sl = StringLength(cur.xlinkData)
                loop
                    set temp = SubString(cur.xlinkData, si-1, si)
                    if  temp == "-" or temp == "=" or si > sl then
                        set to = Node[S2I(SubString(cur.xlinkData, sa, si-1))]
                        if to != 0 and to != cur and cur.xlinkSize < MAX_LINKS then
                            if temp == "=" then
                                set sa = si
                                loop
                                    exitwhen SubString(cur.xlinkData, si, si+1) == "-" or si >= sl
                                    set si = si + 1
                                endloop
                                if sa == si then // there were no chars after the equal sign
                                    call Error("Node "+I2S(i)+" has missing weight data for link "+I2S(cur.xlinkSize+1)+" (has an = but no value for weight)")
                                    set weight = 1
                                else
                                    set weight = S2R(SubString(cur.xlinkData, sa, si))
                                endif
                                set si = si + 1
                                set cur.xlinkWeight[cur.xlinkSize] = weight
                                set cur.xlinkLength[cur.xlinkSize] = weight * SquareRoot((to.xx-cur.xx)*(to.xx-cur.xx)+(to.xy-cur.xy)*(to.xy-cur.xy))
                            else
                                set cur.xlinkWeight[cur.xlinkSize] = 1.
                                set cur.xlinkLength[cur.xlinkSize] = SquareRoot((to.xx-cur.xx)*(to.xx-cur.xx)+(to.xy-cur.xy)*(to.xy-cur.xy))
                            endif
                            call Edge.create(cur, to)
                            set cur.xlinks[cur.xlinkSize] = to
                            set cur.xlinkEnabled[cur.xlinkSize] = true
                            set cur.xlinkSize = cur.xlinkSize + 1
                        else
                            if to == 0 then
                                call Error("Link "+I2S(cur.xlinkSize+1)+" for Node "+I2S(i)+", doesn't link to a valid node!")
                            elseif to == cur then
                                call Error("Link "+I2S(cur.xlinkSize+1)+" for Node "+I2S(i)+", links to self!")
                            endif
                            if cur.xlinkSize >= MAX_LINKS then
                                call Error("Node "+I2S(i)+" links to more than MAX_LINKS Links!")
                            endif
                        endif
                        set sa = si
                    endif
                    exitwhen si > sl
                    set si = si + 1
                endloop    
            else
                call Error("Node not created for ID "+I2S(i))
            endif
            set i = i + 1
        endloop
    endfunction
    
    private function onInit takes nothing returns nothing
        set isNode = Filter(function isNodeFunc)
        if MAX_STRUCT > 8190 then 
            call Error("MAX_NODES and MAX_LINKS exceed 8190.  Either reduce the number of nodes or the number of links!")
        endif
        call SetupNodes.execute()
        call LinkNodes.execute()
    endfunction
    
endlibrary

// ==================================================================================
// PASMove Plugin - by Ammorth                                          Feb 17, 2010
//    **Requires JassHelper (vJass) to compile**
//    Requires: PAS (in this map)
//              optional PASMoveSafety (in this map)
//
// about:
//   This is a plugin for Pathing Algorithm System that can order units around on paths.
//   It really only has 2 function wrappers, but you can do a few extra things using
//   the base types of this library
//
// Requirements:
//   - PAS
//   - optional PASMoveSafety
//
// Installation:
//   - Create a new trigger called PASMove
//   - Copy this code to the new trigger
//   
// Setup:
//   - Modify the constant globals below to your liking
//
// Function List:
//   PASMove_IssuePointPathOrder(unit whichUnit, real x, real y, string order) -> boolean
//   PASMove_IssuePointPathOrderById(unit whichUnit, real x, real y, string order) -> boolean
//   PASMove_UnitPath.create(unit whichUnit, PAS_Path, path, integer order) -> PASMove_UnitPath
//
// Usage:
//   You can quickly order units to cordinates using the following 2 functions:
//
//     PASMove_IssuePointPathOrder(unit whichUnit, real x, real y, string order)
//
//   or
//
//     PASMove_IssuePointPathOrderById(unit whichUnit, real x, real y, string order)
//
//   They function just like their native IssuePointOrder() counter-part, execept they use the PAS
//   path to move units on.  The unit will move to the nearest edge, around the path, and then off
//   the path once they are near the desired point.  The order passed is the order given to the unit
//   at each node, to the next node.  Therefore, you should choose only orders that will move units
//   ("move", "smart", "attack", etc) otherwise units will get stuck and not move around.
//
//   Aswell, you can directly use the UnitPath struct via the following methods:
//
//     PASMove_UnitPath.create(unit whichUnit, PAS_Path, path, integer order)
//
//   will create the PASMove_UnitPath struct, from there you can use:
//
//     PASMove_UnitPath.registerAfterPath(afterPath function)
//
//   this will allow you to register a function that will be called once a unit has completed moving.
//   the function must take a unit (which will be the unit that finished pathing) and return nothing.
//   You can then do other stuff with the unit or order it to move somewhere else. (check the Populate
//   City test trigger for an example.
//
//   You can then call:
//
//     PASMove_UnitPath.startPath()
//
//   which will begin ording the unit around the supplied path.  Calling this again after a unit is
//   already moving will cause it to start moving from the start again (causing it to run straight
//   from the where it currently is, to the nearPoint).  Therefore it is recommended to call this
//   only once and right after you have created the UnitPath.
//
//   To get a UnitPath attached to a unit, use:
//
//     PASMove_UnitPath[whichUnit]
//
//   to get the path (if any).  A unit without a path will return 0 (null).
//
//   If you want to remove a UnitPath pre-maturly, you can call .destroy() on the UnitPath to remove it.
//   
//   Keep in mind, once a unit is done pathing, the UnitPath will be cleared automatically, before your
//   afterPath function is called.  Aswell, if you generate a new UnitPath for a unit, any old UnitPath
//   associated with that unit will be destroyed.  Destroying a UnitPath also doesn't cause a unit to stop,
//   nor will it call the afterPath function.  The unit will keep moving to its next location before comming
//   to a stop.
//
// Notes:
//
//   When a unit dies or is removed, their UnitPath is not removed.  Aswell, if a unit get stuck while trying
//   to move to a node or a point, there is no way to really detect it.  For these reasons I wrote a plugin
//   for PASMove, PASMoveSafety.  If this is included in your map, it will periodically check for stuck,
//   dead or removed units, and either clean up the UnitPath or re-order the unit on its way.  This way, you can
//   be assured units will reach their destination and will be cleaned up upon dying/being removed.  Some maps
//   may not run into issues with either, which is why I made it optional, as it does take up a bit of CPU power.
//
// ==================================================================================
library PASMove initializer onInit requires PAS optional PASMoveSafety
globals
// ==================================================================================
//
//  Start of Constant Globals
//

// the range at which a unit is deemed to be at a point.  This is not used for nodes, only points
// such as nearStart, nearEnd and end.
    private constant real IN_RANGE_OF_POINT = 64
    
// The period between checking if units are at nodes.  Lower numbers means more checks per second
// but more CPU intensive.  Higher numbers means less frequent checks.  This is a time in seconds.
    private constant real TIMER_PERIOD = 0.025 

// if Debug Mode is on and this is true, it will show an effect on all active nodes.
// About ActiveNodes.  to reduce calculations, only nodes that have units moving to them
// will be checked for nearby units.  These nodes are considered active.  This is good
// to debug PASMovement, and it can also be fun to watch how the plugin operates.
    private constant boolean SHOW_ACTIVE_EFFECT = false // only works if DebugMode is enabled in JassHelper
    
//
//  End of Constant Globals
//
// ==================================================================================
endglobals
    public keyword UnitPath
    private keyword ActiveNode
    private keyword ActivePoint
            
    // hides these methods from the outside so you can't call them
    // you shouldn't have to call them, ever.
    private keyword orderUnitToNext

    globals
        
        
        private timer mainTimer = null
        private constant hashtable storage = InitHashtable() 
        private constant integer getPath = -1 // negatives can't interfere with stored structs
        private group TempGroup = CreateGroup()
    endglobals
    
    private function Error takes string msg returns nothing
        debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "PASMovement Error: "+msg)
    endfunction
    
    private struct ActiveNode
        PAS_Node n
        integer count
        
        integer slot
        
        static thistype array actives
        static integer activeSize = 0
        
        static thistype array fromNodes
        
        static method create takes PAS_Node n returns thistype
            local thistype this = thistype.allocate()
            
            set .n = n
            set .count = 1
            
            set .slot = .activeSize
            set .actives[.slot] = this
            set .activeSize = .activeSize + 1
            
            set .fromNodes[n] = this
            
            return this
        endmethod
        
        static method add takes PAS_Node n returns nothing
            local thistype this = thistype.fromNodes[n]
            if this == 0 then
                call thistype.create(n)
            else
                set .count = .count + 1
            endif
        endmethod
        
        method remove takes nothing returns boolean // true if removed
            local thistype last
            if this != 0 and .count != 0 then // prevent double-free
                set .count = .count - 1
                if .count == 0 then // no more counts for node, remove from active
                    set .activeSize = .activeSize - 1
                    
                    set .fromNodes[.n] = 0
                    set last = .actives[.activeSize]
                    set .actives[.slot] = last // move the last active node to here
                    set last.slot = .slot // update the last active node to the new slot
                    call .destroy()
                    return true
                endif
            else
                call Error("Double-free of type ActiveNode!")
            endif
            return false
        endmethod
        
        method checkForPather takes nothing returns boolean
            local unit u = null
            local UnitPath path
            call GroupEnumUnitsInRange(TempGroup, .n.x, .n.y, .n.nodeSize, null)
            loop
                set u = FirstOfGroup(TempGroup)
                exitwhen u == null
                set path = UnitPath[u]
                if path.step.data == .n then // this unit as at the proper node

                    call path.orderUnitToNext()
                    
                    if .remove() then // was removed, stop checking
                        call GroupClear(TempGroup)
                        set u = null
                        return true
                    endif                                      
                endif
                call GroupRemoveUnit(TempGroup, u)
            endloop
            
            set u = null
            return false
        endmethod
    endstruct
    
    private struct ActivePoint
        PAS_Point p
        
        integer slot
        
        static thistype array actives
        static integer activeSize = 0
        
        static thistype array fromPoints
        
        static method create takes PAS_Point p returns thistype
            local thistype this = thistype.allocate()
            set .p = p
            
            set .slot = .activeSize
            set .actives[.slot] = this
            set .activeSize = .activeSize + 1
            
            set .fromPoints[p] = this
            
            return this
        endmethod
        
        static method add takes PAS_Point p returns nothing
            local thistype this = thistype.fromPoints[p]
            if this == 0 then
                call thistype.create(p)
            else
                call Error("Double add of Point to ActivePoint!")
            endif
        endmethod
        
        method remove takes nothing returns boolean // true if removed
            local thistype last
            if this != 0 then // prevent double-free
                set .activeSize = .activeSize - 1
                
                set.fromPoints[.p] = 0
                
                set last = .actives[.activeSize]
                set .actives[.slot] = last // move the last active node to here
                set last.slot = .slot // update the last active node to the new slot
                call .p.destroy()
                call .destroy()
                return true
            else
                call Error("Double-free of type ActivePoint!")
            endif
            return false
        endmethod
        
        method checkForPather takes nothing returns boolean
            local PAS_Point tempPoint = 0
            local unit u = null
            local UnitPath path
            call GroupEnumUnitsInRange(TempGroup, .p.x, .p.y, IN_RANGE_OF_POINT, null)
            
            loop
                set u = FirstOfGroup(TempGroup)
                exitwhen u == null
                set path = UnitPath[u]
                if path.point == .p then // this unit as at the proper point
                    // only 1 unit should be moving to a specific point
                    set path.point = 0
                    call path.orderUnitToNext()
                    
                    if .remove() then // was removed, stop checking
                        call GroupClear(TempGroup)
                        set u = null
                        return true
                    endif
                endif
                call GroupRemoveUnit(TempGroup, u)
            endloop
            
            set u = null
            return false
        endmethod
        
    endstruct
            
    private function onTimerPeriod takes nothing returns nothing
        local integer i = 0
        local ActiveNode n = 0
        local ActivePoint p = 0
        loop
            exitwhen i >= ActiveNode.activeSize
            set n = ActiveNode.actives[i]
            static if DEBUG_MODE then
                if SHOW_ACTIVE_EFFECT then
                    call DestroyEffect(AddSpecialEffect("Abilities\\Spells\\Other\\GeneralAuraTarget\\GeneralAuraTarget.mdl", n.n.x, n.n.y))
                endif
            endif
            if not n.checkForPather() then // don't increment i if we removed a node
                set i = i + 1
            endif
        endloop
        set i = 0
        loop
            exitwhen i >= ActivePoint.activeSize
            set p = ActivePoint.actives[i]
             static if DEBUG_MODE then
                if SHOW_ACTIVE_EFFECT then
                    call DestroyEffect(AddSpecialEffect("Abilities\\Spells\\Other\\GeneralAuraTarget\\GeneralAuraTarget.mdl", p.p.x, p.p.y))
                endif
            endif
            if not p.checkForPather() then // don't increment i if we removed a node
                set i = i + 1
            endif
        endloop
    endfunction
        
    function interface afterPath takes unit u returns nothing
    
    private keyword orderUnitToNext

    public struct UnitPath
        unit pather
        PAS_Point point
        PAS_Path path
        Link step
        integer stepType
        integer order
        afterPath func
        
        real tox
        real toy
        boolean toExist
        
        static method operator[] takes unit u returns thistype
            return LoadInteger(storage, getPath, GetHandleId(u))
        endmethod
        
        static method create takes unit u, PAS_Path p, integer order returns thistype
            local thistype this = thistype.allocate()
            set .toExist = false
            set .pather = u
            set .point = 0
            set .path = p
            set .step = 0
            set .stepType = 0
            set .order = order
            set .func = 0
            call SaveInteger(storage, getPath, GetHandleId(.pather), this)
            return this
        endmethod
        
        method onDestroy takes nothing returns nothing
            static if LIBRARY_PASMoveSafety then // link into safety sytem
                call PASMoveSafety_RemoveUnitPath(this)
            endif
            if LoadInteger(storage, getPath, GetHandleId(.pather)) == this then
                call SaveInteger(storage, getPath, GetHandleId(.pather), 0)
            endif
            set .pather = null
            if .point != 0 then
                call ActivePoint.fromPoints[.point].remove() // destroys the point aswell
                set .point = 0
            endif
            if .step != 0 then // need to clean-up an active node
                call ActiveNode.fromNodes[.step.data].remove()
                set .step = 0
            endif
            if .path != 0 then
                call .path.destroy()
                set .path = 0
            endif
            set .toExist = false
        endmethod
        
        method registerAfterPath takes afterPath ap returns nothing
            set .func = ap
        endmethod                
        
        method orderUnitToNext takes nothing returns nothing
            local unit u = null
            local PAS_Node n = 0
            local afterPath func = 0
            if .stepType == 0 then // havn't done anything yet
                // move to the nearest point on the starting edge
                set .stepType = 1
                if IsUnitInRangeXY(.pather, .path.nearStart.x, .path.nearStart.y, IN_RANGE_OF_POINT) then
                    call .orderUnitToNext()
                else
                    set .point = PAS_Point.create(.path.nearStart.x, .path.nearStart.y)
                    call ActivePoint.add(.point)
                    set .tox = .path.nearStart.x
                    set .toy = .path.nearStart.y
                    call IssuePointOrderById(.pather, .order, .path.nearStart.x, .path.nearStart.y)
                endif
            elseif .stepType == 1 then // moving to nodes
                if .step == 0 then // first node
                    set .step = .path.nodes.first
                else
                    set .step = .step.next
                endif
                if .step == 0 then // last node
                    set .stepType = 2
                    if IsUnitInRangeXY(.pather, .path.nearEnd.x, .path.nearEnd.y, IN_RANGE_OF_POINT) then
                        call .orderUnitToNext()
                    else
                        set .point = PAS_Point.create(.path.nearEnd.x, .path.nearEnd.y)
                        call ActivePoint.add(.point)
                        set .tox = .path.nearEnd.x
                        set .toy = .path.nearEnd.y
                        set .toExist = true
                        call IssuePointOrderById(.pather, .order, .path.nearEnd.x, .path.nearEnd.y)
                    endif 
                else // moving to a normal node
                    set n = PAS_Node(.step.data)
                    if IsUnitInRangeXY(.pather, n.x, n.y, n.nodeSize) then
                        call .orderUnitToNext()
                    else
                        call ActiveNode.add(n)
                        set .tox = n.x
                        set .toy = n.y
                        set .toExist = true
                        call IssuePointOrderById(.pather, .order, n.x, n.y)
                    endif
                endif
            elseif .stepType == 2 then // moving to final point
                set .stepType = 3
                if IsUnitInRangeXY(.pather, .path.end.x, .path.end.y, IN_RANGE_OF_POINT) then
                    call .orderUnitToNext()
                else
                    set .point = PAS_Point.create(.path.end.x, .path.end.y)
                    call ActivePoint.add(.point)
                    set .tox = .path.end.x
                    set .toy = .path.end.y
                    set .toExist = true
                    call IssuePointOrderById(.pather, .order, .path.end.x, .path.end.y)
                endif
            elseif .stepType == 3 then // at final point
                set .toExist = false
                if .func != 0 then
                    set u = .pather
                    set func = .func
                    call .destroy()
                    call func.execute(u)
                    set u = null
                    return
                else
                    call .destroy()
                endif
            endif
        endmethod
        
        method startPath takes nothing returns nothing
            set .stepType = 0
            set .step = 0
            if .step != 0 then // was walking to a node, clean it up
                call ActiveNode.fromNodes[.step.data].remove()
                set .step = 0
            endif
            if .point != 0 then // was walking to a point, clean it up
                call ActivePoint.fromPoints[.point].remove()
                set .point = 0
            endif
            static if LIBRARY_PASMovementSafety then // link into safety sytem
                call PASMoveSafety_AddUnitPath(this)
            endif
            call .orderUnitToNext()
        endmethod

    endstruct
        
    
    public function IssuePointPathOrderById takes unit u, real x, real y, integer order returns boolean
        local real sx = GetUnitX(u)
        local real sy = GetUnitY(u)
        local PAS_Path p = PAS_GetPath(sx, sy, x, y)
        local UnitPath unitpath = UnitPath[u]
        if unitpath != 0 then // already on a path
            call unitpath.destroy()
        endif
        if p != 0 then // path exists
            // assign the path to the unit
            set unitpath = UnitPath.create(u, p, order)
            // start the unit on the path
            call unitpath.startPath()
            return true
        endif
        return false     
    endfunction
    
    public function IssuePointPathOrder takes unit u, real x, real y, string order returns boolean
        local integer o = OrderId(order)
        if o != 0 then
            return IssuePointPathOrderById(u, x, y, o)
        endif
        return false
    endfunction
    
    private function onInit takes nothing returns nothing
        set mainTimer = CreateTimer()
        call TimerStart(mainTimer, TIMER_PERIOD, true, function onTimerPeriod)
    endfunction


endlibrary

// ==================================================================================
// PASMoveSafety Plugin - by Ammorth                                    Feb 17, 2010
//    **Requires JassHelper (vJass) to compile**
//    Requires: PAS (in this map)
//              LinkedList (by Ammorth, wc3c)
//
// about:
//   This plugin works with PASMove and makes sure units reach their destinations as well as 
//   provides clean-up to removed/dead units.  If a unit is trapped while trying to move to
//   a node, it can fail moving in the wc3 pathing engine and stop.  Because PASMove does
//   not detect failed paths, the units will be forgotten forever.  This sript remedies that
//   by searching through moving units for ones that get stuck, and push them on their way.
//   Some maps may not run into this issue (usually happens when many units are trying to move
//   within a few nodes) and so this feature is optional to PASMove.
//
// Requirements:
//   - LinkedList (by Ammorth, at wc3c)
//   - PAS
//   - although PASMove isn't required for this script, it makes little sense to include this
//     if PASMove is not present...  
//
// Installation:
//   - Create a new trigger called PASMoveSafety
//   - Copy this code to the new trigger
//   
// Setup:
//   - Modify the constant globals below to your liking
//
// Usage:
//   - None, just setup and enjoy!
//
// ==================================================================================
library PASMoveSafety initializer onInit requires PAS, LinkedList
globals
// ==================================================================================
//
//  Start of Constant Globals
//
// the number of units to check per period.  This is to make sure you don't check too many units at once.
// Also note, if the number of moving units is less than this, it will check all units every period
// It will also not check the same unit multiple times per period
    private integer AMOUNT_TO_CHECK_PER_PERIOD = 25
    
// the time in seconds between checks.  Setting this to higher values will reduce load while setting
// it to lower values will increase load but find stuck unit faster
    private real TIMER_PERIOD = 0.25
    
//  End of Constant Globals
//
// ==================================================================================
    private timer mainTimer = null
endglobals
    
    private struct Safety
        PASMove_UnitPath p
        Link myLink
        
        static List toCheck
        static Link current
        
        static thistype array pathToSafety
        
        static method create takes PASMove_UnitPath p returns thistype
            local thistype this = thistype.allocate()
            set .pathToSafety[p] = this
            set .p = p
            set .myLink = Link.createLast(.toCheck, this)
            return this
        endmethod
        
        method onDestroy takes nothing returns nothing
            if .myLink == .current then // make sure we arn't removing the current link
                if .current.prev != 0 then
                    set .current = .current.prev
                else
                    set .current = .toCheck.last
                endif
            endif
            call .myLink.destroy()
            set .pathToSafety[.p] = 0
            set .p = 0
        endmethod
        
        static method doCheck takes nothing returns nothing
            local thistype s = 0
            local integer count = 0
            local integer array checked
            if thistype.toCheck.size == 0 then // no units to check
                return
            endif
            if thistype.current == 0 then
                set thistype.current = thistype.toCheck.last
            endif
            loop
                exitwhen count >= AMOUNT_TO_CHECK_PER_PERIOD
                
                set s = Safety(thistype.current.data)
                
                if checked[s] == 1 then //looped around
                    return
                endif
                set checked[s] = 1
                // we check for null units, dead units and units that stopped moving
                if GetWidgetLife(s.p.pather) <= 0.405 then // dead or removed
                    call s.p.destroy()
                elseif GetUnitCurrentOrder(s.p.pather) == 0 then // stopped moving
                    if s.p.toExist == true then
                        call IssuePointOrderById(s.p.pather, s.p.order, s.p.tox, s.p.toy)
                    endif
                endif
                
                if thistype.current.prev != 0 then
                    set thistype.current = thistype.current.prev
                else
                    set thistype.current = thistype.toCheck.last
                endif
                
                set count = count + 1
            endloop
        endmethod
    endstruct

    public function AddUnitPath takes PASMove_UnitPath p returns nothing
        if Safety.pathToSafety[p] == 0 then // already added, no point to add again
            call Safety.create(p)
            //call BJDebugMsg("registered safety")
        endif
    endfunction
    
    public function RemoveUnitPath takes PASMove_UnitPath p returns nothing
        if Safety.pathToSafety[p] != 0 then
            call Safety.pathToSafety[p].destroy()
            //call BJDebugMsg("unregistered safety")
        endif
    endfunction
    
    private function onInit takes nothing returns nothing
        set Safety.toCheck = List.create()
        set Safety.current = 0
        set mainTimer = CreateTimer()
        call TimerStart(mainTimer, TIMER_PERIOD, true, function Safety.doCheck)
    endfunction

endlibrary

// ==================================================================================
// PASGPS Plugin - by Ammorth                                           Feb 17, 2010
//    **Requires JassHelper (vJass) to compile**
//    Requires: ARGB (by Vexorian, at wc3c)
//              PAS (in this map)
//              
// about:
//   This is a plugin for Pathing Algorithm System that creates a GPS-style waypoint
//   arrow above a unit, directing it to a given point, along the PAS nodes.
//
// Requirements:
//   - PAS
//   - ARGB
//
// Installation:
//   - Create a new trigger called PASGPS
//   - Copy this code to the new trigger
//   - Import both PAS_GPS_Arrow.mdx and PAS_GPS_Arrow.blp to your map
//   - Modify the path for both imports to remove "war3mapImported\"
//   
// Setup:
//   - Modify the constant globals below to your liking
//   - Make sure the textmacro for the object merger line provides a unique rawcode id to your map
//     (aka, if 'pasg' conflicts with another unit in your map, change it to something else)
//
// Usage:
//   The following 2 functions are used to add and remove the GPS arrow on the given unit:
//
//     PASGPS_UnitSetGPS(unit whichUnit, real x, real y)
//
//   sets a GPS arrow to the provided location while:
//
//     PASGPS_UnitRemoveGPS(unit whichUnit)
//   
//   will remove the GPS arrow (if it exists)
//
//   Because of the nature of GPS arrows, I have decided to make it only 1 per player.  Therefore,
//   if you create a new GPS arrow for a unit and the player already has an arrow on another unit,
//   that arrow will be removed and the new one will be created as normal.
//
//   Also, arrows will only be visible to the owning player.  Think of them like a UI extension.
//
// ==================================================================================
library PASGPS initializer onInit requires PAS, ARGB
// ==================================================================================
//
//  Start Object Merger Line
//
// set the value inside the quotes to a unique rawcode that isn't used in your map
//! runtextmacro PASGPS_GPS_ID("pasg")
//
//  This will auto-generate a unit in the object editor as well as asign the global
//  PASGPS_GPS_ID to the value here.
//
//  End Object Merger Line
//
// ==================================================================================
private keyword UnitGPS
globals
// ==================================================================================
//
//  Start of Constant Globals
    
// the time, in seconds that the timer updates the visuals/path for each unit
// setting this value lower will provide smoother visuals but with increased load
    private constant real TIMER_PERIOD = 0.025
    
// how long a GPS arrow will remain after the destination is reached
// this is mainly to play the death animation of the arrow
    private constant real CLEAN_TIME = 0.4 // should be longer than death animation

// the ARGB color of the arrow for when you are on course
    private ARGB ARROW_COLOR_ON = 0xFF00FF00
    
// the ARGB color of the arrow for when you are slightly off course
    private ARGB ARROW_COLOR_MID = 0xFFFFFF00

// the ARGB color of the arrow for when you are totally off course
    private ARGB ARROW_COLOR_OFF = 0xFFFF0000
    
// the angle, in degrees, you can be off course before the arrow start changing color
    private constant real ARROW_ANGLE_GIVE = 33
    
// the angle, in degress, for when you are totally off course
// note, angles between ARROW_ANGLE_GIVE and ARROW_ANGLE_OFF will use a blend of
// the ARROW_COLOR_ON, ARROW_COLOR_MID and ARROW_COLOR_OFF.  When the unit is
// farther than this angle, ARROW_COLOR_OFF will be used.
    private constant real ARROW_ANGLE_OFF = 90 

// when the unit gets within IS_AT_POINT to its current target, it will get the next target
// basically, how close you have to get to each point for it to register you arrived
    private constant real IS_AT_POINT = 192
    
// how far you must deviate from progress before the path is recalculated.
// sometimes players choose their own route and when they stop following the path for this distance
// a new route is generated to the end point for them.  This way, if they find an alternative path
// the system will tell them to go down that path instead.  This value shouldn't be too small, as it could cause
// the arrow to continually point back onto the path, if the unit gets too far off.
    private constant real DEVIATE_PATH = 512

//  End of Constant Globals
//
// ==================================================================================
    private ARGB arrowHide = 0x00FFFFFF // used to set alpha to 0 for other player
    private constant real arrowGive = ARROW_ANGLE_GIVE*bj_DEGTORAD
    private constant real arrowOff = ARROW_ANGLE_OFF*bj_DEGTORAD - arrowGive
    private constant real arrowMid = arrowOff/2
    private timer mainTimer = null
    private UnitGPS array GPSunits // we only support 1 unit per player
endglobals

//! textmacro PASGPS_GPS_ID takes VALUE
//! external ObjectMerger w3u hfoo $VALUE$ uabi Aloc umdl "PAS_GPS_Arrow.mdl" ushu "" uaen "" utar "" umvh 200 umvs 522 umvr 3 umvt fly ucol 0 ufoo 0 uhom 1 uhpm 99999 uhpr 99999 upgr "" unam "PASGPS Arrow"
    globals
        public constant integer GPS_ID = '$VALUE$'
    endglobals
//! endtextmacro
    
    // requires radians to be passed and returns radians
    private function AngleBetweenAngles takes real angle1, real angle2 returns real
        local real ax = Cos(angle1)
        local real ay = Sin(angle1)
        local real bx = Cos(angle2)
        local real by = Sin(angle2)
        return Acos(ax * bx + ay * by)
    endfunction
    
    private struct Point
        real x
        real y
    endstruct

    private struct UnitGPS
        unit u
        unit arrow
        
        integer curPoint
        
        real targetx
        real targety
        
        real goodx
        real goody
        real gooddist
        
        real curx
        real cury
        real face
        
        real endx
        real endy
        
        boolean onCleanUp
        real cleanFor
        
        PAS_Path path
        Link cur
        
        method isInRange takes real x, real y returns boolean
            return SquareRoot((.curx-x)*(.curx-x)+(.cury-y)*(.cury-y)) <= IS_AT_POINT
        endmethod
        
        method cleanUp takes nothing returns nothing
            if .arrow == null then // we were told to path to where we were, no visuals to clean up
                call .destroy()
            else
                call SetUnitAnimation(.arrow, "Death")
                set .onCleanUp = true
                set .cleanFor = 0
            endif
        endmethod
        
        method getTarget takes nothing returns boolean
            if isInRange(.path.end.x, .path.end.y) then // already at end, no need to path
                    return false
                endif
            if .curPoint == 0 then // just starting
                if isInRange(.path.nearStart.x, .path.nearStart.y) then
                    set .curPoint = 1 // move on
                    set .cur = .path.nodes.first
                    set .gooddist = 999999
                else
                    set .targetx = .path.nearStart.x
                    set .targety = .path.nearStart.y
                    return true
                endif
            endif
            if .curPoint == 1 then // nodes
                loop
                    if .cur != 0 then
                        if isInRange(PAS_Node(.cur.data).x, PAS_Node(.cur.data).y) then
                            set .cur = .cur.next
                            set .gooddist = 999999
                        else
                            set .targetx = PAS_Node(.cur.data).x
                            set .targety = PAS_Node(.cur.data).y
                            return true
                        endif
                    else
                        set .curPoint = 2
                        set .gooddist = 999999
                        exitwhen true
                    endif
                endloop
            endif
            if .curPoint == 2 then // near end
                if isInRange(.path.nearEnd.x, .path.nearEnd.y) then
                    set .curPoint = 3 // move on
                    set .gooddist = 999999
                else
                    set .targetx = .path.nearEnd.x
                    set .targety = .path.nearEnd.y
                    return true
                endif
            endif
            if .curPoint == 3 then
                if isInRange(.path.end.x, .path.end.y) then
                    set .curPoint = 4
                    set .gooddist = 999999
                else
                    set .targetx = .path.end.x
                    set .targety = .path.end.y
                    return true
                endif
            endif
            return false // at the end
        endmethod
        
        method pointAt takes nothing returns nothing
            local real rad =  Atan2(.targety - .cury, .targetx - .curx)
            local real off = AngleBetweenAngles(.face, rad)
            local real r = 0
            local ARGB color = 0
            if off < arrowGive then // all first color
                set color = ARROW_COLOR_ON
            else
                set off = off-arrowGive // mix colors
                if off < arrowMid then // mix first 2 colors
                    set r = off/arrowMid
                    set color = ARGB.mix(ARROW_COLOR_ON, ARROW_COLOR_MID, r)
                else
                    set off = off-arrowMid
                    if off < arrowOff then // mix second colors
                        set r = off/arrowOff
                        set color = ARGB.mix(ARROW_COLOR_MID, ARROW_COLOR_OFF, r)
                    else
                        set color = ARROW_COLOR_OFF // all last color
                    endif
                endif
            endif
            // hide arrow for other players
            if GetLocalPlayer() != GetOwningPlayer(.u) then
                set color = ARROW_COLOR_OFF
            endif
            if .arrow == null then // create an arrow
                set .arrow = CreateUnit(GetOwningPlayer(.u), GPS_ID, .curx, .cury, rad*bj_RADTODEG)
                call SetUnitBlendTime(.arrow, 0.)
                call SetUnitAnimation(.arrow, "birth") 
                call QueueUnitAnimation(.arrow, "stand")
            else
                call SetUnitFacing(.arrow, rad*bj_RADTODEG)
            endif
            call color.recolorUnit(.arrow)
            call SetUnitX(.arrow, .curx)
            call SetUnitY(.arrow, .cury)
        endmethod
        
        method newPath takes nothing returns boolean
            if .path != 0 then
                call .path.destroy()
            endif
            set .path = PAS_GetPath(.curx, .cury, .endx, .endy)
            if .path == 0 then // there is no path
                call .cleanUp()
                return false
            endif
                
            set .goodx = .curx
            set .goody = .cury
            
            set .curPoint = 0
            
            if .getTarget() then // returns true if there is a target
                set .gooddist = SquareRoot((.curx-.targetx)*(.curx-.targetx)+(.cury-.targety)*(.cury-.targety))
                call .pointAt()
                return true
            else // done the path or already at the end
                call .cleanUp()
            endif  
            return false
        endmethod
        
        method update takes nothing returns nothing
            local real dist
            set .face = GetUnitFacing(.u)*bj_DEGTORAD // we work in radians
            set .curx = GetUnitX(.u)
            set .cury = GetUnitY(.u)
            
            if .onCleanUp then // cleaning up
                set .cleanFor = .cleanFor + TIMER_PERIOD
                call SetUnitX(.arrow, .curx)
                call SetUnitY(.arrow, .cury)
                if .cleanFor >= CLEAN_TIME then // animation is done, time to remove
                    call .destroy()
                endif
                return
            endif
            
            if .getTarget() then // we arn't at the end
            
                set dist = SquareRoot((.curx-.targetx)*(.curx-.targetx)+(.cury-.targety)*(.cury-.targety))
                call .pointAt()
                
                if dist <= .gooddist then // getting closer, or a new target
                    set .gooddist = dist
                    set .goodx = .curx
                    set .goody = .cury
                    
                else // getting farther away
                    set dist = SquareRoot((.curx-.goodx)*(.curx-.goodx)+(.cury-.goody)*(.cury-.goody))
                    if dist >= DEVIATE_PATH then // we are too far away from where we should be, recalculate path
                        call .newPath()
                    endif
                endif
            else
                call .cleanUp()
            endif
        endmethod
        
        method onDestroy takes nothing returns nothing
            local integer p = GetPlayerId(GetOwningPlayer(.u))
            set GPSunits[p] = 0
            set .u = null
            if .arrow != null then
                call RemoveUnit(.arrow)
                set .arrow = null
            endif
        endmethod
        
        static method create takes unit for, real x, real y returns thistype
            local thistype this = thistype.allocate()
            local integer p = GetPlayerId(GetOwningPlayer(for))
            local real angle
            if GPSunits[p] != 0 then // already GPS for this player
                call GPSunits[p].destroy()                
            endif
            
            set .onCleanUp = false
            set .endx = x
            set .endy = y
            
            set .u = for
                        
            set .face = GetUnitFacing(.u)*bj_DEGTORAD
            set .curx = GetUnitX(for)
            set .cury = GetUnitY(for)
            
            set .arrow = null
            
            
            set GPSunits[GetPlayerId(GetOwningPlayer(for))] = this
            
            call .newPath() // does all the other settings

            return this
        endmethod
        
    endstruct
    
    private function onTimerPeriod takes nothing returns nothing
        local integer i = 0
        loop
            exitwhen i > bj_MAX_PLAYERS
            if GPSunits[i] != 0 then
                call GPSunits[i].update()
            endif
            set i = i + 1
        endloop
    endfunction
    
    public function UnitSetGPS takes unit u, real x, real y returns nothing
        call UnitGPS.create(u, x, y)
    endfunction
    
    public function UnitRemoveGPS takes unit u returns nothing
        local integer p = GetPlayerId(GetOwningPlayer(u))
        if u != null and GPSunits[p] != 0 and GPSunits[p].u == u then
            call GPSunits[p].cleanUp()
        endif
    endfunction

    private function onInit takes nothing returns nothing
        set mainTimer = CreateTimer()
        call TimerStart(mainTimer, TIMER_PERIOD, true, function onTimerPeriod)
    endfunction


endlibrary

library PASGrid requires PAS
{
    public struct PAS_Grid
    {
        private constant integer MY_NODES = 0xFFFF;
        
        real x0, x1, y0, y1, gridSpace;
        
        integer width;
        integer height;
        
        private method create_child_child (real x, real y, integer w, integer h)
        {
            // notice I don't add any links here -- I'd like a separate "linkTo" 
            // function -- maybe your strings could be in a "linkToMulti" 
            //function that parses the strings?
            PAS_Node.add(MY_NODES + w + width * h, x, y, gridSpace);
            
            // <code to link this node to the ones around it -- will be a fairly
            // complicated loop, so I'm not going to work it out right now>
        }
        
        private method create_child (real x, integer w)
        {
            real y;
            for (y = x0; y0 <= y <= y1; y += gridSpace)
            {
                this.create_child_child.execute(x, y, w, R2I((y - y0) / gridSpace));
            }
        }
        
        static method create (real x0, real y0, real x1, real y1, real gridSpace) -> thistype
        {
            thistype this = thistype.allocate();
            
            real x;
            
            this.x0 = x0; this.x1 = x1;
            this.y0 = y0; this.y1 = y1;
            this.gridSpace = gridSpace;
            
            this.width  = R2I((x1 - x0) / gridSpace);
            this.height = R2I((y1 - y0) / gridSpace);
            
            for (x = x0; x0 <= x <= x1; x += gridSpace)
            {
                this.create_child.execute(x, R2I((x - x0) / gridSpace));
            }
            
            return this;
        }
    }
}

library PAS_Init initializer Init requires PAS
    globals
        private PAS_Node array n
    endglobals
    private function Init takes nothing returns nothing
        set n[1]=PAS_Node.create(100,0)
        set n[2]=PAS_Node.create(200,0)
        set n[3]=PAS_Node.create(100,100)
        call PAS_Link.create(n[1], n[2])
        call PAS_Link.create(n[1], n[3])
    endfunction
endlibrary