Pathfinding question

#1Geath RuzePosted 5/29/2012 11:04:51 AM
If wanted to have multiple Agents pathfinding at the same time I would need to use threading for this correct? I'm thinking this is the way to do it.
---
"Darkness gives rise to cowardice, but fear not...you can die in the light."
#2PTP2009Posted 5/29/2012 11:17:49 AM
Depends on how you want them to behave. If they need to have a lot of independence, then yeah, threads will probably make this easier. If it's a "turn based" thing where each Agent takes one step per turn, you could just cycle through them in one thread.
#3Geath Ruze(Topic Creator)Posted 5/29/2012 11:54:44 AM
yeah they're going to be independent so threading it is. Also another question. I was on a site that talked about ways to speed up pathfinding (A*). One of the ways is to use a multi tiered approach. One that uses large nodes, another for medium and then one for smaller. Thing is I have one 2d array map and each square is a node. Would I need to create separate 2d arrays.and then switch between these arrays when I want to use a different scale pathfinding system?

Don't know if I'm thinking correctly for that because how I'm thinking seems to be a waste of space.
---
"Darkness gives rise to cowardice, but fear not...you can die in the light."
#4Cybertic DragonPosted 5/30/2012 1:06:58 AM
I don't think you need several 2D arrays. Say your map is 16x16 and your guy is at (1,2). When you want to approximate a coarse-grained map with 4x4 squares, you know your guy is in the big square that's at (0,0) and needs to get to the squares at (0,4), (4,0) or (4,4). Do something similar for gradually smaller squares, for example 2x2 and then 1x1.

You're going to need to be careful with this algorithm though. You can only jump from one big square to another if there's some reasonably clear path between those two. It doesn't need to be a straight line, but there needs to be a path between them that doesn't involve going into another big square.
#5Cybertic DragonPosted 5/30/2012 1:10:53 AM
This also seems unnecessarily complicated. First implement A* with just basic 1x1 squares and put your effort into designing a good heuristic (this is 90% of the work of A*). Keep the bookkeeping logic self-contained per agent so that you can easily parallelize it later, but I'd do that last.
#6nesisPosted 5/30/2012 4:50:45 AM
[This message was deleted at the request of the original poster]
#7nesisPosted 5/30/2012 11:19:18 AM
You could easily pre-check and store the connectivity of sides on big squares (eg, sides A, B, C, D, and say which connects to which) and the probable cost of each of those connections. I'd imagine you'd want to represent it with either a 4x3 triangular matrix or an array of 6 numbers (integers?), with sentinel values for non-connectedness (eg, -1).
---
____Learn to Draw Stuff____||_(\((3_1__.
|__www.drawfunction.com__||_))\)_5_5_|
#8Geath Ruze(Topic Creator)Posted 5/30/2012 4:36:25 PM
thats a good idea. Won't need unnecessary arrays.I've got A* running, just need to seperate the code so that it can be contained within the Agent. Right now all the pathfinding and bounds checking is inside the map. At the time I was just wondering if I could actually code it. I should really start thinking ahead about the design, would save me time.
---
"Darkness gives rise to cowardice, but fear not...you can die in the light."
#9ForetakenPosted 5/30/2012 5:02:14 PM
There's a ton of information out there on hierarchical pathfinding.

Por ejemplo:

http://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf
---
[self release]
#10Geath Ruze(Topic Creator)Posted 6/6/2012 10:21:43 PM
I've run into a problem with having multiple agents pathfinding at the same time while sharing a map.

Say AgentX is going along pathfinding just fine and then encounters AgentY. AgentY has been pathing like a madman and on his way he has been changing the nodes Gscore that he has encountered just like AgentX. This means that AgentX will have wrong information if his path crosses AgentY and won't Pathfind correctly.

Don't know if that made sense how I'm explaining, but I'm trying to figure out how I can have both AgentX and AgentY pathfind and retain each's information about the map without regard for the other(the exception is when they bump into each other, so they can't just ignore each other completely). I've come up with having each node have an Agent_code to differentiate between agents so if a different agent has traversed to that node the Current agent will instead use the nodes original values. However that proves problematic because if AgentX needs to repath due to an object how will he get access to his personal change to that nodes Gscore if another agent comes along and makes his change? He can't because AgentX will look back see that another agent has been there and will use the original node value instead of his previous change to that node.

The only other thing I could think of is to give each Agent another data structure to store the nodes they've traversed. Then that seems rather space consuming especially on large maps.

hmm on second thought maybe that won't matter. Maybe the agentCode will work. ugh gotta bust out the scratch paper...yay...

-_- I miss writing hello world programs right now lol. I just jumped into the threading pool without a thimble. (nice one if I do say so myself)
---
"Darkness gives rise to cowardice, but fear not...you can die in the light."