Теория автоматов

Определение автомата и его разновидности. Таблицы и графы переходов и выходов. Подавтоматы. Теорема о приведенном автомате

Операции с автоматами

Преобразование автомата Мили в автомат Мура и автомата Мура в автомат Мили. Эквивалентность автоматов. Различимость состояний автоматов. Минимизация автоматов. Синтез автоматов. Распознающие автоматы

Автомат - система механизмов, устройств, в которой полностью автоматизированы процессы получения, преобразования, передачи энергии, материалов, информации Термин "автомат" используется в двух аспектах:

1) техническом,

2) математическом.

При математическом подходе под автоматом понимается математическая модель технического устройства, у которого должны быть входы, внутренние состояния и выходы. Относительно деталей структуры устройства сведений не должно быть.

При техническом подходе под автоматом понимается вполне реальное устройство, например, телефонный автомат, торговый автомат и т. д. В данном случае, естественно, известными являются детали внутреннего строения устройства.

Частным и важным случаем автомата выступает цифровой автомат (ЦА), в котором полностью автоматизированы процессы приема, преобразования, хранения и выдачи цифровой информации.

С точки зрения сигналов ЦА полезно определить как систему, которая может принимать входные сигналы, под их воздействием переходить из одного состояния в другое, сохранять его до прихода следующего входного сигнала, выдавать выходные сигналы.

ЦА считается конечным, если конечны множества входных сигналов X, состояний S и выходных сигналов Y. Конечный автомат можно поставить в соответствие такому устройству, как компьютер. Компьютер перерабатывает поступающие входные данные в выходные данные (результат), но этот результат соответствует не только входным данным, но и текущему состоянию компьютера, т.е. тем данным, которые хранятся в памяти компьютера, например, результаты предыдущих вычислений, программы вычислений.

Работа ЦА осуществляется в автоматном времени, определяемом числом периодов поступления входных сигналов.

Абстрактным автоматом называют математическую модель дискретного устройства, имеющего один входной канал, куда поступают последовательности символов какого-либо языка, один выходной канал, с которого снимают последовательности символов какого-либо другого языка и находящегося в каждый из моментов дискретного времени в каком-либо состоянии. Графически абстрактный автомат представлен рис.

Слова входного языка можно представить символами множества X={x 1 ,x 2 ,...x n }, который называют входным алфавитом , а слова выходного языка - символами множества Y={y 1 ,y 2 ,...y p }, который называют выходным алфавитом . Множество состояний автомата S={s 1 ,s 2 ,...s m } называют алфавитом состояний .

Понятие состояние автомата используется для описания систем, выходные сигналы которых зависят не только от входных сигналов в данный момент времени, но и от некоторой предыстории, т.е. сигналов, которые поступали на входы системы ранее. Следовательно, цифровые автоматы относятся к последовательностным схемам, которые, как уже отмечалось, обладают памятью. Понятие состояние автомата соответствует некоторой памяти о прошлом, поэтому ввод этого понятия позволяет устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входных сигналов.

Работу абстрактного автомата следует рассматривать применительно к конкретным интервалам времени, т.к. каждому интервалу дискретности t будет соответствовать свой выходной сигнал y(t). Следовательно, функционирование автомата рассматривается через дискретные интервалы времени конечной продолжительности. В абстрактной теории цифровых автоматов считается, что входные сигналы воздействуют на синхронный автомат в момент начала каждого i -того интервала (кванта) времени, выделенного соответствующим синхроимпульсом (тактом), а изменение внутренних состояний автомата происходит в интервалы времени между смежными синхроимпульсами, когда нет воздействия входных сигналов.

Понятие «состояние» используют для того, чтобы установить функциональную зависимость генерируемых автоматом символов и/или слов выходного языка от символов и/или слов входного языка при реализации автоматом заданного алгоритма. Для каждого состояния автомата sÎS и для каждого символа xÎX в момент дискретного времени [t] на выходе устройства генерируется символ yÎY. Эту зависимость определяет функция выходов автомата j. Для каждого текущего состояния автомата sÎS и для каждого символа xÎX в момент дискретного времени [t] автомат переходит в очередное состояние sÎS. Эту зависимость определяет функция переходов автомата y. Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата (s 1[ s 2 s 3 ...) и последовательности выходных символов (y 1 y 2 y 3 ...), которые для последовательности символов (x 1 x 2 x 3 ...) разворачиваются в моменты дискретного времени t = 1,2,3,.... В прямоугольных скобках указывают моменты дискретного времени, которые называют иначе тактами, в круглых скобках - последовательности символов алфавитов X, Y и S.

Итак, математическая модель конечного автомата есть трехосновная алгебра, носителями которой являются три множества X, Y и S, а операциями - две функции j и y.

В данной статье под термином «конечный автомат» подразумевается алгоритм, который может находиться в одном из небольшого количества состояний. «Состояние» - это некое условие, определяющее заданную взаимосвязь входных и выходных сигналов, а также входных сигналов и последующих состояний. Смышленый читатель сразу отметит, что конечные автоматы, описанные в данной статье, это автоматы Мили. Автомат Мили – это конечный автомат, где выходные сигналы являются функциями текущего состояния и входного сигнала, в отличие от автомата Мура, в котором выходные сигналы – это функции только состояния. В обоих случаях последующее состояние – это функция текущего состояния и входного сигнала.

Рассмотрим пример простого конечного автомата. Представьте, что в текстовой строке вам нужно распознать последовательность символов «//». На рисунке 1 показано, как это выполняется при помощи конечного автомата. Первое появление слеша не дает выходного сигнала, но приводит к тому, что автомат переходит во второе состояние. Если во втором состоянии автомат не находит слеша, он возвращается к первому, поскольку необходимо наличие 2-х слешей подряд. Если второй слеш найден, автомат выдает сигнал «готово».

Выясните, что необходимо заказчику.

Составьте диаграмму перехода состояний

Закодируйте «скелет» конечного автомата без детализации операций перехода.

Убедитесь, что переходы функционируют правильно.

Конкретизируйте детали переходов.

Проведите тест.

Пример конечного автомата

Рассмотрим более интересный пример конечного автомата - программу, контролирующую втягивание и выдвижение шасси самолета. Хотя у большинства самолетов эта процедура выполняется при помощи электрогидравлического управляющего механизма (просто потому, что на борту отсутствует компьютер), в некоторых случаях, например в беспилотных летательных аппаратах, стоит использовать программное управление.

Для начала разберемся с оборудованием. Шасси самолета состоит из передней опоры, основного левого шасси и основного правого шасси. Они приводятся в действие гидравлическим механизмом. Гидравлический насос с электроприводом подает давление на силовой исполнительный механизм. При помощи программного обеспечения насос включается или выключается. Компьютер регулирует положение клапана направления - «вниз» или «вверх», чтобы позволить давлению поднять или опустить шасси. Каждая из опор шасси имеет концевой выключатель: один из них закрывается, если шасси поднято, другой - если оно зафиксировано в положении «вниз». Чтобы определить, находится ли самолет на земле, концевой выключатель на стойке передней опоры замыкается, если вес самолета приходится на переднюю опору. Средства управления пилота состоят из верхнего/нижнего рычага шасси и трех лампочек (по одной на каждую опору), которые могут выключаться, загораться зеленым (положение «вниз») или красным светом (положение «переход»).

А теперь перейдем к разработке конечного автомата. Первый, и самый сложный шаг – это понять реальные ожидания заказчика. Одним из преимуществ конечного автомата состоит в том, что он заставляет программиста продумывать все возможные случаи и, как следствие, получать от заказчика всю требуемую информацию. Почему я считаю это самым сложным этапом? А сколько раз вам давали описание задачи подобное этому: не задвигайте шасси, если самолет находится на земле.

Безусловно, это важно, но заказчик считает, что на этом все заканчивается. А как насчет остальных случаев? Достаточно ли задвигать шасси в тот момент, когда самолет отрывается от земли? Что, если самолет подскочит на кочке на взлетно-посадочной полосе? Что, если пилот переведет рычаг переключения скоростей в положение «вверх» во время парковки и, как следствие, начнет взлетать? Должно ли шасси в этом случае подняться?

Одним из преимуществ мышления в терминах конечного автомата является то, что вы можете быстро нарисовать диаграмму перехода состояний на проекционной доске, прямо перед заказчиком, и пройти весь процесс вместе с ним. Принято такое обозначение перехода состояний: «событие, которое явилось причиной перехода»/«выходной сигнал как результат перехода». Если бы мы разрабатывали только то, о чем изначально просил заказчик («не задвигать шасси, если самолет находится на земле»), то мы бы получили автомат, изображенный на рисунке 2.

При составлении диаграммы перехода состояний (или любого другого алгоритма) помните о следующем:

Компьютеры работают очень быстро по сравнению с механической аппаратурой

Инженер-механик, который объясняет, что требуется сделать, возможно, не знает о компьютерах и алгоритмах всего того, что знаете вы. И это тоже положительный момент, в противном случае, вы бы не потребовались!

Как поведет себя ваша программа, если сломается механическая или электрическая деталь?

Конечный автомат, основанный на том, что действительно требуется заказчику, показан на рисунке 3. Здесь мы хотим воспрепятствовать втягиванию шасси самолета до тех пор, пока он точно не будет в воздухе. Для этого после открытия переключателя приземления автомат в течение нескольких секунд находится в ожидании. Мы также хотим реагировать на нарастающий фронт рычага пилота, а не на уровень, что позволит избежать проблем, если кто-то подвинет рычаг, пока самолет находится на парковке. Втягивание или выдвижение шасси занимает несколько секунд, и мы должны быть готовы к ситуации, что пилот в процессе этой операции передумает и переместит рычаг в противоположном направлении. Также обратите внимание, что если самолет снова приземлится, пока мы находимся в состоянии «Waiting for takeoff», таймер перезапустится и втягивание шасси произойдет, только если самолет будет находиться в воздухе в течение 2-х секунд.

Реализация конечного автомата

Листинг 1 – это моя реализация конечного автомата изображенного на рисунке 3. Давайте обсудим некоторые детали кода.

/*листинг 1*/

typedef enum {GEAR_DOWN = 0, WTG_FOR_TKOFF, RAISING_GEAR, GEAR_UP, LOWERING_GEAR} State_Type;

/*Этот массив содержит указатели на функции, вызываемые в определенных состояниях*/

void (*state_table)() = {GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear};

State_Type curr_state;

InitializeLdgGearSM();

/*Сердце автомата – этот бесконечный цикл. Функция, соответствующая

Текущему состоянию, вызывается один раз в итерацию */

while (1) {

state_table();

DecrementTimer();

void InitializeLdgGearSM(void )

curr_state = GEAR_DOWN;

/*Остановка аппаратуры, выключение лампочек и т.д.*/

void GearDown(void )

/* Переходим в состояние ожидания, если самолет

Не на земле и поступила команда поднять шасси*/

if ((gear_lever == UP) && (prev_gear_lever == DOWN) && (squat_switch == UP)) {

curr_state = WTG_FOR_TKOFF;

prev_gear_lever = gear_lever;

void RaisingGear(void )

if ((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) {

curr_state = GEAR_UP;

/*Если пилот изменил свое решение, перейти в состояние «опускание шасси»*/

if (gear_lever == DOWN) {

curr_state = LOWERING_GEAR;

void GearUp(void )

/*если пилот передвинул рычаг в положение «вниз»,

Переходим в состояние «опускание шасси»*/

if (gear_lever == DOWN) {

curr_state = LOWERING_GEAR;

void WtgForTakeoff(void )

/* Ожидание перед поднятием шасси.*/

if (timer <= 0.0) {

curr_state = RAISING_GEAR;

/*Если мы снова коснулись или пилот поменял решение – начать все заново*/

if ((squat_switch == DOWN) || (gear_lever == DOWN)) {

curr_state = GEAR_DOWN;

/* Don"t want to require that he toggle the lever again

This was just a bounce.*/

prev_gear_lever = DOWN;

void LoweringGear(void )

if (gear_lever == UP) {

curr_state = RAISING_GEAR;

if ((nosegear_is_down == MADE) && (leftgear_is_down == MADE) &&(rtgear_is_down == MADE)) {

curr_state = GEAR_DOWN;

Во-первых, вы можете заметить, что функциональность каждого состояния реализуется отдельной Си функцией. Конечно, можно было бы реализовать автомат, используя оператор switch с отдельным case `ом для каждого состояния, однако это может привести к очень длинной функции (10-20 строк кода на 1 состояние для каждого из 20-30 состояний). Также это может привести к ошибкам, если будете изменять код на конечных стадиях тестирования. Возможно, вы никогда не забывали оператор break в конце case`a, но со мной такие случаи бывали. Код одного состояния никогда не попадет в код другого, если для каждого состояния у вас будет отдельная функция.

Чтобы избежать применения оператора switch, я использую массив указателей на функции состояний, а переменную, используемую в качестве индекса массива, объявляю типа enum.

Для простоты оборудование ввода-вывода, ответственное за считывание состояния переключателей, включение и выключение насосов и т.д., представлено в виде простых переменных. Предполагается, что данные переменные представляют собой «магические адреса», связанные с оборудованием невидимыми средствами.

Другая очевидная вещь - в этот момент код не играет особой роли. Он просто переходит от одного состояния к другому. Это важный промежуточный этап и его не следует игнорировать. Кстати, было бы неплохо добавить операторы печати, заключенные между директивами условной компиляции (#ifdef DEBUG .. #endif), которые бы выводили текущее состояние и значения входных сигналов.

Залог успеха кроется в коде, который вызывает переход состояний, т.е. определяет, что произошел ввод данных.

Если код правильно проходит через все состояния, следующим этапом становится написание «начинки» кода, то есть именно того, что производит выходной сигнал. Помните, что каждый переход имеет входной сигнал (событие, которое вызвало его) и выходной сигнал (аппаратное устройство ввода-вывода, как в нашем примере). Зачастую это полезно зафиксировать в виде таблицы перехода состояний.

В таблице перехода состояний одна строка приходится на один переход состояния.

При кодировании конечного автомата старайтесь сохранить его силу – ярко выраженное соответствие между требованиями заказчика и кодом. Вероятно, придется скрыть подробности касательно оборудования в другом уровне функций, например, для того, чтобы код конечного автомата максимально походил на таблицу перехода состояний и диаграмму перехода состояний. Подобная симметрия помогает предотвратить ошибки и объясняет то, почему конечные автоматы являются такой важной частью арсенала программиста встраиваемых систем. Конечно, вы могли бы добиться того же эффекта путем установки флажков и бесконечного множества вложенных операторов if, однако при этом будет очень сложно отслеживать код и сравнивать его с пожеланиями заказчика.

Фрагмент кода в листинге 2 расширяет функцию RaisingGear(). Обратите внимание, что код для функции RaisingGear() стремится к зеркальному отображению 2-х рядов таблицы переходов для состояния Raising Gear.

void RaisingGear(void )

/*После того, как все переключатели подняты, переходим в состояние «шасси поднято»*/

if ((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) {

pump_motor = OFF;

gear_lights = EXTINGUISH;

curr_state = GEAR_UP;

/*Если пилот передумал, начать втягивание шасси*/

if (gear_lever == DOWN) {

pump_direction = DOWN;

curr_state = GEAR_LOWERING;

Помните о том, что следует избегать скрытых состояний. Скрытое состояние появляется тогда, когда по причине лени вы пытаетесь добавить условное субсостояние вместо того, чтобы добавить конкретное состояние. Например, если ваш код обрабатывает один и тот же входной сигнал разными способами (т.е. инициирует разные переходы состояний) в зависимости от режима, то он является скрытым состоянием. В этом случае я бы задумался, а не следует ли разбить данное состояние на два? Применение скрытых состояний сводит на нет все преимущество использования конечного автомата.

В качестве тренировки вы можете расширить конечный автомат, который мы только что рассмотрели, добавив таймаут к циклу втягивания или выдвижения шасси, т.к. инженер-механик не хочет, чтобы гидравлический насос работал дольше 60 секунд. Если цикл заканчивается, пилот должен быть предупрежден переключением зеленой и красной лампочки, и он должен иметь возможность снова переместить рычаг, чтобы повторить попытку. Также вы можете спросить гипотетического инженера-механика, как сказывается на насосе изменение направления на противоположное во время его работы, потому что это происходит в 2-ух случаях, когда пилот передумывает. Конечно, механик скажет, что негативно. Тогда как бы вы изменили конечный автомат, чтобы быстро остановить насос при изменении направления?

Тестирование конечного автомата

Прелесть кодирования алгоритмов в виде конечных автоматов состоит в том, что план проведения теста почти автоматически пишется сам. Все, что вам нужно сделать – это пройти через каждый переход состояния. Я обычно делаю это с маркером в руках, вычеркивая стрелки на диаграмме перехода состояний по мере того, как они успешно проходят тест. Это хороший способ избежать «скрытых состояний» - в тестах они упускаются чаще, чем конкретные состояния.

Это требует значительного терпения и большого количества кофе, так как даже конечный автомат средних размеров может иметь до 100 различных переходов. Кстати, количество переходов – это отличный способ измерить сложность системы. Последнее определяется требованиями заказчика, а конечный автомат делает очевидными объемы тестирования. При менее организованном подходе объем требуемого тестирования может оказаться таким же внушительным, но вы об этом просто не узнаете.

Очень удобно использовать в коде операторы печати, выводящие текущее состояние, значения входных и выходных сигналов. Это позволяет вам с легкостью наблюдать то, что выражает «Золотое Правило Тестирования Программ»: проверяйте, что программа выполняет задуманное, а также то, что она не делает ничего лишнего. Другими словами, получаете ли вы только те выходные сигналы, которые вы ожидаете, и что еще происходит помимо этого? Нет ли «затруднительных» переходов состояний, т.е. состояний, которые случайно проходят, только для одного повтора цикла? Меняются ли выходные сигналы, когда вы этого не ожидаете? В идеале выходные сигналы ваших printfs должны заметно напоминать таблицу перехода состояний.

Наконец - и это касается любого встроенного ПО, а не только ПО, основанного на конечных автоматах - будьте очень осторожны при первом запуске ПО на реальном оборудовании. Очень легко ошибиться с полярностью сигналов – «Ой, я думал, что «1» означает поднять шасси, а «0» - опустить его». Во многих случаях, мой помощник по оборудованию применял временный «куриный переключатель» для защиты ценных компонентов, пока не был уверен, что мое ПО перемещает предметы в правильном направлении.

Запуск

Когда все требования заказчика выполнены, я могу запускать конечный автомат подобной сложности через пару дней. Практически всегда автоматы выполняют то, что я хочу. Самое сложное – это, конечно, точно понять, чего хочет заказчик и убедиться, что заказчик сам знает, чего он хочет. Последнее занимает значительно больше времени!

Мартин Гомез – программист Лаборатории Прикладной Физики при Университете Джона Хопкинса. Занимается разработкой ПО для обеспечения полетов исследовательских космических кораблей. Проработал в области разработки встраиваемых систем в течение 17 лет. Мартин – бакалавр наук в области аэрокосмического инжиниринга и магистр в области электроинжиниринга (университет Корнелл).

Одним из критериев сложности конечного автомата является число его состояний. Чем меньше это число, тем проще дискретное устройство, реализующее данный автомат. Поэтому одной из важных задач теории конечных автоматов является построение автомата с наименьшим числом состояний.

Поскольку в современных компьютерах любая информация представ­ляется в виде двоичных кодов, то для построения автомата можно исполь­зовать элементы, имеющие лишь два различных устойчивых состояния, одно из которых соответствует цифре 0,а другое цифре 1.

Приведём несколько примеров конечных автоматов.

Пример 1. Элемент задержки (элемент памяти).

Элементы задержки представляют собой устройство, имеющее один вход и один выход. Причем значение выходного сигнала в момент времени t совпадает со значением сигнала в предыдущий момент. Схематично элемент задержки можно изобразить следующим образом (рис. 2).

Предположим, что входной и, следовательно, выходной алфавит есть X ={0, 1}, Y ={0, 1}. Тогда Q ={0, 1}. Под состоянием элемента задержки в момент времени t понимается содержание элемента памяти в данный момент. Таким образом q (t )= X (t 1), a Y (t )= q (t )=X (t 1).

Зададим элемент задержки таблицей, где а 1 =0, а 2 =1, q 1 =0, q 2 =1,

(a 1 , q 1)= (0, 0)=0,  (a 1 , q 1)= (0, 0)=0;

(a 1 , q 2)= (0, 1)=0,  (a 1 , q 2)= (0, 1)=1;

(a 2 , q 1)= (1, 0)=1,  (a 2 , q 1)= (1, 0)=0;

(a 2 , q 2)= (1, 1)=1,  (a 2 , q 2)= (1, 1)=1;

q a
	=0,  =0	=0,  =1
	=1,  =0	=1,  =1

Диаграмма Мура изображена на рис. 3

Для представления этого автомата системой булевых функций ис­пользуем таблицу автомата и вышеизложенный алгоритм. При этом ко­дирование производить не нужно, так как входной и выходной алфавиты и состояния уже закодированы.

Обратим внимание на то, что т=п=р =2. Тогда k =r =s =1, и поэтому элемент задержки задается двумя функциями  и  . Таблица истинности этих функций содержит 2 k + r =2 2 =4 строки и k +r +r +s =4 столбца:

x	z

Пример 2. Двоичный сумматор последовательного действия.

Данный сумматор последовательного действия представляет собой устройство, осуществляющее сложение двух чисел в двоичной системе исчисления. На входы сумматора подаются числа х 1 и x 2 , начиная с младших разрядов. На выходе формируется последовательность, соответствующая записи числа х 1 +x 2 в двоичной системе исчисления (рис. 4).

Входной и выходной алфавиты определены однозначно: X ={00; 01; 10; 11}, Y ={0,1}. Множество состояний определяется значением пере­носа при сложении соответствующих разрядов чисел х 1 и x 2 . Если при сложении некоторых разрядов образовался перенос, то будем считать, что сумматор перешел в состояние q 1 . При отсутствии переноса будем считать, что сумматор находится в состоянии q 0 .

Сумматор задается таблицей.

q a	q 0	q 1
	q 0 , 0	q 0 , 1
	q 0 , 1	q 1 , 0
	q 0 , 1	q 1 , 0
	q 1 , 0	q 1 , 1

Диаграмма Мура сумматора последовательного действия изображена на рис. 5.

Заметим, что входные и выходные символы уже закодированы. Состояния закодируем следующим образом:  (q 0)=0,  (q 1)=1. Поэтому сумматор последовательного действия задается двумя булевыми функциями, таблица истинности которых следующая:

x 1	x 2	z

Пример 3. Схема сравнения на равенство.

Схема сравнения на равенств представляет собой устройство, срав­нивающее два числа х 1 и x 2 , заданное в двоичной системе исчисления. Это устройство работает следующим образом. На вход устройства после­довательно, начиная со старших, подаются разряды чисел х 1 и x 2 . Эти разряды сравниваются. При совпадении разрядов на выходе схемы формируется выходной сигнал 0, в противном случае на выходе появляется сигнал 1. Ясно, что появление 1 в выходной последовательности означает, что сравниваемые числа х 1 и x 2 различны. Если же выходная последовательность является нулевой и ее длина совпадает с числом разрядов сравниваемых чисел, то х 1 и x 2 .

Для этого автомата X ={00, 01, 10, 11}; Y ={0,1}.

Функционирование схемы определяется двумя состояниями. Состояние q 0 соответствует равенству сравниваемых в данный момент разрядов. При этом автомат остается в этом же состоянии. Если в следующий момент сравниваемые разряды будут различны, то автомат перейдет в новое состояние q 1 и в нем остается, так как это означает, что числа различны. Таким образом, схему сравнения можно задать таблицей:

q x	q 0	q 1
	q 0 , 0	q 1 , 1
	q 1 , 1	q 1 , 1
	q 1 , 1	q 1 , 1
	q 0 , 0	q 1 , 1

Диаграмма Мура схемы сравнения на равенство изображена на рис. 6.

Кодирование состояний произведем следующим образом:  (q 0)=0,  (q 1)=1. Автомат будет задаваться двумя функциями.

x 1	x 2	z

Пример 4. Схема сравнения на неравенство.

Схема сравнения на неравенство представляет собой устройство, позволяющее выяснить, равны ли сравниваемые х 1 и x 2 , и если они не равны, выяснить, какое из них больше другого. Это устройство имеет два входа и два выхода. Выходные сигналы y 1 (t ) и y 2 (t )определяются по следующим правилам:

y 1 (t )=y 2 (t )=0, если x 1 (t )=x 2 (t );

y 1 (t )=1, y 2 (t )=0, если x 1 (t )>x 2 (t ), то есть x 1 (t )=1, x 2 (t )=0;

y 1 (t )=0, y 2 (t )=1, если x 1 (t )<x 2 (t ), то есть x 1 (t )=0, x 2 (t )=1.

Таким образом, при подаче на вход схемы сравнения на неравенство чисел x 1 =x 1 (l)…x 1 (t ) и x 2 =x 2 (l)…x 2 (t )последовательно сравниваются разряды этих чисел, начиная со старших. Выходные сигналы формулируются согласно вышеуказанным правилам. При этом, если выходная последовательность состоит из нулевых пар, то x 1 =x 2 . Если первая, отличная от нулевой, пара имеет вид , () то x 1 >x 2 (x 1 <x 2).

Из описания схемы следует, что

X ={00, 01, 10, 11}, Y ={00, 01, 10}.

Состояние схемы определяется следующим образом. Предположим, что в начальный момент времени t =1 автомат находится в состоянии q 1 . Если сравниваемые разряды чисел х 1 и х 2 совпадают, то автомат остается в этом состоянии. Заметим, что на выходе при этом появится сигнал 00. Если же разряд числа х 1 будет меньше (больше) соответствующего разряда числа х 2 , то автомат перейдет в состояние q 2 (q 3). При этом на выходе появится сигнал 01 (10). В дальнейшем при подаче оставшихся разрядов чисел х 1 и х 2 на входы автомата автомат будет оставаться в состоянии q 2 (q 3) и вырабатывать выходной символ 10 (01). Из вышеизложенного следует, что схему сравнения на неравенство можно задать таблицей:

q x	q 1	q 2	q 3
	q 1 , 00	q 2 , 01	q 3 , 10
	q 2 , 01	q 2 , 01	q 3 , 10
	q 3 , 10	q 2 , 01	q 3 , 10
	q 1 , 00	q 2 , 01	q 3 , 10

Соответствующая диаграмма Мура изображена на рис. 7.

Входной и выходной алфавиты здесь уже закодированы. Состояния q 1 , q 2 и q 3 закодируем:  1 (q 1)=00,  (q 2)=01,  (q 3)=10.

Следовательно, данную схему можно задать системой, состоящей из четырех булевых функций, которые зависят от четырех переменных. Эти функции частично определены и задаются таблицей истинности

	x 1	x 2	z 1	z 2

В таблице символами * отмечены наборы переменных x 1 , x 2 , z 1 , z 2 , на которых функции  1 ,  2 ,  1 ,  2 не определены. Положим значения функций  1 ,  2 ,  1 ,  2 на этих наборах равными 1.

Сегодня мы поговорим о автоматах, но отнюдь не тех что держат в руках солдаты российской армии. Речь пойдет о таком интересном стиле программирования микроконтроллеров как автоматное программирование. Точнее это даже не стиль программирования а целая концепция, благодаря которой программист микроконтроллеров может значительно облегчить свою жизнь. Благодаря которой многие задачи представленные перед программистом решаются гораздо легче и проще, избавляя программиста от головной боли. Кстати автоматное программирование зачастую называют SWITCH-технологией.

Хочу заметить что стимулом написания этого поста послужил цикл статей о SWITCH-технологии Владимира Татарчевского. Цикл статей называется «Применение SWITCH-технологии при разработке прикладного программного обеспечения для микроконтроллеров» Так что в этом статье я постараюсь по большей части привести пример рабочего кода и его описание.

Кстати я запланировал ряд статей посвященных программированию, в которых буду подробно рассматривать приемы программирования под микроконтроллеры АВР, не пропустите …. Ну что ж поехали!

Программа последовательно выполняет команды заложенные программистом. Для обычной компьютерной программы совершенно нормально когда программа отработала и остановила свое исполнение, выводя при этом результаты своей работы на монитор.

Программа под микроконтроллер не может просто закончить свое исполнение. Вот представьте себе, что вы включили плеер или магнитофон. Вы нажали кнопочку power, выбрали желаемую композицию, и наслаждаетесь музыкой. Однако когда музыка прекратила трепать барабанную перепонку вашего уха, плеер завис и никак не реагирует на нажатие кнопочек а тем более на ваши танцы с бубном.

А что здесь такого? Все нормально — контроллер, тот что в недрах вашего плеера просто закончил выполнение своей программы. Вот видите неудобненько как-то получается.

Так вот отсюда мы делаем вывод, что программа под микроконтроллер просто не должна останавливаться. По сути своей она должна представлять собой бесконечный цикл — только в этом случае наш плеер работал бы правильно. Дальше я вам покажу какие бывают конструкции программного кода под микроконтроллеры, это даже не конструкции а некоторые стили программирования.

Стили программирования.

«Стили программирования» — звучит как-то непонятно, ну да ладно. Что я хочу этим сказать?Представим, что человек никогда до этого не занимался программированием, то есть вообще полный чайник.

Этот человек прочел много книг по программированию, изучил все основный конструкции языка. Он насобирал информации по крупицам, благо сейчас доступ к информации неограничен. Все это хорошо, но как будут выглядеть его первые программы? Мне кажется что он не будет мудрствовать, а пойдет по пути от простого к сложному.

Так вот эти стили и являются ступеньками ведущими от простого уровня к более сложному, но и в тоже время более эффективному.

Поначалу я не задумывался о каких-то конструктивных особенностях программы. Я просто формировал логику программы — чертил блок-схему и писал код. От чего постоянно натыкался на грабли. Но это было первое время когда я не парился и использовал стиль «простое зацикливание», затем стал применять прерывания, далее были автоматы и пошло поехало…

1. Простое зацикливание. Программа в этом случае зацикливается без каких-либо премудростей и в этом есть свои плюсы и минусы. Плюс лишь в простоте подхода, не нужно выдумывать хитрые конструкции, пишешь так как думаешь (постепенно роя себе могилу).

Void main(void) { initial_AL(); //инициализация периферии while(1) { Leds_BLINK(); //функция светодиодной мигалки signal_on(); //функция включения сигнала signal_off(); //функция выключения сигнала l=button(); //переменная отвечающая за нажатие кнопок switch(l) //В зависимости от величины переменной выполняется то или иное действие { case 1: { Deistvie1(); //Вместо функции может быть условный оператор Deistvie2(); //или еще несколько веток switch case Deistvie3(); Deistvie4(); Deistvie5(); }; case 2: { Deistvie6(); Deistvie7(); Deistvie8(); Deistvie9(); Deistvie10(); }; . . . . . . . . } } }

Рабочая точка программы движется по порядку. При этом последовательно выполняются все действия, условия и циклы. Код начинает тормозить, приходится вставлять много лишних условий, усложняя тем самым восприятие.

Все это очень сильно запутывает программу, делая из кода клубок условий. В итоге к этому коду не добавить ни отнять, он становится как монолитный кусок. Конечно когда объем не большой, код поддается модификациям, но чем дальше тем сложнее.

С таким подходом я написал несколько программок, они были не большие и вполне рабочие но наглядность оставляла желать лучшего. Чтобы добавить какое-то новое условие, приходилось перелопачивать весь код, потому, что все было завязано. Это порождало много ошибок и головной боли. Компилятор ругался как только мог, отлаживание такой программы превращалось в ад.

2. Цикл + прерывания.

Отчасти разрулить бесконечный тормозной цикл можно используя прерывания. Прерывания помогают вырваться из порочного круга, помогают не пропустить важного события, добавляют дополнительный функционал (прерывания от таймеров, внешние прерывания).

Допустим на прерывание можно повесить обработку кнопок, или отслеживание важного события. В результате программа становится более наглядной но не менее запутанной.

К сожалению прерывание не спасет от каши, в которую превращается программа. Не удастся разделить на части то, что представляет собой единое целое.

3. Автоматное программирование.

Вот мы и подбираемся к главной теме данной статьи. Программирование в конечных автоматах избавляет программу от недостатков присущих первым двум примерам. Программа становится проще, ее легко модифицировать.

Программа написанная в автоматном стиле похожа на переключатель, который в зависимости от условий переключается в то или иное состояние. Количество состояний программисту изначально известно.

В грубом представлении это как выключатель освещения. Есть два состояния включено и выключено, и два условия включить и выключить. Ну а обо всем по порядку.

Реализация многозадачности в switch-технологии.

Микроконтроллер способен управлять нагрузкой, моргать светодиодами, отслеживать нажатие клавиш и многое другое. Но как все это делать одновременно? Для решения этого вопроса существует множество решений. Самый простой из них я уже упоминал это использование прерываний.

В процессе работы программы, когда происходит прерывание, контроллер отвлекается от выполнения кода программы и кратковременно выполняет другой кусок программы за который отвечает прерывание. Прерывание отработает, тогда рабочая точка программы продолжит с того места, с которого контроллер прервался на прерывание (само слово говорит о том что контроллер прерывается).

Другой способ реализации многозадачности это использование операционных систем. Да действительно стали уже появляться маленькие ОСьки, которые можно применить на маломощном контроллере. Но зачастую этот способ получается несколько избыточным. Ведь зачем расходовать ресурсы контроллера излишней работой когда вполне можно обойтись малой кровью.

В программах написанных по switch — технологии подобная «иллюзия» многозадачности получается благодаря системе обмена сообщений. Я написал «иллюзия», потому, что так и есть на самом деле, ведь программа физически не может в одно и тоже время выполнять различные участки кода. О системе обмена сообщениями я расскажу немного дальше.

Система обмена сообщениями.

Разрулить многочисленные процессы и создать иллюзию многозадачности можно используя систему обмена сообщениями.

Допустим нам нужна программа в которой идет переключение светодиода. Вот у нас есть два автомата, назовем их LEDON -автомат ответственный за включение светодиода и автомат LEDOFF — автомат ответственный за выключение светодиода.

Каждый из автоматов имеет два состояния, то есть автомат может быть в активном состоянии так и неактивном состоянии, как рубильник либо включено, либо выключено.

При активации одного автомата происходит зажжение светодиода, при активации другого светодиод гасится. Рассмотрим небольшой пример:

Int main(void) { INIT_PEREF(); //инициализация периферии (светодиоды) InitGTimers(); //инициализация таймеров InitMessages(); //инициализация механизма обработки сообщений InitLEDON(); //инициализация автомата LEDON InitLEDOFF(); //инициализация автомата LEDOFF SendMessage(MSG_LEDON_ACTIVATE); //активируем автомат LEDON sei(); //Разрешаем прерывания //Главный цикл программы while(1) { ProcessLEDON(); //итерация автомата LEDON ProcessLEDOFF(); //итерация автомата LEDOFF ProcessMessages(); //обработка сообщений }; }

В строках 3 -7 происходят различные инициализации поэтому нас это сейчас не особо интересует. А вот дальше происходит следующее: перед запуском главного цикла (while(1)), мы отправляем сообщение автомату

SendMessage(MSG_LEDON_ACTIVATE)

ответственному за зажжение светодиода. Без этого маленького шажка наша шарманка не заработает. Далее главный бесконечный цикл while выполняет основную работу.

Небольшое отступление:

Сообщение имеет три состояния. А именно состояние сообщение может быть неактивно, установлено но неактивно и активное состояние.

Получается, что сообщение изначально было неактивно, когда мы отправили сообщение, оно получило состояние «установлено но неактивно». И это дает нам следующее. При последовательном выполнении программы автомат LEDON сообщение не получает. Происходит холостая итерация автомата LEDON при котором сообщение просто не может быть принято. Так как сообщение имеет состояние «установлено но неактивно» программа продолжает свое выполнение.

После того как все автоматы в холостую протикают, очередь доходит до функции ProcessMessages(). Эта функция всегда ставится в конце цикла, после выполнения всех итераций автоматов. Функция ProcessMessages(), просто переводит сообщение из состояния «установлено но неактивно» в состояние «активно».

Когда бесконечный цикл выполняет второй круг, картина уже становится совершенно другая. Итерация автомата ProcessLEDON уже не будет холостой. Автомат сможет принять сообщение, перейдет в зажженное состояние и также в свою очередь отправит сообщение.Оно будет адресовано автомату LEDOFF и жизненный цикл сообщения повторится.

Хочу заметить, что сообщения которые имеют состояние «активно», при встрече с функцией ProcessMessages уничтожаются. Поэтому сообщение может быть принято только одним автоматом. Есть еще один тип сообщений — это широковещательные сообщения, но я их рассматривать не буду, в статьяхТатарчевского они также хорошо освещены.

Таймеры

С помощью правильной организации обмена сообщениями мы можем контролировать порядок работы конечных автоматов, но только лишь сообщениями нам не обойтись.

Наверное вы заметили, что предыдущий фрагмент программы, приведенный в качестве примера, не будет работать так, как задумано. Автоматы будут обмениваться сообщениями, светодиоды будут переключаться, вот только мы этого не увидим. Мы увидим только тускло горящий светодиод.

Все потому, что мы не продумали грамотную отработку задержек. Ведь нам не достаточно попеременного включения-выключения светодиодов, светодиод должен задерживаться в каждом состоянии, допустим на секунду.

Алгоритм будет следующим:

Можно кликнуть чтобы увеличить

Забыл дописать на этой блок схеме, что когда таймер дотикал, конечно же выполняется действие — зажжение светодиода или его гашение.

1. Входим в состояние посредством принятия сообщения.

2. Проверяем показания таймера/счетчика, если дотикало, то выполняем действие, иначе просто отправляем сообщение самому себе.

3. Отправляем сообщение следующему автомату.

4. Выход

В следующем входе все повторяется.

Программа по SWITCH-технологии. Три шага.

А давайте напишем программу в конечных автоматах и для этого нам нужно будет проделать всего три простых шага. Программа будет простой но именно с простых вещей стоит начинать. Нам подойдет программа с переключающимся светодиодом. Это очень хороший пример, так не будем изобретать ничего нового.

Программу я буду составлять на языке СИ, но это совсем не значить что в конечных автоматах нужно писать только на Си, вполне можно использовать любой другой язык программирования.

Программа будет у нас модульной и поэтому будет разбита на несколько файлов. Модули у нас будут следующие:

• Модуль основного цикла программы содержит файлы leds_blink.c, HAL.c, HAL.h
• Модуль таймеров содержит файлы timers.c, timers.h
• Модуль обработки сообщений содержит файлы messages.c, messages.h
  
• Модуль автомата 1 содержит файлы ledon.c, ledon.h
• Модуль автомата 2 содержит файлы ledoff.c , ledoff .h

Шаг 1.

Создаем проект и сразу подключаем к нему файлы наших статичных модулей:timers.c, timers.h, messages.c, messages.h.

Файл leds_blink.c модуля основного цикла прогарммы.

#include "hal.h" #include "messages.h" //модуль обработки сообщений #include "timers.h" //модуль таймеров //Прерывания по таймеру //############################################################################################ ISR(TIMER0_OVF_vect) // переход по вектору прерывания (переполнение таймера счетчика T0) { ProcessTimers(); //Обработчик прерываний от таймера } //########################################################################################### int main(void) { INIT_PEREF(); //инициализация переферии (светодиоды) InitGTimers(); //инициализация таймеров InitMessages(); //инициализация механизма обработки сообщений InitLEDON(); //инициализация автомата LEDON InitLEDOFF(); StartGTimer(TIMER_SEK); //Запуск таймера SendMessage(MSG_LEDON_ACTIVATE); //активируем автомат FSM1 sei(); //Разрешаем прерывания //Главный цикл программы while(1) { ProcessLEDON(); //итерация автомата LEDON ProcessLEDOFF(); ProcessMessages(); //обработка сообщений }; }

В первых строчках происходит подключение к основной программе остальных модулей. Здесь мы видим что подключены модуль таймеров и модуль обработки сообщений. Далее по тексту программы идет вектор прерывания по переполнению.

Со строчки int main (void) можно сказать начинается основная программа. И начинается она с инициализации всего и вся. Здесь инициализируем периферию, то есть задаем начальные значения портам ввода вывода компаратору и всему остальному содержимому контроллера. Все это делает функция INIT_PEREF, здесь ее запускаем, хотя основное ее тело находится в файле hal.c.

Далее мы видим инициализации таймеров, модуля обработки сообщений, инициализации автоматов. Здесь эти функции также просто запускаются, хотя сами функции прописаны в файлах своих модулей. Видите как удобно. Основной текст программы остается легко читаемым и не загромождается избыточным кодом от которого черт ногу сломи.

Основные инициализации закончились теперь нам нужно сделать запуск основного цикла. Для этого отправляем стартовое сообщение, и к тому же заводим наши часики -запускаем таймер.

StartGTimer(TIMER_SEK); //Запуск таймера SendMessage(MSG_LEDON_ACTIVATE); //активируем автомат FSM1

А основной цикл, как я уже и говорил выгладит очень просто. Записываем функции всех автоматов, просто записываем в столбик, без соблюдения очередности. Эти функции являются обработчиками автоматов и находятся в модулях автоматов. Завершает эту автоматную пирамидку функция модуля обработки сообщений. Это я конечно уже рассказывал ранее когда разбирались с системой отправки сообщений. Теперь можно посмотреть как выглядят еще два файла модуля основного цикла программы

Hal.h — это заголовочный файл модуля основного цикла программы.

#ifndef HAL_h #define HAL_h #include #include //Стандартная библиотека включающая в себя прерывания #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //компаратор #define ViklKomparator 1<

Как вы могли заметить этот файл по своей сути не содержит ни строчки исполняемого кода — это все макроподстановки и подключение библиотек. Наличие этого файла просто очень хорошо облегчает жизнь, он улучшает наглядность.

А вот файл Hal.c — это уже исполняемый файл, и как я уже упоминал, в нем содержится различный инициализации периферии.

#include "hal.h" void INIT_PEREF(void) { //Инициализация портов ввода-вывода //################################################################################### Komparator = ViklKomparator; //инициализация компаратора - выключение DDRD = 1<

Ну чтож модуль основного цикла программы я показал теперь нам осталось сделать последний шаг, нам нужно написать модули самих автоматов.

Шаг 3.

Нам осталось написать модули конечных автоматов, в нашем случае автомата LEDON и автомата LEDOFF. Для начала приведу текст программы автомата зажигающего светодиод файл ledon.c.

//файл ledon.c #include "ledon.h" #include "timers.h" #include "messages.h" unsigned char ledon_state; //переменная состояния void InitLEDON(void) { ledon_state=0; //здесь можно выполнить инициализацию других //переменных автомата при их наличии } void ProcessLEDON(void) { switch(ledon_state) { case 0: //неактивное состояние if(GetMessage(MSG_LEDON_ACTIVATE)) //если сообщение есть то оно будет принято { //и пойдет проверка таймера if(GetGTimer(TIMER_SEK)==one_sek) //если таймер засек 1сек то выполняем { StopGTimer(TIMER_SEK); PORTD = 1<

Здесь в первых строчках как всегда подключаются библиотеки и объявляются переменные. Далее у нас пошли уже функции, с которыми мы уже встречались. Это функция инициализации автомата InitLEDON и функция уже самого обработчика автомата ProcessLEDON.

В теле обработчика уже происходит отработка функций из таймерного модуля и модуля сообщений. А сама логика автомата выполнена на основе конструкции switch-case. И здесь можно заметить что обработчик автомата можно также усложнить добавив несколько переключателей case.

Заголовочный файл для автомата будет еще проще:

//файл fsm1 #ifndef LEDON_h #define LEDON_h #include "hal.h" void InitLEDON(void); void ProcessLEDON(void); #endif

Здесь подключаем связующий файл hal.h а также указываем прототипы функций.

Файл ответственный за выключение светодиода будет выглядеть практически также только в зеркальном отражении, так, что здесь я его выводить не буду — неохота 🙂

Все файлы проекта вы можете скачать вот по этой ссылке ====>>>ССЫЛКА .

Вот всего три шага и наша программа приобрела законченный вид а значит на этом моя миссия на сегодня закончена и пора закругляться. Мне кажется что информация приведенная в этой статье будет для вас очень полезно. Но настоящую пользу она принесет только тогда, когда вы будете применять это знание на практике.

Кстати я запланировал ряд интересных проектов которые будут особенно интересны, так что обязательно подпишитесь на новые статьи . Также я планирую делать рассылку дополнительных материалов, поэтому многие уже подписываются через основную страницу сайта. Подписаться можно и здесь.

Ну теперь у меня действительно все, поэтому я желаю вам удачи, прекрасного настроения и до новых встреч.

С н/п Владимир Васильев

Конечный автомат - это некоторая абстрактная модель, содержащая конечное число состояний чего-либо. Используется для представления и управления потоком выполнения каких-либо команд. Конечный автомат идеально подходит для реализации искусственного интеллекта в играх, получая аккуратное решение без написания громоздкого и сложного кода. В данной статье мы рассмотрим теорию, а также узнаем, как использовать простой и основанный на стеке конечный автомат.

Мы уже публиковали серию статей по написанию искусственного интеллекта при помощи конечного автомата. Если вы еще не читали эту серию, то можете сделать это сейчас:

Что такое конечный автомат?

Конечный автомат (или попросту FSM - Finite-state machine) это модель вычислений, основанная на гипотетической машине состояний. В один момент времени только одно состояние может быть активным. Следовательно, для выполнения каких-либо действий машина должна менять свое состояние.

Конечные автоматы обычно используются для организации и представления потока выполнения чего-либо. Это особенно полезно при реализации ИИ в играх. Например, для написания «мозга» врага: каждое состояние представляет собой какое-то действие (напасть, уклониться и т. д.).

Конечный автомат можно представить в виде графа, вершины которого являются состояниями, а ребра - переходы между ними. Каждое ребро имеет метку, информирующую о том, когда должен произойти переход. Например, на изображении выше видно, что автомат сменит состояние «wander» на состояние «attack» при условии, что игрок находится рядом.

Планирование состояний и их переходов

Реализация конечного автомата начинается с выявления его состояний и переходов между ними. Представьте себе конечный автомат, описывающий действия муравья, несущего листья в муравейник:

Отправной точкой является состояние «find leaf», которое остается активным до тех пор, пока муравей не найдет лист. Когда это произойдет, то состояние сменится на «go home». Это же состояние останется активным, пока наш муравей не доберется до муравейника. После этого состояние вновь меняется на «find leaf».

Если состояние «find leaf» активно, но курсор мыши находится рядом с муравьем, то состояние меняется на «run away». Как только муравей будет в достаточно безопасном расстоянии от курсора мыши, состояние вновь сменится на «find leaf».

Обратите внимание на то, что при направлении домой или из дома муравей не будет бояться курсора мыши. Почему? А потому что нет соответствующего перехода.

Реализация простого конечного автомата

Конечный автомат можно реализовать при помощи одного класса. Назовем его FSM. Идея состоит в том, чтобы реализовать каждое состояние как метод или функцию. Также будем использовать свойство activeState для определения активного состояния.

Public class FSM { private var activeState:Function; // указатель на активное состояние автомата public function FSM() { } public function setState(state:Function) :void { activeState = state; } public function update() :void { if (activeState != null) { activeState(); } } }

Всякое состояние есть функция. Причем такая, что она будет вызываться при каждом обновлении кадра игры. Как уже говорилось, в activeState будет храниться указатель на функцию активного состояния.

Метод update() класса FSM должен вызываться каждый кадр игры. А он, в свою очередь, будет вызывать функцию того состояния, которое в данный момент является активным.

Метод setState() будет задавать новое активное состояние. Более того, каждая функция, определяющая какое-то состояние автомата, не обязательно должна принадлежать классу FSM - это делает наш класс более универсальным.

Использование конечного автомата

Давайте реализуем ИИ муравья. Выше мы уже показывали набор его состояний и переходов между ними. Проиллюстрируем их еще раз, но в этот раз сосредоточимся на коде.

Наш муравей представлен классом Ant , в котором есть поле brain . Это как раз экземпляр класса FSM .

Public class Ant { public var position:Vector3D; public var velocity:Vector3D; public var brain:FSM; public function Ant(posX:Number, posY:Number) { position = new Vector3D(posX, posY); velocity = new Vector3D(-1, -1); brain = new FSM(); // Начинаем с поиска листка. brain.setState(findLeaf); } /** * Состояние "findLeaf". * Заставляет муравья искать листья. */ public function findLeaf() :void { } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { } public function update():void { // Обновление конечного автомата. Эта функция будет вызывать // функцию активного состояния: findLeaf(), goHome() или runAway(). brain.update(); // Применение скорости для движения муравья. moveBasedOnVelocity(); } (...) }

Класс Ant также содержит свойства velocity и position . Эти переменные будут использоваться для расчета движения с помощью метода Эйлера . Функция update() вызывается при каждом обновлении кадра игры.

Ниже приводится реализация каждого из методов, начиная с findLeaf() - состояния, ответственного за поиск листьев.

Public function findLeaf() :void { // Перемещает муравья к листу. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this) <= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }

Состояние goHome() - используется для того, чтобы муравей отправился домой.

Public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }

И, наконец, состояние runAway() - используется при уворачивании от курсора мыши.

Public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) { // Нет, уже далеко. Пора возвращаться к поискам листочек. brain.setState(findLeaf); } }

Улучшение FSM: автомат, основанный на стеке

Представьте себе, что муравью на пути домой также нужно убегать от курсора мыши. Вот так будут выглядеть состояния FSM:

Кажется, что изменение тривиальное. Нет, такое изменение создает нам проблему. Представьте, что текущее состояние это «run away». Если курсор мыши отдаляется от муравья, что он должен делать: идти домой или искать лист?

Решением такой проблемы является конечный автомат, основанный на стеке. В отличие от простого FSM, который мы реализовали выше, данный вид FSM использует стек для управления состояниями. В верхней части стека находится активное состояние, а переходы возникают при добавлении/удалении состояний из стека.

А вот и наглядная демонстрация работы конечного автомата, основанного на стеке:

Реализация FSM, основанного на стеке

Такой конечный автомат может быть реализован так же, как и простой. Отличием будет использование массива указателей на необходимые состояния. Свойство activeState нам уже не понадобится, т.к. вершина стека уже будет указывать на активное состояние.

Public class StackFSM { private var stack:Array; public function StackFSM() { this.stack = new Array(); } public function update() :void { var currentStateFunction:Function = getCurrentState(); if (currentStateFunction != null) { currentStateFunction(); } } public function popState() :Function { return stack.pop(); } public function pushState(state:Function) :void { if (getCurrentState() != state) { stack.push(state); } } public function getCurrentState() :Function { return stack.length > 0 ? stack : null; } }

Обратите внимание, что метод setState() был заменен на pushState() (добавление нового состояния в вершину стека) и popState() (удаление состояния на вершине стека).

Использование FSM, основанного на стеке

Важно отметить, что при использовании конечного автомата на основе стека каждое состояние несет ответственность за свое удаление из стека при отсутствии необходимости в нем. Например, состояние attack() само должно удалять себя из стека в том случае, если враг был уже уничтожен.

Public class Ant { (...) public var brain:StackFSM; public function Ant(posX:Number, posY:Number) { (...) brain = new StackFSM(); // Начинаем с поиска листка brain.pushState(findLeaf); (...) } /** * Состояние "findLeaf". * Заставляет муравья искать листья. */ public function findLeaf() :void { // Перемещает муравья к листу. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this) <= 10) { //Муравей только что подобрал листок, время // возвращаться домой! brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "findLeaf", что означает, // что состояние "findLeaf" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "goHome", что означает, // что состояние "goHome" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) { // Нет, уже далеко. Пора возвращаться к поискам листочков. brain.popState(); } } (...) }

Вывод

Конечные автоматы, безусловно, полезны для реализации логики искусственного интеллекта в играх. Они могут быть легко представлены в виде графа, что позволяет разработчику увидеть все возможные варианты.

Реализация конечного автомата с функциями-состояниями является простым, но в то же время мощным методом. Даже более сложные переплетения состояний могут быть реализованы при помощи FSM.