1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
function block_char(block_id) local chars = "abcdefghij" return sub(chars, block_id, block_id) end function can_shift(line) return sub(line, #line, #line) == "-" end -- shifts all blocks of the given id or higher rightwards one cell, -- leaving all blocks left of that id unchanged function shift(line, block_id) local char = block_char(block_id) local pos = 1 for i = 1, #line do if sub(line, i, i) == char then pos = i break end end local pre = sub(line, 1, pos-1) local post = sub(line, pos, #line-1) return pre.."-"..post end function find_solutions(blocks, length, min_spaces) -- build and store the leftmost solution local line = "" for block_id = 1, #blocks do for i = 1, blocks[block_id] do line = line..block_char(block_id) end if block_id ~= #blocks then for i = 1, min_spaces do line = line.."-" end end end if (#line > length) return {} -- no solutions, can't fit while #line < length do line = line.."-" end local solutions = {line} find_spreads(solutions, line, 1, #blocks) return solutions end function find_spreads(solutions, line, block_id, num_blocks) local my_line = line while can_shift(my_line) do if block_id < num_blocks then find_spreads(solutions, my_line, block_id + 1, num_blocks) end my_line = shift(my_line, block_id) solutions[#solutions + 1] = my_line end end blocks = {2, 2, 2} length = 8 min_spaces = 0 solutions = find_solutions(blocks, length, min_spaces) |
Let's say we want to find every possible way of placing 3 blocks each of length 2 into a line which is 8 units long. There are 10 possible solutions:
How can we find these? I first encountered this problem during my honours project and the solution involves a nice little recursive function, so I thought I might as well share. We always begin by building the equivalent of the topmost solution above: all blocks adjacent to each other and as far left as possible. From here we take the rightmost block and shift it rightwards one cell at a time, storing the result, until we hit the end of the line. Then we grab the preceding block and shift that by one cell, then continue shifting the last block again. This will find all the configurations in the order given above, top to bottom. Below is a simple implementation in Lua where we're treating the line as a string for which each block has it's own letter and empty cells are '-'. The recursion happens in the find_spreads function.
Notice that this can also handle having a minimum number of spaces between each pair of blocks. I've made a little PICO-8 program to demonstrate the algorithm. Below left you can see the rendering of our example setup: block lengths of 2, 2, 2; line length of 8 and no minimum number of spaces. On the right is every configuration for block lengths 1, 2, 3; line length 11 and at least 1 space between each pair. If you didn't care about preserving block order and simply wanted every configuration of a set of blocks, you could run the above algorithm multiple times with every possible rearrangement of the initial block order.
"A composition of an integer n is a way of writing n as the sum of a sequence of (strictly) positive integers" - Wikipedia.
A composition can include multiple integers of the same value and the order of the values matters, so each unique arrangement of a composition of n is also a distinct composition of n. Each positive integer n has 2^(n-1) compositions. For example 5 has 2^4=16 compositions: Compositions of 5: { 5 } { 4, 1 } { 1, 4 } { 3, 2 } { 2, 3 } { 3, 1, 1 } { 1, 3, 1 } { 1, 1, 3 } { 2, 2, 1 } { 2, 1, 2 } { 1, 2, 2 } { 2, 1, 1, 1 } { 1, 2, 1, 1 } { 1, 1, 2, 1 } { 1, 1, 1, 2 } { 1, 1, 1, 1, 1 }
So why do we care and how do we find them? Well for my purposes I needed to find the compositions of n as part of my honours project, but it seems like something that could come up in all sorts of areas and it was an interesting problem to have to solve. As for how to find them, the point of this post is to share the recursive algorithm I came up with because I think it's rather elegant. This is essentially a more detailed, less formal explanation of my algorithm than what I wrote for Appendix C of my dissertation.
Finding the compositions with only 2 elements
In my project I needed to separately find all the compositions with exactly 2 elements and all the compositions with 3 or more. My algorithm for finding those with 3+ elements can in fact be used to find all compositions, but I thought I might as well share how you would find only those compositions with exactly 2 elements as well.
It's pretty simple really. To find every pair of positive integers which sum to n, just start with n-1 and 1 and keep decrementing the former and incrementing the latter until you have 1 and n-1. Obviously there will be n-1 compositions of n with exactly 2 elements. As an example here's some Lua code:
What follows is a print function, calling code and the resultant output:
4 compositions of 5: { 4, 1, } { 3, 2, } { 2, 3, } { 1, 4, } Finding all the compositions of n
The way my algorithm works is conceptually quite simple. You start with the set of n 1s and store a copy, since it's a valid composition of n. Then you remove the last 1 and add it in turn to each of the other numbers, storing the result. This process repeats recursively, backtracking up the recursion whenever the last number isn't a 1.
The diagram below illustrates this idea for finding the compositions of 4. The boxes collect all the results garnered from one function call and the arrows show the recursion. First we start with our set of 4 1s. Whenever we encounter an arrow it means 'remove the last 1 and add it to each of the remaining numbers'. The list of compositions found is on the right in the order that they were found (top to bottom). Notice that one of the solutions was found multiple times.
One duplicate set might not seem like much, but we'll be storing exponentially more duplicates as n increases. For example we would store 23 compositions of 5 even though there are only 16 unique compositions. To fix this we just need to start adding the 1 from further into the set. If we find the ith composition within a single function call (box in the diagram) then when we remove the last 1 we start adding it from the ith number in the set. For example:
First we have our set of 1s. We remove the last 1 (giving us { 1, 1, 1 }) and begin to add it to each remaining number in turn, starting with the 1st number. This gives us the set { 2, 1, 1 }, which ends in a 1 so we recurse. This was the 1st composition found in this function call so we start on the 1st number again, getting { 3, 1 }. Again we recurse and get { 4 }, which doesn't end in a 1 so we backtrack. Now we add our 1 to the 2nd number from the { 2, 1, 1 } set, giving us { 2, 2 }. This doesn't end in a 1 so we backtrack. We add a 1 to the 2nd number from our initial set, giving { 1, 2, 1 }. This ends in a 1 so we recurse, but it's the 2nd solution we found in this function call (box) so we start adding from the 2nd number, giving { 1, 3 } instead of duplicating the { 2, 2 } set. Here we backtrack again to get our final composition { 1, 1, 2 }. We know we're done when we've backtracked all the way to our original set.
Below is some Lua code for the complete algorithm, with some calling code at the end and the resulting output afterwards.
16 compositions of 5: { 1, 1, 1, 1, 1, } { 2, 1, 1, 1, } { 3, 1, 1, } { 4, 1, } { 5, } { 3, 2, } { 2, 2, 1, } { 2, 3, } { 2, 1, 2, } { 1, 2, 1, 1, } { 1, 3, 1, } { 1, 4, } { 1, 2, 2, } { 1, 1, 2, 1, } { 1, 1, 3, } { 1, 1, 1, 2, }
I mentioned before that I wanted to be able to find only compositions with 3 or more elements. If you uncomment the first line from the find_comps function then it will do just that. In fact you can set this number to whatever you like and it will only find compositions with at least that many elements. For example:
11 compositions of 5: { 1, 1, 1, 1, 1, } { 2, 1, 1, 1, } { 3, 1, 1, } { 2, 2, 1, } { 2, 1, 2, } { 1, 2, 1, 1, } { 1, 3, 1, } { 1, 2, 2, } { 1, 1, 2, 1, } { 1, 1, 3, } { 1, 1, 1, 2, }
September 2015 - May 2016
Demo
Here's an overview of what my project was about and how it works. If you just want to see the puzzle solvers in action jump to ~14:30.
Dissertation
Download
You can download the program for yourself if you'd like (you'll need a Windows PC with support for DirectX 11). It comes with my set of test models and a copy of my dissertation. I'm quite proud of how much I managed to achieve with this project and of the quality of my dissertation. There were a lot of very interesting problems to solve and creating so many different algorithms to solve them was one of my favorite things about this project. I think I can sum it up best with this extract from my conclusion section:
"This project has covered a lot of new ground and involved the creation of many algorithms for tackling the sub-problems within the larger goals of generating and solving 3D puzzles. These include:
Enemies, areas and the difficulty indexThe Enemy class was written with extensibility in mind. Although I only ended up putting one enemy type in the game (spikes), the placement of and interactions with those enemies are designed to be generic or easily extended. An example of this is the difficulty index. Each enemy type has a difficulty index which is higher the more challenging the enemy is. Spikes have the lowest difficulty index of 1 because they are simply static obstacles which the player has to avoid touching. If there were enemies which patrolled or had attack patterns, they would have a higher difficulty index. In my post about the tile map generation I explained how each room consists of a 4 x 4 set of Area instances. I also explained that not every area has to be part of the room's path (i.e. it can be a solid block of tiles) and that most areas also have a chance of becoming a tunnel; a narrower play space which won't have enemies or collectables inside. Enemies also won't be placed in the start or end area of a room. The number of enemies spawned per room depends on the current level, but the number of areas available in that room to spawn enemies in depends on the tile map generation. With that in mind, the pseudocode for placing enemies is as follows: - Calculate a total difficulty index for the room based on the current level. - Count how many areas are available to spawn enemies in. - Assign all available areas an equal portion on the room's difficulty index. - Randomly assign any leftover difficulty index resulting from integer division. - For each area:
This algorithm assumes that at least one enemy type has a difficulty index of 1 to fill gaps in an area’s difficulty. Each enemy type has different logic to decide whether it is possible and where to spawn within an area. For example spikes will only be spawned adjacent to the floor, ceiling or walls of an area and will not be spawned covering the gaps used for travelling between areas. Note that unless it were included in the "Is there somewhere I can spawn?" check for each enemy type, there’s nothing stopping enemies from being spawned on top of each other. In fact this currently happens a lot on the higher difficulty levels where there simply isn't enough floor/wall/ceiling space to accommodate all of the spikes. While this tends to work quite well and could easily be expanded upon, there is a major issue related to the tile map generation. There are only minimal checks performed during the tile map generation to ensure that there are a reasonable number of areas that could house enemies. For example a room which connected the start and end areas exclusively with tunnels would be rejected since there'd be nowhere to place enemies or collectables. More sophisticated checks would need to be included if there were more complex enemy types (and more enemy types in general). In keeping with the extensibility focus, there's actually functionality for the player to fire projectiles and for enemies to be damaged by and eventually die from these impacts, however the only enemy type in the game is the spikes, which cannot be killed. Gotta get that sweet, sweet goldThe level generation often produces side areas and sets of side areas which are not connected to the path from start to end. I wanted a reason to entice players to explore these areas, which led to the golden collectables. Each is worth 10 points but perhaps more importantly will also heal the player a single health point (up to the maximum health of 100). These collectables are the only way to recover lost health. There are 20 collectables per room and 4 rooms per level. If the player picks up all 80 in a single level they'll get 200 bonus points once they pass through the exit, meaning that there’s a total of 1000 points per level up for grabs. The actual spawn logic for collectables is very simple. Collectables are only spawned in areas which can also contain enemies in order to force a risk/reward scenario. They are placed on a random tile within the area which isn't adjacent to a surface. As with enemies there is nothing to stop collectables being spawned on top of each other. If a room has very few areas in which enemies and collectables can spawn, each of those areas will have a very dense set of collectables and enemies. Oh God Why 2: Why, God, Why?!I enjoyed making Oh God Why immensely, especially researching and developing my own level generation algorithms. The rest of the game and how it works is all fairly standard stuff though, so I won't bore you with it.
Needless to say, I'm quite proud of the project and what I managed to do. I wanted to share the game and let other people experience it, which led me to write these articles and to start work on a PC port which is nearing completion. I'll likely finish it in the next few days, so stay tuned and you'll be able to muck around with Oh God Why yourself soon. January 2014 - May 2014 Click here for an overview of Oh God Why. Click here to see how the tile map itself is generated. Generating the tile map in Oh God Why is the first phase of the level generation process. It defines the geometry of the level in the visual space of sprites, but those visuals also need to be represented in the physics space of Box2D for collision detection purposes. This is the second phase. Box2D is a 2D physics system which uses rigid bodies to represent objects. Normally you'd have one body per sprite, such as for the player (which is really just a rectangle). But having one body for each tile is hugely inefficient and causes the physics system to slow down considerably (I tried that first; start out simple). There's another problem with doing it the brute-force way: due to the way Box2D works it's possible to collide with the edge between two adjacent bodies, even if they line up perfectly and there's no gap between them. This meant that as much as possible I had to have a single body represent each continuous surface in its entirety. If you look at a screenshot example of the tile map we're trying to cover, such as the sample room I used in the previous post: It should become apparent that it isn't possible to break that space up into rectangles and have every player-facing surface represented as a single edge. For example, try breaking up the area in the lower left quarter. You might come up with something like this: No matter how you do it, at least one edge will be represented by more than a single body. Once I realized this it became clear I had to prioritize horizontal surfaces over vertical ones, since the player spends much more time in contact with lateral surfaces. PseudocodeBefore I explain how I did things, I'll show the results. Here is a debug screenshot of the now familiar sample room. The Box2D bodies for the tile map are shown in semi-transparent pink with yellow outlines: Every horizontal surface is represented by a single body, but some vertical surfaces have multiple adjacent bodies (including that troublesome area in the bottom left). Here's what I did: - Tiles are stored in an array of pointers, with a NULL pointer meaning a space. - There is a similarly sized array of booleans for whether each tile has a body representing it. Every boolean starts off false and those which correspond to NULL pointers in the tile array do not matter. All booleans which correspond to non-NULL pointers (i.e. actual tiles) should be true by the end of the algorithm. - Start in the top left corner of the tile array, working left to right and top to bottom. Find the first non-NULL pointer. - Make a new Box2D body which is sized and positioned to cover just that tile, and set the corresponding boolean to true. - Check the next tile over.
*There's actually one additional check performed when the body is expanding vertically. As well as checking that all of the tiles directly below the current ones exist, it also checks that the tiles to either side of that don't. This stops the body from expanding vertically over tiles which would've been expanded over horizontally later. This is part of the horizontal prioritization, resulting in the two bodies shown here on the left rather than the three on the right: Phase 2: CompleteAlthough by no means a perfect solution to the problem, this was certainly an interesting one to put together. The other obvious approach would be to create bodies representing edges rather than tiles, but that gets back to the problem of having too many bodies in the physics system. Box2D does provide functionality for having a chain of connected edges but it's designed for creating relatively simple convex shapes (and cannot handle concave shapes), so probably wouldn't be suitable for the job.
There is another caveat to this system too. Since each room is generated individually, the problem of having perfectly aligned but distinct bodies still applies when transitioning from one room to another. The easiest fix for this would be to have each room generate a section of a single large tile map for the entire level, then run this algorithm on the resulting array. Not only would it fix the transition issue, it would also generate far fewer bodies overall. Next time I'll finish explaining Oh God Why's level generation by detailing phases 3 and 4: populating the level with enemies and collectibles. |
THIS WEBSITE IS ABANDONED. GO HERE INSTEAD:
|