I’ve been interested in sokoban-style games ever since I played BoxWorld on Windows. I was never particularly good at solving them, but that never stopped me. I loved games like Kye and Chip’s Challenge too, but there’s something about the simplicity of Sokoban that makes it such a good puzzle game.

As part of making Square Man, I included a number of sokoban-like levels, but I had to make them all by hand, and I wasn’t particularly good at that either. Mostly, I just made levels randomly (like, by-hand random, not by-machine random) and hoped the level would be difficult enough. For development purposes, I made a sokoban solver in the dev version of Square Man, but that was WAY too slow for any puzzle that got even slightly too complicated.

So my goal became to make something that could procedurally make these levels and solve them too. I knew I had to do it in a more efficient language, and I originally thought about C, but that seemed more complicated than I wanted to get. I knew I needed to quickly check against large sets of previously checked positions, and I didn’t want to deal with C strings directly. So I chose C++. I hadn’t done C++ in a while, so I had to relearn some of its paradigms. It was weird suddenly thinking about passing objects by value (though I tried as much const & as I could).

I managed to write the bulk of it in one weekend. I started by building the Sokovan object that handled all the positions and moving and stuff. Internally, it stored the whole level as a single string which made some things a lot easier and more efficient than setting up a matrix. With this object, I built a level player on the command line (which isn’t too useful, but it was still cool.) Then I did the solver, which eventually turned into a modified A* algorithm (well, sort of, anyway), and it’s pretty decent. It can solve most things relatively fast.

The real trick, I think, was the generator. I used a lot of ideas from different places (there was actually a really interesting paper written on the topic), and while I used a few ideas, I made the whole algorithm myself. That is, I didn’t use anyone else’s code, and I didn’t use any generative AI. The process involves creating an empty grid, randomly placing goals with boxes on top of them, and then working backwards the maximum number or iterations without duplicating a previous position.

That last part requires some explanation: what is a “previous position?” I originally set it up to be any configuration of the level that had previously been reached, which basically amounts to the player’s position and the position of the boxes. However, I realized that a lot of these positions are just duplicates of one another. Any space that a player can reach just by walking is essentially the same position: it’s the box pushes that really matter.

So for both the generator and the solver, I used a key based on the current level state, only I did what was essentially a flood-fill out from the player’s position to every space the player could reach without pushing. This counted as one position, and it eliminated a bunch of duplicate positions. This made the solver deviate from A* in that for each step, it walks to every square a player can reach until it reaches a box, and then we push that box (if able) and add that configuration to the queue. So the solution isn’t necessarily the most efficient, but I think that could be rectified by sorting the new queue data by path length (I haven’t tried it yet.)

Well anyway, after going to all that trouble, I got a generator that worked really well, and that gave me the idea to create a website featuring a new level every day, and so Daily Box Game was born. All these levels are generated by my sokoban generator, though I use a python script to run the generator and check the output. Levels have to meet certain criteria to be considered, and after that I check them manually to make sure they’re not too simple.

You can see the results for yourself. Give Daily Box Game a try now!