Как сделать удаление лица в мире единичного куба a la Minecraft?

Ответ 1

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

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

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

Более сложная проблема заключается в удалении закрытых интерьеров. Мое предложение: этого не стоит. Путем удаления закрытых интерьеров размещение или удаление блока становится нелокальной операцией. Вероятнее всего, вы получите больше производительности, потратив время на оптимизацию своего количества партий (используйте по возможности текстурные атласы/массивы) и ваши данные вершин.

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

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

  A
+++++
+   +
+   + B
+   +
+++++

Границы A и B смежны. Если вы поместите новый блок, вы измените смежность:

     +++++
     +   +
   C +   +
     +   +
  A  +++++
+++++  D
+   +
+   + B
+   +
+++++

A теперь смежна с C и B, смежными с D.

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

Точка этого графика смежности такова: если все немерти лица соединены в графе, то будет показан только один цикл графика; все другие циклы графов не будут видны. Цикл графика представляет собой группу граней, которые все связаны друг с другом, прямо или косвенно.

Большой вопрос: как вы находите видимый цикл? Следующий алгоритм предполагает, что блоки помещаются/удаляются сущностью. Это означает, что видима хотя бы одна грань любого размещенного блока. Это также означает, что любые мертвые лица, которые становятся живыми, удаляя блок, видны.

Когда вы размещаете блок, вы можете создать один или несколько новых циклов граней. Чтобы обнаружить это, вы сначала найдете все не мертвые лица (те, которые не примыкают к чему-то), которые вы создали, разместив блок. По крайней мере один из них будет виден; найдите это лицо.

Затем для каждого другого не мертвого лица в новом блоке используйте поиск по графику A * (A-star), чтобы найти это лицо. A * - алгоритм поиска графа на основе приоритетов. В этом случае "расстояние" для алгоритма - это расстояние между квадратом, в котором находится текущая грань, и квадрат, на котором находится видимая грань.

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

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

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

С удалением вам нужно найти все невидимые циклы лиц, прилегающие к блоку. Затем вам нужно найти это одно видимое лицо, как раньше. Затем вы удаляете блок и просматриваете эти циклы с помощью A *, чтобы увидеть, могут ли они найти видимую грань. Эти циклы, которые могут быть видны. Те циклы, которые не могут быть не видны.

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

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

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