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 > Warcraft III Modding > Developer's Corner > Triggers & Scripts
User Name
Password
Register Rules Get Hosted! Chat Pastebin FAQ and Rules Members List Calendar



Reply
 
Thread Tools Search this Thread
Old 11-27-2008, 12:24 AM   #1
bomber7
User
 
Join Date: Sep 2007
Posts: 102

bomber7 is on a distinguished road (12)

Default 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.

(PLEASE SEE ATTACHED DIAGRAM)

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)


Edit: Ooops, added diagram.
Attached Images
File Type: jpg Question.jpg (12.1 KB, 24 views)

Last edited by bomber7 : 11-27-2008 at 12:26 AM.
bomber7 is offline   Reply With Quote
Sponsored Links - Login to hide this ad!
Old 11-27-2008, 12:35 AM   #2
Pyrogasm
Lackadaisically Absent.
 
Pyrogasm's Avatar


Respected User
 
Join Date: Sep 2006
Posts: 4,523

Submissions (9)

Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)

Hero Contest - Fourth place

Send a message via ICQ to Pyrogasm Send a message via AIM to Pyrogasm Send a message via MSN to Pyrogasm Send a message via Yahoo to Pyrogasm
Default

...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 Thread Done for, unless someone else wants to revive it...
It lasted a damn long time.

Please; Ask for Help Appropriately














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.
Pyrogasm is offline   Reply With Quote
Old 11-27-2008, 12:42 AM   #3
bomber7
User
 
Join Date: Sep 2007
Posts: 102

bomber7 is on a distinguished road (12)

Default

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.
bomber7 is offline   Reply With Quote
Old 11-27-2008, 01:47 AM   #4
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

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.
__________________
Ammorth is offline   Reply With Quote
Old 11-27-2008, 02:03 AM   #5
bomber7
User
 
Join Date: Sep 2007
Posts: 102

bomber7 is on a distinguished road (12)

Default

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.
bomber7 is offline   Reply With Quote
Old 11-27-2008, 02:13 AM   #6
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

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.
Ammorth is offline   Reply With Quote
Old 11-27-2008, 06:08 AM   #7
bomber7
User
 
Join Date: Sep 2007
Posts: 102

bomber7 is on a distinguished road (12)

Idea

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.

Collapse 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
        set dx = x-AllMadeNodes[a].x
        set dy = y-AllMadeNodes[a].y
        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
    set LastNodeMade = AllMadeNodes[CurrentNodeAmount-1] //Sets it as the last one made
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 AddY
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 Node PrevNode = LastNodeMade //For linking nodes together.
local boolean MadeANode = false //Disabled at the moment, probably enabled soon again.
local Node AlreadyHere
    debug call BJDebugMsg("Arm called to discover " + I2S(Direction))

    if GoingLeft then //Sets the variables that determine the probes movement direction.
        set AddX = CHECK_DIST
        set AddY = 0
    elseif GoingUp then
        set AddX = 0
        set AddY = CHECK_DIST
    elseif GoingRight then
        set AddX = -CHECK_DIST
        set AddY = 0
    elseif GoingDown then
        set AddX = 0
        set AddY = -CHECK_DIST
    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
        set MadeANode = false
        
        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
        
        //Detect dead end
        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
                        set ny = y+(ROAD_SIZE/2)
                    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.AttachNodes[PrevNode.Attachs] = LastNodeMade
                        set AlreadyHere.Attachs = PrevNode.Attachs + 1
                        set LastNodeMade.AttachNodes[PrevNode.Attachs] = AlreadyHere
                        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 
                    //if (not MadeANode) then
                        
                        call BuildNode()
                        set LastNodeMade.x = nx
                        set LastNodeMade.y = ny
                        set MadeANode = true
                        //Makes the node visible if debug mode is on
                        debug call CreateUnit(Player(0),'h000',LastNodeMade.x,LastNodeMade.y,0)
                        //Attaches the new node to the previous node.
                        set PrevNode.AttachNodes[PrevNode.Attachs] = LastNodeMade
                        set PrevNode.Attachs = PrevNode.Attachs + 1
                        set LastNodeMade.AttachNodes[PrevNode.Attachs] = PrevNode
                        set LastNodeMade.Attachs = PrevNode.Attachs + 1
                        set PrevNode = LastNodeMade
                    //endif
                    
                    set FoundDist1 = ROAD_SIZE
                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
                        set ny = y-(ROAD_SIZE/2)
                    else
                        set ny = y+(ROAD_SIZE/2)
                    endif
                    
                    set AlreadyHere = NodeOnTop(nx,ny)
                    if not (AlreadyHere == 0) then
                        debug call BJDebugMsg("Node found, connecting and terminating.")
                        set AlreadyHere.AttachNodes[PrevNode.Attachs] = LastNodeMade
                        set AlreadyHere.Attachs = PrevNode.Attachs + 1
                        set LastNodeMade.AttachNodes[PrevNode.Attachs] = AlreadyHere
                        set LastNodeMade.Attachs = PrevNode.Attachs + 1
                        return
                    endif
                    
                    set ExploreX = nx
                    set ExploreY = ny
                    set ExploreD = 0
                    call ExecuteFunc("ExploreNow")
                    
                    //if (not MadeANode) then
                        
                        call BuildNode()
                        set LastNodeMade.x = nx
                        set LastNodeMade.y = ny
                        set MadeANode = true
                        
                        debug call CreateUnit(Player(0),'h000',LastNodeMade.x,LastNodeMade.y,0)
                        
                        set PrevNode.AttachNodes[PrevNode.Attachs] = LastNodeMade
                        set PrevNode.Attachs = PrevNode.Attachs + 1
                        set LastNodeMade.AttachNodes[PrevNode.Attachs] = PrevNode
                        set LastNodeMade.Attachs = PrevNode.Attachs + 1
                        set PrevNode = LastNodeMade
                    //endif
                    
                    set FoundDist1 = ROAD_SIZE
                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
                        set nx = x-(ROAD_SIZE/2)
                    else
                        set nx = x+(ROAD_SIZE/2)
                    endif
                    
                    set AlreadyHere = NodeOnTop(nx,ny)
                    if not (AlreadyHere == 0) then
                        debug call BJDebugMsg("Node found, connecting and terminating.")
                        set AlreadyHere.AttachNodes[PrevNode.Attachs] = LastNodeMade
                        set AlreadyHere.Attachs = PrevNode.Attachs + 1
                        set LastNodeMade.AttachNodes[PrevNode.Attachs] = AlreadyHere
                        set LastNodeMade.Attachs = PrevNode.Attachs + 1
                        return
                    endif
                    
                    set ExploreX = nx
                    set ExploreY = ny
                    set ExploreD = 270
                    call ExecuteFunc("ExploreNow")
                    
                    //if (not MadeANode) then
                        
                        call BuildNode()
                        set LastNodeMade.x = nx
                        set LastNodeMade.y = ny
                        set MadeANode = true
                        
                        debug call CreateUnit(Player(0),'h000',LastNodeMade.x,LastNodeMade.y,0)
                        
                        set PrevNode.AttachNodes[PrevNode.Attachs] = LastNodeMade
                        set PrevNode.Attachs = PrevNode.Attachs + 1
                        set LastNodeMade.AttachNodes[PrevNode.Attachs] = PrevNode
                        set LastNodeMade.Attachs = PrevNode.Attachs + 1
                        set PrevNode = LastNodeMade
                    //endif
                    
                    set FoundDist1 = ROAD_SIZE
                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
                        set nx = x-(ROAD_SIZE/2)
                    else
                        set nx = x+(ROAD_SIZE/2)
                    endif
                    
                    set AlreadyHere = NodeOnTop(nx,ny)
                    if not (AlreadyHere == 0) then
                        debug call BJDebugMsg("Node found, connecting and terminating.")
                        set AlreadyHere.AttachNodes[PrevNode.Attachs] = LastNodeMade
                        set AlreadyHere.Attachs = PrevNode.Attachs + 1
                        set LastNodeMade.AttachNodes[PrevNode.Attachs] = AlreadyHere
                        set LastNodeMade.Attachs = PrevNode.Attachs + 1
                        return
                    endif
                    
                    set ExploreX = nx
                    set ExploreY = ny
                    set ExploreD = 90
                    call ExecuteFunc("ExploreNow")
                    
                    //if (not MadeANode) then
                        
                        call BuildNode()
                        set LastNodeMade.x = nx
                        set LastNodeMade.y = ny
                        set MadeANode = true
                        
                        debug call CreateUnit(Player(0),'h000',LastNodeMade.x,LastNodeMade.y,0)
                        
                        set PrevNode.AttachNodes[PrevNode.Attachs] = LastNodeMade
                        set PrevNode.Attachs = PrevNode.Attachs + 1
                        set LastNodeMade.AttachNodes[PrevNode.Attachs] = PrevNode
                        set LastNodeMade.Attachs = PrevNode.Attachs + 1
                        set PrevNode = LastNodeMade
                    //endif
                    
                    set FoundDist1 = ROAD_SIZE
                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
local Node ToPass = LastNodeMade
    //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.
    set LastNodeMade.x = x
    set LastNodeMade.y = y
    
    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
File Type: gif WC3ScrnShot_112608_222729_05.gif (357.6 KB, 15 views)
File Type: gif WC3ScrnShot_112608_222723_04.gif (348.5 KB, 10 views)
File Type: gif WC3ScrnShot_112608_225038_01.gif (130.7 KB, 11 views)
bomber7 is offline   Reply With Quote
Old 11-27-2008, 07:18 AM   #8
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

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
                add intersection to stack
            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
File Type: gif node-gen.gif (44.9 KB, 11 views)
__________________
Ammorth is offline   Reply With Quote
Old 11-27-2008, 08:46 PM   #9
MaD[Lion]
MaD Da ViNci
 
MaD[Lion]'s Avatar


Respected User
 
Join Date: Apr 2003
Posts: 1,699

Submissions (10)

MaD[Lion] is a jewel in the rough (225)MaD[Lion] is a jewel in the rough (225)MaD[Lion] is a jewel in the rough (225)MaD[Lion] is a jewel in the rough (225)

Default

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 SystemSystem for making better cinematics and with fancy effects
Timing SystemTiming system that simulates the usage of PolledWait just with 0.01 accuracy
MaD[Lion] is offline   Reply With Quote
Old 11-29-2008, 01:19 AM   #10
bomber7
User
 
Join Date: Sep 2007
Posts: 102

bomber7 is on a distinguished road (12)

Default

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.
bomber7 is offline   Reply With Quote
Old 11-29-2008, 01:37 AM   #11
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 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.
__________________
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 06:18 PM.


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