Goal-Oriented Action Planning

Материал из xrWiki
Перейти к: навигация, поиск

Goal-Oriented Action Planning (GOAP) – сравнительно новый, но уже популярный метод планирования. По сути своей он похож на методы доказательства теорем, но проще, из-за специфики его применения в играх (детальное описание смотрите в AI Game Programming Wisdom 2).

Для GOAP нам необходимо задать представление мира в терминах объекта. Каждое свойство представления мира должно оцениваться evaluator-ом. Каждое действие объекта имеет список условий своего выполнения (preconditions) и эффектов, т.е. того, что мы ожидаем от действия; кроме того, каждое действие имеет свой вес. На основании этой информации, имея текущее состояние мира и целевое (т.е. состоянием мира, в котором какие-то его свойства имеют какие-то значения), можно построить последовательность действий кратчайшего веса, которая переведёт мир из текущего состояния в целевое. Действие может несколько раз встречаться в построенной последовательности. Если при заданных параметрах последовательность не может быть построена, то выполняется предыдущая последовательность действий.

Детали реализации.

В нашей реализации GOAP размер представления мира не ограничен, т.к. при построении последовательности действий оцениваются только те свойства мира, которые необходимы для нахождения оптимального решения. После построения последовательности, будет выполняться только первое действие последовательности, до тех пор, пока не изменится цель или не изменится текущее состояние мира. Если последовательность перестроилась, и её первое действие не совпадает с предыдущим, то у предыдущего вызывается метод finalize, у нового – initialize. Для выполнения действия вызывается метод execute. Если при заданных параметрах последовательность не может быть построена, то в лог пишется предупреждение об этом вместе с dump-ом текущего состояния мира (вернее, только тех свойств мира, которые были оценены при нахождении последовательности) и целевого. Действие само по себе может быть не атомарным. Таким образом, возможно построение иерархических моделей GOAP.


Дмитрий Ясенев

02.04.2004