wc3campaigns
WC3C Homepage - www.wc3c.netUser Control Panel (Requires Log-In)Engage in discussions with other users and join contests in the WC3C forums!Read one of our many tutorials, ranging in difficulty from beginner to advanced!Show off your artistic talents in the WC3C Gallery!Download quality models, textures, spells (vJASS/JASS), systems, and scripts!Download maps that have passed through our rigorous approval process!

Go Back   Wc3C.net > Resources > Code Resources > Samples
User Name
Password
Register Rules Get Hosted! Chat Pastebin FAQ and Rules Members List Calendar



Reply
 
Thread Tools Search this Thread
Old 12-17-2006, 07:09 AM   #1
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default PAS (Pathing Algorithm System)

NOTE: You have been redirected in order for our attachments to be made available to you. This will only last two minutes; these measures where taken to avoid hotlinking and bandwidth theft.
To avoid these restrictions Log in or Register

UPDATED - Version 2.30

Pathing Algorithm System
by Ammorth
Uses Linked Lists by iNfraNe and CSCache by Vexorian
Special Thanks to Dalten

Now Requires JASS Helper

Features

  • Customizable Node Limit
  • Customizable Links Limit
  • Up to 8191 units are able to receive and follow paths
  • System is relatively easy to set-up, but requires a basic knowledge of JASS
  • Uses the popular A* algorithm with a customizable Heuristic
  • Automatically cleans paths stored on removed or dead units
  • Automatically stores path results to speed up consecutive searches

Download Here (Version 2.30)

This system is designed for an RPG with roads. It allows for easy scripting of units traveling to places, while staying on the roads (preserving the RPG style). I would assume it could be used for other uses, but this is the main intent.

Read-Me

Code:
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



Information on the A* algorithm can be found here

This is a demo map. To install this system into your map, open this map with world editor and follow the instructions.

Give credit if you use this in your map.
Attached Images
File Type: jpg PAS Logo.jpg (58.4 KB, 634 views)
File Type: jpg PAS.jpg (131.8 KB, 705 views)
Attached Files
File Type: w3x PAS V2.30.w3x (108.9 KB, 577 views)
__________________

Last edited by Ammorth : 09-08-2007 at 06:02 AM. Reason: Updated to Version 2.30
Ammorth is offline   Reply With Quote
Sponsored Links - Login to hide this ad!
Old 12-17-2006, 12:52 PM   #2
Freakazoid
I love you all.
 
Freakazoid's Avatar
 
Join Date: May 2003
Posts: 1,915

Submissions (14)

Freakazoid is a jewel in the rough (159)Freakazoid is a jewel in the rough (159)

Default

I can see this being used in a TD. Haven't cheked it, but i'll rep you anyway.
__________________
Freakazoid is offline   Reply With Quote
Old 12-17-2006, 01:34 PM   #3
Vexorian
Free Software Terrorist
 
Vexorian's Avatar


Technical Director
 
Join Date: Apr 2003
Posts: 14,898

Submissions (37)

Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)

Hero Contest #3 - 2nd Place

Default

Reading about how the result works, I am afraid it will 'leak' strings.

You could easily change the result method and use an array of integers instead.
__________________
Zoom (requires log in)Wc3 map optimizer 5.0
Someone should fix .wav sound in this thing.
Zoom (requires log in)JassHelper 0.A.2.A
Turns your simple code into something that is complicated enough to work.
Faster != more useful
Vexorian is offline   Reply With Quote
Old 12-17-2006, 01:44 PM   #4
blu_da_noob
Nonchalant
 
blu_da_noob's Avatar


Respected User
 
Join Date: Mar 2006
Posts: 1,933

Submissions (2)

blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)

[Quicksilver #2] - 2nd Place[Quicksilver#1] 1st place

Send a message via MSN to blu_da_noob
Default

I'm sorry man, but using groups of units for looping and your other recursion stuff? This is crying out for the salvation of JASS.
blu_da_noob is offline   Reply With Quote
Old 12-17-2006, 02:35 PM   #5
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default

Quote:
Originally Posted by vexorian
Reading about how the result works, I am afraid it will 'leak' strings.

You could easily change the result method and use an array of integers instead.

Wow, I would never think string-leaking would be an issue... Okay, ill look into the integer arrays.

Quote:
Originally Posted by blu_da_noob
I'm sorry man, but using groups of units for looping and your other recursion stuff? This is crying out for the salvation of JASS.

Whats wrong with the methods I use? The system runs extremely fast and has no noticeable lag while outputting the path.

I did try make a JASS only version, but ran into problems with the "ForGroup" loop and local variables.

I'll look over the system and see if I can remove the unitgroup loop.
__________________
Ammorth is offline   Reply With Quote
Old 12-17-2006, 02:47 PM   #6
blu_da_noob
Nonchalant
 
blu_da_noob's Avatar


Respected User
 
Join Date: Mar 2006
Posts: 1,933

Submissions (2)

blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)

[Quicksilver #2] - 2nd Place[Quicksilver#1] 1st place

Send a message via MSN to blu_da_noob
Default

For Group's use a separate function, so ofcourse they don't transfer locals. Just use temp globals. Hell, you can usually even find suitable BJ globals, so you don't even need declare new ones.

(Using globals does not "defeat the point of using JASS". If you think that the only advantage JASS has is locals, you're way off.)

Last edited by blu_da_noob : 12-17-2006 at 02:53 PM.
blu_da_noob is offline   Reply With Quote
Old 12-17-2006, 03:47 PM   #7
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default

Okay, I have removed the recursive trigger, the unitgroup loop and increased the maximum node limit to 300.

The system is still in GUI though.

I am only having one slight problem. Changing the output to integer arrays. The problem lies here.

I could put all the nodes in a integer variable (like I'm doing with strings) but complex paths will most likely exceed the integer bit limit.

I could also put all the values in a 2d array, but if the path is too long, it could exceed the array limit. (300 nodes x 30 node-paths = 9000 values = exceeds array limit)

And ideas or can I just keep the string output?

Edit: After some brains-storming, I have came up with 2 ideas (if I'm not allowed to stick with strings)

1) Push the system back to 90 nodes maximum, and then the nodes would always fit the integer array (90 x 90 = 8100 < 8192)
2) Use a gamecache as my array, and store all the values in there, under the proper headings. (there would be a lot of entries for the gamecache, which could be worse than the leaking strings (memory-wise).

Ill do some tests and see which is worse.

Opinnions?

Edit 2: I ran a few tests about string leaks and gamecache memory usage.

Here is the data.

Click to see Data
Hidden information:

Code:
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


As you can see, the increase in memory usage (from threads) is minute. As for a gamecache, it is less information, but the run-time is greater.
__________________

Last edited by Ammorth : 12-17-2006 at 05:48 PM.
Ammorth is offline   Reply With Quote
Old 12-17-2006, 08:48 PM   #8
Dalten
User
 
Join Date: Aug 2003
Posts: 255

Submissions (1)

Dalten is on a distinguished road (19)

Default

Seems to work pretty slick, well done.
Dalten is offline   Reply With Quote
Old 12-17-2006, 09:23 PM   #9
PipeDream
Moderator
 
PipeDream's Avatar


Code Moderator
 
Join Date: Feb 2006
Posts: 1,405

Submissions (6)

PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)

Default

Dijkstra's in GUI = incredible hack. Very nice. However it's impossible to understand, maintain or improve.

- I very much doubt that gamecache is slower than strings
- This is a good spot to use DARY's heap implementation
- Since this is planar, you have a good distance heuristic for A*
- It would be really good to cache the generated paths so that you slowly generate the all-pairs solution. Then this would scale well for units.
- You can go past 90 to 127 nodes in an array for the full dense path matrix because it's symmetric (graph is undirected)
__________________
PipeDream is offline   Reply With Quote
Old 12-17-2006, 10:33 PM   #10
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default

Quote:
Originally Posted by Dalten
Seems to work pretty slick, well done.
Thanks! That means a lot coming from you! After seeing your thief project and the systems involved, you must be quite talented. Let's just say, without your ideas, I would not be here doing these kinds of things today.

Quote:
Originally Posted by PipeDream
Dijkstra's in GUI = incredible hack. Very nice. However it's impossible to understand, maintain or improve.
I will add comments to the triggers once I find a method the mods approve of.

Quote:
Originally Posted by PipeDream
- I very much doubt that gamecache is slower than strings
Iv been around for a few years now, and I've heard gamecache is rather slow.

Another thing I would like to bring up is that using a gamecache would also leak strings because the categories and labels would have to be different. Look at my tests for example. One stores in multiple labels, the other only stores in 1.

Quote:
Originally Posted by PipeDream
- It would be really good to cache the generated paths so that you slowly generate the all-pairs solution. Then this would scale well for units.
Iv thought of this, but I decided against it. The system does all the brute calculations at map init and then just loops through numbers to generate the path. The actual calculations are basic, the run-time is fast; so why not generate everything on the fly. And to store all the values would be a slight waste of memory, in my opinion.

Quote:
Originally Posted by PipeDream
- This is a good spot to use DARY's heap implementation
Can you provide a link, or explain a little bit about what this is? I can't seem to find it anywhere.

Quote:
Originally Posted by PipeDream
- You can go past 90 to 127 nodes in an array for the full dense path matrix because it's symmetric (graph is undirected)
I'm not sure exactly what you mean by that. The nodes, if a player wanted to, could be positioned end to end. This would create a path that equals the number of nodes (maximum). The result would be 127*127 > 8192, which is not allowed.
__________________
Ammorth is offline   Reply With Quote
Old 12-18-2006, 12:15 AM   #11
Vexorian
Free Software Terrorist
 
Vexorian's Avatar


Technical Director
 
Join Date: Apr 2003
Posts: 14,898

Submissions (37)

Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)

Hero Contest #3 - 2nd Place

Default

gamecache can sometimes be the fastest solution, it is not all in the books sometimes a gamecache lookup is great cause it turns the big O to constant.

So you used Dijkstras, hmnn now I am kind of scared to look at it since it is in GUI well pipes DARY is in the resources section should be in systems in the first or second page
__________________
Zoom (requires log in)Wc3 map optimizer 5.0
Someone should fix .wav sound in this thing.
Zoom (requires log in)JassHelper 0.A.2.A
Turns your simple code into something that is complicated enough to work.
Faster != more useful
Vexorian is offline   Reply With Quote
Old 12-18-2006, 12:47 AM   #12
PipeDream
Moderator
 
PipeDream's Avatar


Code Moderator
 
Join Date: Feb 2006
Posts: 1,405

Submissions (6)

PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)

Default

Dynamic array link in my sig.
The path matrix I mean is one that maps current node to next node in path given some target. You would generate a path from it like this:
Collapse JASS:
function GetPath takes matrix pathmatrix, integer source, integer dest returns path
    loop
        exitwhen source == dest
        set source = getnextnodeinpath(pathmatrix,source,dest)
        if source == unknown then
             dijkstra(pathmatrix,source,dest)
        endif
        if source == no path exists then
             error out
        endif
        add source to path
    endloop
endfunction
Since the path from i to j is equal to the path from j to i backwards, the matrix is symmetric, so you only need to store (n^2+n)/2 of its elements.
As a side bonus using the path matrix representation lets you plug in various other pathing algorithms in instead of dijkstra. It takes full advantage of any extra path information an algorithm finds-in dijkstra's case, the shortest paths to all the nodes from the source.

The dijkstra lists for 127 nodes will also fit into an 8192 element array. For your pathological end to end example, you have one list of length 1, one of 2, ... up to 126 or 127. Again that's (n^2+n)/2 total elements which <8191 for 127.
__________________
PipeDream is offline   Reply With Quote
Old 12-18-2006, 05:11 AM   #13
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default

Well, let me just say "I think I did it!"

I have done the following:

1) Kept the 300 node maximum
2) Removed the use of strings in the output. The system now stores the output (as integers) in a gamcache under an array of labels, under the Unit ID of the called unit.
3) The system is still in GUI (Vexorian, you should take a look at it. I use a few conditional loops. )
4) Included the movement system into the actual pathing system. This allows for full functionality of the system.


I am cleaning up all unused variables, adding comments to the system, and double-checking all the code.

PipeDream, my system can be symmetrical, but it also allows for "one-way" nodes. So a unit could go from node 001 to node 002, but not backwards to 001. The algorithm would then find a way around it.

I hope this meets the standards of the mods!

I'll see what you all think when I upload it.
__________________
Ammorth is offline   Reply With Quote
Old 12-18-2006, 11:12 PM   #14
xombie
Banned
 
Join Date: Oct 2006
Posts: 858

xombie has a spectacular aura about (79)xombie has a spectacular aura about (79)xombie has a spectacular aura about (79)

Default

Could you perhaps apply this same logic to locations, hence creating a far smaller node and more usefulness. As of now, Warcraft has a maximum movespeed of 522. With a more precise system (far far more nodes) you could use a SetUnitPosition loop to move a unit faster than 522, but within the same path (because blizzard has some sort of shortest path algorithm as well, which tells a unit where to go when you click 'Move')
xombie is offline   Reply With Quote
Old 12-18-2006, 11:18 PM   #15
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default

Quote:
Originally Posted by xombie
Could you perhaps apply this same logic to locations, hence creating a far smaller node and more usefulness. As of now, Warcraft has a maximum movespeed of 522. With a more precise system (far far more nodes) you could use a SetUnitPosition loop to move a unit faster than 522, but within the same path (because blizzard has some sort of shortest path algorithm as well, which tells a unit where to go when you click 'Move')

You could modify the movement trigger to move the units in increments, instead of ordering the unit to move there. This would get taxing on the system though if you were to have many units being moved at once.

The system does use GUI locations. You can make them as small as you want and as close as you want, You just are not able to exceed 300 nodes. The pathing system built into warcraft 3 finds absolute distances. This system can keep units on a path, between nodes.

Hope that answers your question.
__________________
Ammorth is offline   Reply With Quote
Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off


All times are GMT. The time now is 03:51 AM.


Affiliates
The Hubb The JASS Vault Clan WEnW Campaign Creations Clan CBS GamesModding Flixreel Videos

Powered by vBulletin (Copyright ©2000 - 2019, Jelsoft Enterprises Ltd).
Hosted by www.OICcam.com
IT Support and Services provided by Executive IT Services