Рубрика «конечные автоматы»

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

Под катом вы найдете дополненную расшифровку выступления Александра Сычева (Brain89) на AppsConf, в котором он поделился вариантами применения конечного автомата при разработке неигровых приложений.

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

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

Кибердемоны: искусственный интеллект DOOM 2016 - 1

DOOM построен на философии, известной как "push forward combat" («агрессивный бой»), влияющей на нарратив, дизайн уровней, перемещения игрока и многое другое. Если вкратце, то он является критическим взглядом и реакцией на современные шутеры. В то время как Call of Duty заставляет игрока ползать за укрытиями и снимать врагов издалека, DOOM нарушает эти правила, создавая мощный, быстрый, «спинномозговой» геймплей. Но как это всё устроено, и что предпринимает ИИ, чтобы сделать игровой процесс живым?
Читать полностью »

Модель конечного автомата (finite-state machine, FSM) находит применение в написании кода для самых разных платформ, включая Android. Она позволяет сделать код менее громоздким, неплохо укладывается в парадигму Model-View-Presenter (MVP) и поддаётся несложному тестированию. Разработчик Владислав Кузнецов рассказал на Droid Party, как эта модель помогает в развитии приложения Яндекс.Диск.

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

Спойлер

Cкажу cразу, что не буду объяснять слишком формально.

Конечные автоматы (finite-state machine)

Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами в обмен на простоту понимания, удобство рас­суждения и легкость программной или аппаратной реализации.

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

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

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

Пример 1

  • По горизонтали вверху находятся возможные входные символы.
  • По вертикали слева находятся текущие возможные состояния.

image

Здесь видно, что из состояния 0 в состояние 1 можно попасть только, если у нас будет входной символ 'a', из состояния 1 в состояние 2, если символ 'b'.

Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.

Стартовое состояние — состояние откуда КА начинает свою работу.

Заключительное состояние — множество состояний в которых автомат принимает определенную цепочку символов, в ином случае отвергает.
Читать полностью »

image

Введение

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

image

«Чувства» в разработке игр — это полезная метафора для понимания, создания и обсуждения той части ИИ, которая занимается сбором информации о важных объектах симулируемой среды игры. Неигровыми персонажами в реалистичном трёхмерном пространстве обычно бывают люди, животные или другие создания со зрением и слухом, поэтому такая метафора очень удобна.

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

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

В этой статье описывается подход к дизайну и реализации высокоточной сенсорной системы для ИИ в игре от первого лица с упором на стелс. Описанные здесь техники взяты из опыта разработки ИИ для Thief: The Dark Project, а также из ознакомления с кодом Half-Life. В первой части статьи изложены базовые концепции чувств ИИ на мотивирующем примере Half-Life. Во второй части излагаются более строгие требования к сенсорным системам в дизайне стелс-игр и описывается система, созданная для Thief.
Читать полностью »

hh2e_lecture_slides_banner_3

Господа! Сегодня на 1 сентября, в День Знаний, группа из украинских преподавателей вузов, их аспирантов, а также российских инженеров, решили, по согласованию с британскими издателями Elsevier через компанию Imagination Technologies, сделать небольшой подарок всем учителям компьютерной архитектуры и цифровой схемотехники, особенно тем, которые используют популярный учебник Дэвида Харриса и Сары Харрис.

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

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

Итого, вырезка из слайдов, чтобы вы поняли, о чем идет речь:
Читать полностью »

Введение

SimInTech является средой для создания математических моделей любых систем, уравнение динамики которых можно представить в виде входо-выходных соотношений (представление DataFlow). Для реализации подхода конечных автоматов в среде SimInTech существовал блок условного выполнения субмодели, который обеспечивал остановку и запуск моделирования по условию, приходящему извне. Такой подход обеспечивает возможность разделить общую модель на состояния и в каждый момент времени рассчитывать только те субмодели, условия выполнения которых установлены в true. Однако, такая реализация автоматного подхода не очень удобна, с точки зрения наглядности, и требовала дополнительной настройки параметров системы.

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

В данной статье показан пример использования элементов библиотеки «Конечные автоматы» для создания системы управления.
Читать полностью »

Господа! Только что на сайте Imagination Technologies вышло исправленное издание бесплатного учебника на русском языке «Цифровая схемотехника и архитектура компьютера» Дэвида Харриса и Сары Харрис (кстати, они не супруги и вообще не родственники – просто так совпало). Предыдущее издание этого учебника вышло год назад, пост о нем собрал 145,000 просмотров на Хабре, количество скачиваний с британского сайта вызвало у его британских админов подозрение, что их атакуют русские хакеры, а впоследствие команду переводчиков лично благодарили за учебник преподаватели МФТИ, МВТУ им. Баумана, харьковского ХНУРЭ и других университетов.

silicon_russia_ad_selected_160730_174932

Книжка содержит «введение во все», доступное способному школьнику или младшему студенту, который после ее прочтения может спроектировать, написать на SystemVerilog или VHDL и реализовать на ПЛИС несложный, но при этом совершенно настоящий конвейерный процессор. Книга написана живым языком и для введения концепций, например конечных автоматов, использует примеры типа:

Новая редакция популярного бесплатного учебника электроники, архитектуры компьютера и низкоуровневого программирования - 2
Читать полностью »

Привет!

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

Со-основатель, технический директор и главный учитель нашего образовательного проекта Хекслет Кирилл Мокевнин рассказывает про сложность программирования интерфейсов и каким образом можно совладать со сложностью если вы знакомы с одной базовой концепцией информатики. Заодно расскажет и покажет идеальный JS-фреймворк для программирования UI.

Читать полностью »