Stuff I read last week

2017-04-23

• Procedural Generation of Sokoban Levels Done by working backwards: generate a random level from prefab tiles, set level in an already solved state, work backwards from solution to the initial state with the longest critical path.

  Surprisingly expensive: In practice it can generate several levels over the course of a day depending on how much CPU power it is given and how large the desired levels are.

• Generating Sokoban Puzzle Game Levels with Monte Carlo Tree Search As the title says, Monte Carlo Tree Search. This looks a lot more intriguing, especially since they say it generates acceptable quality results very quickly (seconds) and then gradually iterate to improve the quality. Clever solution for ensuring puzzle is solvable without needing a general Sokoban solver for every intermediate step (use sequences of valid moves as the mechanism for iterating on the puzzle generation).

  Need to reread to see if I really understand what they're doing. But this might be the approach I'll try for the project I'm reading this stuff for.

• Working with puzzle design through state space visualization Cool analysis and visualization of puzzle state spaces. Not sure it'd really scale to actual logic puzzle games though, seems more suited for adventure or action-adventure games.
• A Mind is Born A byte by byte and trick by trick dissection of a 256 byte C64 demo. Very heavy reading (I'm only a 3rd of the way through; need to revisit it), but totally worth it.

  Catchy soundtrack, too.

• Asset Systems and Scalability [video] A couple of years ago it was reported that the Destiny asset pipeline was totally screwed up, and even the tiniest changes would take hours. Chris Butcher explains in minute detail how and why that happened. Wish there were more postmortems like this, rather than the usual "5 things that went right, 5 things that went wrong" platitudes.
• Using C++11 Capturing Lambdas w/ Vanilla C API Functions Use a pure C ABI for compile speed, but add little template shims with embedded closures for type-safety.
• Automatic Puzzle Level Generation: A General Approach using a Description Language Finally. I was starting to think there was nothing written on procedural generation on non-Sokoban puzzles. Though this goes all the way to the other end of the spectrum, and generates levels for any Puzzlescript-based game. Not sure there's anything actionable here except for ideas on heuristics.
• Theseus 3D Claims good procedural level generation results with incredibly simple algorithm (10-20 iterations of GA with just mutation, no crossover, and just a single level surviving each iteration). Might be intrinsic to Theseus and Minotaur puzzles. A relatively tiny state space, which can be further pruned due to the sudden death failure conditions.