PyGame QIX clone, filling areas

I'm playing around with PyGame.

Now I'm trying to implement a QIX clone.

I have my game loop, and I can move the player (cursor) on the screen.

In QIX, the movment of the player leaves a trace (tail) on the screen, creating a polyline.

If the polyline with the screen boundaries creates a polygon, the area is filled.

How I can accomplish this behaviour ?

How store the tail in memory ?

How to detect when it build a closed shape that should be filled ?

I don't need an exact working solution, some pointers, algo names would be cool.

At start, there is only the gray border, where the player can move his cursor around.

• First scenario:

The user moves his cursor from point A trough point B, drawing the red multiline until point C. At this point, because of crossing the border, the point A should be connected with point C automaticaly, creating a polygon, which should be filled (that orange stuff on my drawing). Filling the polygon is damn simple in PyGame, because I provide the sequence of points,and PyGame cares of the rest.

• Second scenario:

The user moves on the border to point D, from where he draws a line to point E. Because he is crossing the line of the previous polygon, and with his lines and the border another polygon can be created, it should be filled too. (the green one).

• Third scenario:

The player moves further on the polygon (he can move on existing polygon lines), and draws a line from point G to point F. Here again, because of the border and the existing lines, another polygon should be filled (the blue one).

• Maybe there is some answers here (similar question) : gamedev.stackexchange.com/questions/26377/… – tigrou Apr 15 '12 at 22:10
• Thanks, but the link shows primitive use cases. I updated my question, so maybe it's more clear what I try to acomplish – astropanic Apr 17 '12 at 19:07

Here's how I'd approach it:

1. There is always a single open area, represented by a polygon. All other areas are irrelevant.
2. A line starts when you move from the perimeter of the polygon into the polygon's interior.
3. A line stops when you move from the polygon's interior back onto the perimeter.
4. When you stop the line, you have divided the polygon into two polygons.
5. You then decide which of the two polygons to fill, and which to keep as the open area. In Qix, the side that the Qix (enemy) was on stayed open and the other side was filled.

How do you subdivide the polygon? You use the endpoints of your line to divide the polygon perimeter into two sections, then use the new line to complete those two sections into new polygons.

For example, let's say your open area is a polygon with points [p0, p1, p2, p3, p4, p5]. Your start point A occurs between p1 and p2, and your end point B occurs between p3 and p4. The new line that was drawn is [A, s, t, u, v, B]. We first split the polygon into two segments [A, p2, p3, B] and [B, p4, p5, p0, p1, A]. These two segments together form the original polygon. Then we glue the new line into each (once forwards, once backwards), forming [A, p2, p3, B, v, u, t, s] and [B, p4, p5, p0, p1, A, s, t, u, v]. You fill one of these polygons and keep the other as your new open area.

I've not implemented this and don't know for sure if it will work, but that's the approach I would use: polygon subdivision instead of polygon filling.

This is a problem involving multiple discrete substeps. Here is an outline of what I'd suggest:

• Wait until the player forms an intersection of multiple lines
• Get a pixel from each side of the intersection
• Pathfind to see if they can connect to each other
• Pixels that cannot connect to each other are separate areas
• Perform a flood-fill to get all pixels in the area

I would store the state of the game's pixels in a Numpy array (numpy dot scipy dot org). Color could be three separate arrays for RGB, but the array I'll be focusing on is the line/no line array. Just initialize it with zeros and set it to the size of your game field, and every time the player passes through a pixel, set the corresponding item in the array to 1. You'll want to display these on the screen as a different color, as they're your line!

Every time the player pixel moves, I would check to see if it passed (and drew a line next to) an existing line. If so, I would get a pixel from each possible division:

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


Dots are empty pixels, lines are (obviously) lines, and Xs are the empty pixels we want to select. We can do so in the following manner:

• Add all empty pixels adjacent to the player/intersection to a list.
• Loop through the list removing pixels if the next item in the list is adjacent (in the game field) to the one you're on.

Once you have pixels from all possible sides of the intersection, run A* on each possible pair. (See http://www-cs-students.stanford.edu/~amitp/gameprog.html#paths or Google a-star for more information.) If a path can be found between a pair, remove one of the connected pixels from the list.

After looping and pathing for all pairs, the pixels that remain should each be in a separate, enclosed area! To get all the pixels in each area, perform a flood fill from that area's pixel. See http://en.wikipedia.org/wiki/Flood_fill.

Good luck!

Your areas are just series of points. The hard work comes with taking the series of points forming (usually) a concave polygon and triangulating them so you can render and probably project a texture on to them. See http://en.wikipedia.org/wiki/Polygon_triangulation for more details

• it's not a problem with triangulation, PyGame take care of that. I updated my question with an image, and some use cases, take a look so you get the point. Thanks anyway – astropanic Apr 17 '12 at 19:09