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

Kenbak-1: самая первая серийная персоналка - 1

Считается, что эпоха персоналок наступила в 1974 году, когда компания MITS наладила массовое производство знаменитого Altair 8800, положившего начало буму «домашних» компьютеров. До этого ЭВМ были слишком громоздкими и чересчур дорогими для простого обывателя. Однако ещё в 1971 году серийно выпускался компьютер, который мог приобрести обычный человек, чтобы изучить азы программирования. Правда, эта машина не имела ни монитора, ни клавиатуры, ни привычного современным пользователям интерфейса — даже командной строки…
Читать полностью »

image

Goldeneye 007 — одна из самых важных игр в истории. Она определила дальнейшее развитие целого поколения консольных игр и проложила шутерам от первого лица дорогу на рынок консолей. Перенесёмся более чем на 20 лет назад, чтобы узнать, как одной из самых популярных на Nintendo 64 игр удалось реализовать ИИ врагов и друзей, у которого можно чему-то научиться даже сегодня.

Об игре

После своего выпуска в 1997 году GoldenEye 007 не только определил судьбу поколения, но и превзошёл все ожидания. В эту игру мало верила сама Rare, Nintendo и даже владелица прав на франшизу Бонда — компания MGM. Выпущенная спустя два года после выхода фильма и спустя год после появления консоли на рынке, она казалась обречённой на провал, но стала третьей по продажам (восемь миллионов копий) за весь срок жизни платформы, уступив только Super Mario 64 и Mario Kart 64. Не говоря уже о том, что в 1998 году она заработала компании Rare награду BAFTA и звание разработчика года.

Искусственный интеллект Goldeneye 007 - 2

Эта игра оставила нам огромное наследие: она задала стандарты того, что нужно ожидать от следующих поколений шутеров от первого лица, особенно в поведении ИИ: персонажи с паттернами патрулирования, враги, запрашивающие подкрепление, убегающие в страхе мирные жители, плавная навигация и поиск пути, богатый набор анимаций, динамические свойства, возникающие в процессе игры, и многое другое. Она не только задала стандарты поколения, но и повлияла на игры, которые её превзошли — Half Life, Crysis, Far Cry и многие другие.
Читать полностью »

Обратная разработка первоапрельской «Змейки» от Google - 1

Возможно, кто-то из вас заметил, что Google на 1 апреля добавила в приложение Google Maps для Android и iOS интерактивную игру «Змейка».

Специалисты Check Point обычно заняты исследованием последних киберугроз, но здесь очень увлеклись этой игрой, правда, сильно расстраивались из-за проигрышей… поэтому возникла логичная мысль: почему бы её не взломать!
Читать полностью »

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

image

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

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

Тест FizzBuzz — написать программку, которая выдаёт числа от 1 до 100, где кратные трём заменяются словом “Fizz”, кратные пяти — словом “Buzz”, а кратные пятнадцати — “FizzBuzz”. Поскольку такая программа реализуется в нескольких строчках кода, то её часто задают на собеседованиях чтобы отсеять тех, кто вообще не умеет программировать.

Реализация FizzBuzz на FPGA - 1
Плата Mojo FPGA, подключенная к порту serial-to-USB. Большой чип на плате — это Spartan 6 FPGA

Реализация FizzBuzz в цифровой логике, а не в коде, довольно бессмысленна, но показалась мне хорошим примером для обучения.1 Для этого проекта я использовал простую плату разработки Mojo V3 FPGA для начинающих. На ней установлен FPGA семейства Xilinx Spartan 6. Это один из самых маленьких FPGA, но у него 9000 логических ячеек и 11 000 триггеров — так что малыш на многое способен.
Читать полностью »

image

Введение

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

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

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

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

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

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

Задача про обезьян и бесконечность - 1

Потрясающий факт, но еще интереснее попытаться понять, сколько же времени ей понадобится для набора конкретного текста. А вам очевидно, что строку «abc» набирать гораздо быстрее чем «aaa»? Решению этой задачи и посвящен этот пост. Попутно объясняется префикс функция и ее свойства.

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

В ноябре прошлого (уже) года, Hola объявила конкурс по программированию почтовых фильтров на js, и недавно опубликовала его результаты.

Я разделил второе место с Ильей Макаровым, и сейчас я расскажу…

Как это было

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

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


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js