Todo list online
3D конструктор из пластилина и зубочисток! Как сделать в домашних условиях!
Строительство наклонных стен
Посмотрите на эти три примера наклонных стен. Все три являются рабочими стенами, и все они имеют аналогичный дизайн (этапы). Стена слева состоит из отдельных блоков по диагонали. Стены посередине и справа одинаковы, за исключением того, что вместо отдельных блоков они состоят из двухблочных и трехблочных сегментов соответственно. Это позволяет создавать более крутые и крутые уклоны.
Построение многоугольников с наклонными стенами
Вы можете делать всевозможные формы, соединяя наклонные стены под разными углами. Вот четыре разных полигона: алмаз, параллелограмм, пятиугольник и шестиугольник.
Чтобы создать многоугольники, подобные одному из них, выполните следующие действия:
Визуализируйте, как будет выглядеть многоугольник.
Постройте одну сторону.
Завершите другие стороны многоугольника.
Обратите особое внимание на стороны, обращенные в одном и том же направлении (параллельно) и боках с одинаковой длиной (конгруэнтно).
Исправить любые ошибки.
Если ваш многоугольник не соединяется точно так же, перепроверьте длину и угол каждой стороны, чтобы выяснить, где проблема, чтобы вы могли ее исправить.
Несколько общих полигонов создают действительно интересные здания:
Octagon: Восемь односторонних многоугольников почти всегда создаются с 4 нормальными линиями и 4 диагональными линиями.Эти формы хороши для строительства больших, экспансивных комнат. Вы также можете построить диагональные стороны короче, чем другие, чтобы ось восьмиугольника выглядела скорее как квадрат с отрубленными углами.
Построение на плоскости
Нам понадобятся: карандаш, линейка, циркуль.
Построение угла в 60
1. Проведём прямую и отметим на ней точку А.
2. Из точки А проведём дугу произвольного радиуса и получим точку В.
3. Из точки В проведём дугу радиуса АВ, чтобы она пересекла ранее начерченную дугу.
4. Проведённая через точку пересечения (С) и точку А прямая будет второй стороной требуемого угла.
Построение угла в 45
1. Построим угол 60, кака описано выше.
2. Разделим полученный угол пополам.
3. Угол между лучами 60 и 30 разделим пополам. В результате получим угол в 45.
Построение угла в 75
1. Построим угол в 60, как описано выше, и разделим его пополам.
2. В ходе дальнейшего деления надвое получим угол в 15.
3. Отразим угол в 15 через луч 60 и так получим угол в 75.
Построение угла в 90
1. Построим угол в 60, как описано выше, и разделим его пополам.
2. Получившийся угол в 30 через луч 60 и так получим угол точно в 90.
Разделение отрезка на равные части.
1. Проведём прямую и отметим на ней отрезок АВ.
2. Из точки А проведём вспомогательную прямую и разделим её на столько одинаковых частей, на сколько требуется разделить отрезок АВ. Делить будем при помощи циркуля. Последнюю точку обозначим буквой С.
3. Последнюю точка (С) соединим с концом отрезка АВ. Построим рад параллельных отрезку СВ прямых по всей длине отрезка АВ. Точки пересечения параллельных прямых с отрезком АВ и будут точками раздела отрезка на несколько равных частей.
Построение правильного пятиугольника.
1. Проведём окружность радиусом 50 мм. Через центр окружности проведём взаимно перпендикулярные горизонтальную и вертикальную линии.
Построение правильного шестиугольника.
1. Проведём окружность радиусом 50 мм.
2. Через центр окружности проведём взаимно перпендикулярные горизонтальную и вертикальную линии.
3. Из точки А на линии окружности отложим шесть раз радиус нашей окружности. Соединив прямыми точки пересечения, получим шестиугольник.
Построение правильного семиугольника.
1. Проведём окружность заданного радиуса. Через центр окружности проведём взаимно перпендикулярные горизонтальную и вертикальную линии.
2. Из точки D проведём дугу радиусом равным радиусу окружности.
Общий метод построения многоугольников.
1. Проведём окружность радиусом 50 мм. Через центр окружности проведём взаимно перпендикулярные горизонтальную и вертикальную линии. Продолжим горизонтальную лини. За точки А и В.
2. Из точки D проведём дугу радиусом, равным радиусу окружности так, чтобы дуга пересекла горизонтальную линию.
3. При помощи вспомогательной прямой разделим вертикальную линию на столько равных частей, сколько сторон многоугольника требуется получить. Для примера показано построение одиннадцатиугольника.
Создание сеток шестиугольников
Сетки из шестиугольников (гексагональные сетки) используются в некоторых играх, но они не так просты и распространены, как сетки прямоугольников. Я коллекционирую ресурсы о сетках шестиугольников уже почти 20 лет, и написал это руководство по самым элегантным подходам, реализуемым в простейшем коде. В статье часто используются руководства Чарльза Фу (Charles Fu) и Кларка Вербрюгге (Clark Verbrugge). Я опишу различные способы создания сеток шестиугольников, их взаимосвязь, а также самые общие алгоритмы. Многие части этой статьи интерактивны: выбор типа сетки изменяет соответствующие схемы, код и тексты. (Прим. пер.: это относится только к оригиналу, советую его изучить. В переводе вся информация оригинала сохранена, но без интерактивности.).
Примеры кода в статье написаны псевдокодом, так их легче читать и понимать, чтобы написать свою реализацию.
Геометрия
Шестиугольники — это шестигранные многоугольники. У правильных шестиугольников все стороны (грани) имеют одинаковую длину. Мы будем работать только с правильными шестиугольниками. Обычно в сетках шестиугольников используются горизонтальная (с острым верхом) и вертикальная (с плоским верхом) ориентации.
Шестиугольники с плоским (слева) и острым (справа) верхом
У шестиугольников по 6 граней. Каждая грань общая для двух шестиугольников. У шестиугольников по 6 угловых точек. Каждая угловая точка общая для трёх шестиугольников. Подробнее о центрах, гранях и угловых точках можно прочитать в моей статье о частях сеток (квадратах, шестиугольниках и треугольниках).
Разница между двумя ориентациями в том, что x и y меняются местами, что приводит к изменению углов: углы шестиугольников с плоским верхом равны 0°, 60°, 120°, 180°, 240°, 300°, а с острым верхом — 30°, 90°, 150°, 210°, 270°, 330°.
Углы шестиугольников с плоским и острым верхом
Размер и расположение
В некоторых играх для шестиугольников используется пиксель-арт, который не точно соответствует правильным шестиугольникам. Формулы углов и расположений, описанные в этом разделе, не будут совпадать с размерами таких шестиугольников. Остальная часть статьи, описывающая алгоритмы сеток шестиугольников, применима даже если шестиугольники немного растянуты или сжаты.
Системы координат
Давайте приступим к сборке шестиугольников в сетку. В случае сеток квадратов существует только один очевидный способ сборки. Для шестиугольников же есть множество подходов. Я рекомендую использовать в качестве первичного представления кубические координаты. Осевые координаты или координаты смещений следует использовать для хранения карт и отображения координат для пользователя.
Координаты смещений
Горизонтальное расположение «нечет-r»
Горизонтальное расположение «чёт-r»
Вертикальное расположение «нечет-q»
Вертикальное расположение «чёт-q»
Кубические координаты
Ещё один способ рассмотрения сеток шестиугольников — видеть в них три основные оси, а не две, как в сетках квадратов. В них проявляется элегантная симметрия.
Заметьте три основные оси на сетке кубов и их соотношение с шестью диагональными направлениями сетки шестиугольников. Диагональные оси сетки соответствуют основному направлению сетки шестиугольников.
Поскольку у нас уже есть алгоритмы для сеток квадратов и кубов, использование кубических координат позволяет нам адаптировать эти алгоритмы под сетки шестиугольников. я буду использовать эту систему для большинства алгоритмов статьи. Для использования алгоритмов с другой системой координат я преобразую кубические координаты, выполню алгоритм, а затем преобразую их обратно.
Изучите, как кубические координаты работают для сетки шестиугольников. При выборе шестиугольников выделяются кубические координаты, соответствующие трём осям.
Но вы можете возразить, что не хотите хранить 3 числа для координат, потому что не знаете, как хранить карту в таком виде.
Осевые координаты
Координаты смещения — это первое, о чём думает большинство людей, потому что они совпадают со стандартными декартовыми координатами, используемыми для сеток квадратов. К сожалению, одна из двух осей должна проходить «против шерсти», и это в результате всё усложняет. Кубическая и осевая система идут «по шерсти» и у них более простые алгоритмы, но хранение карт немного более сложное. Существует ещё одна система, называемая «чередуемой» или «двойной», но здесь мы не будем её рассматривать; некоторые считают, что с ней проще работать, чем с кубической или осевой.
Координаты смещения, кубические и осевые
Ось — это направление, в котором соответствующая координата увеличивается. Перпендикуляр к оси — это линия, на которой координата остаётся постоянной. На схемах сеток выше показаны линии перпендикуляров.
Преобразование координат
Вероятно, что вы будете использовать в своём проекте осевые координаты или координаты смещения, но многие алгоритмы проще выражаются в кубических координатах. Поэтому нам нужно уметь преобразовывать координаты между системами.
Осевые координаты близко связаны с кубическими, поэтому преобразование делается просто:
В коде эти две функции могут быть записаны следующим образом:
Координаты смещения совсем немного сложнее:
Примечание о реализации: я использую a&1 (побитовое «И») вместо a%2 (деления с остатком) для определения, является ли число чётным (0) или нечётным (1). Подробное описание см. на странице примечаний к моей реализации.
Соседние шестиугольники
Дан один шестиугольник, с какими шестью шестиугольниками он находится рядом? Как и можно ожидать, легче всего дать ответ в кубических координатах, довольно просто в осевых координатах, и немного сложнее в координатах смещения. Также может потребоваться рассчитать шесть «диагональных» шестиугольников.
Кубические координаты
Осевые координаты
Как и раньше, мы используем для начала кубическую систему. Возьмём таблицу Cube(dx, dy, dz) и преобразуем в таблицу Hex(dq, dr) :
Координаты смещения
В осевых координатах мы вносим изменения в зависимости от того, в каком месте сетки находимся. Если мы в столбце/строке смещения, то правило отличается от случая столбца/строки без смещения.
Сетка для чётной (EVEN) и нечётной (ODD) строк
Сетка для чётной (EVEN) и нечётной (ODD) строк
Сетка для чётного (EVEN) и нечётного (ODD) столбцов
Сетка для чётного (EVEN) и нечётного (ODD) столбцов
Использование вышеуказанных таблиц подстановки — это простейший способ вычисления соседей. Если вам интересно, можно также почитать об извлечении этих чисел.
Диагонали
Перемещение в «диагональном» пространстве в координатах шестиугольников изменяет одну из трёх кубических координат на ±2 и две другие на ∓1 (сумма должна оставаться равной 0).
Как и раньше, мы можем преобразовать эти координаты в осевые, откинув одну из трёх координат, или преобразовать в координаты смещения, предварительно вычислив результаты.
Расстояния
Кубические координаты
Эквивалентом этой записи будет выражение того, что одна из трёх координат должна быть суммой двух других, а затем получение её в качестве расстояния. Можно выбрать форму деления пополам или форму максимального значения, приведённую ниже, но они дают одинаковый результат:
На рисунке максимальные значения выделены цветом. Заметьте также, что каждый цвет обозначает одно из шести «диагональных» направлений.
Осевые координаты
В осевой системе третья координата выражена неявно. Давайте преобразуем из осевой в кубическую систему для расчёта расстояния:
Координаты смещения
Как и в случае с осевыми координатами, мы преобразуем координаты смещения в кубические координаты, а затем используем расстояние кубической системы.
Мы будем использовать тот же шаблон для многих алгоритмов: преобразуем из шестиугольников в кубы, выполняем кубическую версию алгоритма и преобразуем кубические результаты в координаты шестиугольников (осевые или координаты смещения).
Отрисовка линий
Как нарисовать линию от одного шестиугольника до другого? Я использую линейную интерполяцию для рисования линий. Линия равномерно сэмплируется в N+1 точках и вычисляется, в каких шестиугольниках находятся эти сэмплы.
Диапазон перемещения
Диапазон координат
Для заданного центра шестиугольника и диапазона N какие шестиугольники находятся в пределах N шагов от него?
Этот цикл проходит только по нужным координатам. На рисунке каждый диапазон является парой линий. Каждая линия — это неравенство. Мы берём все шестиугольники, удовлетворяющие шести неравенствам.
Пересекающиеся диапазоны
Если нужно найти шестиугольники, находящиеся в нескольких диапазонах, то перед генерированием списка шестиугольников можно пересечь диапазоны.
Препятствия
Повороты
Для заданного вектора шестиугольника (разницу между двумя шестиугольниками) нам может понадобиться повернуть его, чтобы он указывал на другой шестиугольник. Это просто сделать, имея кубические координаты, если придерживаться поворота на 1/6 окружности.
Поворот на 60° вправо сдвигает каждую координату на одну позицию вправо:
Поворот на 60° влево сдвигает каждую координату на одну позицию влево:
«Поиграв» [в оригинале статьи] со схемой, можно заметить, что каждый поворот на 60° меняет знаки и физически «поворачивает» координаты. После поворота на 120° знаки снова становятся теми же. Поворот на 180° меняет знаки, но координаты поворачиваются в своё изначальное положение.
Вот полная последовательность поворота положения P вокруг центрального положения C, приводящего к новому положению R:
Кольца
Простое кольцо
В этом коде cube начинается на кольце, показанном большой стрелкой от центра к углу схемы. Я выбрал для начала угол 4, потому что он соответствует пути, в котором двигаются мои числа направлений. Вам может понадобиться другой начальный угол. На каждом этапе внутреннего цикла cube двигается на один шестиугольник по кольцу. Через 6 * radius шагов он завершает там, где начал.
Спиральные кольца
Проходя по кольцам по спиральному паттерну, мы можем заполнить внутренние части колец:
Площадь большого шестиугольника равна сумме всех окружностей плюс 1 для центра. Для вычисления площади используйте эту формулу.
Обход шестиугольников таким способом можно также использовать для вычисления диапазона перемещения (см. выше).
Область видимости
Что видимо из заданного положения с заданным расстоянием, и не перекрывается препятствиями? Простейший способ определить это — нарисовать линию к каждому шестиугольнику в заданном диапазоне. Если линия не встречается со стенами, то вы видите шестиугольник. Перемещайте мышь по шестиугольникам [на схеме в оригинале статьи], чтобы увидеть отрисовку линий к этим шестиугольникам и стены, с которыми линии встречаются.
Этот алгоритм может быть медленным на больших площадях, но его легко реализовать, поэтому рекомендую начать с него.
Существует много разных определений видимости. Хотите ли вы видеть центр другого шестиугольника из центра начального? Хотите ли вы видеть любую часть другого шестиугольника из центра начального? Может быть, любую часть другого шестиугольника из любой точки начального? Мешающие взгляду препятствия меньше полного шестиугольника? Область видимости — это более хитрое и разнообразное понятие, чем кажется на первый взгляд. Начнём с простейшего алгоритма, но ждите, что он обязательно правильно вычислит ответ в вашем проекте. Бывают даже случаи, когда простой алгоритм даёт нелогичные результаты.
В руководстве Кларка Вербрюгге описывается алгоритм для вычисления области видимости «начинаем с центра и двигаемся наружу». См. также проект Duelo, у которого есть на Github онлайн-демо области видимости с направлениями. Также можете прочитать мою статью об расчёте 2d-видимости, в ней есть алгоритм, работающий с многоугольниками, в том числе и с шестиугольниками. У сообщества любителей roguelike есть хороший набор алгоритмов для сеток квадратов (см. здесь, здесь и здесь). Некоторые из них можно адаптировать под сетки шестиугольников.
Шестиугольники в пиксели
Для шестиугольников с плоскими верхами
Для шестиугольников с острыми верхами
Матричный подход будет удобен позже, когда нам нужно будет преобразовать координаты пикселей обратно в координаты шестиугольников. Всё, что нам понадобится — обратить матрицу. Для кубических координат можно либо использовать кубические базисные векторы (x, y, z), или сначала преобразовать их в осевые, а затем использовать осевые базисные векторы (q, r).
Для координат смещения нам нужно будет сместить номер столбца или строки (он больше не будет целым). После этого можно использовать базисные векторы q и r, связанные с осями x и y:
К сожалению, координаты смещения не имеют базисных векторов, которые можно использовать вместе с матрицей. Это одна из причин того, почему преобразования из пикселей в шестиугольники сложнее в координатах смещения.
Другой подход: преобразовывать координаты смещения в кубические/осевые координаты, затем использовать преобразование кубических/осевых координат в пиксели. Благодаря встраиванию кода преобразования при оптимизации он в результате будет таким же, как выше.
Из пикселей в шестиугольники
Один из самых частых вопросов заключается в том, как взять положение пикселя (например, щелчка мыши) и преобразовать его в координату сетки шестиугольников? Я покажу, как это делается для осевых или кубических координат. Для координат смещения проще всего будет преобразовать в конце кубические координаты в координаты смещения.
Преобразование координат пикселей обратно в координаты шестиугольников достаточно прямолинейно. Мы можем обратить матрицу:
Вот код для осевых шестиугольников с острыми верхами:
А вот код для осевых шестиугольников с плоскими верхами:
Существует множество других способов преобразования пикселей в шестиугольники. На этой странице перечислены известные мне.
Округление до ближайшего шестиугольника
Для некубических координат проще всего будет преобразовать их в кубические координаты, воспользоваться алгоритмом округления, а затем преобразовать обратно:
Хранение карт в осевых координатах
Чаще всего осевая система координат вызывает жалобы потому, что приводит к ненужному расходованию пространства при использовании прямоугольных карт. Это одна из причин в пользу системы координат смещения. Однако все системы координат шестиугольников приводят к расходу пространства при использовании треугольных или шестиугольных карт. Мы можем использовать одну стратегию для хранения всех этих типов карт.
Прямоугольная карта
Треугольная карта
Шестиугольная карта
Ромбовидная карта
Заметьте на схеме, что неиспользуемое пространство находится справа и слева от каждой строки (за исключением ромбовидных карт). Это даёт нам три варианта стратегий хранения карты:
Если карты имеют фиксированные формы, то «первые столбцы» можно вычислять «на лету», а не хранить их в массиве.
Зацикленные карты
В некоторых играх требуется, чтобы карта «склеивалась» по краям. Квадратную карту можно обернуть только по оси x (что примерно соответствует сфере) или по обеим осям x и y (что примерно соответствует тору). Сворачивание зависит от формы карты, а не от формы её элементов. Сворачивание квадратной карты проще выполняется в координатах смещения. Я покажу, как выполняется сворачивание шестиугольной карты в кубических координатах.
Относительно центра карты существует шесть «зеркальных» центров. При выходе с карты мы вычитаем ближайший к нам зеркальный центр, пока снова не вернёмся на основную карту. На схеме [в оригинале статьи] попробуйте покинуть центральную карту, и понаблюдайте, как один из зеркальных центров входит в карту с противоположной стороны.
Поиск пути
При использовании поиска пути на графах, например алгоритма поиска A*, алгоритма Дейкстры или Флойда-Уоршелла поиск пути на сетках шестиугольников не отличается от поиска пути на сетках квадратов. Пояснения и код из моего руководства по поиску пути применимы и для сеток шестиугольников.
[В оригинале статьи пример интерактивен, нажатиями мыши можно добавлять и удалять стены]
Дополнительное чтение
Я хочу в дальнейшем расширять это руководство. У меня есть список на Trello.