Publications Hubs Companies Users Comments

Алгоритм устранения пробок для автомобильного интернета

3 min

3.2K

Производители автомобилей вовсю ведут тестирование пиринговых систем связи между автомобилями по WiFi, на которых будет построены сети связи V2V (vehicle-to-vehicle). Подобные сети могут кардинально улучшить ситуацию на дорогах, если автомобили начнут передавать друг другу информацию о загруженности трасс, о пробках на дорогах, о сигналах светофора и т.д. На перекрёстках автомобили могут сверять свои траектории, обмениваясь данными в реальном времени. Создание сети V2V принципиально важно для нормальной работы автопилотов, которые в будущем заменят живых водителей и должны координироваться с другими автомобилями.

Технически сеть V2V можно поднять уже сейчас, но основная проблема — программное обеспечение. Каковы оптимальные алгоритмы и оптимальная скорость транспортных средств в потоке? Как должны координировать своё движение роботы-автомобили, если их на дороге будет большинство? Над одним из аспектов этой проблемы работают учёные из Сеульского университета, которые опубликовали научную работу Dissolution of traffic jam via additional local interactions (PDF). Они создали алгоритм для V2V, который гарантирует очень быстрое устранение пробок на дороге за счёт обмена информацией и мгновенного изменения скоростного режима всех автомобилей перед пробкой и после пробки.

Читать дальше →

+20

uladzimir Sep 25 2012 at 14:14

Теория сложности на простых примерах

5 min

22K

Popular science

From sandbox

Задайтесь вопросом «ГДЕ?». Где находится центр управления движением галактик или поведением циклона? Где та сила, что объединяет атомы в сложные соединения, те в свою очередь — в цепочки белков, и порождает такие устойчивые и сложные явления как биологическая жизнь, разум, социум.

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

приглашаю под кат

+73

exeditor Oct 12 2012 at 01:27

Игра «Жизнь» Конвея в непрерывной среде

1 min

33K

Algorithms*

Немецкий учёный Штефан Рафлер создал интересную модификацию «Жизни» — клеточного автомата, придуманного в 1970 году Джоном Конвеем, в которой вместо дискретной прямоугольной сетки жизнь развивается в непрерывной среде. «Клетки» в ней имеют форму дисков, планеры могут летать в любых направлениях и водить хороводы — получается совершенно завораживающая картина.

Вот слайд-шоу с кратким описанием алгоритма, документ с более глубоким погружением в детали и исходники.

+60

maxcoolmakarov Dec 20 2020 at 22:52

Хеш-функции на основе клеточных автоматов

3 min

4.9K

Cryptography*

From sandbox

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

+13

PatientZero Dec 30 2020 at 11:25

Создание процедурной анимации смерти при помощи автоматов падающего песка

2 min

9.8K

Python*Game development*

Translation

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

Автоматы падающего песка

Автомат падающего песка — это клеточный автомат, симулирующий перемещение песчинок и создание куч песка под действием гравитации.

Правила просты:

Если ячейка под песчинкой пуста, то песчинка движется в пустую ячейку (см. (a)).
Если ячейка под песчинкой заполнена, но свободна ячейка внизу слева или внизу справа, то песчинка движется туда (см. (b)). Если свободны обе, то одна из них выбирается случайным образом.
В остальных случаях песчинка не движется.

Читать дальше →

+65

PatientZero Jan 19 2021 at 09:33

Использование алгоритма Прима для генерации соединённых друг с другом пещер

4 min

13K

Game development*Algorithms*

Translation

Я решил объяснить один из алгоритмов генерации карты, используемых в моей игре In the House of Silence. Главное преимущество этого способа заключается в том, что в отличие от других алгоритмов, он никаким образом не может сгенерировать карту с разделёнными частями.

Генерация идеального лабиринта

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

Для понятности я привёл псевдокод, описывающий алгоритм Прима. Будет довольно просто приспособить его под любой язык программирования.

Читать дальше →

+50

Yoel Oct 20 2021 at 17:23

«Ижора»: клеточный автомат-компьютер

9 min

9.2K

Open source*Entertaining tasksLisp*Algorithms*DIY

Tutorial

From sandbox

Хотелось бы поделиться с читателями Хабра довольно необычной разработкой: настоящим компьютером, сделанном в виде клеточного автомата, действующего по простому правилу Fireworld2 с четырьмя состояниями клеток. Текущая базовая версия компьютера называется "Ижора 1". Еще с 1950-х годов существует такая традиция: давать компьютерам географические названия.

Паттерн, состоящий из более 6 миллионов клеток, содержит 256 килобайт памяти и снабжен монохромным экраном 128x64 пикселей, отражающим состояние экранного раздела ОЗУ, примерно как в ZX Spectrum и других популярных исторических моделях персональных компьютеров. Программы можно писать на ассемблере, компилировать в машинный код, тестировать на эмуляторе и вводить специальной утилитой в сам клеточный автомат. Другая утилита позволяет сохранять текущее состояние компьютера. Для запуска компьютера необходима программа Golly - лучшая на сегодня площадка для подобного рода исследований.

Ассемблер и эмулятор написаны на языке Common Lisp, скрипты для ввода программ в сам клеточный автомат и сохранения его состояния - в Python. Компьютер имеет 32-битную архитектуру и на данный момент в нем все один регистр и одна операция: вычитание с условным переходом в случае отрицательного или нулевого результата (Subleq). Несмотря на примитивность такой модели, давно доказана ее универсальность. Существует даже операционная система Dawn OS, написанная для эмулятора Subleq-процессора.

Итак, суммируем: виртуальный компьютер с экзотической моделью программирования и ресурсами уровня древних ПК 1980-х, исполняющий всего около 10 операций в секунду, требующий современный компьютер с несколькими гигабайтами памяти (рекомендуемый минимум - 8 гигабайт), с эмулятором и ассемблером на Лиспе. Зачем и кому это нужно? Очень краткий ответ: ради хака и ретрокомпьютинга. Ниже - более подробно.

Читать далее:

+40

TLHE Dec 11 2023 at 11:01

Удивительные клеточные автоматы: обратные и расширенные поколения

Easy

7 min

3.2K

Timeweb Cloud corporate blogProgramming*Algorithms*Mathematics*Popular science

Review

👾, Хабр!
Давно не виделись.

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

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

Дополнение поколений является самым популярным, среди всех модификаций стандартной модели, и даже, фактически, оно стало частью правила по умолчанию, наравне с B/S, используясь практически во всех прочих расширениях, хотя использование поколений, конечно, опционально.

Со временем участники сообщества начали предлагать дополнения и к этому варианту конфигурации. На поверхности лежали многие вариации, как ещё возможно изменить или переставить состояния клеток. Одним из них были и обратные поколения, a.k.a. snoitareneG, с которых мы и начнём.

Читать дальше →

+39

PatientZero Oct 31 2017 at 13:50

Реализация «Тетриса» в игре «Жизнь»

39 min

38K

Abnormal programming*Game development*Algorithms*Compilers*

Translation

То, что начиналось как приключение, закончилось одиссеей.

Задача по созданию тетрис-процессора размером 2 940 928 x 10 295 296

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

PhiNotPi
El'endia Starman
K Zhang
Muddyfish
Kritixi Lithos
Mego
Quartata

Также мы хотим поблагодарить 7H3_H4CK3R, Conor O'Brien и многих других пользователей, вложивших свои труд в решение этой задачи.

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

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

Читать дальше →

+166

Nick_mentat Nov 11 2017 at 02:19

Симулятор машинок Брайтенберга

9 min

16K

Programming*Algorithms*C#*Robotics development*

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

Итак, что же это такое?

(Осторожно, в статье чрезвычайно много картинок и анимаций!)

Читать дальше →

+39

PatientZero May 14 2018 at 11:29

Процедурная генерация подземелий в roguelike

31 min

45K

Game development*

Translation

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

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

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

Конечно же, преимущества процедурных карт бессмысленны без большой вариативности механик и контента — однообразный hack-and-slash здесь не подойдёт. Поэтому все roguelike, выдержавшие испытание временем, имеют глубокий геймплей.

Этот пост является результатом моей работы над генерацией карт для Cogmind.

Читать дальше →

+41

OsipovRoman Oct 10 2019 at 18:11

30.000$ за решение задач о Правиле 30 для клеточных автоматов — конкурс от Стивена Вольфрама

43 min

18K

Wolfram Research corporate blogEntertaining tasksProgramming*Algorithms*Mathematics*

Translation

Оригинал перевода в моём блоге

Прямая трансляция Стивена Вольфрама о конкурсе (на английском)

Сайт конкурса

Поясним для читателей, что означает «Правило 30» — это элементарный клеточный автомат (см. Wiki), состояние которого (правило построения нового уровня ячеек на основе старого) в двоичной системе счисления задается как 0-0-0-1-1-1-1-0, что можно интерпретировать как 30 в десятичной системе счисления.

Итак, с чего все началось? — «Правило 30»

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

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

Итак, сегодня я предлагаю соискателям 30000 долларов США в качестве общей суммы призов за ответы на три основных вопроса о Правиле 30.

Правило 30 чрезвычайно просто:

Существует последовательность строк черных и белых клеток (ячеек) и, учитывая конкретную строку чёрно-белых ячеек, определяются цвета ячеек в строке ниже, рассматривая каждую ячейку в отдельности и ее смежных соседних ячеек, затем к ним применяется следующее простое правило подстановки, а именно:

Код
RulePlot[CellularAutomaton[30]]

[Посмотрите ролик, в котором за пару минут рассказывается суть клеточных автоматов и Правила 30 — примечание переводчика]

+36

PatientZero Oct 16 2019 at 10:20

Процедурные паттерны, которые можно использовать с тайловыми картами

15 min

10K

Game development*Unity3D*Game design*

Translation

Процедурная генерация используется для повышения вариабельности игр. Среди известных проектов можно упомянуть Minecraft, Enter the Gungeon и Descenders. В этом посте я объясню некоторые из алгоритмов, которые можно применять при работе с системой Tilemap, появившейся как 2D-функция в Unity 2017.2, и с RuleTile.

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

О чём этот пост?

Мы рассмотрим одни из самых распространённых способов создания процедурных миров, а также пару вариаций, созданных мной. Вот пример того, что вы сможете создавать после прочтения статьи. Три алгоритм работают вместе, создавая карту при помощи Tilemap и RuleTile:

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

Читать дальше →

+15

Geotyper Jun 1 2019 at 20:55

Жизнь на частицах 3D

4 min

9.6K

Programming*Game development*Algorithms*Mathematics*Concurrent computing*

ПривеТ! Решил поделиться с читателями своими небольшими экспериментами с системами частиц в трехмерном пространстве. За основу взял публикацию на Хабре об экспериментах с частицами в 2D пространстве.

+49

xcont Sep 26 2019 at 04:38

Эволюционирующие клеточные автоматы

22 min

37K

Abnormal programming*JavaScript*Algorithms*Mathematics*Machine learning*

Соединим клеточные автоматы с генетическим алгоритмом и посмотрим, что из этого получится.

В статье присутствуют Gif (трафик!) и контрастные картинки. У эпилептиков может случиться эпилептический припадок.

Читать дальше →

+128

PatientZero Jul 24 2019 at 17:27

Генерация подземелий и пещер для моей игры

4 min

25K

Game development*Algorithms*Game design*

Translation

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

Разбиение пространства

Существует множество способов генерации комнат для подземелья (случайное размещение, генерация на основе агентов, с использованием separation steering behavior или физического движка, и т.д.). Но мой любимый метод — это разбиение пространства, потому что оно легко контролируется и расширяется.

Способов разбиения пространства тоже очень много: разделение на сетки, двоичное разбиение пространства, разбиение пространства деревом квадрантов, диаграммы Вороного и т.д. Я решил использовать двоичное разбиение пространства, потому что оно хорошо подходит для генерации прямоугольных комнат. Этот метод получил популярность благодаря статье на RogueBasin.

Единственная сложность этого алгоритма — выбор позиции разделения. Если мы не наложим ограничение на позицию разделения, то будем получать странные разбиения пространства:

Такого поведения можно избежать несколькими способами. Один из них — ограничить позицию разделения двумя соотношениями длин сторон, например, в интервале от 30% до 70% или от 40% до 60%. Другой способ — использовать вместо равномерного распределения нормальное или биномиальное, благодаря этому повысится вероятность разделения по центру стороны, а не по краям. Эти способы устраняют проблему, но сложно понять, как конкретно параметры влияют на окончательный результат.

Читать дальше →

+63

aureliano_b Jun 16 2021 at 09:09

Я подарю тебе маленькую вселенную

10 min

8.9K

Open source*Programming microcontrollers*DIYElectronics for beginners

CyberHeart

Эстетика навесного монтажа обладает особой притягательной силой. Есть в этом что-то одновременно и от скульптуры, и от handcraft ювелирки. Вот и у меня давно "чесались руки" собрать какой-нибудь незамысловатый но симпатичный электронный гаджетик в таком стиле. И тут же хочется добавить: "… так что, как только я сложил вместе рамку и сердечко, мое воображение немедленно дорисовало все остальные компоненты и мне ничего не оставалось, кроме как соединить их воедино". Но нет. В действительности затея эта пылилась у меня в столе почти десяток лет, пока не дождалась неожиданного в своей простоте "инсайта", вдохновившего меня доделать некогда задуманное.

Итак, все началось почти декаду назад...

+22

goodok Nov 1 2010 at 21:38

«Живые графы» — выращивание графов на клеточных автоматах с примерами на Silverlight

15 min

15K

Algorithms*

From sandbox

Введение

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

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

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

живой граф

Такой предельно упрощённой и наглядной моделью могут оказаться «Живые графы» — конечные автоматы на графе, каждый узел которого содержит некое исполняющее устройство (автомат) с конечным числом состояний и с набором примитивных правил, управляющих созданием или изменением новых связей между узлами.

Читать дальше →

+76

leshabirukov Feb 4 2015 at 00:44

Не-фон неймановский компьютер на базе комбинаторной логики

8 min

26K

Concurrent computing*Functional Programming*

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

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

Сейчас готов ранний прототип, существующий как в виде потактового программного симулятора, так и в виде реализации на ПЛИС.

Читать дальше →

+43

codeholic Mar 23 2015 at 20:24

Иглобрюх и дары «Жизни»

10 min

37K

Entertaining tasksProgramming*Mathematics*

From sandbox

Многие программисты, по крайней мере моего поколения, знают игру «Жизнь», правила которой были предложены британским математиком Джоном Конвеем (John Conway) в 1970 году. Но что знают немногие, так это то, что она до сих пор активно развивается и радует новыми открытиями. Историей одного из таких открытий я хочу поделиться в этой статье.

Читать дальше →

+69

2 3