Screenshots (v2)

Development log/history (v2)

When I make games, I am often motivated by specific technical challenges. In V1, my challenge was to implement an engine supporting different tiles sizes, despite the SMS native 8x8 tiles. This made the 4x4 and 12x12 engines a lot of fun.

In V2, I wanted to learn and implement path finding to upgrade the controls to feel more modern. Today, many online or mobile implementations of this game use a pointing device to control the player, which means that instead of walking to a desination step by step, you just say "go there" and it happens, provided that a path exists. I really like this approach as it saves a lot of time.

So the challenge understanding how path finding algorithms work, and choosing or adapting one so it would work given the system memory constranints. It turned out to be easier than I though. What I did is similar to the Sample algorithm described on the Pathfinding wikipedia page.

To search the optimal path, each location needs a counter indicating its distance. The SMS only has 8kB of RAM and I was already tight on memory. But I already had an array of bytes of 64x48 to hold the level state. Each byte indicates if this is a wall, floor, a box, a target, a box on a target, or outside space. Only 3 bits are used, meaning the upper 5 bits were free. This is where I store the distance. No need for a new array!

Path finding algorithms often seem to use a list or queue of next locations to examine, but I was not sure how big of a list I would need to be certain that the algorithm would work even for the large levels, and if this list would fit into memory... So I came up with this algorithm which does not use a list. Instead it scans the full surface of the level to find new canditates.

Stage 1: Init and seed

1. Init distance of locations to 0
2. Set distance of locations left/right/above/below the player to 1 if they are walkable. (walkable = floor or target)
3. Set cur_distance to 1.

Stage 2: Search until destination is found
For each location where distance = cur_distance, do:

1. For walkable neighbor that still have a distance of 0, set distance to cur_distance+1
2. If a neighbor was the destination, stop here and enter stage 3
3. If there were no locations at all with distance = cur_distance, there is no open path, give up here.
4. Increment cur_distance. If cur_distance becomes greater than 30 (the max. that fits in 5 bits minus one) set it back to 1. (not 0).
5. Repeat.

Stage 3: Back track and mark the path
If we are here, the destination was reached. It is now time to mark the path the player will follow. The value of 31 is reserved for this. Set cur_distance to the distance of the destination, and set the distance of the destination to 31 (path marker). Then, starting with the current position set to the destination:

1. Look at neighbors and select one where distance = cur_distance - 1 (or 30 if cur_distance is 1). If there are several equal canditates, just pick any. Set the distance of the picked neighbor to 31 (path marker).
2. Set the current position to the selected neighbor.
3. Decrease cur_distance. If if falls below 1, set it to 30.
4. Repeat from step 1 until the starting point is found

Stage 4: Move the player along the marked path
At this point, the player can just move following the path markers. Starting with the current player position:

1. Look to neighbors for a path marker (31).
2. Move player to that neighbor.
3. Clear the path marker.
4. Repeat until no path markers are found. The player should then be on the target.

The above worked fine, but it was a bit slow due to the way Stage 2 scans the whole level all the time. So I ended up adding a short list of "next locations" which Stage 2 uses. The list is short, so if it fills up, no problem, the algorithm reverts to the "scan the whole level" approach and everything still works.

The only thing left after this worked was to add support for pointing devices such as the Sports Pad and the Mega Mouse. I was pleasantly surprised by the the Sports Pad. My experience with it, using the Sports Pad Soccer game was far from good... but it turned out to work very well when used as Trackball to move a pointer!

Here is a video showing the path finding in action. Doing all this walking around manually would be a bit unpleasant, wouldn't it?

Development log/history (v1)

Yes, yes, another Sokoban clone.. But this one has lost its vowels ;-)

SKBN is a sokoban clone called SKBN. The 128kB ROM contains the 1043 levels of the Microban and Sasquatch level sets created by David W. Skinner.

In this project, I focused mostly on making sure that all levels of those sets would be playable, even large ones.

To achieve this, the engine supports different tile sizes: 24x24, 16x16, 12x12, 8x8 and 4x4. The 12x12 engine was the most challenging, as the two grids of 8x8 tiles (native) and 12x12 tiles (virtual) create interesting complications, combining vertical and/or horizontal splits. The required tiles are built on-the-fly while displaying and playing the level.

The 4x4 engine is useful for previews, but also for very large levels. But those may not be very playable unless you use an emulator or an RGB-connected display.

The in-game menu has options to undo a move or the last push. The history can hold 1000 moves.

Of course, solving more than 1000 levels in one session is unthinkable (probably) so the completion status of the levels is saved in SRAM, or directly on flash, if the game is running on a compatible cartridge such as those I designed...

Screenshots (v1)

Download

Version 2.0 September 14, 2022 (Wednesday)
After about a year of working part time on this project, version 2 is finally ready! Added 100 raphnet levels (mostly very easy) Added more levels by Jacques Duthen, previously unpublished: Sokogen-990702, Sokogen-990917, and Sokogen-991123 Updated the title screen Added options and credits screens Add themes: New (V2), Mac and Ksoko. V1 theme still available. Change keys in-game: Button 1 opens the menu, Button 2 undos the last push. Support for point mode (with path finding) Support for the Sports Pad and the Mega Mouse Add background music (can be turned off in the options)
File(s): skbn-v2.zip (186.7 KB)

---

Physical edition

This game is also available in cartridge format from my online store! https://www.raphnet-tech.com/products/skbn_sms/index.php

Box

The physical edition (for now) contains only the cartrige, but since I received a request I designed this box:



Here are PDF and PNG versions for printing (PDF recommended)
skbn-box-art.png
skbn-box-art.pdf

Thanks

Making this game would have been much more difficult without these tools:

• devkitSMS (SMSlib et PSGlib): https://github.com/sverx/devkitSMS
• png2tile (PNG to SMS graphics conversion): https://github.com/yuv422/png2tile
• DefleMask tracker: https://deflemask.com/
• sdcc (Small Device C Compiler), a C compiler supporting the Z80: https://deflemask.com/
• The fake box shown at the top of the page was rendered using Maxim’s POV-Ray Box.
  https://www.smspower.org/maxim/Misc/POV-RayBox

A big thanks to the authors of the above!


Of course, there would be nothing to see here without the game contents, the levels! I used levels that can be redistributed freely provided that their author is credited.

• Thanks to David W. Skinner for the Microban and Sasquatch collections.
• Thanks to Jaques Duthen for the Dimitri & Yorick, Sokogen-990602, Sokogen-990702, Sokogen-990917, and Sokogen-991123 collections.