Level designers often like to cut terrain pieces into bits and paste them together into new shapes. Currently this needs to be done using black (eraser) terrain and the no-overwrite flag which is confusing and cumbersome, especially for more complex arrangements.
I propose to do away with the no-overwrite flag and support terrain composition instead. This would work with the following grouping functionality:
The designer selects an arrangement of terrain pieces (which may include black pieces), and can group them together into a single new terrain piece. Thus a new terrain piece is defined that behaves like a regular terrain piece. Parts of the composite piece that are covered by black terrain also part of the composite piece will become transparent. The original terrain pieces involved in the grouping are removed, but the game remembers which pieces a composite piece is comprised of, and also creates a new memory bitmap for this composite piece. Optionally, there could also be an ungroup functionality, which decomposes a composite piece into its parts.
Composite pieces can be defined recursively using existing composite pieces. The level stores how each defined piece is composed, and creates an internal memory bitmap of each such piece as it reads its definition from the level file. If a composite piece is not used in the level, the editor should ensure that the definition is also removed from the level file. Once the player loads a different level, internally the bitmaps of composite pieces can be deleted.
Backward compatibility.Existing levels exploiting no-overwrite can be converted automatically.
Currently, the drawing algorithm draws the pieces in the order in which they are in the level file from back to front, black terrain erases, no-overwrite tiles don't overwrite already drawn tiles and are only drawn over void.
We achieve the same result as follows:
Input: An ordered list of terrain pieces, optionally with black terrain or no-overwrite flag.
Output: Definitions of composite terrain pieces, and an ordered list of (composite) terrain pieces (free from black or no-overwrite pieces) to be drawn from back to front.
We read the input list in order. At any given time, the current output O is an ordered list of (composite) terrain pieces. Three cases, depending on the next piece T in the input list:
- T is normal terrain: append T to O.
- T is no-overwrite terrain: prepend T to O. (Note: This works because O contains no black/no-overwrite pieces.)
- T is black terrain: Initially, define S as the set of tiles in O that T overlaps.
While there exists a tile T' in O\S such that there are tiles F and B in S with F overlapping T' and T' overlapping B, add T' to S. While there exists a sequence of tiles T1 -> T2 -> ... -> Tn in O\S such that there are tiles F and B in S with F -> T1 and Tn -> B, add T1, ..., Tn to S. Here -> denotes the overlapping relation. Group the tiles in S into a new tile N, and remove S and T from O. Let F be the tile with the lowest index overlapping N, and let B the tile with the highest index that is overlapped by N. Add N to O somewhere between B and F. (The following is Nepster's idea, with a slight fix:) Define a set S+ of all terrain pieces of O\S that are reachable via -> from S (i.e. via a sequence for forward edges). Then reindex them starting from max(S), while keeping their order. Put N in the list right before S+, and delete T and S from O.
Implementation notes:
- If we want to allow composing steel and normal tiles, you'll have to remember the mask of each composite tile with bits for solidity and steel.
- If a level does not contain no-overwrite pieces, no conversion is necessary.
- Multiple consecutive black pieces can be processed in step, resulting in only one grouping. Black pieces that are not overlapped by anything else can just be added to the end of the list without grouping.
- While processing terrain pieces, you could maintain a directed graph modeling the overlap relation within O. As a new piece is added to O, the graph needs to be updated. When a grouped tile is added (and thus some pieces deleted from O), I think the edges pointing to the new tile can be inferred from the edges belonging to the deleted vertices.