Предыстория гейм-девелоперского хобби (знакомство с программированием):

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

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

И тут в голову пришла гениальная мысль — хочу простейшую игру, значит надо искать мануал по созданию такой игры — змейка, арканоид. Нашел все что нужно на YouTube. И тут началось. Так вышло, что мои первые мануалы были по программе для разработки 2D игр — GameMaker.

Моя первая змейка по мануалу уже вскоре была изучена до дыр, где я всячески ее модифицировал. Далее аппетит разыгрался и я не мог остановиться: арканоид, тетрис, лото, теннис, гонки, платформеры, 2D физика, шахматы (по сети), работа с частицами, прочие скрипты для бытовых задач.

Со всем этим в голове уже уложились основы: переменные, массивы, структуры данных, условия, циклы и т.д.

Сильный аппетит к кодингу

Далее, сам в шоке от себя и аппетитов, начал мечтать реализовать что-то любимое из досовских игр (Civilization), а так же Sega (Dune: The Battle For Arrakis), где нужно всего лишь достать исходники для реализации.

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

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

Далее пошли: курсор игры, юниты и механика передвижения, дороги, параметры ячеек (горы, степь и т.п.), первостепенные и основные игровые менюшки, города на карте и механика городов (и визуальный обзор города).

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

Я начал заваливаться. Теперь я не знаю, как довести до ума работу. Намерение и сила воли для проекта начали иссякать. Ниже будут скриншоты наработок.

Любимая игра

Но совсем скоро я нашел новое развлечение в кодинге: Dune 2 The Battle For Arrakis. Любимая игра на Sega. К удивлению на тот момент у нее было очень много фан-групп и актуальных модификаций, в большем числе во вконтактике, из-за чего очень быстро получилось достать исходники.

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

С любовью вспоминая времяпровождение в компьютерных залах за Warcraft 3 с его кастомными картами, в жанрах: Tower Defence, Hero Defence и т.п., я очень быстро влюбился в идею наложить жанр Tower Defence на мою будущую игру: Dune - TowerDefence с недолгими уровнями-сессиями и в небольшом окне.

Вскоре я начал реинжиниринг анимаций с оригинала (эмулятор SEGA GENS на ПК), а в процессе подготовки анимаций движений неожиданно встал вопрос: как будем двигать юнитов!? Краем глаза я уже видел в движке, что есть вшитые функции поиска пути, но они казались сложными, и я боялся их как огня.

Пришлось с этим разбираться, что получалось весьма успешно. Параллельно пилился интерфейс игры, менюшек, и уже вырисовывалась цельная картинка игрового процесса. Спустя три месяца мне удалось собрать свою первую большую и законченную игру в жанре Tower Defence. Сначала было 5 уровней-сессий по 10-20 минут, три уровня сложности + редактор своей игры. Со временем добавил обнову до 10 уровней.

Запись геймлея на «YouTube»:

Ссылка на exe-файл в «GoogleDrive»

Dune (прочие скриншоты, справа настройка режима своей игры, где можно настраивать баланс и рисовать свою карту)

Алгоритм поиска пути и крах ожиданий

Алгоритм поиска пути предназначен для построения маршрута между двумя точками в дискретном пространстве (в программировании игр это в т.ч. координатная сетка).

Статья об алгоритме (Рязанцев Д.Д.,Жиляк Н.А.):* кафедра вычислительных методов и программирования, Кафедра информационных технологий автоматизированных систем, Белорусский государственный университет информатики и радиоэлектороники: Алгоритм поиска пути в игровом приложении. Алгоритм Дейкстры

Еще стати на хабре об алгоритме: Простое объяснение алгоритмов поиска пути и A* Алгоритмы поиска пути: Алгоритм дейкстры и А*

На сегодняшний день есть прекрасный сайт с тест-визуализацией разных алгоритмов поиска пути

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

Теперь я позарился на Dune: The Battle For Arrakis в обычном жанре стратегии, со 100% повторением оригинала, но с адаптацией под современность: полный экран, управление мышью и т.п.

Очень быстро я накропал редактор, интерфейсы: карта мира, мини карта и т.п., и принялся к тестам алгоритма поиска пути.

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

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

По памяти, что пробовал в разных комбинациях: трассировка, волновой алгоритм, HPA, A*, Dijkstra, JPS (Jump Point Search - был реализован в игре StarCaft II).

Надежда угасала. Пришлось познакомиться с С++, чтобы написать стороннюю dll-библиотеку для подхвата GameMaker, что ускоряло работу алгоритма.

Здесь я в оконцовке своего проигрыша над задачей молился на JPS (Jump Point Search), который сильно хвалили за быстродействие, и я думал тут будет выигрыш во всем, но я не смог найти нормальных исходников, в отличие от остальных, и пытался воспроизвести хоть что-то по крупицам, а в итоге не смог понять в т.ч. сердцевину в работе алгоритма — бинарную кучу.

На этом месте мои силы иссякли. Я устал перебирать алгоритмы и в итоге переключился на разработку прог на C++, чем я безумно увлечен и по сей день.

Здесь на хабре есть статья по Jump Point Search, но я ее в то время не осилил: Алгоритм поиска пути Jump Point Search

Огромное спасибо инди-разработчику за его статью алгоритма поиска пути, очень помог в свое время, ответив мне в теме (визуализация на картинках ниже): Статья “Поиск пути” — обсуждение на форуме astralax

Полная статья инди-разработчика: Astralax Magic Particles

Dune. GameMaker. Визуализация поиска пути — красные квадраты это захват клетки шага перед собой, а красная линия это предполагаемый маршрут. Используется нативный алгоритм поиска пути.

GameMaker. Алгоритм взят у astralax.ru. Проработка поиска пути (мой конспект в то время)

GameMaker. Алгоритм взят у astralax.ru. Анимация. Визуализация HPA-алгоритма, чтобы лучше представлять его работу. Общая сетка игрового поля делится на подсетки (районы) для оптимизации. Путь из точки А (красная) в точку B (зеленая), обсчет идет задом наперед.

GameMaker. Алгоритм взят у astralax.ru. Проработка поиска пути (тесты лабиринтов). HPA-алгоритм.

GameMaker. Алгоритм взят у astralax.ru. Проработка поиска пути (тесты перехода нескольких юнитов, из левого-нижнего края в правый-нижний, где случился баг — часть юнитов не перешли)

Еще одна визуализация HPA из гугл-картинок

Представление квантовых штук через алгоритм поиска пути:

Всегда интересовал этот квантовый мир, тот элемент непонятности, с которым к нему относятся. В СМИ часто мелькали новости, то про разработку квантового компьютера, то про очередные эксперименты, результаты которых не укладываются в голове, но отлично укладываются в заголовках СМИ.

Однажды возник интерес углубиться в это. Раздумывая над популяряным экспериментом «Опыт Юнга» (двухщелевой эксперимент), пришел к интересным мыслям и аналогиям из опыта программирования.

Этот эксперимент доказал, что свет является не просто частицей-пулей, летящей по прямой, а ведет себя как волна, подобно распространению звука.

«Опыт Юнга» (ссылка на сервис научных статей в областях физики, математики, информатики): Young’s experiment and the finiteness of information

Эксперимент можно повторить самому, что описывается в журнале “Квант” (1981г, научно-популярный физико-математический журнал академии наук СССР и академии педагогических наук СССР): Сделать опыт Юнга? Это не так сложно

Иллюстрация эксперимента с сайта postnauka.org

Пытаясь представить фотон, как волну, мозг закипал, пока из его глубин не пришла ассоциация с выполнением кода программы.

Ведь все это так похоже:

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

Две щели, разная геометрия, разный результат: да это же алгоритм поиска пути, - дискретная сетка, графы, эвристика, веса ячеек, и все такое.

Здесь мне очень понравилась эта аналогия и моя фантазия пошла в разгон, что дало свое личное представление о квантовых штуках.

Метафоры для квантовых штук:

Ниже я постарался подобрать под свои измышления исходные законы и термины из реальной квантовой механики популярных экспериментов и пометил их символом “^” (значит гуглим самостоятельно), чтобы было примерное сравнение по ходу чтения (могу ошибаться).

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

Так как доказать я этого не могу и не стараюсь этого делать, я просто имею смелость полноценно сравнить это с кодингом.

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

● [Образ спрайта для фотона]:

Фотон: фундаментальная частица, квант электромагнитного поля. В виде фотонов испускается и поглощается электромагнитное излучение. Фотон имеет свойства как частицы, так и волны. У него нет ни электрического заряда, ни массы. Цитата с сайта “Ядерная физика в интернете”: Фотон

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

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

Этот образ дает одновременно и ощущение точки-частицы (сам спрайт, как сущность или его центр) и некая неопределенность в виде прозрачности пикселей по краям.

● [Образ пространства]:

В квантовой физике есть термин ^Локальность, где подразумевается, что ничто не может узнать друг о друге быстрее скорости света (передача информации).

Но так же есть термин ^Нелокальность, что допускает взаимосвязи (корреляции) на любых расстояниях, но при этом привычная передача информации так же ограничена скоростью света.

Статьи (^Локальность, ^Нелокальность):
“Ядерная физика в интернете (страница 8)”: Распутываем запутанную квантовую механику: как мы понимаем неравенства Белла 52 года спустя
Сервис научных статей в областях физики, математики, информатики: Time series and the meaning of quantum non-locality

В метафоре пространства, за передвижение спрайта будет отвечать образ глобальной дискретной 3D сетки (вселенский движок), где каждая ячейка это набор всевозможных параметров-переменных в ее памяти.

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

Метафора квантовой механики глазами гейм-девелопера:

Представим наш мир в виде бесконечной 3D сетки координат с ячейками ^планковской длины. А бегающие по ней фотоны (^Волновой пакет информации) это спрайты с альфа-каналом и размытыми краями, где в центре альфа вероятнее всего близка к 1.0.

Сетка это рабочая структура, по которой работает “рендер-движок” реальности. Скорость света в данном случае это радиус расширения взаимодействия с сеткой (^Световой конус), для которой движок ведет непрерывный расчет поиска пути, по типу алгоритмов A^, HPA, Dijkstra (^Принцип наименьшего действия, ^Интегралы по траекториям Фейнмана).

Каждая ячейка сетки имеет свой вес и скрытые параметры (^Амплитуда вероятности, ^ Виртуальное возбуждение поля) и по умолчанию содержит случайный фоновый шум (^Квантовые флуктуации).

Пока для фотона-спрайта происходят вычисления в сетке (^Суперпозиция), пиксели прозрачны (виртуальны), их нельзя зафиксировать материально. Вычисления для движка это просто такт, а для наблюдателя — всевозможные состояния.

Этот подход не различает ^локальность и ^нелокальность, т.к. движок всегда глобален, а наблюдатель пребывает в сфере его взаимодействий.

А теперь наложим подход на знаменитый эксперимент с двумя щелями (Опыт Юнга):

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

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

Чем выше суммарный вес в точке, тем выше вероятность, что именно в ней пиксель спрайта выйдет наружу (Коллапс волновой функции).

Геометрия пространства это множитель карты весов (^Интерференция). Чем сложнее, тем более выражена.

Итоговая точка-пиксель спрайта определяется псевдослучайным образом, с учётом вероятностей фонового шума ячеек выбранного маршрута (Квантовые флуктуации).

Движок сетки обсчитывает все ходы мгновенно. С таким подходом удается визуализировать результаты эксперимента.

Эксперимент с квантовым ластиком и отложенным выбором (^Kim et al., 1999):

Это усовершенствованный эксперимент «Опыт Юнга», где на пути волны света установлены дополнительные инструменты для взаимодействия, чтобы показать еще более интересную природу волны. Опыт создает иллюзию, что фотон заранее знает, какие условия для него выберет экспериментатор.

Статья на хабре: Назад в будущее? Квантовый ластик с отложенным выбором

Сервис научных статей в областях физики, математики, информатики: A Delayed Choice Quantum Eraser

Для фотона-спрайта при выстреле формируется во времени карта весов (^Уравнение Шрёдингера) вектора волны опроса ячеек по траектории двух щелей.

Далее на пути сразу же встречается специальный кристалл, свойства которого позволяют трансформировать наш фотон-спрайт с единым весом в два суб-спрайта наследника (A и B) меньшего веса.

Спрайт “A” (^сигнальный) направили по короткому пути для его скорой детекции (^Коллапс).

Спрайт “B” (холостой) направили по долгому пути-лабиринту, чтобы понять момент истощения сервисного веса информации общего пути волны при контакте с детекторами (Декогенерация).

Если спрайт «B» будет достаточно истощен детекторами, то его память общего веса от спрайта-родителя истощится и его отрежет от общего пакета информации родителя (^Интерференция отсутствует).

В этом эксперименте метафора отсекает влияние из будущего, т.к. есть только перерасчёт карты весов в каждый момент времени — реальном времени.

Метафора квантовой механики глазами хобби-гейм-девелопера. Попытка понять квантовые штуки через алгоритмы поиска пути