How to calculate a path around a moving Object

I wrote a little game-engine, featuring a tile-based map and the A* algorithm for pathfinding. But I have a problem, when 2 objects collide and block a waypoint. They are coming from opposite directions, so they can't move anymore and will never reach their next waypoint. I thought of some possible solutions like

• movable objects cannot collide with other movable objects
• recalculate the path flagging the blocked tiles
• just calculate the path to the next free waypoint, flagging every tile with movable objects as blocked

I really don't want to do the first possibility, thats a little bit shabby for a not action-game like engine. The last two possibilities could 开发者_运维知识库get very slow if there are much movable objects on the map. What do you think should I do? By the way, the first possibility is implemented in "Stronghold", the other two can be found in any newer strategy game.

---

There's no single correct answer of course, but I can share what I've done with a similar problem:

I agree that passing through looks old school at this point. However, if your objects are smaller than your navigation mesh, you can do collision avoidance with bounding boxes without actually invalidating the path. Make collision avoidance small and local relative to the larger path.

If that doesn't work for your game, adding blocks is usually the best way. If you are concerned about the cost of pathfinding, you can wait until there is a collision, temporary add "blocks", and re-path. Another approach is to just periodically insert blocks and re-path. This can give natural looking paths and avoids the "run into each other before moving" which can look odd.

The cost depends a lot on your A* algorithm. If the algorithm doesn't cache results, then the blocks don't have incremental cost, and you can run A* as often as makes sense. For example: run A* once a frame and keep a queue of A* tasks.

If your algorithm does cache results, try to group A* computation so that you do multiple solves before moving the blocks around.