Terrain composition

[geoo]

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.

[Nepster]

The algorithm throws an exception at "Add N to O somewhere between B and F":
Assume you already have four terrain pieces, that overlap in a linear fashion: X3 -> X2 -> X1 -> X0 (and X3 does neither overlap X1 nor X0, and X2 does not overlap X0). Then add a black piece T that overlaps only X3 and X0. If I understand your algorithm correctly, only X0, X3 and T get grouped together. But now the index of the group must be at least 3, but at most 0.

[geoo]

Ok yes, thanks for spotting this.

I should update it as follows.

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.

Should become

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.

This make the algorithm a bit tricker implementation-wise, but modeling this problem as a graph should make it solvable in roughly quadratic time (at most N BFSs or DFSs as after each one we add at least one tile to S).

EDIT: But that still doesn't solve it. What does solve it, but maybe is more greedy than necessary, is this:

Let F be the front-most tile in S and B the back-most tile in S. Let E (eligible tiles) be the set of tiles in O\S which are between F and B. While there is a tile in E reachable from S via the overlap relation, move it from E to S.

But there should be a way to use the previous version with a clever reordering of tiles.

[Simon]

Excellent read. I'm intrigued because the magic happens with black pieces, not with no-overwrite pieces. A worthy stab at a difficult problem!

Here's another problem case, unrelated to Nepster's problem.



The resulting group must be all of 0, 1, 2, 3, and the black tile on top. This may easily blow up to large parts of a level.

If we exchange the z-order of pieces 1 and 2, the group becomes smaller, only encompassing tiles 0, 3, and the black tile. Do we want huge tiles? Or do we have to bring additional expensive re-ordering algorithms to the table, to minimize the size of the groups? Or am I overestimating the impact of this problem?

-- Simon

[ccexplore]

Terrain composition, ie. the ability to group a set of terrain pieces and treat it as one entity, is definitely sorely needed, independent of whether/how no-overwrite can be removed.

I'm definitely curious to know whether it is always possible to remove no-overwrite.  I'm pretty sure the answer is yes when no eraser (black) pieces are involved, but beyond that I'm less sure and have never dug deeper myself to try to rigorously prove one way or the other.

[Simon]

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.

I am convinced that this algorithm is correct. I call this algorithm the main pass. I remain concerned about the greediness in allocating new tiles. Here are refinements that make the algorithm more complex, but less greedy.

• The output list O will contain both black and normal pieces. It won't contain no-overwrite pieces.
• Before the main pass, we run through the input list, classifying each black piece T as dangerous (= overlaps at least one no-overwrite piece T' that would be drawn later than T, i.e., the main pass will process first T, then T') or as peaceful (= not dangerous). This classification remains constant per black piece, even though we later turn no-overwrite pieces into yes-overwrite.
• During the main pass, on encountering a dangerous black piece, we handle it like geoo's main pass, as quoted above in this post.
• During the main pass, on encountering a peaceful black piece T, we keep T black, and append T to O.
  
• During the main pass, on encountering a no-overwrite piece T, we handle it like geoo's main pass: Make T yes-overwrite, then prepend T to the output list O. That's correct: Even though O may contain black pieces, prepending as yes-overwrite works because none of these black pieces overlap T.

-- Simon

[Nepster]

In the following I will call geoo's algo the following part (input a set of black terrain pieces T and output the new group N + a new ordering of the tiles):

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.

With that let me try to reformulate your suggestion a bit, to see whether I understood your proposal: You essentially want to shift triggering geoo's algo from encountering black pieces to encountering no-overwrite pieces. More precisely:

Code Select Expand

Whenever encountering a no-overwrite piece N, trigger geoo's algo for the initial set T = {all N-dangerous black pieces}.
Here an N-dangerous piece B is defined as follows:

Code Select Expand


- B is black
- B has lower index than N
- There exists a pixel p, which is solid in both B and N, but not solid in any piece that has index between B and N

i.e. any black piece that defines an obstruction to turning N into the very first piece.

Edit: Clarification of what I talk about compared to Simon's main pass.

[Simon]

Definition: The main pass is all of geoo's algo that I quoted. It is not the sub-algorithm that triggers on encountering a black piece T in the input list.

My algo does a classification, then a modified main pass. The main pass has a complicated path-finding method for handling black pieces. I'd like to reduce how often we call the black-piece-handling method.

At a glance, you introduce a completely new viewpoint: You assert that I shift the work from black pieces to no-overwrite pieces. I didn't look at it that way, but maybe it's an equivalent formulation? I'll shower first, then re-read your post. I will answer later again.

Overlap can mean one of these: a) selection boxes overlap, b) on the game map, the earlier tile shares a to-be-colored pixel with the later tile, c) shares a pixel on the map and no pieces in-between share that pixel. I wrote the algo refinement delilberately agnostic of a), b), c), so either will work.

-- Simon