Game Development Reference
In-Depth Information
Figure 10.7
The direction of the search matters.
Note the direction of search, from the goal to the current state. This is for
performance reasons. As long as A* has a good heuristic, it will find the lowest-
cost path, but the performance will vary, depending on which end of the final
path the search starts. The typical GOAP or STRIPS case gives the actor many
possible actions that might be checked if we start by acting on the current state.
Most of those actions will not take us closer to our goal, which gives us a large
search space to examine and discard. If we start at the goal, we are far more likely
to see only a few actions that need to be searched to take us toward the current
state. As Figure 10.7 suggests, if you start at the base of a tree looking for an ant
that is on the tip of one of the leaves, it would be easier for the ant to find you at
the base of the tree than it will be for you to find the ant.
If all the actions are simple enough that each one changes only a single post-
condition, then we can create a good heuristic for A* to use when estimating.
That heuristic is that the minimum cost to finish A* from any point is the
number of conditions that need to change. If the minimum cost of a step is 1 and
the actions can change only one condition, this heuristic holds true. Plans could
cost more if the designer gave some steps higher weight than the minimum to
help steer the search. Plans could also cost more if there are no direct paths.
Indirect paths happen when the steps that lead to the goal add extra unmet
conditions that will need to be satisfied by later actions. A real-world example
might be in order.
Search Nedrilad ::

Custom Search