What is the situation?
What you see here is what one gets after following the getting started tutorial, which include having a terrain and some obstacles, and moving an agent so that it reaches a target. This discussion is about the following caveat:
Left: An agent has to reach its target location, and a path is planned through a choke point (narrow passage between the gray walls).
Right: A building is created blocking the choke point, disconnecting the two sides of the map. I achieved this marking an invisible box as obstacle and calling Scan() on the graph. Notice how a new path now directs the agent next to the wall, as it’s the position closest to the target.
What I would like to have?
Buildings affect the graph when they are created and destroyed. A building at the appropriate location may split the graph in two disconnected components, like shown above. In such a case, I would like the agent to stop next to the building, rather than next to the wall. Why? Because unlike terrain obstacles, buildings may be lifted up, burried, destroyed, i.e. they may not be blocking the way in the near future. IRC, this is what happens in Starcraft2, where if a ramp is blocked by a building and a unit is sent up, it will try to go there and stop at the blockade.
A simple solution - which is not what I want - would be to ignore buildings during path planning, but add a collision/avoidance mesh so that agent avoids them. This however is suboptimal for two reasons. First, buildings can create a convex blockade which may get an agent stuck. Second, if the graph is still a single connected component, i.e. there may be a longer free path somewhere else, the agent should pick it. This means that, the path planning should actually be aware of buildings.
How can this be solved?
The naive solution I can think of is to use two graphs:
First, a graph that only considers terrain obstacles.
Second, a graph that considers both terrain obstacles and buildings.
In a normal scenario, the second graph is used. When no successful path can be found, a path from the first graph is returned (this should always succeed, assuming a single connected component at the start of the game). In the movement update however, the building is considered for blocking, so the agent will get stuck next to the building (and possibly attack it to remove the obstacle).
Discussion
Since I am very new to the A* Pathfinder Project, I was wondering if the developers already thought of this scenario, and provide (through the free or pro versions) a better way to deal with it.
Thanks in advance.