Jump to content
  • Advertisement
Sign in to follow this  
tom_mai78101

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

This topic is 2137 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement

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

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!