00_head

We have mentioned and shown a couple of times that our basic level art is mainly made out of small chunks corresponding to pieces of geometry – flats and corners with different sizes and decorations. With colored outlines and world-mapped patterns this makes it relatively quick to add basic art to a level, but depending on the complexity of the geometry it can still take the better part of an hour.

Since we are only two people with limited time, a while back we added functionality to automate the placement of these pieces – removing the mundane tasks of giving the level shape and readability to allow us to focus on the creative side of making each level look distinct.

Going into this, we had a few requirements;

  • It had to work with existing content as we already had some level art and a lot of levels.
  • It also had to work with the same object types as the editor as we want to be able to change around the result after autogeneration had happened.
  • Since we wanted to do this for several different art styles and have quick turnaround, it had to be completely data-driven and allow for a controlled degree of randomness.

Debug art

Pictured is a typical Backworlds level – most of our geometry is made out of axis-aligned boxes. The geometry is not fixed to a grid but can have any position or size – this is not particularly convenient from a programming or design standpoint, but it allows us to be flexible. In essence, placing art on the level is a simple matter of following the box edges.

After box split and overlap removal

The first step of the method is to split boxes until there are no edges with points from other boxes in the middle – in essence, we want each edge of every box to either align with an edge from another box that has exactly same length, or nothing at all. We then remove all the overlapping boxes.

At this point, we can extract a number of points from the corners of our split boxes, and a number of edges going between these points – these edges are where we might have to place art.

Point classifiction

(Saturation/Value manipulated for clarity)

Since all boxes are axis-aligned, a point can be classified by which of its quadrants are filled and not – there are essentially six possible configurations;

  • We’ll never have the case where no quadrants are filled since every point is the corner of a box.
  • If all quadrants are filled, we are not drawing any lines to this point – we remove the point and all lines connected to it.
  • If two connected quadrants are filled, this point is in the midpoint of a straight line – we can remove the point and merge the two lines connected to it.
  • If only a single quadrant is filled, we keep the point and tag it as an outer corner.
  • If three quadrants are filled, we keep the point and tag it as an inner corner.
  • If two opposing quadrants are filled, we split the point and tag both new points as outer corners. Due to how we build levels this is not something that usually happens.

Filler sprites

First thing we do is add filler art to all the boxes – due to how the engine works we get some overlap here, but since we merge each parallax layer in release builds it doesn’t really matter.

Corners added

Second, we add inner and outer corners to all points. We pick random corners from a list of sprites defined in data, but each corner also needs to be small enough that it can fit on the lines that connect to the point. To make sure we never end up without a corner, we always have one each inner and outer corner piece that are very small.

Min/Max overlap values for pieces

Finally, we add the straight edges. All of the sprites have a width and a value determining how much it is allowed to overlap on the edges – this way, each graphic have a min and max length. For every line between points, we add edge pieces while keeping track of the total min and max length and stop when the mean value is greater than the length of the line. We then distribute these edge pieces along the line – after every piece, we add a random offset within the piece’s overlap range and keep track of the total added distance to make sure we do not make the line too long or too short.

Completed autogeneration. Again, Hue and value have been modified for visibility

The last few steps of this operation are remarkably complex due to the different fudge values of different pieces, a few things I learned from this that I would have done differently had I begun today;

  • It would have been faster to make slight modifications to the edge art than to have to track them in data – ensuring consistency in how the lines were placed would not really have made the sprites more difficult to work with manually but it would have made them much easier to process. I wanted to avoid making any changes at all to the source art, but by doing that I had to specify complex cases in data that could have been avoided if we had just made small changes to the images.
  • When using edge detection and geometric values, be careful with threshold values. On numerous occasions I got visual artifacts or unresolved geometry because boxes that were only a few pixels apart had inadvertently been merged or thin boxes removed. I ended up barely using any threshold values and it worked better.
  • Randomness is only useful so far. Randomizing pieces was a given, but randomizing their individual offsets along a line to nudge them a few pixels in either direction was probably not noticeable. It also created a ton of extra work since I needed to keep track of the max and min potential overlap and how much I had to nudge each piece to stay within limits.
  • Even though the sprites need to function like regular objects, make sure they are distinguishable from manually placed art even after the level has been saved and reloaded. We frequently add or remove pieces to the autogeneration setup or decided to try something new, so it was important to be able to quickly remove old art.