Perspective: Daily Puzzle
Perspective: Daily Puzzle is the latest in a series of casual puzzle games released by Aletheia Ware in which players navigate a 3-dimensional maze by swiping to rotate the puzzle and tapping to enable gravity.
A new puzzle is released everyday, getting more difficult throughout the week, can you solve it in the shortest time?
-
-
Puzzle Generation
I spent a while trying to design an algorithm to generate puzzles with given characteristics such as the number of blocks, portals, and moves required to solve. But none of these algorithms were very good, and the generated puzzles did not feel natural or organic.
One day I was having lunch with a friend who specializes in Machine Learning and he was explaining how Generative Adversarial Networks (GANs) work - essentially one algorithm generates data, and another scores the generated data. This separation made it easy to test each part in isolation. While I wasn't using Machine Learning, the idea of a two part algorithm could be applied to puzzle generation. One algorithm could generate random puzzles and the second could use pathfinding to figure out a) whether the puzzle is solvable, b) how many moves are required to solve it, and c) how much of the puzzle was visitable.
The generator would take some information (size, elements, etc.) and generate a random puzzle which may or may not be solvable. The scorer would accept a puzzle and return an integer score (more moves = higher score, unused elements = penalty so all elements are visitable ie. false paths). I just had to wait a few days while it iterated through billions of permutations until the first set of puzzles was complete.
A few times the scorer would end up in an infinite loop and not make any progress, it turned out that portals could end up stacked and result in a portal infinite loop - something I had previously enjoyed in Valve's game series Portal.
The execution was parallelized so each of the 8 cores was used and the tasks were re-niced to -20 but a lot of time was still spent task/context switching, obviously the scheduler is trying to be fair to all processes and maintain a responsive system but the computer was not being used for anything else so fairness and responsiveness did not matter. Furthermore, when a task running on one core is swapped out to a different core, the higher-level caches are invalidated and the task needs to fetch from the lower-level cache or worse: main memory.
Taskset is very useful in this scenario as it can set a process's affinity, meaning the process will always be scheduled on the same core, this meant the scheduler did not spend so much CPU time context switching and ensured the tasks could make best use of the fastest cache levels. The graph comparison below shows the difference between not using taskset (top) where the CPU usage oscillates just below the max, and using taskset (bottom) where the CPU usage is anchored at 100%.
There are still many optimizations than can be made to improve the efficiency, as always the code is open source, feel free to take a look, suggest improvements, or send a pull request!
-
-
