Wc3C.net Pathing - Don't Understand
 Register Rules Get Hosted! Chat Pastebin FAQ and Rules Members List Calendar

11-27-2008, 12:24 AM   #1
bomber7
User

Join Date: Sep 2007
Posts: 102

Pathing - Don't Understand

This problem has bothered me for awhile and no matter how I look at it I can never quite figure it out.

The Problem: I want a system/trigger that can tell a unit how to get from A to B stepping on only a certain type of terrain.
The Facts:
-The certain type of terrain actually makes up a road.
-The road only makes 90 degree turns and intersections.
-The road is always a set width/height. (Made of a single repeating unit)
-The system must be fast as it will be in use with up to a hundred (possibly more) units at any one time

Now with the above in mind I'm going to take you through my thought process.
The following details how I attempted to solve my problem. I'm not sure if even the first step is right, but nonetheless here it is.

1. The upper left shows an example of how the terrain might look. Black is terrain the unit can move on.

2. I figured that a good start would be to place a node at every turn/intersection in the road. It kind of made me think of a system of router/hubs. Each router/hub tells the packet to go to the next router/hub in line until finally one gives it a computer as a destination.
It might be possible to make a rect. at each node (Programatically if I figure out how, or manually if not)
When a unit enters this rect, the units final destination would be determined, and it would send the unit to the next node that would work towards getting there.

3. I decided it was pretty important to note that a unit's path can start/end where there isn't a node. Thats another problem with the node idea.

It comes down to the fact I have no idea how to calculate which node to send a unit to. The closest node isn't always going to be the solution because sometimes there isn't a path between the two nodes.

-----------------------------------------------------------------------

I don't care whether or not your idea/plan builds off of my node idea, I just need something that works. I don't even need a working trigger. Just a concept. I consider myself quite adept at Jass/vJass though maybe that's just me being an idiot (lol)

Attached Images
 Question.jpg (12.1 KB, 24 views)

Last edited by bomber7 : 11-27-2008 at 12:26 AM.

11-27-2008, 12:35 AM   #2
Pyrogasm

Respected User

Join Date: Sep 2006
Posts: 4,523

Submissions (9)

...and this is why people make systems :)

You have two options, both of which are equally good resources: SSP or PAS.
__________________
Quote:
 Originally posted by Rising_Dusk Your spells are mostly ignored because they are not very cool so we aren't very excited to review/approve them, but you are incredibly persistent and won't give us an excuse to graveyard it. That is generally what results in a resource being ignored for a long time.

The Spell Request ThreadDone for, unless someone else wants to revive it...
It lasted a damn long time.

Quote:
 Originally posted by Kyrbi0 Huh. Almost makes me wish I had a girlfriend, to take advantage of today (wait, no, that's not what I meant... I mean, take advantage of the fact that it is international women's day... gah, never mind).
Quote:
 Originally posted by Pyrogasm Rome may not have been built in a day, but the Romans sure as hell didn't say "look at this great city we built guys!" when they had nothing more than a bit of stone and some cottages.

 11-27-2008, 12:42 AM #3 bomber7 User   Join Date: Sep 2007 Posts: 102 Thank you. Alot. I really did try searching. Anyway, thanks. I should be able to use/modify one of those to fit my situation. Edit: After looking at both of those systems neither actually generates a node-map. (Both of them require you enter it in) I'll have to make some code to generate the path itself. That's going to be a pain. However, I think I can handle it. I'll post back if I can't. Last edited by bomber7 : 11-27-2008 at 01:00 AM.
11-27-2008, 01:47 AM   #4
Ammorth

Join Date: Sep 2006
Posts: 1,812

Submissions (10)

I was looking at upgrading my PAS to generate its own node path based on terrain tiles. There are a few issues with this though, regarding tiles have to be joined for a path to exist between them. This causes limitations in the terrainning aspect as roads need to be solid and cannot break up with bits of grass.

I think the most effective way to generate the node map would be with a JAPI script that generates the code which contains all the node info. Then the use would copy the generated script back into the map. This would then remove the need to scan the map and generate the nodes on each map load, greatly decreasing loading time.
__________________

 11-27-2008, 02:03 AM #5 bomber7 User   Join Date: Sep 2007 Posts: 102 Sorry, I'm unfamiliar with japi. Is there a link where I could learn more? Also, if you have any tips to simplify the process of making the nodes I could use them. Its pretty damn complicated (and not very fast) the way I have it pictured right now. The way I'm approaching it right now: Start the process at the end of one road. It will then proceed to explore that road way (going straight) Whenever it detects a branch/turn in the road it sends another of itself to go look through that roadway. (In other words it calls itself) Each instance of the function terminates when it reaches the end of its road, going in a straight line at all times. The tricky part is having the function also terminate when it encounters a road that has already been 'explored' That part can make the whole process very slow especially if I'm making a bunch of nodes. Last edited by bomber7 : 11-27-2008 at 02:10 AM.
11-27-2008, 02:13 AM   #6
Ammorth

Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Think about a maze generation algorithm. If you want to look it up, while I post what I mean, check wikipedia.

Start at any node and mark it in the closed list. Add nodes adjacent to this node to the open list.

Now, loop through all nodes in the open list and add them to the closed list. For any adjacent nodes, check if they are in any of the lists. If they are in the open list, add them to close. If they are in neither of the lists, add the node to the open list.

Note: each node can only exist in one list at a time (aka. adding to closed means remove from open and add to close).

While you are doing this, keep track of which nodes link to which. Now, since your paths are straight, you can count a continual path in the same direction (without a junction) as the link between 2 nodes.

Say you were at an intersection node. When you proceed to the east, you would continue going east till you reach a node that has nodes that are adjacent north west or south, or a node that has no east adjacent (dead end). This node would be your next node, and it would link to the previous node. So you don't have to keep track of the links, only the nodes.

Essentially what you would get is a list of nodes and the nodes they are adjacent to. Now, you need an algorithm to traverse the nodes. A* (the one used in PAS) is probably your best bet for performance. It still isn't the best, so I would store paths after they are generated (using a gamecache or something).

If you want to your your router/hub system, you would have to keep track on which nodes, the adjacent nodes link to and continue till every node knows how to get to every other node. This can be messy, and I don't know of an efficient way of doing this via script (manually seems rather easy).
__________________

Last edited by Ammorth : 11-27-2008 at 02:25 AM.

11-27-2008, 06:08 AM   #7
bomber7
User

Join Date: Sep 2007
Posts: 102

I'm sorry, but after trying that in my head, and on paper. I really don't understand what you mean. What nodes is the above based off of?

On the bright side, I was about 80% successful with the following code.
It took me a couple of hours to get this far.

Basically it starts at one road, and sends a probe which only goes straight along that road. Whenever that probe detects branches in the road its following, it creates a node, links the node to the previous node, and sends another probe down the detected branch.

If one probe detects a node along its current path, it detects its previous node with the detected node then terminates. If a probe hits the end of its road, it terminates.

Here are some screenshots. The green balls are the automatically generated nodes. Obviously I still have some bugs to work out, it didn't get all the roads (Some branches remained un-realized for some reason), and in one location it placed a node on a location that wasn't road.

The first probe is sent downwards starting at the location of the peasant/footman. (I used units for testing purpose so I could easily relocate the start location of the probe (and thus node) network.

JASS:
```globals
constant real Percision = .1 //Precision of determining middle of first road of starting point
constant real ROAD_SIZE = 642.53 //The width of the road (as best as I could tell)
constant real CHECK_DIST = 10 //This is the distance the probe goes before checking for intersections/turns
constant real ROAD_BRANCH = ROAD_SIZE/2 + 20 //This is the distance to check away from the center of the road to determine if thr road branches/turns
constant real JUMP_DIST = ROAD_SIZE/2 + 10 //The distance away from the probe that the new probe will be spawned at (to check out a road branch.)
real ExploreX //These globals are used to pass values over executefunc
real ExploreY
integer ExploreD
Node LastNodeMade //This is also used to pass values over functions. Sort of like the GetLastCreatedUnit() bj.
Node array AllMadeNodes //An array storing all the nodes currently created
integer CurrentNodeAmount = 0 //used when trying to pass through the above array
boolean GlobalTerm = false //Not used anymore, was used for testing.
endglobals

struct Node //The node itself
real x = -1
real y = -1
integer Attachs = 0 //Amount of Nodes attached to this node
Node array AttachNodes[5] //The other nodes actually attached to this one
endstruct

function NodeOnTop takes real x, real y returns integer //A small function for determining if there are any nodes very close to a location
local integer a = 0                                     //Used when preparing to make a new node. (no point in making a new node if theres one 10 pixels from it)
local real dx
local real dy
loop
exitwhen a == CurrentNodeAmount
if ((dx*dx+dy*dy) <= 100) then //I don't use square root, instead I simply square the distance
return AllMadeNodes[a]     //This cuts down on processor usage
endif
set a = a + 1
endloop
return 0
endfunction
function BuildNode takes nothing returns nothing //A neat little function for preping another node for me, probably a waste of processor time, but oh well
set AllMadeNodes[CurrentNodeAmount] = Node.create() //Makes the new node
set CurrentNodeAmount = CurrentNodeAmount + 1 //Adds it to the list
endfunction
//The arm function is a probe. It moves in only ONE direction. When it detects branches to the left/right of itself it sends more probes down those paths.
function RunArm takes real Cx, real Cy, integer Direction returns nothing
local real AddX //These two are used to move the probe the direction its moving, up/down/left/right
local real x = Cx //I want to be able to change x,y
local real y = Cy
local real nx //used when preparing to make a node/ sending a new probe
local real ny
local boolean GoingUp = (Direction == 90) //Saves a bit of processor time
local boolean GoingLeft = (Direction == 0)
local boolean GoingRight = (Direction == 180)
local boolean GoingDown = (Direction == 270)
local boolean SomethingFound = false //Used when the probe hits the end of its road to terminate it
local real FoundDist1 = 0 //I don't want to detect the same branch more than once. This helps me do that.
local real FoundDist2 = 0
local boolean MadeANode = false //Disabled at the moment, probably enabled soon again.
debug call BJDebugMsg("Arm called to discover " + I2S(Direction))

if GoingLeft then //Sets the variables that determine the probes movement direction.
elseif GoingUp then
elseif GoingRight then
elseif GoingDown then
else
call BJDebugMsg("Critical Error <Pathing>: UNKNOWN DIRECTION " + I2S(Direction))
return
endif

loop
exitwhen SomethingFound or GlobalTerm //Somethingfound is true when you hit the end of the road. globalterm is for debug purposes

if FoundDist1 > 0 then //This counts the variable down. The variable is set to the roads width when the probe detects a road on the right or left
set FoundDist1 = FoundDist1 - CHECK_DIST //This stops it from detecting another road on that same side until this variable is 0. (Thus you don't detect the same road twice)
endif
if FoundDist2 > 0 then
set FoundDist2 = FoundDist2 - CHECK_DIST
endif

if not (GetTerrainType(x,y) == 'Ybtl') then
set SomethingFound = true
else
//Detect Intersection/Turn
if GoingDown or GoingUp then //Argh, it gets complicated here
if (GetTerrainType(x-ROAD_BRANCH,y) == 'Ybtl') and (FoundDist1 <= 0) then //Determins if theres a branch on the left
debug call BJDebugMsg("Branch Going Left")

set nx = x
if GoingDown then //This decides the location of the node.
set ny = y-(ROAD_SIZE/2) //You want to put it in the center of the intersection
else
endif

set AlreadyHere = NodeOnTop(nx,ny) //This determins if theres a node already at the location or not
if not (AlreadyHere == 0) then //If there is, it connects the previous node to that one, then ends the probe
debug call BJDebugMsg("Node found, connecting and terminating.")
set AlreadyHere.Attachs = PrevNode.Attachs + 1
set LastNodeMade.Attachs = PrevNode.Attachs + 1
return
endif
//If theres no node, it makes one.
set ExploreX = nx
set ExploreY = ny
set ExploreD = 180
call ExecuteFunc("ExploreNow") //This initiates the preparation of a probe to explore the branch that was found
//I probably need the madeanode, but for debug purposes its been removed

call BuildNode()
//Makes the node visible if debug mode is on
//Attaches the new node to the previous node.
set PrevNode.Attachs = PrevNode.Attachs + 1
set LastNodeMade.Attachs = PrevNode.Attachs + 1
//endif

endif //Now the next three if/thens are simply duplicates of the above with different directions.
if (GetTerrainType(x+ROAD_BRANCH,y) == 'Ybtl') and (FoundDist2 <= 0) then
debug call BJDebugMsg("Branch Going Right")

set nx = x
if GoingDown then
else
endif

if not (AlreadyHere == 0) then
debug call BJDebugMsg("Node found, connecting and terminating.")
set AlreadyHere.Attachs = PrevNode.Attachs + 1
set LastNodeMade.Attachs = PrevNode.Attachs + 1
return
endif

set ExploreX = nx
set ExploreY = ny
set ExploreD = 0
call ExecuteFunc("ExploreNow")

call BuildNode()

set PrevNode.Attachs = PrevNode.Attachs + 1
set LastNodeMade.Attachs = PrevNode.Attachs + 1
//endif

endif
else //See Above
if (GetTerrainType(x,y-ROAD_BRANCH) == 'Ybtl') and (FoundDist1 <= 0) then
debug call BJDebugMsg("Branch Going Down")

set ny = y
if GoingRight then
else
endif

if not (AlreadyHere == 0) then
debug call BJDebugMsg("Node found, connecting and terminating.")
set AlreadyHere.Attachs = PrevNode.Attachs + 1
set LastNodeMade.Attachs = PrevNode.Attachs + 1
return
endif

set ExploreX = nx
set ExploreY = ny
set ExploreD = 270
call ExecuteFunc("ExploreNow")

call BuildNode()

set PrevNode.Attachs = PrevNode.Attachs + 1
set LastNodeMade.Attachs = PrevNode.Attachs + 1
//endif

endif //See Above
if (GetTerrainType(x,y+ROAD_BRANCH) == 'Ybtl') and (FoundDist2 <= 0) then
debug call BJDebugMsg("Branch Going Up")

set ny = y
if GoingRight then
else
endif

if not (AlreadyHere == 0) then
debug call BJDebugMsg("Node found, connecting and terminating.")
set AlreadyHere.Attachs = PrevNode.Attachs + 1
set LastNodeMade.Attachs = PrevNode.Attachs + 1
return
endif

set ExploreX = nx
set ExploreY = ny
set ExploreD = 90
call ExecuteFunc("ExploreNow")

call BuildNode()

set PrevNode.Attachs = PrevNode.Attachs + 1
set LastNodeMade.Attachs = PrevNode.Attachs + 1
//endif

endif
endif
endif
if MadeANode then //This was only enabled for debug purposes to simplify the network. not used at the moment
//return
endif
set x = x + AddX //Moves the probe along its path
set y = y + AddY
//call CreateUnit(Player(0),'h000',x,y,0) //THis enabled a visual path of the probes, only used for major debugging. Probably not going to be used anymore.
endloop

//call BJDebugMsg("ENDED")
//call CreateUnit(Player(0),'h000',x,y,0)
endfunction

function ExploreNow takes nothing returns nothing
local real x = ExploreX //Load up the globals into locals
local real y = ExploreY
local integer direction = ExploreD
//if ExploreD
call TriggerSleepAction(0) //Sleep. This prevents a very strange WC3 crash. (The window closes w/o error.)

if direction == 0 then //This sets the new probe up to start a bit along the road its supposed to discover.
set x = x + JUMP_DIST
elseif direction == 90 then
set y = y + JUMP_DIST
elseif direction == 180 then
set x = x - JUMP_DIST
else
set y = y - JUMP_DIST
endif
set LastNodeMade = ToPass //Pass the node using the global variables
call RunArm(x,y,direction) //Run the probe
endfunction

function BuildNodes takes nothing returns nothing //Everything starts here
local real x = R2I(GetUnitX(gg_unit_hpea_0002)) //This gives the general starting location of the probe.
local real y = R2I(GetUnitY(gg_unit_hpea_0002)) //I used a unit so I could move it around and test everything
loop
exitwhen (not (GetTerrainType(x,y) == 'Ybtl'))
set x = x + .1
endloop
set x = x - ROAD_SIZE/2
loop
exitwhen (not (GetTerrainType(x,y) == 'Ybtl'))
set y = y + .1
endloop
set y = y - ROAD_SIZE/2 //These two above loops center the starting spot in the road.

call BuildNode() //Builds the very first node.

call RunArm(x,y,270)
debug call CreateUnit(Player(0),'h000',x,y,0) //Make the node visible in debug mode.

//call TriggerSleepAction(20) //Debug junk
//set GlobalTerm = true
endfunction

//===========================================================================
function BuildNodesWait takes nothing returns nothing
call TriggerSleepAction(1)
call BuildNodes()
endfunction

function InitTrig_BeginNodeCreation takes nothing returns nothing
call ExecuteFunc("BuildNodesWait")
endfunction

```

If anyone sees any problems in my code that may have caused the above mentioned bugs.

Sorry about not understanding your suggestion Ammorth, I'm kind of tired right now.

P.S. I know theres several location where a simple change in my code would give a slight reduction in processor time usage. I'm quite tired now and haven't gotten around to optimization yet. First I need it to work.
Attached Images
 WC3ScrnShot_112608_222729_05.gif (357.6 KB, 15 views) WC3ScrnShot_112608_222723_04.gif (348.5 KB, 10 views) WC3ScrnShot_112608_225038_01.gif (130.7 KB, 11 views)

11-27-2008, 07:18 AM   #8
Ammorth

Join Date: Sep 2006
Posts: 1,812

Submissions (10)

uploaded an image to try show what I mean. The green dots are the travelling nodes, the yellow nodes are the open nodes, the red nodes are the closed nodes

some pseudo-code
Code:
```add first node to open stack (group)
while open group isn't empty
select node from top of open stack
select an untravelled path at random adjacent to chosen node
if no untraveled paths left for the node
remove node from stack
else
proceed till an intersection is reached
if intersection is not open
endif
endif
endwhile```

I just noticed I made a bunch of mistakes on when I closed the nodes. The nodes should have been closed in the opposite way they were reached. So, you will close the first node last and then you will finish.
Attached Images
 node-gen.gif (44.9 KB, 11 views)
__________________

11-27-2008, 08:46 PM   #9

Respected User

Join Date: Apr 2003
Posts: 1,699

Submissions (10)

A* is a great algorithm for pathfinding, i suggest u go study it :) im planning on making a pathfinding system too
__________________
Current Projects:
 MaDOS (outdated) System for object movements & effects - NEW VERSION IS UNDER W.I.P Cinematic System System for making better cinematics and with fancy effects Timing System Timing system that simulates the usage of PolledWait just with 0.01 accuracy

 11-29-2008, 01:19 AM #10 bomber7 User   Join Date: Sep 2007 Posts: 102 Thank you for the informative gif. 53 frames of pathing goodness ^.^ Anyway I got the node system all figured out. It properly creates/links all nodes. The registration process (registering it with PAS) works pretty good too. (Though in debug PAS points out some errors in the node links, mostly its all good) I can order units to go from node to node and watch PAS path them out. Its almost beautiful. Lol Anyway, I have another requirement which I'm wondering if PAS can handle. Currently, my code autogenerates a network of 89 nodes. My requirement is I'm going to need four such networks which will be totally independent of eachother. Each node has a max of three connections. (My code doesn't totally work at a four way intersection, and in my laziness I just modified them to make them two three way intersections...) Can PAS handle individual networks? (No nodes in the first network will ever be connected to any nodes in any other network.) No units will be ordered to go from one network to the next. Last edited by bomber7 : 11-29-2008 at 01:24 AM.
11-29-2008, 01:37 AM   #11
Ammorth

Join Date: Sep 2006
Posts: 1,812

Submissions (10)

PAS should be able to handle any number of node connections you need. If you can't get it to work, you can send me the code (pm or email at ammorth(at)gmail(dot)com and I can help you debug it).

As for multiple networks, PAS can handle them, but be warned: If you try and order a unit from 1 network to a node in the other, PAS will have to search though the entire originating network before it returns an error (aka, no path). You could get around this by either making sure networks don't ask for paths to eachother, or verifying, before passing the value, that the nodes exist in the same network (depending on how set-up the nodes within PAS, it could be by node range). If you can't do either, just make sure the networks are small enough that PAS can traverse the entire network before reaching the op limit.
__________________