How would that work?
🎉 Celebrating 25 Years of GameDev.net! 🎉
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
Is A* good when entities should collide with eachother?
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.
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.
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.
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.
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:
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
