Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Different A* paths for different entities: Question on Path Node Management


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 tom_mai78101   Members   -  Reputation: 608

Like
0Likes
Like

Posted 16 December 2013 - 09:27 AM

I can only think up an A* algorithm that uses path nodes for 1 entity. If I were to expand on this by increasing the number of active entities within a set world boundary, there will be many different A* algorithm generated paths for the entities to follow. Each path then will have to share the same nodes within the world, otherwise all the entities must wait until the active entity finishes its path, clears its path nodes, and it's the other's turn to start walking the other entity's own path.

 

I'm trying to solve the problem where two paths share some common path nodes. I can't have one node of one path have a parent of another node of another path; in other words, I can't have two path nodes have their parents intertwined together, otherwise it would be catastrophic, but much less than more than 2 entities active.

 

I could make one entity move until the entity reaches its target, wipe the path nodes in the world clean, then recalculate a new A* path for the other entity, but that wouldn't be realistic. I have also thought upon having the A* algorithm be embedded inside the entity structure, but the path nodes problem easily hinders this.

 

How do you solve this? Or in other words, how do I solve the problem of sharing same path nodes for different A* paths?


Edited by tom_mai78101, 16 December 2013 - 09:28 AM.


Sponsor:

#2 JTippetts   Moderators   -  Reputation: 10064

Like
0Likes
Like

Posted 16 December 2013 - 09:38 AM

After a path is constructed, I copy the steps of the path to a path vector and hand that off to the entity, freeing up the pathfinder system to find a path for another unit.



#3 tom_mai78101   Members   -  Reputation: 608

Like
0Likes
Like

Posted 16 December 2013 - 10:01 AM

Do you continuously copy the steps of the path to a unit's path vector, free up the pathfinder's system, repeat for the next unit, and so on?

 

I can think up one possible situation that if the first unit's path vector contains a path that overlaps the path of the second unit, the overlapped area of the two paths will contain path nodes that are unusable. Especially when the pathfinder has to start in the same game cycle tick.


Edited by tom_mai78101, 16 December 2013 - 10:04 AM.


#4 ApochPiQ   Moderators   -  Reputation: 17622

Like
1Likes
Like

Posted 16 December 2013 - 11:12 AM

A potential solution to this is to mark nodes as having a higher cost when they are likely to be occupied by other units, thereby causing A* to path around them. You also might want to solve this in your path-following logic rather than your path-finding logic. Getting unit avoidance to work well at the A* level is tricky and requires a lot of 4-dimensional math; path-following is a much easier place to handle the issue.



#5 JTippetts   Moderators   -  Reputation: 10064

Like
1Likes
Like

Posted 16 December 2013 - 11:19 AM

I just generate one path, hand it off to the unit that requested it, generate another for the next one, hand it off. If there are collisions along the route, it's not really the responsibility of the pathfinder to handle them. The pathfinder just finds a path. The path execution system that actually moves units is where the responsibility lies to resolve collisions, either by having one unit delay while another paths through, or by calling a local path solver (not a full path-find) to try to find a local solution to a blocked path.

 

Now, I suppose you could include fields in your nodes to mark them as blocked at a certain time, t. I'd probably implement this as a vector per node and incorporate the time-stamped block as part of the heuristic, to steer units around the blocked node. After a path executes a node step it would be responsible for clearing out any time blocks. Going this route just seems a bit overly complex to me, given that local collision resolution typically works well enough.

 

Pathfinding is plagued with the same kinds of temporal simulation complexities that physics are, with the additional burden of prediction. You probably aren't going to ever build the "perfect" pathfinder; about the best you can hope for is one that works "good enough" for your particular scenario.



#6 ferrous   Members   -  Reputation: 2957

Like
0Likes
Like

Posted 16 December 2013 - 05:16 PM

As a last resort you could always cheat completely and let units pass through each other =) 






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS