PAS (Pathing Algorithm System)

Pathing Algorithm System  Version 2.30 - README

Created By Ammorth

Uses Linked Lists by iNfraNe and CSCache by Vexorian

Special thanks to Dalten

Please give credit if you use it in your map.


=============Installation===============

1) Copy the "PAS System" trigger to your map.
2) Copy the custom unit "Pathing Node" ('h000') to your map
3) If you do not already have CSCache or LinkedLists in your map, copy the "CSCache" and/or the "LinkedLists" libraries (triggers) to your map
4) Make sure to save your map using JASSHelper (best used with the JASS NewGen Pack http://www.wc3campaigns.net/showthread.php?t=90999)

==================Usage=================

First off, you have to make the regions in WE.  Create regions at all the intersections or between the paths.
Units will walk in a relatively straight line, so if the road curves, its good to place a few to guide the unit along.
You can look at the demo map for an example.

Now, you must modify the user Input section of the PAS System (near the very top, within the "= Start of User Input =" and
"= End of User Input =").  To do this, use the following functions and the demo setup as a guide:


--> function PAS_CreateNode takes integer nodeNum, rect nodeRect, string nodeLinks, string nodename, real radius returns nothing

This function creates a node to be used in the system.
 - nodeNum is the number of the node (the first node should be 1 and the second should be 2 and so on).
 - nodeRect is the name of the region you placed in the WE.  Please note that the regions start with "gg_rct_" and
   then have the region name (spaces are converted to underscores "_" ).  Example: region "Node 01" would be
   "gg_rct_Node_01".
 - nodeLinks is a string that contains the information that the node links to (like a path between the nodes).  Make
   sure that you stick hyphens( "-" ) in between the different nodes.
 - nodeName is an optinal setting to assign a name to a node (to be used with pathing to a named node).  It simply
   takes a name of the node.
 - radius is the distance the unit pathing must be from the node for it to have "arrived".  Set this to any value equal to
   or below 0 to use the system default.

Example:  call PAS_CreateNode(1, gg_rct_Node_001, "2-24", "first node")


--> function PAS_SystemSettings takes integer maxNodes, integer maxLinks, integer nodeID, real fromDistance, real sampleRadius, real sysPeriod returns nothing

This function sets up all the values used in the system.
 - maxNodes is the total number of nodes in the system.
 - maxLinks is the total amount of links any one node can have.
 - nodeID is the ID of the node unit that you copied from the demo map.  An example is 'h000' (with the ' ' ).  To get
   this number, go to the Object Editor (F6) and select "View > Display Data is raw Values" (Crtl + D).  Now, navigate
   to the custom units and find the pathing node unit.  It should say "h###:hfoo (Pathing Node)" and all you need is the
   "h###" where the numbers are displayed.  Then you take that and place it between ' and '.
 - fromDistance is the distance the unit has to be from the node to classify as "arrived". (default is 64.00)  This is a
   system default and will be used if a node requests the system default.
 - sampleRadius is the distance away from the unit the system check for near-by nodes to start from. (default is 1024.00)
 - sysPeriod is the time (in seconds) between checks to see if the unit has reached the correct node. (default is 0.10)

Example:  call PAS_SystemSettings(29, 3, 'h000', 64.00, 1024.00, 0.10,)


Notes: - The system uses a Heuristic that can be customizable to your system.  It is located in the Custom Script Section
         right after the global variables.  There, you can read up about each of the different methods and learn how to make
         your own if need be.  The default is "real distance" remainning.  You can read more about the heuristics further in
         this README. 

       - (PAS_MaxNodes-1)*PAS_MaxLinks+PAS_MaxLinks cannot exceed 8190 due to the limit of array slots. If you do, your system will run
         into serious problem.  Normally, if this becomes a problem, large path-searches will result in a thread op (thread limit).
         Methods of preventing this include using less nodes/links.

       - When a unit dies or is removed, the system now removes the path from the unit.

       - The system uses JassHelper's built in debug mode.  To turn on debug mode and recieve error messages if an error occurs, make
         sure to check "Debug Mode" within JassHelper's menu.  When all the bugs have been fixed, you can turn it off to remove the
         debug code from the system on save, to speed up performance and remove the messages.
         
       - Becuase of the way the paths are generated, getting different paths within the same thread can result in an OP limit.  This
         problem has been reduced in Versions 2.30 and later since the system now stores and reuses paths that were already generated.
         Keep in mind, large path searches may also result in an OP limit.

Once all this is done, the system is ready to find paths and move units.  To do so, you can use the following functions.


--> function PAS_IssuePathOrderToNode takes unit whichUnit, integer toNode, string order, boolean instant returns boolean
 - whichUnit is the Unit you want to assign a path to.
 - toNode is the node number of the node you want the unit to move to.
 - order, this is the order string that will be used to move the unit.  Only certain orders are supported since the nature of
   the system is to continually order the unit to a new node when it reaches the current one (patrol will not work for the entire path).
   the default values are "move" or "attack" or "smart"
 - instant, if set to true will make the unit update to the new path instantly, instead of when it stops moving.
 
This function returns a boolean that, if false means the pathing failed to find a path.  An error Message will be displayed
on the screen if DEBUG is turned on.

Example:  call PAS_IssuePathOrderToNode(someUnit, 23, "move", false)

Note: The above function searches for a path.



--> function PAS_IssuePathOrderToName takes unit whichUnit, string name, string order, boolean instant returns boolean
 - whichUnit is the Unit you want to assign a path to.
 - nodeName is the name of the node you want the unit to move to.
 - order, this is the order string that will be used to move the unit.  Only certain orders are supported since the nature of
   the system is to continually order the unit to a new node when it reaches the current one (patrol will not work for the entire path).
   the default values are "move" or "attack" or "smart"
 - instant, if set to true will make the unit update to the new path instantly, instead of when it stops moving.
This function returns a boolean that, if false means the pathing failed to find a path.  An error Message will be displayed
on the screen if DEBUG is turned on.

Example:  call PAS_IssuePathOrderToName(someUnit, "start", "attack", true)

Note: The above function searches for a path.


--> function PAS_CancelPathOrder takes unit whichUnit, boolean stop returns nothing
 - whichUnit is the unit you want to cancel the order for, or delete the current path for.
 - stop, if set to true will order the unit to stop where it is instead of it continuing it's current order.

Note: PAS Versions 2.30 and later now remove the path automatically when the unit dies or is removed.  It is still good practice to
      remove the paths yourself before removing or killing a unit.


--> function PAS_LoadPathToMemory takes integer start, integer end returns boolean
 - start is the beginning node of the path to be saved
 - end is the ending node of the path to be saved

Note: PAS Versions 2.30 and later now use an internal path storage system to store paths.  Paths are stored automtically after a search
      and are then reused on the same search to same processor.  This function can be used to load paths to memory that would be used often,
      to save processing time later on.  
  
The boolean returned will be true if the path was loaded and false if the nodes were invalid or the path already exists in memory

Example:  call PAS_LoadPathToMemory(3, 18)

Note: The above function searches for a path.


function LoadPathToMemoryByNames takes string start, string end returns boolean
 - start is the beginning node of the path to be saved
 - end is the ending node of the path to be saved
  
Note: PAS Versions 2.30 and later now use an internal path storage system to store paths.  Paths are stored automtically after a search
      and are then reused on the same search to same processor.  This function can be used to load paths to memory that would be used often,
      to save processing time later on.  
  
The boolean returned will be true if the path was loaded and false if the nodes were invalid or the path already exists in memory

Example:  call PAS_LoadPathToMemory("barn", "house")

Note: The above function searches for a path.


==============The Heuristic============

The heuristic is the reason the A* algorithm is so effective; it is the brain of the system.  A heuristic is an algorithm that
simply guesses something.  In PAS the heuristic guesses the distance left to reach the destination.

The heuristics can be found in the PAS System trigger near the top, right after the input section.

Why are heuristics good?  Well, a heuristic can quickly eliminate paths that are unlikely to reach the destination.  They also
decided which paths that could reach the destination are the mostly likely to reach it the fastest.  Normally when trying to
find a path from point A to point B there are multiple routes, each taking a slightly different time than the others.  The 
heuristic can guess (fairly close to the start) which path should reach the destination the quickest.  Sometimes it's incorrect
but then A* backtracks and tries the next best path.

A* is only as good as the heuristic is.  If you plan on using a custom heuristic, it's best to make sure what you want.  The
heuristic should ALWAYS choose the shortest POSSIBLE path at any-time (even if it currently is impossible to reach the destination
in the distance it guesses)!  This is so then A* can always find the shortest path.

The Real Distance version, is the best heuristic possible, which is why it is used as the default:

function PAS_AStarHeuristic takes real x1, real y1, real x2, real y2 returns real
    return SquareRoot((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))
endfunction

Lets break it down.  The system gives the heuristic 2 points (2 cordinates each).  The heuristic then compares the points and
finds the shortest distance remainning to get from point 1 to point 2.  As you can see, this simply uses the distance between
points formula to predict the shortest path (which is a straight line from A to B).

Another Heuristic insluded is (what I call) the "Grid Path" heuristic.  This heuristic finds the shortest grid path from A to B.

function PAS_AStarHeuristicGridPath takes real x1, real y1, real x2, real y2 returns real
    local real a = x1-x2
    local real b = y1-y2
    if a < 0 then
        set a = -a
    endif
    if b < 0 then
        set b = -b
    endif
    return (a + b)
endfunction

This function gets the absolute value of the difference in X and difference in Y of the 2 points, adds them up and returns it
as the shortest possible path.  This should only be used if your paths are COMPLTELY Grid-like in the sense that units can only
go up, down, left, or right.  If any diagonals, curves or the like are used, use the Real Distance heuristic.

===============Version Log=============

  --2.30--
  
    - PAS now saves paths internally and reuses them in later searches.
    - Functions that take a name now use a table to increase search time for named nodes
    - The Movement function has been changed to a stack method instead of the unitgroup method from before
    - Structs have been introduced to store path data for the units as well as returning point data for the segment function
    - Units will now locate the nearest path and start from there.  This has been changed from the nearest node.  This prevents units from
      back-tracking and cutting corners.
    - Path orders now take an order string as an argument in place of a boolean (more control).
    - 

  --2.23--

    - Converted to CSCache for storage methods in-place of PAS_DATA (creates more stability within the system and it is a more general method.)
    - Now uses JassHelper's built in debug mode to debug the code.

  --2.22--

    - Made the system within libraries to condense it and allow the user-input stuff near the top
    - Added custom distances for nodes to allows for larger or smaller nodes
    - Revised parts of the README to include information on the heuristic.

  --2.21--

    - Changed the storage method from UserUnitValue to 3 integer global arrays stored by the Handle number of the unit in question

  --2.20--

    - Added functionality to calculate a path and then store it for quicker path issuing (if you use the same path many times)
    - cleaned up a few leaks
    - Added an easy method to change the attachment functions used so maps that already use UnitUserData can still use the system
      by changing the functions to use a different method of storage
    - Changed the method of system setup input to functions instead of setting variables


  --2.10--

    - Re-wrote the A* algorithm function so it always finds the best path (if the heuristic permits)
    - Added boolean "instant" to the pathing functions so the user can order the unit on the next path right-away, instead of
      waiting for the next node.
    - Added boolean "stop" to the cancel function so it can be used to clear the list attached to units who are to be removed or die.

  --2.00--

    - Re-wrote the entire system from scratch
    - Now requires JASSHelper to work (if there is demand, may release a non-JASSHelper Version)
    - Changed the algorithm to A* (A-Star)
         *Reason* - Dijkstra's Algorithm was having problems with thread limits and did too many calculations to find paths
                  - A* does way less calculations on average and still finds the optimal path (only if the heuristic used is
                    optimized for the current system).

    - Replaced the GameCache with Linked Lists (thanks iNfraNe)
    - Added node names

  --1.05--

    - Converted the final trigger to JASS
    - Cleaned up some more BJ functions that I missed
    - fixed some of the conditions so they are more optimized

  --1.04--

    - Cleaned up a few lines of JASS to improve performance.

  --1.03--

    - Converted the main triggers to JASS
    - Cleaned up a few performance issues and installation problems.

  --1.02--

    - Changed the order of the System Triggers to allow for an easier installation
    - Fixed the preview image.

  --1.01--

    - Completely revised the script, and removed un-needed code
    - Changed from a string-based system, to a integer-based system
    - Included the MOVEUNITS trigger into the system
    - Increased the maximum number of nodes to 300
    - Other changes and fixes

  -1.00--

   - First Public Release

Set 1000 different Strings

Before        First      Second
85,856K       86,080K      86,064K
85,896K       86,104K      86,072K
85,160K       85,348K      85,400K

1000 Different GC Values (this uses different strings which may interfere with the data)

Before        First
85,908K       86,208K
85,728K       86,028K
85,156K       85,460K

1000 Different GC Values in same Category and Index (does not show memory used to store values)

Before        First
85,168K       85,252K
85,912K       85,996K
85,860K       85,936K

A loop that ran until thread limit (5882 loops) that set different string values

Before        First      Second
85,724K       87,728K      87,856K
85,160K       87,168K      87,224K
85,160K       87,160K      87,228K