PyGame QIX clone, filling areas

Question

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).

Answer 1

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.

Answer 2

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!

Answer 3

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

Answer 4

What I did was represented the main area with a grid, with values depending on grid content (empty area (0), inner polygon (1), current path(2), old (4), fast filled (8), ...). Single byte is enough to store the information of a grid.

In order to have newly created polygon at least size 1 + all borders, minimum movement in each directions was always 3 grids.

Inner polygon is the polygon which borders unclaimed area. Movement is only possible on grids that belong to inner polygon (other values are mainly for painting purposes).

My approach was:

• You draw a path, until you intersect with current inner polygon
• The properties of this path are: first (path[0]) an last (path[-1]) points lies on current inner polygon, but for the second point (path[1]) this holds true in all cases: if we find grids in all four directions, two grids would be on the path, one would be in the area without Qix (inner) and one would be in the area with Qix (outer).
• for the duration of searching I set the second point (path[1]) in the path to empty (0)
• I randomly select one of the two points (inner, outer)
• I perform A* from Qix's location to path[1]
• if outer was selected, it would be found as previous node of the node corresponding to grid path[1] (there is no need to reconstruct the path, we check the previous node of node we searched for).
• the value of path[1] is set back to current path.

Now we clearly know which point is inner and which is outer. But, before we continue, we need to identify the common edges of polygon which still belongs to inner polygon and newly created claimed polygon:

• we create new point (TBP, temporary blocking point), we will use this point to force A* to search in a single direction only
• if outer lies on inner polygon then TBP <- outer, else TBP is point that lies in an opposite direction of vector path[0] -> path[1], from path[0] (two cases: whether we start new polygon perpendicular on some edge or as extension ...)
• set value of TBP to empty space (0)
• set values for first (path[0]) and last node (path[-1]) in path to inner polygon
• perform A* from first (path[0]) and last node (path[-1]). We are searching only on grids that has values inner polygon. Only one solution is possible. Change values to nodes in the path to old. This path is removed from inner polygon and movement on it are not possible anymore.
• set value of TBP to inner polygon (1)

And finally:

• set all nodes in the path to inner polygon (1)
• perform FloodFill from inner point

Algorithm can be applied in any language.