RS Game Maker Community
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

 
Расширенный поиск
  Главная  Форум   Вики Блоги FAQ Игры Статьи Примеры Войти Регистрация  
Вики
Все желающие приглашаются редактировать вики. Можете писать о своих (или чужих) играх, размещать туториалы, постить статьи - главное навесить категорию.
Страниц: 1   Вниз
  Печать  
Конечные автоматы
0 Пользователей и 1 Гость смотрят эту тему.
input.txt
Не очень
Активный участник
**

Репутация: 18
Online Online

Сообщений: 132


12.8 Gb

12 Октябрь 2015 в 07:53
Конечные автоматы
   Если вы сделали или пытались сделать хотя бы одну игру, то наверняка сталкивались с конечными автоматами. Почти уверен, что никто из вас этого не заметил. Однако создавая кнопку, персонажа, управляемого игроком, или простую дверь, приходится неявно реализовывать автомат для данного объекта. Интересно, что для этого даже не обязательно знать, что это такое.

    Немного теории. В сети полно статей по этой теме, так что не буду здесь подробно всё описывать. Впрочем, описывать особенно и нечего. Итак, давайте разберёмся, что такое конечный автомат, а главное, зачем он нам понадобился.
Пример 1 Пусть у нас в игре есть Красная Бочка®, которая будет взрываться от попадания пули. Простая функция это объект, который на входной сигнал (пуля) будет реагировать выходным сигналом (взрыв). В результате получим бешеную бочку, взрывающуюся от каждой пули, так как функция это просто сопоставление вход-выход и памяти не имеет. А потому не может запомнить, что бочка, вообще-то, уже взорвана.
Тут мы как раз подходим к конечному автомату, который характеризуется способностью учитывать прошлые события.
Пример 2 Рассмотрим ту же бочку, но с двумя состояниями: "целая" и "взорванная". Изначально бочка целая. Теперь опишем, как она будет реагировать на пули:
  • Пуля попадает в целую бочку. Бочка реагирует сигналом "взрыв" и переходит в состояние "взорванная"
  • Пуля попадает во взорванную бочку. Бочка не реагирует :)


* barrel_sm.png (8.17 Кб. 353x176 - просмотрено 522 раз.)


Таким образом, автомат определяется следующим:
  • начальным состоянием
  • набором возможных входных сигналов
  • набором возможных выходных сигналов
  • таблицей переходов
Таблица переходов является главной частью конечного автомата. Она сопоставляет выходной сигнал каждой паре "текущее состояние + входной сигнал" (см. список из примера 2).

На этом с теорией заканчиваю, а все, кто заинтересовался направляются на Википедию и в Гугл.

Эта статья была написана с целью представить реализацию конечных автоматов в GameMaker. Этот набор скриптов предназначен для простого описания объектов с множеством состояний. Некоторые могут не согласиться: "Я всю жизнь писал без этих ваших автоматов, и всё отлично работает". Не собираюсь никого заставлять, но при создании сколько-нибудь сложного объекта приходится писать большой switch-case или множество if-ов (в том числе вложенных), а затем мучительно их отлаживать. Предлагаемый подход должен заметно упростить задачу.

Описание функций
fsm_init_globals()
Нужно вызвать один раз в начале работы. Выполняет подготовку к использованию других функций.


fsm_create(state)
Создаёт новый конечный автомат (далее КА). Возвращает индекс нового КА. state - начальное состояние. Может быть строкой или числом.


fsm_destroy(id)
Удаляет КА с индексом id.


fsm_add_rule(id, state, in, out, new_state)
Используется для заполнения таблицы переходов. id - индекс КА, state - состояние, in - входной сигнал, out - выходной сигнал, new_state - новое состояние. Т.е. если КА находится в состоянии state и принимает сигнал in, то переходит в состояние new_state, при этом выдавая сигнал out.


fsm_add_default_rule(id, state, out, new_state)
Эта и следующая функция сокращают описание сложных объектов. Например, если есть КА с М состояниями, принимающий К сигналов, то таблица переходов будет содержать М*К строк. Чтобы описание подобного КА не превращало код в wall-of-text можно ввести правила по-умолчанию. Т.е. если КА находится в состоянии state и принимает любой сигнал, кроме тех, для которых задано явное правило, то переходит в состояние new_state, при этом выдавая сигнал out.


fsm_add_default_const_rule(id, state, out)
То же, что и fsm_add_default_rule(), но КА остаётся в том же состоянии.


fsm_delete_rule(id, state, in)
Удаляет правило из таблицы переходов.


fsm_get_current_state(id)
Возвращает текущее состояние (может быть строкой или числом)


fsm_set_state(id, state)
Изменяет состояние КА, при этом выходной сигнал не изменяется. state - новое состояние (строка или число).


fsm_get_last_output(id)
Возвращает последний выходной сигнал (может быть строкой или числом).


fsm_send_input(id, in)
Передаёт сигнал в КА. При этом может измениться его состояние. Возвращает сигнал, выданный КА при получении сигнала in.


fsm_exists(id)
Возвращает true, если КА с индексом id существует.


fsm_delete_default_rule(id, state)
Удаляет правило по-умолчанию для данного состояния


fsm_write(id)
Сохраняет автомат в строку.


fsm_read(id, string)
Загружает авомат из строки


fsm_clear(id)
Очищает таблицу переходов (удаляе все правила).


fsm_copy(dest, source)
Копирует source в dest.


Последняя версия (1.1):
* fsm_1.1.zip (65.87 Кб - загружено 94 раз.)

История версий

1.1
  • Новые функции
    • fsm_write(), fsm_read() для сохранения в строку и загрузки обратно. Работает аналогично стандартным ds_XXX_write() и ds_XXX_read()
    • fsm_copy(). Также аналогично ds_XXX_copy()
    • fsm_delete_default_rule()
    • fsm_clear() очищает таблицу переходов.

1.0
  • Релиз


Примеры использования (см. во вложениях):
Простой пример
Обычная кнопка
Сигналы:

  • Курсор наведён (enter)
  • Курсор убран (leave)
  • Левая кнопка нажата (pressed)
  • Левая кнопка отпущена (released)

Состояния:
  • Начальное (normal)
  • Выделена (hover)
  • Нажата и выделена (down_in)
  • Нажата (down_out)


* button_sm.png (13.73 Кб. 438x289 - просмотрено 541 раз.)

На диаграмме показаны переходы между состояниями.
Сложный пример
Сложная анимация персонажа.
Это тот случай, когда текстовое описание выглядит менее запутано, чем графическое. Я даже специально нарисовал диграмму для сравнения. Чтобы разобраться, что здесь происходит, лучше посмотреть код. Там есть комментарии, так что всё должно быть понятно.
Хотя есть один грязный хак с возвращаемым значением: при переходе в новое состояние выдаётся 1, если персонаж будет двигаться влево; -1, если вправо. Если состояние не изменилось возвращается 0. Потом проверяем значение: если не 0, то меняем спрайт и направление.

* stick_animation_sm2.png (200.87 Кб. 2390x1179 - просмотрено 557 раз.)

Прикреплённые файлы Графические миниатюры:


Другие файлы:

* state_machines.zip (166.79 Кб - загружено 87 раз.)

* fsm_1.1.zip (65.87 Кб - загружено 94 раз.)
Последнее редактирование: 18 Октябрь 2015 в 07:19 от input.txt
 
Огион
Завсегдатай
****

Репутация: 133
Offline Offline

Сообщений: 984


Ответ № 1 13 Октябрь 2015 в 23:15
Конечный автомат — удобная штука, но традиционные реализации слишком громоздки. Поэтому в своём последнем проекте я применяю суперпростой подход, описанный на Хабре. KISS во все поля.

Состояние объекта — это просто переменная state, различным состояниям соответствуют константы типа HERO_STATE_ONGROUND, HERO_STATE_JUMPING. В событии шага есть большой switch, прописывающий поведение объекта в различных состояниях, включая переходы в другие состояния. При этом сам объект свою переменную state не трогает: когда нужно сделать переход, он вызывает метод, который проверяет корректность перехода, выполняет логику выхода из старого состояния и логику входа в новое состояние и уже тогда меняет значение state.

Поскольку в GM нет методов (функций, принадлежащих объекту), приходится использовать их суррогат — скрипты особого формата. Это что-то вроде БЭМа — костыля для веба, который Яндекс придумал и успешно применяет.
/*
object__method(instid)
*/
var instid;
instid = argument0;

with (instid) {
    /*
    Логика метода
    */
}
Можно ещё проверять, является ли id экземпляром object (или его наследника), но я обхожусь без этого.

Итак, чтобы сменить состояние экземпляра o_hero с HERO_STATE_ONGROUND на HERO_STATE_JUMPING, надо вызвать метод state_jumping, который выглядит так:
/*
hero__state_jumping(instid)
*/
var instid;
instid = argument0;

with (instid) {
    _hero__set_state(HERO_STATE_JUMPING);
    /*
    Логика входа в состояние HERO_STATE_JUMPING
    */
}
Можно ещё проверять, корректен ли переход, но я обхожусь и без этого.
Внутренний метод _hero__set_state выглядит следующим образом:
/*
_hero__set_state(stateto)
*/
var stateto;
stateto = argument0;

if (state == stateto) {
    exit;
}

switch (state) {
    case HERO_STATE_ONGROUND:
        /*
        Логика выхода из состояния HERO_STATE_ONGROUND
        */
        break;
    case HERO_STATE_JUMPING:
        /*
        Логика выхода из состояния HERO_STATE_JUMPING
        */
        break;
}
state = stateto;
По идее, _hero__set_state, как любой «метод», должен принимать id экземпляра и выполнять логику над ним. Но поскольку это внутренняя функция, которую мы вызываем только внутри конструкции with, я обхожусь и без этого тоже.
Последнее редактирование: 16 Май 2017 в 13:50 от Огион
input.txt
Не очень
Активный участник
**

Репутация: 18
Online Online

Сообщений: 132


12.8 Gb

Ответ № 2 15 Октябрь 2015 в 04:17
Т.е. при получении сигнала выполняется любой удобный код, который переводит автомат в новое состояние (и может делать что-то ещё), вместо того, чтобы выбирать это состояние по таблице переходов? Или предлагается отказаться от сигналов и дёргать "методы" state_X() из самого объекта?

Моя идея была посылать сообщения в чёрный ящик, который что-то там решает, меняет состояние и посылает ответ. Ущербность такого подхода: куча дублирующихся состояний (типа run_left/run_right), т.к. переходы безусловные. Плюсы: вся логика переходов складывается в одно место, и может быть изменена в любое время без анальной головной боли.

Возможен синтез двух вариантов: объект посылает сигналы в автомат ("нажата кнопка влево", "потерян контакт с полом" и т.д.). Автомат вызывает state_X() и занимается прочей полезной работой. Объект наслаждается результатом.

Кстати, судя по количеству и содержанию комментариев на Хабре, не только я не понял ту идею.
Lagevae
Норм
Старожил
******

Репутация: 194
Offline Offline

Награды:
За перевод справки Game Maker 8Легенда сайта
Сообщений: 2 703

Ответ № 3 15 Октябрь 2015 в 05:17
Хм, не могу пройти мимо не написав, что весьма и весьма полезный тред тут открылся.
Помню, как-то давно (пару-тройку лет назад) Райдо открывал тред про анимацию, но никто так и не отписался, а я так ждал, что туда зайдёт кто-нибудь умный и раскидает всё как надо. Время шло, я городил деревья из if'ов, это всё глючило и не работало, пока я надеялся что когда-нибудь мне всё-таки как-нибудь случайно удастся узнать как же это делается.
И вот, пару недель назад Огион упомянул, отвечая кому-то на вопрос, что для этих целей используется конечный автомат. Я тогда так чисто в голове отметил, что окей, зацепка есть, а тут вот уже и целый тред открылся. Честно - понятно пока мало, но концепция в целом вроде прозрачна, и стало ясно куда копать.
Спасибо, пацаны. Полезно.

therein lies the beauty
input.txt
Не очень
Активный участник
**

Репутация: 18
Online Online

Сообщений: 132


12.8 Gb

Ответ № 4 18 Октябрь 2015 в 07:12
Вышло небольшое дополнение. Подробности в шапке (история версий).
Последнее редактирование: 18 Октябрь 2015 в 07:20 от input.txt
Страниц: 1   Вверх
  Печать  
 
Перейти в:  

RSGMC (gmakers.ru) © 2007—2018
Счётчик–@Mail.ru