Game Development Reference
In-Depth Information
decomposition of everything. Details of the flashlight and other methods for
making fire are not shown.
The decompositions are hierarchical. In a rich environment, there will be many
such decompositions to choose from for each task; our farmer has a flashlight
and a lantern at his disposal for use as a light source, and probably more than one
means of making fire. The task library is comparable to a rich script library
[Kelly07] and can be computed offline [Kelly08]. There are some compelling
advantages to HTN: The plans can be rapidly forward searched, and they deal
gracefully with changing conditions. While they can be computed offline,
designers can create plans to their liking as well.
The highest-level abstract tasks tend to be a very close match to typical goals that
might be presented to a STRIPS or GOAP planner. Instead of running A* from
the end goal back to the current state, we can more rapidly find matching high-
level abstract tasks that take us to our goal, a welcome performance improvement.
Instead of hoping that the ant on the leaf finds us at the base of the tree, we pull
out the closest thing we have to an ant-locator plan and follow it directly to the
ant. The forward search with HTN is faster than the backward search with GOAP.
Because of their forward and hierarchical nature, HTNs are also part of plan
execution. Again using our farmer example, suppose the farmer starts to use the
flashlight, and the batteries fail before he gets out the door. The light source task
needs to re-plan, but nothing higher in the hierarchy has to change. The basic
plan for getting to the barn and exploring the noises is sound. Only the part about
getting some light has to change. A GOAP or STRIPS planner would have to
restart the search because its plans do not natively retain the dependencies
explicitly or keep alternatives that were discarded along the way. Once a GOAP or
STRIPS planner discovers the flashlight in our example, it will discard using the
lantern. Even if a clever implementation were to recognize that only a portion of
the plan had failed, GOAP or STRIPS would need to search through all actions
for alternative means of making light. The HTN planner in Figure 10.8 has the
alternative light sources encoded in the abstract tasks.
To make sure everything works properly, HTNs include a new feature known as
critics . Critics detect conflicts early in an effort to minimize backtracking. Instead
of going out to investigate noises in the barn, suppose our farmer was going out
after dark to light a bonfire for roasting marshmallows. Critics would detect the
fact that he might not have enough matches to both light the lantern and light the
bonfire.
 
Search Nedrilad ::




Custom Search