Доброго времени суток, уважаемое хабрасообщество. Это мой первый пост, поэтому, прошу, не судите строго.
Как-то давно мне в руки попалась головоломка в виде кубика с лабиринтом внутри, по которому катался шарик. С тех пор у меня в голове засела идея сделать такую же игру-головоломку. Наконец-то решила заняться разработкой игр и воплотить старую идею в жизнь. На всю работу было потрачено два месяца неспешной работы по вечерам. В общей сложности 120-150 часов. То что получилось вы можете попробовать здесь.
Но просто пиарить свой проект на хабре мне не хочется, поэтому я решила написать здесь о нескольких проблемах, с которыми я столкнулась во время написания игры. Кому-то эти проблемы покажутся элементарными (здесь же множество маститых программистов), но, возможно для кого-то их решение окажется полезным.
Итак,
_| ← левая стена
↑
правая стена
Верхняя стена — переход на следующий слой.
Я использовала алгоритм Эллера, любезно разложенный по полочкам в этом посте, дополнив его для трехмерного случая:
Расставляем правые стенки, аналогично левым.
Расставляем верхние стенки:
Копируем слой.
Удаляем левые и правые стенки.
Если у ячейки есть верхняя стенка — присваиваем ей новое множество.
Удаляем верхние стенки.
Повторяем пункты 2-8 N-2 раза (первый слой мы создавали отдельно, последний тоже создаем отдельно).
Копируем слой.
Проставляем всем ячейками стенки сверху.
Разрушаем границы между ячейками, находящимися в разных множествах.
Я не уверена на 100% что при таком построении лабиринтов нет циклов, но получаются весьма интересные лабиринты.
Так как лабиринт создается автоматически — выход из него, тоже должен задаваться автоматически. Эту проблему я решила просто:
Вот что получилось:
Для тех кому лень пробовать игру опишу ситуацию: после того как лабиринт сгенерирован и загружен получается кубик, внутри которого много много стенок. Даже сделав эти стенки полупрозрачными, разобраться в лабиринте при большом количестве вершин не представляется возможным. Было принято решение показывать «срез» лабиринта — все слои кроме одного делать практически прозрачными. Но так как кубик крутится во все стороны, кроме определения номер отображаемого уровня встала задача определения правильной грани для показа.
Первое решение этой проблемы: выбирать грань в зависимости от углов наклона кубика (rotation). Я такой вариант реализовала, однако он работал не особо хорошо, видимо я не учла все комбинации углов и граней: граней 6 штук и кубик вращается по каждому из трех направлений от 0 до 360 градусов.
Второе решение:
На кубике имеются три стрелки, обозначающие направления. Они нужны как для визуальной ориентации игрока, так и для определения нужной грани.
Кроме стрелок мне понадобились еще три точки на углах куба:
— в нижнем левом ближнем углу (откуда начинаются стрелки) — spot1.
— в верхнем правом дальнем углу (по диагонали куба от первого) — spot2.
— третья точка на выбор (PivotPoint)
— позиция камеры, тогда отображаться будет та грань, которая больше всего видна камере
— точка под кубом по центу, тогда отображаться будет так грань, которая больше всего обращена книзу.
Алгоритм:
Вот, пожалуй и все большие проблемы, с которыми я столкнулась. Разработка велась на движке Unity3D (я потратила много времени еще и потому что первый раз работала с ним). Скрипты писались на C#.
Спасибо за внимание. Критика и предложения только приветствуются.
P.S. Если будете ругать дизайн — я только за. Таланта к нему у меня нет, может хоть умные люди что подскажут.
Как-то давно мне в руки попалась головоломка в виде кубика с лабиринтом внутри, по которому катался шарик. С тех пор у меня в голове засела идея сделать такую же игру-головоломку. Наконец-то решила заняться разработкой игр и воплотить старую идею в жизнь. На всю работу было потрачено два месяца неспешной работы по вечерам. В общей сложности 120-150 часов. То что получилось вы можете попробовать здесь.
Но просто пиарить свой проект на хабре мне не хочется, поэтому я решила написать здесь о нескольких проблемах, с которыми я столкнулась во время написания игры. Кому-то эти проблемы покажутся элементарными (здесь же множество маститых программистов), но, возможно для кого-то их решение окажется полезным.
Итак,
проблема первая — Генерация трехмерного лабиринта.
Зачем создавать лабиринт автоматически:
- — Хочется и самой поиграть в свою игру, а лабиринты, которые сам создаешь, проходить не интересно
- — Для больших лабиринтов, от 5х5х5 и больше ручное создание весьма проблематично
_| ← левая стена
↑
правая стена
Верхняя стена — переход на следующий слой.
Я использовала алгоритм Эллера, любезно разложенный по полочкам в этом посте, дополнив его для трехмерного случая:
- Создаем не ряд, как в исходном алгоритме, а сразу слой (матрица NxN). Каждой ячейка присваиваем новый номер множества.
- Расставляем левые стенки:
Расставляем правые стенки, аналогично левым.
Расставляем верхние стенки:
- если ячейка единственная в своем множестве без верхней стенки — не создаем стенку.
- в остальных случаях решаем, ставить стенку или нет, случайным образом.
Копируем слой.
Удаляем левые и правые стенки.
Если у ячейки есть верхняя стенка — присваиваем ей новое множество.
Удаляем верхние стенки.
Повторяем пункты 2-8 N-2 раза (первый слой мы создавали отдельно, последний тоже создаем отдельно).
Копируем слой.
Проставляем всем ячейками стенки сверху.
Разрушаем границы между ячейками, находящимися в разных множествах.
Я не уверена на 100% что при таком построении лабиринтов нет циклов, но получаются весьма интересные лабиринты.
Проблема вторая — выход из лабиринта.
Так как лабиринт создается автоматически — выход из него, тоже должен задаваться автоматически. Эту проблему я решила просто:
- Начальная точка известна: шарик всегда появляется в ячейке (0,0,0). Чтобы было интереснее всего, выход из лабиринта должен находиться на максимальном удалении од входа.
- Для определения удаленности ячейки я использовала Волновой алгоритм (описывать не буду, думаю все знают), взяв за начальную ячейку (0,0,0).
- Среди получившихся меток дальности ячеек выбираем максимальные, но так чтобы они лежали на гранях куба (хотя бы одна из координат равна 0 или N-1).
- Среди получившихся «кандидатов» на выход случайным образом выбираем одну.
- Определяем грань которой выбранная ячейка прикасается к внешнему кубу и устанавливаем в ней выход.
Вот что получилось:
Проблема третья — определение грани для показа.
Для тех кому лень пробовать игру опишу ситуацию: после того как лабиринт сгенерирован и загружен получается кубик, внутри которого много много стенок. Даже сделав эти стенки полупрозрачными, разобраться в лабиринте при большом количестве вершин не представляется возможным. Было принято решение показывать «срез» лабиринта — все слои кроме одного делать практически прозрачными. Но так как кубик крутится во все стороны, кроме определения номер отображаемого уровня встала задача определения правильной грани для показа.
Первое решение этой проблемы: выбирать грань в зависимости от углов наклона кубика (rotation). Я такой вариант реализовала, однако он работал не особо хорошо, видимо я не учла все комбинации углов и граней: граней 6 штук и кубик вращается по каждому из трех направлений от 0 до 360 градусов.
Второе решение:
На кубике имеются три стрелки, обозначающие направления. Они нужны как для визуальной ориентации игрока, так и для определения нужной грани.
Кроме стрелок мне понадобились еще три точки на углах куба:
— в нижнем левом ближнем углу (откуда начинаются стрелки) — spot1.
— в верхнем правом дальнем углу (по диагонали куба от первого) — spot2.
— третья точка на выбор (PivotPoint)
— позиция камеры, тогда отображаться будет та грань, которая больше всего видна камере
— точка под кубом по центу, тогда отображаться будет так грань, которая больше всего обращена книзу.
Алгоритм:
- Замеряем расстояния между каждой стрелкой и PivotPoint.
- Замеряем расстояния между spot1 и PivotPoint и spot2 и PivotPoint.
- Если spot1 ближе к PivotPoint чем spot2, то берем две ближние стрелки, иначе берем две дальние стрелки.
- Комбинация двух стрелок определяет грань, которую необходимо отобразить.
- Если spot1 ближе к PivotPoint чем spot2, то отображаем «пол» для данного слоя, иначе отображаем «потолок» (куб перевернулся).
Вот, пожалуй и все большие проблемы, с которыми я столкнулась. Разработка велась на движке Unity3D (я потратила много времени еще и потому что первый раз работала с ним). Скрипты писались на C#.
Спасибо за внимание. Критика и предложения только приветствуются.
P.S. Если будете ругать дизайн — я только за. Таланта к нему у меня нет, может хоть умные люди что подскажут.