I made a 2D platformer randomization crate called Shiftnanigans (https://github.com/AustinHellerRepo/Shiftnanigans) as part of my work on the open source game Jumpy (https://github.com/fishfolk/jumpy). Within the map editor of Jumpy, the Randomize button will randomize the placement of tiles and elements, maintaining the general structures of the map. I've described the two abstract concepts and sets of structs used to accomplish this functionality below. This is just a general overview, but I am happy to elaborate further if anyone has questions about the algorithms and data structures used.
Web demo (click Map Editor -> Open Map -> Level #12 -> Randomize (in the top right)): https://fishfolk.github.io/jumpy/player/latest/
The PixelBoard and PixelBoardRandomizer
In order to randomize a 2D platformer or tile-based map, the PixelBoardRandomizer takes in a grid of "pixels" as a PixelBoard, detects wall and non-wall pixels, groups them together, and finds locations for those groups such that no two groups overlap while also maintaining contact with adjacent walls (or not, as applicable). Wall chunks that do not make contact with the corners are considered "wall segments" and can shift around along the edge of the map. Each randomized PixelBoard can be repeatedly randomized itself without affecting the size or adjacency of pixel groups, allowing repeated execution of the randomization function on a previously randomized PixelBoard.
To optimize this process, shifters (described below) are ultimately used to compare pixel group locations to each other, incrementing to the next randomized location for the specific pixel group. All pixel groups are ultimately compared to each other to ensure that they are all valid together in some combination of locations. Instead of placing all of the pixel groups down randomly one at a time just to find out that the last pixel group won't fit (ultimately because the very first pixel group is in a bad spot), each pixel group is paired up with each other pixel group as a cartesian product and is compared together.
The PixelBoard and PixelBoardRandomizer Continued
This is where it gets a little complex. Each pair of pixel groups iterates over all possible locations for those pixel groups in a round robin cycle, allowing each pair of pixel groups an opportunity to check if their current random locations are valid together. As valid pairs of pixel groups are discovered, a hypergraph is filled with connecting edges between hypergraph node's subnodes where each hypergraph node is conceptually a pixel group, a subnode is a location for that pixel group, and the edge indicates that the two locations of each pixel group are valid together. Once a cliché is discovered between all hypergraph nodes, that indicates that each pixel group location connected together within the cliché are all valid together and would form a valid, randomized PixelBoard.
Shifters and Incrementers
Shifters are just 2-dimensional skewed arrays with a pointer to a current cell where navigation through the array is defined by a few basic operations: forward, backward, and increment. The shifter starts with a column pointer in the 0th row's 0th column. You can imagine that an increment moves the current column pointer down the array, a forward action creates a new active column pointer in the next column at the top row of the array, and a backward action removes the current column pointer and makes the previous column pointer active where it left off. If any action is not possible a None is returned, indicating that a backward action must occur so that the previous column can increment once, and then return forward at the top of the column again with a new column pointer, ultimately iterating over all possible combinations of column cells.
An incrementer returns a collection of cells. One of the most useful applications is being basically a wrapper on a shifter that returns, with each iteration of the incrementer, a collection of cells (one per column) as a permutation of the underlying shifter as it moves forward and increments, only moving backward with subsequent iterations of the incrementer that would cause the underlying shifter to increment or move backward and then move forward again with each iteration.
With these two data structures understood, it is possible to create many interesting variations of shifters and incrementers that "fail fast" while performing some interesting traversal of a state space. For example, the pair of pixel groups iterate over their possible locations in an expanding square sequence/permutation using the ShiftingSquareBreadthFirstSearchShifter. This could be improved upon by implementing a decrement movement on shifters and utilizing that functionality to search in a triangular shape outward instead of a square.
Efficiencies:
- Shifters make it very easy to find invalid pairs of column cells and fail fast as opposed to generating a long list of column cells just to discover that the first pair are invalid together.
- Only pairs of pixel groups that could ever conflict or overlap are compared (so one wall isn't paired with another wall, for example).
- When a new edge is added to the hypergraph, that edge is the starting point for searching for a cliché within the hypergraph.
- A cliché search is only performed if each hypergraph node's subnode for the new edge is connected to all other hypergraph nodes at least once.
Next steps:
- Allow for specifying that "wall segments" should not shift around, greatly improving performance but reducing degree of randomness.
- Create a few examples in the Github repository based on common uses of this functionality
- Implement a decrement action for shifters, permitting more efficient state space search algorithms.
- Create trait implementations that more easily convert existing iterators into variations of shifters or incrementers.
