Как я могу заполнить внутреннюю часть замкнутой петли на карте плитки?

В моей игре игрок может динамически изменять ландшафт. Карта хранится в 2D-массиве сборных 3D-объектов. На данный момент это хорошо работает. Игрок изменяет ландшафт, выбирая, какую плиту они хотели бы создать (например, скалу вверх или вниз), а затем щелкать отдельные плитки или «рисовать» над несколькими, удерживая кнопку мыши и прокручивая.

Я не хочу, чтобы игрок должен вручную щелкнуть каждую плиту, которую они хотят подняться или упасть в высоту. Самое элегантное решение, которое я могу себе представить, заключается в том, чтобы игрок «рисовал» петлю плиток утеса, которая затем заполняется автоматически, когда петля закрывается. Представьте, возможно, кто-то рисует линию, используя MS Paint или Photoshop, до тех пор, пока эта линия не закроется в форму, которая затем автоматически запустится.

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

Я понятия не имею, как это можно сделать, неважно, элегантно или оптимально. Существуют очевидные возможные решения (найдите средний вектор всех фрагментов в цикле, а затем алгоритм dijkstra из среднего значения, пока пространство не заполнится с правильной высотой), но они предполагают, что сформированная форма является блаженной или квадратной. Неправильная форма, где средняя точка выходит за пределы формы, возможна и, вероятно, разрушит это решение!

Как заполнить внутреннюю часть замкнутого цикла? Я хотел бы получить теоретическое решение, которое я могу уйти и реализовать на C #. На данный момент кажется, что существует, вероятно, концептуальное совпадение между растровой графикой и процедурными картами!

5 голосов | спросил inappropriateCode 23 Maypm17 2017, 13:30:47

2 ответа


15

Короткая . После завершения формы вы должны иметь несколько из 2 очков для каждой затронутой строки на оси x . Оттуда он становится просто делением на эти пары точек для каждой строки, а затем заполняет inbetweens .


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

 Шаги 1 и 2

Шаг 1 : Нарисуйте петлю внутри вашей игры /редактора /независимо от того, что вы хотите сделать.

Шаг 2 . Получите точки , затронутые вашим циклом. Это ребра вашей формы .

 Шаги 3 и 4

Шаг 3 : Итерируйте по этим точкам и получите те, у которых есть один или нет соседи. Это наши запуски и остановки (или любое другое имя, которое вы найдете).

Шаг 4 : Итерируйте по своим запускам /остановкам и создайте пары из двух.

Шаг 4b - Специальный случай . Если у вас есть нечетное количество статистических данных /остановок, вы можете избавиться от центральной точки .

 Шаг 5

Шаг 5 : теперь вы можете заполнить область 2 между каждой парой точек .

1 С ФОТОГРАФИЯМИ! Я ЗНАЮ, ПРАВО?
2 Ну, это на самом деле сегменты не области . Линией между двумя точками является сегмент . Все дело в области .


Как упоминалось в комментариях, этот алгоритм вообще не является пуленепробиваемым, вот одно из предлагаемых улучшений на Шаг 4b by @DMGregory

«Улучшение

ответил dot_Sp0T 23 Maypm17 2017, 13:56:58
1

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

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

Однако есть альтернативное решение, которое позволяет избежать необходимости полностью находить такую ​​внутреннюю отправную точку, а также обрабатывать произвольные самопересекающиеся фигуры: вместо заполнения наполнителем внутри вашего цикла вместо этого заполнять внешнюю сторону.

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

 Иллюстрация внешней заливки залива

Внутренняя часть цикла будет состоять из каждой точки внутри ограничивающей рамки, в которой not был затронут алгоритм заполнения заливки.

Хорошая вещь об этом алгоритме заключается в том, что его просто невозможно реализовать, особенно если вы уже знакомы с такими вещами, как алгоритм Дейкстры , который в основном представляет собой особый вид заполнения наводнений. В отличие от алгоритма fillline , предложенного dot_Sp0T , нет никаких особых случаев с углами или с граничными линиями, которые выравниваются с сеткой ; все, что вам нужно сделать, это убедиться, что граница непрерывна и закрыта, а затем заливка заливает ее внешний вид.

Обратите внимание, что если петля игрока может самопересекаться, эти алгоритмы могут давать разные результаты. Например, для самопересекающейся граничной формы, показанной на изображении ниже, даже /нечетное правило заполнения , полученное из заливки scanline, заполнило бы фиолетовую область слева, в то время как внешний алгоритм заполнения залива, который я описал, будет обрабатывать всю голубую область справа как находящуюся внутри цикла:

 Сравнение правил заполнения

Это зависит от вас, какое поведение вы считаете более разумным. (Конечно, возможны и другие правила заполнения, такие как правило ненулевого обмотки , который заполнил бы верхнее «отверстие» в форме выше, но не нижнюю.)

ответил Ilmari Karonen 5 TueEurope/Moscow2017-12-05T18:17:37+03:00Europe/Moscow12bEurope/MoscowTue, 05 Dec 2017 18:17:37 +0300 2017, 18:17:37

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132