Приветствую, коллеги! Предлагаю Вам окунуться в мир теории формальных языков, в частности, в парадигму конечных автоматов.
Цель данной статьи: познакомить Вас с алгоритмом построения детерминированного конечного автомата из недетерминированного конечного автомата. И сразу куча вопросов: зачем понадобилось данное преобразование, что такое конечный автомат, что такое ДКА и НКА и зачем мне это знать? Начнём с мотивации.
Fail2ban — утилита чрезвычайно полезная во многих случаях. Думаю, многие используют её для того, чтобы в автоматическом режиме блокировать особенно назойливых «посетителей». К сожалению, если входящий поток становится слишком большим, fail2ban теряет все свои полезные свойства, потому что разбор лога безнадёжно отстаёт от реальности.
Вот, например, лог nginx из 100 тысяч строчек fail2ban при самых простых настройках (failregex='^<ADDR>') разбирает порядка 45 секунд:
$ fail2ban-regex nginx.log '^<ADDR>'
Running tests
=============
Use failregex line : ^<ADDR>Читать полностью »Влияние подпрограмм (англ. subroutine) на программирование без преувеличения огромно. Введенные на заре программирования они не теряют своей актуальности и поныне. Без них практическое программирование представить просто невозможно. Хотя с формальной точки зрения они не так уж и нужны, т.к. чистую теорию интересуют больше свойства алгоритма, чем его размеры.
В теории автоматов понятие вложенных автоматов, на базе которых строилась бы практика автоматных подпрограмм (АПП), обсуждается редко. Подобная (вложенная) иерархическая организация автоматов, если и рассматривается, то весьма поверхностно. Одной из причин подобного отношения может служить сложность реализации вложенной иерархии на аппаратном уровне [1, 2].
Программирование более гибко и предоставляет больше возможностей, чем практика проектирования цифровых схем. В этом нам предстоит убедиться, рассматривая далее программную реализацию вложенных автоматов, а следом и концепцию автоматных рекурсивных алгоритмов.
При всех частных проблемах формирования вложенной автоматной модели ее формальное определение не вызывает каких-то проблем. Но, с другой стороны, выбор построения иерархии модели, безусловно, будет оказывать существенное влияние на ее программную реализацию.
Читать полностью »
В предыдущей моей статье, уважаемый Хабр, я только лишь прикоснулся к проблемам познания современного программирования. Последовавшая дискуссия только подтвердила спонтанно возникшие опасения: источником разногласий сразу же стали пресловутые «теоретические основы». То, что их (разногласий) могло бы не быть или они носили бы другой характер основную массу «настоящих» программистов похоже не тревожит. Более того, возможно, особо и не интересует, т.к. у программистов стимулируется в основном один интерес — код, код и только код. Ну, почти «как доктор прописал» [1]…
Затрагивая в своих статья и комментариях тему корутин, я ни сном ни духом не предполагал насколько они в «нонешнем» тренде. Поражали, правда, «минусовки» моих комментов по поводу и без. За что, мол, ребята-программисты? Однако, как мне представляется, все прояснилось после прочтения статьи о только что утвержденном С++20 и перспективах его дальнейшего развития [2]. К моему изумлению, выяснилось, что корутины находятся в первых рядах настоящих и будущих новшеств моего любимого С++ (см. также библиотеку CppCoro).
Ну, скажите, можно ли серьезно и/или спокойно воспринимать чела, который, похоже, возомнил себя невесть кем? Попал, что называется! :(
Читать полностью »
В процессе программирования внутриигровых сущностей возникают ситуации, когда они должны действовать в различных условиях по-разному, что наводит на мысль об использовании состояний.
Но если вы решите применить способ грубого перебора, то код быстро превратится в запутанный хаос со множеством вложенных операторов if-else.
Для изящного решения этой задачи можно воспользоваться шаблоном проектирования «Состояние» (State design pattern). Ему-то мы и посвятим этот туториал!
Из туториала вы:
Примечание: этот туториал предназначен для опытных пользователей; предполагается, что вы уже умеете работать в Unity и обладаете средним уровнем знаний C#. Кроме того, в этом туториале используется Unity 2019.2 и C# 7.
Привет! Представляю вашему вниманию перевод статьи «FORMALLY SPECIFYING UIS» автора Hillel Wayne.
Относительно недавно я наткнулся на статью про Инженерные методы в разработке ПО, где vasil-sd рассказал про формальную валидацию спецификаций к создаваемым программным продуктам. В качестве инструментария был использован Alloy. Одним из основных лейтмотивов в комментариях был — разобрать статью в контексте какого-нибудь современного веб проекта, потому что дорогодолгосложно использовать формальные методы там, где все делают быстродешево. Так как автор ссылался на блог Hillel Wayne, где такие примеры были, я решил перевести что-то из его статей в качестве дополнения к основному тексту vasil-sd
Предупреждение:
Первым этапом разработки моей игры стала разработка RTS-движка. Я планирую написать серию постов о возникших задачах и их решениях в этом блоге. В этом посте я расскажу как организовал поведения юнитов.
Размышляя с чего начать вообще этот RTS движок, я пришел к выводу, что стоит начать с конкретики и от нее перейти к абстракции. Первой прикладной задачей, пришедшей на ум, был сбор ресурсов, а точнее, добыча дерева.
Читать полностью »
Конечный автомат редко применяется мобильными разработчиками. Хотя большинство знает принципы работы и легко реализует его самостоятельно. В статье разберемся, какие задачи решаются конечным автоматом на примере iOS-приложений. Рассказ носит прикладной характер и посвящен практическим аспектам работы.
Под катом вы найдете дополненную расшифровку выступления Александра Сычева (Brain89) на AppsConf, в котором он поделился вариантами применения конечного автомата при разработке неигровых приложений.
О спикере: Александр Сычев занимается iOS-разработкой восемь лет, за это время участвовал в создании как простых приложений, так и сложных клиентов для социальных сетей и финансового сектора. В данный момент является техлидом в компании Сбербанк.
Читать полностью »
Шутеры от первого лица за долгие годы эволюционировали и стали очень интересной средой для неигровых персонажей: солдаты прячутся за укрытиями, чужие преследуют игрока, а напарники помогают ему в пылу боя. Всё это вписывается в концепцию дизайна современных шутеров: удерживания территории, создания рубежей обороны и сдерживания игрока. В этой статье я на примере перезапуска франшизы DOOM 2016 года расскажу о том, что происходит, когда разработчики отказываются использовать в игре стандартный кодекс поведения.
DOOM построен на философии, известной как "push forward combat" («агрессивный бой»), влияющей на нарратив, дизайн уровней, перемещения игрока и многое другое. Если вкратце, то он является критическим взглядом и реакцией на современные шутеры. В то время как Call of Duty заставляет игрока ползать за укрытиями и снимать врагов издалека, DOOM нарушает эти правила, создавая мощный, быстрый, «спинномозговой» геймплей. Но как это всё устроено, и что предпринимает ИИ, чтобы сделать игровой процесс живым?
Читать полностью »
Модель конечного автомата (finite-state machine, FSM) находит применение в написании кода для самых разных платформ, включая Android. Она позволяет сделать код менее громоздким, неплохо укладывается в парадигму Model-View-Presenter (MVP) и поддаётся несложному тестированию. Разработчик Владислав Кузнецов рассказал на Droid Party, как эта модель помогает в развитии приложения Яндекс.Диск.
— Вначале поговорим по теорию. Думаю, каждый из вас слышал и про MVP, и про стейт-машину, но повторим.Читать полностью »