PyGame QIX clon, áreas de relleno

Estoy jugando con PyGame.

Ahora estoy tratando de implementar un clon QIX .

Tengo mi bucle de juego y puedo mover el jugador (cursor) en la pantalla.

En QIX, el movimiento del jugador deja un rastro (cola) en la pantalla, creando una polilínea.

Si la polilínea con los límites de la pantalla crea un polígono, el área se llena.

¿Cómo puedo lograr este comportamiento?

¿Cómo almacenar la cola en la memoria?

¿Cómo detectar cuándo se crea una forma cerrada que se debe llenar?

No necesito una solución de trabajo exacta, algunos indicadores, algunos nombres serían geniales.

Al principio, solo está el borde gris, donde el jugador puede mover el cursor.

• Primer escenario:

El usuario mueve su cursor desde el punto A hasta el punto B, dibujando la multilínea roja hasta el punto C. En este punto, debido a que cruza el borde, el punto A debe conectarse automáticamente con el punto C, creando un polígono, que debe rellenarse ( esas cosas naranjas en mi dibujo). Llenar el polígono es muy simple en PyGame, porque proporciono la secuencia de puntos, y PyGame se preocupa del resto.

• Segundo escenario:

El usuario se mueve en el borde hasta el punto D, desde donde dibuja una línea hasta el punto E. Debido a que está cruzando la línea del polígono anterior, y con sus líneas y el borde se puede crear otro polígono, también debe rellenarse. (el verde).

• Tercer escenario:

El jugador se mueve más allá en el polígono (puede moverse en líneas poligonales existentes) y dibuja una línea desde el punto G hasta el punto F. Aquí nuevamente, debido al borde y las líneas existentes, se debe llenar otro polígono (el azul) .

Así es como lo abordaría:

1. Siempre hay un área abierta única, representada por un polígono. Todas las demás áreas son irrelevantes.
2. Una línea comienza cuando te mueves desde el perímetro del polígono hacia el interior del polígono.
3. Una línea se detiene cuando te mueves desde el interior del polígono hacia el perímetro.
4. Cuando detiene la línea, ha dividido el polígono en dos polígonos.
5. Luego, decide cuál de los dos polígonos se rellenará y cuál se mantendrá como área abierta. En Qix, el lado en el que estaba el Qix (enemigo) permaneció abierto y el otro lado se llenó.

¿Cómo se subdivide el polígono? Utiliza los puntos finales de su línea para dividir el perímetro del polígono en dos secciones, luego usa la nueva línea para completar esas dos secciones en nuevos polígonos.

Por ejemplo, supongamos que su área abierta es un polígono con puntos [p0, p1, p2, p3, p4, p5]. Su punto de inicio Aocurre entre p1y p2, y su punto final Bocurre entre p3y p4. La nueva línea que se dibujó es [A, s, t, u, v, B]. Primero dividimos el polígono en dos segmentos [A, p2, p3, B]y [B, p4, p5, p0, p1, A]. Estos dos segmentos juntos forman el polígono original. Luego pegamos la nueva línea en cada uno (una vez hacia adelante, una vez hacia atrás), formando [A, p2, p3, B, v, u, t, s]y [B, p4, p5, p0, p1, A, s, t, u, v]. Rellena uno de estos polígonos y mantiene el otro como su nueva área abierta.

No he implementado esto y no estoy seguro si funcionará, pero ese es el enfoque que usaría: subdivisión de polígonos en lugar de relleno de polígonos.

Este es un problema que involucra múltiples subpasos discretos. Aquí hay un resumen de lo que sugeriría:

• Espere hasta que el jugador forme una intersección de varias líneas.
• Obtenga un píxel de cada lado de la intersección
• Pathfind para ver si pueden conectarse entre sí
• Los píxeles que no pueden conectarse entre sí son áreas separadas
• Realice un relleno de inundación para obtener todos los píxeles en el área

Almacenaría el estado de los píxeles del juego en una matriz Numpy (numpy dot scipy dot org). El color podría ser tres matrices separadas para RGB, pero la matriz en la que me centraré es la matriz de línea / sin línea. Simplemente inicialícelo con ceros y ajústelo al tamaño de su campo de juego, y cada vez que el jugador pase por un píxel, configure el elemento correspondiente en la matriz a 1. Querrá mostrarlos en la pantalla con un color diferente. , ya que son tu línea!

Cada vez que se mueve el píxel del jugador, verificaba si pasaba (y dibujaba una línea al lado) una línea existente. Si es así, obtendría un píxel de cada división posible:

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

Los puntos son píxeles vacíos, las líneas son (obviamente) líneas y las X son los píxeles vacíos que queremos seleccionar. Podemos hacerlo de la siguiente manera:

• Agregue todos los píxeles vacíos adyacentes al jugador / intersección a una lista.
• Recorra la lista eliminando píxeles si el siguiente elemento de la lista es adyacente (en el campo del juego) al que está utilizando.

Una vez que tenga píxeles de todos los lados posibles de la intersección, ejecute A * en cada par posible. (Consulte http://www-cs-students.stanford.edu/~amitp/gameprog.html#paths o Google a-star para obtener más información). Si se puede encontrar una ruta entre un par, elimine uno de los píxeles conectados de la lista.

Después de recorrer y recorrer todos los pares, los píxeles que quedan deben estar en un área separada y cerrada. Para obtener todos los píxeles en cada área, realice un relleno de inundación desde el píxel de esa área. Ver http://en.wikipedia.org/wiki/Flood_fill .

¡Buena suerte!

Sus áreas son solo series de puntos. El trabajo duro viene con tomar la serie de puntos que forman (generalmente) un polígono cóncavo y triangularlos para que pueda renderizar y probablemente proyectar una textura sobre ellos. Ver http://en.wikipedia.org/wiki/Polygon_triangulation para más detalles