Code Trip
  • Blog
  • Archive
  • Projects
  • Portfolio
  • CV

Year 4 - Honours Project: Demo, dissertation and download

17/6/2016

0 Comments

 
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

Picture

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."
0 Comments



Leave a Reply.

    Author

    Connor Halford. Studied Computer Games Technology at Abertay, now a Games Programmer at MediaTonic.
    ​

    Useful Sites

    hilite.me converts source code into formatted, embeddable HTML without the need for CSS or Javascript.

    tablesgenerator.com performs a similar task as hilite.me but for tabular data.

    Archives
    All posts

    June 2017
    December 2016
    September 2016
    August 2016
    June 2016
    May 2016
    April 2016
    February 2016
    January 2016
    October 2015
    September 2015
    August 2015
    July 2015
    May 2015
    March 2015
    February 2015
    January 2015
    December 2014
    September 2014
    August 2014
    July 2014
    March 2014
    February 2014
    August 2013
    June 2013
    December 2012

    Categories

    All
    Advice
    AI
    Algorithms
    AMPS
    Audio
    Boost
    Box2D
    Coursework
    DirectX
    Flash
    Game Boy Advance
    Game Jam
    Graphics Programming
    Honours Project
    Maths
    Nonograms
    Oh God Why
    OpenGL
    PICO-8
    Pixel Art
    PlayStation 4
    PlayStation Vita
    Procedural Generation
    SFML
    Shaders
    Spirit Shift
    Twine
    Unity
    XAudio2
    Year 1
    Year 2
    Year 3
    Year 4

    RSS Feed

Powered by
✕