Jump to content
  • Advertisement
Midnightas

Pathfinding Is A* good when entities should collide with eachother?

This topic is 466 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

Advertisement

A* is about finding paths, or more abstractly, about finding the cheapest route through a graph, that's all. It has no opinion on entities or collision between them.

You can recalculate a new A* path when the current one ends up being blocked, and that is often good enough. There are also things you can do with A* to try and reduce collisions, such as change the weight of nodes when you know other entities will be occupying them. You can use steering behaviours or crowd/flocking algorithms when navigating along the A* path to give entities some degree of freedom to avoid each other while following paths. You could share paths among friendly entities so that they can form an orderly line when passing along the same path instead of competing for chokepoints.

There are also more advanced algorithms that attempt to acknowledge the fact that the environment can change, and that a path that was previously found may not always continue to be the best one when other entities become involved. These algorithms are generally based on A*, so you can start with a good A* implementation and adapt it to one of these algorithms later if you need.

Share this post


Link to post
Share on other sites

With this problem I recommend using steering(obstacle avoidance) for entities every frame, it's pretty good for short-range maneuvering. Couple it with A* for longer range navigation which you can run sparingly.

Share this post


Link to post
Share on other sites

Have a look at steering as well as avoidance algorithms such as ORCA, Reciprocal Velocity Obstacles, etc. A* is for strategy, avoidance is for tactics. A* will tell you what route to take, steering and other avoidance mechanisms will give you the details of how to follow that route, including moment-to-moment accelerations for obstacle avoidance.

Share this post


Link to post
Share on other sites

That said, if you are working on a low rez game such as a turn-based game where pieces are on a grid board, there are ways you can incorporate the locations of objects into your A*. For example, there are articles that talk about not only blocking the location of pieces currently, but blocking locations where they will be on future turns. The problem is you have to keep phantom copies of the "board" for those times in the future and iterate through them as you do your pathfinding search. e.g. for step 1, I can use the current locations, for step 2, I use where people are going to be 1 step into the future, step 3, 2 steps into the future, etc. Get's kind of intractable after a bit.

Share this post


Link to post
Share on other sites

My grid agents will flag the node they are standing on/moving to as Occupied and I've implemented an option into my A* that basically says Occupied nodes are unwalkable and skips them during the search much like it would a node marked as unwalkable/wall/etc.  It makes for somewhat boxy movement much like Warcraft 3 or the original Starcraft I suppose.

Since paths are calculated on a single frame I can't determine what nodes might have changed and become occupied after an agent has already calculated a path, so if a node along the agent's path becomes occupied after the fact he will walk right through it.  To counter this, in my update loop (if the agent is currently moving) I determine what node the agent will be standing in next, and if it's occupied the agent will stop, stall for a brief moment, then calculate another path.

I recorded a quick video to show what this looks like:

 

Share this post


Link to post
Share on other sites

  • 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!