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:
Year 4, Semester 2 - Perspective Detective: an augmented reality game on the PlayStation Vita4/4/2016
January 2016 - April 2016 This semester we had a few lectures on augmented reality (AR) and a few on anaglyph 3D and were tasked with making a game that takes full advantage of one of these technologies. I chose AR and made a game called Perspective Detective. It's all about camerasBoth the lectures on anaglyph 3D and especially the lectures on AR involved lots of camera vector/matrix calculations and it got me thinking about how to use cameras as part of gameplay rather than just a way to view gameplay. I'd also been playing The Witness (which is excellent) so I had puzzles on the brain and eventually this led to the concept for Perspective Detective: virtual cameras attached to AR markers which see different versions of the level than the physical camera. As shown in the footage above, I designed 4 puzzles as a proof-of-concept for this mechanic: Level 1 teaches the player the basic mechanics of the game: move from orange to green, don't trust the physical camera, virtual cameras show the true path. Level 2 reinforces these ideas and also forces the player to count out their steps because of a larger level and the fact that the physical camera shows nothing but the start and end points (and the player of course). Level 3 introduces a new perspective trick by making the player look at the level from the opposite direction. The controls are relative to the player not the camera, so by turning things around like this it reverses the controls - to move 'right' you now press left. The arrow atop the player shows the direction of up on the d-pad. The final level uses multiple virtual cameras with alternating halves of the full path. The player has to flick between looking at the physical camera feed to see where they are and the two virtual camera feeds to see where to move next. VisualsI used this camera model by 3dregenerator and built the UI using these sheets by Buch. Both are free for non-commercial use. I also made some simple effects to make everything a bit nicer:
How it worksIn AR the only fixed point is the camera, so that acts as the origin for your coordinate system. The Sony marker tracking library gives you a transformation matrix to go from the camera to the centre of the marker - this transformation includes position, orientation and scale. If we want to position something relative to a marker we just build a local transformation matrix to do whatever we want, then post-multiply that by the marker matrix to get into world coordinates. The axes relative to each marker are shown on the left of my lovingly hand-drawn diagram; the marker lies in the xy-plane and z increases up from the marker. So we have the position of the centre of the marker, a. If we do a local transformation along z we'll get position b and if we do a further transformation along y we'll get position c. The eye of the camera is at b, the look-at vector is (c - b) and the up vector is (b - a). With these we can build a view matrix and then render the level geometry from the perspective of a camera floating above the marker. As the marker moves, so does the view. ThoughtsI had plans for another mechanic but decided not to do it because I really didn't need to and had plenty of other work to be getting on with. Later levels would have had colored glass panes attached to markers and viewing the level through these panes would reveal a different set of information, both for the physical and virtual cameras. This was directly inspired by a similar mechanic in The Witness.
Surprisingly this is the first time I've made a puzzle game and I thoroughly enjoyed designing the levels for it. I might continue playing with this multi-camera dynamic in a purely virtual format as AR games aren't exactly easy to play, though I do think the tactile nature of the player physically moving the cameras (albeit via their markers) adds a lot to the game. Overall I'm really happy with it as a proof-of-concept and those who have played it seemed to really enjoy it!
My initial honours project idea was titled An Evaluation of Level of Detail Techniques for use in Real-Time Games. I was going to implement and compare discrete, continuous and view-dependent LOD techniques and assess their suitability for games based on the run-time cost. LOD is something I'd been thinking about for a while as it seemed like really interesting technology (it is) and I thought it would make a good honours project (I still do). I did a lot of research into existing techniques (I recommend the excellent Level of Detail for 3D Graphics by Luebke et al) and thoroughly enjoyed finding out how they worked. The problem was that these techniques have been around for a long time and at the scope of an honours project I wouldn't be able to build upon them in any interesting way, I would just be able to build them. Reinventing the wheel just wasn't exciting to me and I didn't want to commit the next ~6 months to just implementing other people's research, I wanted to do research.
The thing is, if you want to do something nobody's done before at this scale you either need to have a lot of time/people or you need to go very niche. I chose the latter.
One of the nice things about this project is that it covers a lot of different areas: there's graphics programming in the voxelization process, algorithmic logic in the solver and performance analysis in the evaluation. It's also brand new - as far as I can tell nobody's tried to generate 3D nonograms or algorithmically solve them before (though 2D ones have been tackled).
I've been really excited about this project since I came up with it because of the variety and the fact that I'm covering new ground. Because of this I've been getting an incredible amount of work done very quickly on it; I'm way ahead of schedule. I'll probably post some updates on here as I continue. |
THIS WEBSITE IS ABANDONED. GO HERE INSTEAD:
|