Всем привет, Пикабушники!
Мне хотелось бы поделиться с вами новостью о релизе моего второго игрового проекта для мобильной платформы, а точнее Android, - Polygonal Maze. Как можно понять по названию, суть игры состоит в прохождении лабиринтов, но об этом немного позже.
Вот вам ссылочка на игру в GooglePlay: https://play.google.com/store/apps/details?id=com.FLGames.Po...
Сначала немного дополнительной и возможно лишней информации. Прежде всего, мне всего 16 лет - через неделю 17, соответственно я учусь в 11 классе, в принципе это ни на что не влияет, но мало ли, вдруг кто-то захочет из-за этого меня поддержать и скачает игру. И второе - я не русский, поэтому не слишком обращайте внимание на мелкие ошибки и опечатки: русский мне приходится использовать не так уж и часто.
Но, вернемся к игре. У вас вполне мог возникнуть вопрос: "Что-же нового может предложить игра о лабиринтах, которых и так море в Google Play?".
Ответом на подобный вопрос было бы то, что в данной игре есть 2 совершенно уникальных для подобных игр режима: Anomaly и Explore; а также то, что в отличие от всех остальных игр этого типа в Google Play, по крайней мере я ещё ни разу такого не видел, вместе с классическим типом сетки, состоящей из квадратов, используются сетки состоящие из треугольников и шестиугольников (у меня было желание добавить и восьмиугольные, однако для этого пришлось бы значительно перелопатить алгоритм создания сетки и стен).
Также немаловажной особенностью этой игры является количество уровней. Для каждого режима предусмотрено 200 одинаковых для всех пользователей уровней, что в суме дает нам 1000 лабиринтов. Однако что-же делать если их все удалось пройти? Для этого предусмотрено ещё по 6 уровней для каждого режима, содержимое которых генерируется случайным образом.
В принципе, вся завлекательная информация закончилась, однако я думаю, что хуже мне не станет если я поделюсь с вами некоторой информацией о том, что нужно для генерации лабиринтов.
Прежде всего для такого типа игр нам нужно определиться с тем, как мы будем представлять лабиринт. Если я ничего не забыл, то существует 3 способа: матрица, матрица смежности и список смежности.
Рассмотрим матрицу и в туже секунду поймем, что использовать её никак не вариант, поскольку с её помощью не получиться создавать лабиринты с использованием фигур отличных от квадрата (хотя как-то работать с шестиугольниками на ней всё-же можно, однако она нам точно не подходит).
Следующие два способа требую каких-то знаний теории графов, однако как же вы собрались генерировать лабиринты, если эту теорию не знаете хотя-бы на базовом уровне?
В принципе для нашей задачи подойдет оба оставшихся варианта, однако, как мне кажется, вариант с матрицей смежности будет намного менее производительным, поскольку она хранит информацию связях вершины со всеми остальными, что не имеет смысла, когда у тебя более 500 вершин, а тебе нужно обращаться максимум к 6. Поэтому мой выбор пал на список смежности.
Следующим шагом нам нужно выбрать какие алгоритмы для генерации лабиринтов мы будем использовать. Этих алгоритмов не слишком то и много: Recursive Backtracking (я так и придумал как его перевести, а гуглить лень), алгоритм Крускала и Прима, Бинарного древа, Растущего древа (Growing Tree), Hunt-and-Kill, Sidewinder, алгоритм Эллера и ещё несколько, которые я и не рассматривал, поскольку они одень медлительны. В итоге мною была создана реализация всех этих алгоритмов кроме Sidewinder и Eller (просто было слишком лень это делать), однако алгоритм Бинарного древа в игре не используется, поскольку он слишком простой для прохождения. Если вам интересно узнать побольше об этих алгоритмах, вы можете загуглить jamisbuck, у него отлично описаны все эти алгоритмы, правда всё на английском.
Да, что-то получилось не слишком информативно, но надеюсь данный текст не был для вас скучен и вы спешите играть Polygonal Maze.
P.S. Буду очень рад конструктивной критике, идеям, пожеланиям. Надуюсь вам понравиться. Делитесь впечатлениями в комментариях.