Path changing if an obstacle appears suddenly[A* Aron Granberg]

Hi I’m using the Aron Granberg’s A* project(FREE) for controlling the AI path finding. I’ll write my requirements and how I’m trying to solve them. Please do suggest better ways.

Requirements:

  1. Dynamically constructed NPCs which needs to go to a point in 3D space.

  2. During the movement of the NPCs there can appear a wall somewhere on the path. So it needs to find another way when it faces the wall.

Solutions:

  1. I did like the tutorial on the project page. I can instantiate a prefab and it goes to the target.
  2. Now there is a problem. I have attached the “DynamicGridObstacle” script to the obstacle. So it updates the graph, No problem if the NPC didn’t get instantiated. But in case it does, the NPC gets stuck i.e. It has already computed the path but the obstacle wasn’t there but somewhere it just popped out. To tackle the problem of an obstacle appearing after NPC has left for target I do a seeker.StartPath() for all the NPCs. Is this a good strategy? Help pls :slight_smile:

UPDATE:
So I used a NavMeshObstacle property on the obstacle. If I add those obstacles at runtime, the object modifies the path. Do make sure that “carving” is activated for the obstacle so that your navmeshAgent will recompute the path if it encounters this navmeshObstacle.

Have you considered D*? D* is an upgraded version of A* designed for dynamic path changes.

To stick with A* you need a way to recalculate the path if an obstacle is placed in the way. Here are a few different possibilities to solve.

  • Recalculate every path every time an obstacle is added. Very expensive
  • Have the NPC raycast between there current location and future location at some defined interval. If the NPC can’t ‘see’ the next node, then recalculate the path
  • Define a speed and expected time to reach the next node. It the NPC has not reached the next node in time, recalculate the path.
  • Check if the obstacle lies on any path when instantiated. If so recalculate that path.

Edit: There may be a native way to do this inside the A* path finding project. I’m not familiar enough with the project to comment.