Sokoban type game

Recently, I’ve been programming a specific variant of Sokoban. This version has boxes that can be multiple tiles large, the ability to push multiple boxes (recursively), spikes (which boxes can go over but the pusher can’t), and posts (which the pusher can go over but boxes can’t). I’ll call it ”Sokenban”.

Now the important difference between Sokenban and Sokoban is the multiple tile large boxes and the recursive pushing. Multiple tile large boxes means that each box is labeled with a letter, and all boxes with the same letter move together. This already complicates things. Every time the pusher pushes a box the game doesn’t just check if the location the box is moving to is empty and then move both the pusher and box one tile in that direction, the game actually has to check the location that every box of the letter is moving to, and if all those locations are floors, then move all the boxes of that letter to that location (and move the pusher aswell). To complicate things further, if any of those movements would result in a box on top of another box, this second box and all boxes with that letter will also have to move, and they might run into other boxes, who knows how big a stack of boxes the pusher might move in one turn.

And so in order to get this to work, I have to programme it in a specific way. See, with classic Sokoban it is easy to tell if a move (a single tile in one direction) is legal (that is it doesn’t result in two boxes on top of each other or a box on a wall tile) before even performing the move. The code only needs to update the box locations if it knows the move is legal ahead of time. And generally that is the clever way to do things, since it saves on how much data is changed. But if I were to try to implement that system in Sokenban, it would be much more difficult. In fact, as far as I can tell, it is nearly impossible to know ahead of time whether or not a move by the pusher would result in an illegal position before actually simulating that move. But if you simulate that move and it turns out to be illegal that’s a problem isn’t it? Not necessarily.

The way I’ve programmed Sokenban in the video game I’m making all requires one essential extra mechanic, undoing, because I already need to be keeping track of the previous positions of boxes and the pusher, so that if the player made a mistake that softlocked the puzzle, they could press the undo button and “rewind” their last move. In fact, the game already records the position of every box and pusher, after every move, such that the player can undo all the way up to the beginning of the puzzle if they wanted to.

And so I think the best implementation is for the game to do something inefficient, but elegant. When the player makes a move (a single tile at a time), the game will simulate the whole thing, ignoring all walls, posts, spikes. It will recursively move boxes when one box pushes another (in the same direction), until all boxes affected by the move, have moved. Then, it will “save” or “record” the move, because of course that happens after every move, and finally then, after all the data has already been updated, it will check if the move was illegal (if any boxes are on walls or posts, or if the player is on spikes). If not illegal, great! The game can continue on as usual. But if the move is found to be illegal, the game will undo itself, automatically, as if the player pressed the undo button, but it’ll undo whether the player likes it or not. And all the pre existing code for undoing will run, and that will ensure that the game is back in a legal state. In theory, all this happens in a fraction of a second, and the player won’t even know that, for a moment the box was in a wall, or something.

This seems like an inefficient solution, but I think that a “clever” solution (trying to figure out legal moves ahead of time) wouldn’t be very smart. At least the inefficient solution is consistent.