Полученная в результате конструкция не является столь же эффективной, как чисто процедурный конечный автомат, но все же превосходит по своим исходным показателям производительности все другие средства ИИ, описанные в данной книге. Процедура обновления состояния может вести очередь сообщений о переходе, что позволяет исключить необходимость обработки избыточной информации в коде, предназначенном для выполнения переходов. Эти сообщения могут также сохраняться на жестком диске, что позволяет не забывать о важных событиях и в конечном итоге принимать их во внимание. Сообщения, не требующие хранения, могут рассматриваться как временные. Сбор этих сообщений должен осуществляться без использования очереди сообщения, а после того, как необходимость в них исчезнет, они должны уничтожаться. После объединения этой системы поддержки очередей со средствами реализации приоритетов переходов появляется возможность организовать очередь по приоритетам, с помощью которой могут быть решены все описанные выше проблемы. В этом случае должно быть сохранено только временное сообщение с высшим приоритетом, а затем это сообщение может быть отброшено, если его приоритет ниже по сравнению с приоритетом сообщения, стоящего в начале очереди. ПРИМЕЧАНИЕ Мощь конечного автомата в результате ввода в действие очереди по приоритетам не увеличивается. В процессе моделирования используется отдельная структура данных для преобразования процедурной информации в более формализованную последовательность входных данных, главным образом ради единообразия, поскольку такая организация работы позволяет гарантировать, что формы поведения в игре соответствуют проекту на уровне интуитивного понимания. Оптимизация Предположим, что проектировщик не слишком хорошо знаком с предоставленными в его распоряжение инструментальными средствами и разработал чрезмерно усложненный конечный автомат. Если конечный автомат имеет существенные размеры или количество использующих его несобственных персонажей велико, то вычислительные издержки становятся слишком значительными, чтобы ими можно было пренебречь. Таким образом, разработчик средств ИИ вынужден проводить проверку того, соответствует ли каждый из разработанных им компонентов требованиям оптимальности. Значительным преимуществом конечных автоматов является то, что в их основе лежит тщательно изученная и простая вычислительная модель. В отличие от более сложных моделей, таких как машины Тьюринга, широко известны алгоритмы, позволяющие оптимизировать конечные автоматы. Фактически одним из проверенных методов, позволяющих сравнивать конечные автоматы друг с другом, является создание канонических конечных автоматов . автоматов, имеющих схему в виде наиболее простого графа. В одном из алгоритмов, обеспечивающих выполнение такой оптимизации, производится сравнение всех состояний, вместе взятых, после чего по мере возможности отдельные состояния объединяются . Сравнение состояния лучше всего осуществлять попарно. Слияние двух состояний возможно, если все исходящие переходы указывают на одно и то же состояние. Два состояния сливаются таким образом, что используется лишь одно множество дублирующихся исходящих переходов, но все входящие переходы сохраняются. Рекомендуется переименовать состояние, полученное путем слияния, так, чтобы новое имя указывало на то, какими были предыдущие два состояния. Рис. . Оптимизация порождающего конечного авто мата путем свертывания в одно состояние нескольких состояний с идентичными исходящими переходами . Эмоции Глава . Конечные автоматы . Для современных компьютеров такие временные характеристики оказываются более чем удовлетворительными. Дважды связывая переходы с начальным и конечным состоянием, можно оптимизировать конечный автомат почти до показателя . версии алгоритм проверяет входящие связи каждого состояния. Каждое из подключенных состояний сравнивается с каждым другим состоянием для определения подобия. Интуиция подсказывает, что два подобных состояния с наибольшей вероятностью могут оказаться идентичными. В целом, наибольшие преимущества предоставляет подход, основанный на оптимизации конечных автоматов, независимо от используемого метода. Если есть возможность обеспечить моделирование одной и той же формы поведения с применением меньшего количества состояний, так и следует делать. Однако конечные автоматы с меньшим числом состояний часто являются менее доступными для понимания. С другой стороны, после того как проектировщик вводит дополнительные состояния, обычно изучение работы конечного автомата становится проще. Итак, лучше всего оставить на время неизменным конечный автомат, спроектированный вручную, и приступать к его компиляции в целях создания оптимизированного конечного автомата только на этапе подготовки выпуска, предназначенного для внедрения. Недостатки Недостатки конечных автоматов кажутся незначительными по сравнению с массой преимуществ, но, как показано ниже, их число довольно велико. При создании достаточно крупных систем с конечным числом состояний задача проектирования конечных автоматов может стать очень сложной. По своим вычислительным возможностям конечные автоматы ограничены определенными задачами. Конечные автоматы не могут применяться для решения многих простых задач, таких как подсчет. Конечные автоматы остаются неизменными в том виде, в каком они были спроектированы, и не могут изменяться на этапе прогона. При осуществлении процедурного управления могут возникать проблемы. Выходные данные порождающих конечных автоматов являются весьма предсказуемыми, поэтому не совсем подходят для создания форм поведения. Недостатки порождающих конечных автоматов можно легко учесть на этапе проектирования .