Клон PyGame QIX, заполнение областей

Я играю с PyGame.

Сейчас я пытаюсь реализовать клон QIX .

У меня есть игровой цикл, и я могу перемещать игрока (курсор) на экране.

В QIX движение игрока оставляет след (хвост) на экране, создавая ломаную линию.

Если ломаная с границами экрана создает многоугольник, область заполняется.

Как я могу выполнить это поведение?

Как хранить хвост в памяти?

Как определить, когда он строит замкнутую форму, которая должна быть заполнена?

Мне не нужно точное рабочее решение, некоторые указатели, альтернативные имена было бы круто.

На старте есть только серая граница, где игрок может перемещать курсор.

• Первый сценарий:

Пользователь перемещает курсор из точки A в точку B, рисуя красную мультилинию до точки C. В этой точке из-за пересечения границы точка A должна автоматически соединяться с точкой C, создавая многоугольник, который должен быть заполнен ( этот оранжевый материал на моем рисунке). Заполнение многоугольника чертовски просто в PyGame, потому что я предоставляю последовательность точек, а PyGame заботится обо всем остальном.

• Второй сценарий:

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

• Третий сценарий:

Игрок продвигается дальше по многоугольнику (он может двигаться по существующим линиям многоугольника) и рисует линию от точки G к точке F. Здесь снова, из-за границы и существующих линий, должен быть заполнен другой многоугольник (синий) ,

Вот как я подхожу к этому:

1. Всегда есть одна открытая область, представленная многоугольником. Все остальные области не имеют значения.
2. Линия начинается, когда вы двигаетесь от периметра многоугольника во внутренность многоугольника.
3. Линия останавливается, когда вы перемещаетесь из внутренней части многоугольника обратно по периметру.
4. Когда вы останавливаете линию, вы разделяете многоугольник на два.
5. Затем вы решаете, какой из двух полигонов заполнить, а какой оставить в качестве открытой области. В Qix сторона, на которой находился Qix (враг), оставалась открытой, а другая сторона была заполнена.

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

Например, допустим, ваша открытая область представляет собой многоугольник с точками [p0, p1, p2, p3, p4, p5]. Ваша начальная точка находится Aмежду p1и p2, а ваша конечная точка находится Bмежду p3и p4. Новая линия, которая была нарисована [A, s, t, u, v, B]. Сначала мы разбиваем полигон на два сегмента [A, p2, p3, B]и [B, p4, p5, p0, p1, A]. Эти два сегмента вместе образуют оригинальный многоугольник. Затем мы вклеиваем новую строку в каждую (один раз вперед, один раз назад), образуя [A, p2, p3, B, v, u, t, s]и [B, p4, p5, p0, p1, A, s, t, u, v]. Вы заполняете один из этих полигонов, а другой оставляете своей новой открытой областью.

Я не реализовал это и не знаю наверняка, будет ли это работать, но я бы использовал такой подход: подразделение полигонов вместо заполнения полигонов.

Эта проблема связана с несколькими дискретными подэтапами. Вот схема того, что я бы предложил:

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

Я бы сохранил состояние игровых пикселей в массиве Numpy (scipy dot org). Цвет может быть тремя отдельными массивами для RGB, но массив, на котором я сосредоточусь, это массив строк / без строк. Просто инициализируйте его нулями и установите размер игрового поля, и каждый раз, когда игрок проходит через пиксель, установите соответствующий элемент в массиве равным 1. Вы хотите, чтобы они отображались на экране другим цветом. как они твоя линия!

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

. . . | . 
. . . | . 
. . . | x 
. . x < -

Точки - это пустые пиксели, линии - это (очевидно) строки, а X - это пустые пиксели, которые мы хотим выбрать. Мы можем сделать это следующим образом:

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

Получив пиксели со всех возможных сторон пересечения, запустите A * на каждой возможной паре. (См. Http://www-cs-students.stanford.edu/~amitp/gameprog.html#paths или Google a-star для получения дополнительной информации.) Если можно найти путь между парой, удалите один из подключенных пикселей из списка.

После зацикливания и прохождения всех пар оставшиеся пиксели должны находиться в отдельной замкнутой области! Чтобы получить все пиксели в каждой области, выполните заливку из пикселя этой области. Смотрите http://en.wikipedia.org/wiki/Flood_fill .

Удачи!

Ваши области - это просто ряд точек. Тяжелая работа состоит в том, чтобы взять ряд точек, образующих (обычно) вогнутый многоугольник, и триангулировать их, чтобы вы могли визуализировать и, вероятно, проецировать на них текстуру. См. Http://en.wikipedia.org/wiki/Polygon_triangulation для получения более подробной информации.