Year 4 - Honours Project: Demo, dissertation and download

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

Dissertation stats:

• 21202 words
• 75 pages
• 52 references
• 42 figures
• 15 tables
• 5 appendices

​References:

• 33 literature + websites
• 7 software + libraries
• 7 games
• 5 models + puzzles.

Dissertation - Connor Halford.pdf
File Size:	2076 kb
File Type:	pdf

Download File

---

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:

• How voxelization can be used to create 3D puzzles from existing polygonal models.
• How to construct the leftmost and rightmost solutions for a 2D line by first finding the naïve solutions and then iteratively shifting blocks until all existing state is accounted for.
• Finding all possible solutions for a 2D line by recursively finding the set of spreads for a line then moving these along to find the set of shifts.
• How to measure the ‘leftness’ of a given solution to extract the leftmost and rightmost solutions from the set of all solutions.
• A simplified approach to the linesolver algorithm which uses just two deduction techniques: one to find solid cells and one to find empty cells. The situations where these techniques could lead to false positives are described and handled appropriately. It was also shown how empty lines and lines with a complete description can be detected and solved immediately as early-outs.
• How 2D solving techniques can be applied to 3D puzzles by treating 3D clues as simultaneous sets of 2D clues.
• How to expand a 3D clue into a set of 2D clues, known as finding the compositions of n, where n is the block size. Specific algorithms for finding the double expansion and triple+ expansion of n were described.
• A discussion of different approaches to applying linesolvers to the puzzle space with the goal of using fewer linesolvers and having a lower bad guess rate. A performance comparison of the brute-force, hierarchical and heuristic solvers was conducted and the results discussed.

The ultimate aims for this project were to show how voxelization and 3D puzzle solvers could benefit the 3D puzzle creation pipeline. Voxelization has been shown to be a useful tool in the beginning stages of puzzle design as it allows for rapid prototyping of a subject model at various resolutions. Generated puzzles can then be refined to better represent the original subject or to adjust the difficulty of the puzzle by making modifications in tandem with the 3D solvers. Being able to know whether a change has rendered a puzzle unsolvable without having to spend the time solving it by hand could greatly improve the 3D puzzle designer’s workflow."