Поиск пути на Javascript

В мире С++ есть достаточно много библиотек для поиска пути, самая популярная на мой взгляд это Recast & Detour. Но даже по разумным меркам в ней много лишнего, весит она совсем много, а если портировать её на Javascript еще больше (1Мб). Понимая принципы работы этой библиотеки. Решил создать свою почти с нуля и не мучиться с портированием. За основу был взят алгоритм поиска A-Star (сокращенно А*).

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

Результат работы алгоритма:

javascript-pathfinging-navigationmesh

Всего в 800 строк удалось решить задачу, при этом скорость работы не уступает своим аналогам на C++. А размер без сжатия 19Кб, со сжатием gz 6Кб. При этом мы не используем сторонние библиотеки и нет никаких зависимостей.

Весёлый Youtube

Не так давно, на youtube появилась интересная функция, для автоматического определения названия игры, с указанием описания и ссылки на проект. Но в итоге, мои ролики каким-то странным образом очутились в составе другой игры, где подобного нет вообще. Но самое удивительное, на их сервисе gaming.youtube.com нет возможности добавить информацию о своей игре. Ролики от игры, пришлось перенести в другой раздел — Наука и техника. Возможно, кто-то знает как победить эту беду, буду рад любым идеям.

Двухмерный редактор

Векторный двухмерный редактор был создан с основной целью — создание сечений с последующим преобразованием в 3D модель. Но в процессе развития он изменялся и в него внедрялись всё новые и новые функции. В итоге сейчас это инструмент для работы с векторной графикой и процедурной генерацией. Практически все мои проекты направлены на процедурную составляющую. Мир слишком большой и рисовать его руками, без вспомогательных инструментов, крайне сложно, даже небольшие детали требуют сложной и кропотливой работы.

В чем же преимущество редактора, почему в очередной раз не использую готовые редакторы. Основное отличие редактора от аналогов — он работает сразу с десятками чертежей, каждый из которых содержит различные слои. Чертежи зависят друг от друга. Слои могут содержать сотни и более объектов. Слои так же можно связывать как с текущим чертежом так и с другими чертежами. Это позволяет проработать полноценную 3D модель состоящую только из сечений, которые расположены на разных уровнях.

html5-free-vector-editor

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

html5-procedural-city

Песочница HTML5 + Javascript + WebGL

Для быстрого прототипирования и тестирования идей, нужна изолированная среда, которая, не повлияет на создание продукта. Очень часто многие разработчики тестируют идеи прямо в продукте который разрабатывают. Но это не всегда корректно и не всегда возможно полноценно протестировать полученный результат. По этому для себя создал изолированную среду (песочницу), где можно опробовать идею или протестировать различные функции. В основном среда используется для прототипирования трехмерных сцен и объектов. В песочнице можно в режиме реального времени редактировать код и следить за визуальными изменениями.webgl-sandbox

Год на Javascript + WebGL

Прошел год после начала создания приложений с использованием Javascript. Это было трудным этапом, познать все технологические аспекты. Изменить стиль мышления, стиль написания кода. Но за этот  период удалось развиться, создать необходимые библиотеки, наработать базовый код. Часть портировать из своих разработок на C++, а так же освоить JS как со слабых сторон, так и с сильных. С уверенностью могу сказать, JS отличается от различных языков программирования гибкостью, да язык не идеален, есть масса проблем, но та легкость с которой можно создать сложные приложения, игры и утилиты, полностью покрывают все проблемы. А самый главный аргумент это доступность, хочешь показать проект, просто предложи человеку ссылку.

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

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

При создании одной из игр от первого лица, потребовалось создание процедурного подземелья (с одним уровнем высоты). Подземелье должно быть в космическом, стиле с возможностью редактирования полученного результата. Для этого был выбран самый простой метод, создание сетки определенного размера и размещение на ней комнат. После создания, производилось оформление комнат в нужном стиле с возможностью замены любых деталей на другие модели. Для оформления я использовал генерацию стен и блоков из другого своего процедурного генератора, о котором постараюсь рассказать более подробно в других публикациях.
procedural-tile-generatorПлюсы метода:

  • простота создания,
  • легко модернизировать
  • быстрая генерация

Генерация имен

В прошлой публикации: Как создать генератор названий, мною были приведены самые простые способы создания генератора названий. В различных продуктах используются различные методы, но на практике чаще остальных метод под названием Цепь Маркова. Метод назван в честь Маркова Андрей Андреевича, русского математика, академика, внёсшего большой вклад в теорию вероятностей, математический анализ и теорию чисел.
Чем цепь Маркова лучше других методов? Результат получается более естественный. Используя небольшие словари, удается получить большое число не повторяющихся последовательностей в необходимом виде согласно начальных словарей. Словари можно не использовать, а лишь их преобразованный вид. Но как показывает практика, используя словари легче манипулировать получаемым результатом.

Пример генератора псевдо-Славянских имен из Dreams Gate использующего цепь Маркова:

Нажав кнопку «Генерация», можно получить новый список случайных имен.

Полезные инструменты для повседневной работы

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

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

Рекомендую: Сайт trello.com

1 2 3 4