Arduban - A port of the popular Sokoban puzzle game

#1

banner
banner.png700×192 5.15 KB

A Sokoban clone for the Arduboy. There are other Sokoban games available, but I wanted to create an easy to play version with as many levels as I could fit into memory.

The objective of the game is to move the man, pushing all of the boxes onto the goal squares. You can only push the boxes, you cannot pull them and you can only push one box at a time. The game keeps track of the number of moves you’ve made and saves your best scores (lowest number of moves) for each level.

The game currently has 330 Levels. Because there are so many levels, none of the levels are locked. I’d like people’s opinions on this. I like being able to skip past levels that I am having trouble with and come back to them later, but others prefer the challenge of getting blocked by a level.

Downloads v0.2

Controls

Intro Screen
A Opens the currently selected level
B Opens the settings screen
UP Selects the previous level
DOWN Selects the next level
LEFT Selects the previous unsolved level
RIGHT Selects the next unsolved level

Game Screen
A Undo one move. Hold for 5 sec to reset level
B Returns to the Intro screen
UP Moves the player up
DOWN Moves the player down
LEFT Moves the player left
RIGHT Moves the player right

Level Solved Screen
A Opens the next level
B Returns to the Intro screen

Settings Screen
A Selects the current setting
B Returns to the Intro screen
UP Moves to the previous setting
DOWN Moves to the next setting

Images

Player

Our trusty player, ready and willing to push boxes around for a living!

Player

Box

These are the objective, push these onto the goals.

Box

Goal

This is where you want to push the boxes to.

Goal

Box on Goal

This is the objective of the game, move boxes onto the goals in the least moves possible.

BoxOnGoal

Wall

You can’t move here…

Wall

Credits

  • Levels created by David W. Skinner and Yoshio Murase.
  • This game makes use of the 4x6 Font by @filmote which is under the BSD-3 license.
  • This game uses some gameplay ideas from Circuit Dude by @crait. For example, long pressing the A button during play will explode the player and reset the level. I made it work a bit different, but imitation is the best form of flattery. :star_struck:

Help Wanted

  • Please enter bugs and suggestions here or enter Issues on GitHub
  • I’m a programmer, not an artist, so if anybody wants to help out with the sprites, artwork or sounds, please reach out.
  • If anyone knows why this game plays so slowly in the emulator, help would be appreciated. :slightly_smiling_face:
9 Likes
#2

Given that the level converter is written in C# I’m kind of surprised that the game code doesn’t use more classes and scoped enumerations (enum classes).

#3

I was thinking of using more OOP constructs like classes and enums, but they take more memory and I wanted to squeeze as many levels into the game as possible. Every byte counts :wink:

#4

Enums do not take extra memory over other constants and classes if they are properly written and instantiated (not using ‘new’) are also efficient.

1 Like
#5

It would be nice to clean up the code a bit, if only to scope some of the variables into classes. I’ll give it a shot. It’s been too many years since I’ve done any serious C/C++, so it is fun to see what works and what doesn’t in this environment.

That said, feedback on the gameplay would be appreciated :wink:

#6

That is a falsehood (spread mainly by C programmers).

A class uses no more memory than its component member variables require*.
An enum class uses no more memory than its underlying type.

This:

enum class GameState : uint8_t
{
	GameIntro,
	LevelInit,
	GamePlay,
	LevelSolved,
	GameOver,
	Settings,
};

GameState gameState = GameState::GameIntro;

Uses no more memory than this:

#define STATE_GAME_INTRO    0
#define STATE_LEVEL_INIT    1
#define STATE_GAME_PLAY     2
#define STATE_LEVEL_SOLVED  3
#define STATE_GAME_OVER     4
#define STATE_SETTINGS 5

uint8_t gameState = STATE_GAME_INTRO;

But it’s more type safe.

Likewise this:

class Point2
{
public:
	int16_t x;
	int16_t y;
};

Point2 point { 10, 10 };

Uses no more memory than this:

int16_t x = 10;
int16_t y = 10;

But is more type safe and give you additional freedom.

There are things that can make classes more expensive,
but they are generally easy to avoid,
and are no more expensive than the equivalent C-style code.
(Often people make the mistake of not comparing like for like.)

* There is an exception to this, which is when you introduce virtual functions to a class or inherit from a class that contains virtual functions, because an extra pointer must be embedded in the class to point to the virtual table. As such it adds an overhead of the size of a pointer (sizeof(void *)).

C and C++ are two completely different languages with only partial overlap.
C is not a subset of C++, despite what many people think.

There are actually cases where the same code will behave differently in C and C++.

For example:

void print(int value);
void print(char value);

int main(void)
{
	print('c');
}

In C++, this calls print(char), but in C it calls print(int), because in C, char literals are actually int.

I’ve just made a PR, which you’re free to reject.
I was hoping it would be a pure decrease in RAM usage,
but unfortunately it’s also increased progmem by ~52 bytes as well due to the instantiation of an extra function wtihout the elimination of another function I was hoping would be eliminated.

1 Like
#7

I will take a look at your PR, thanks.

#8

Thanks for the PR @Pharap, accepted and merged. I will add you to the readme.

Any suggestions for the similar code reading the compressed levels in from Flash memory and uncompressing them here?

I don’t think I should worry, but it bothers me that I am copying one byte at a time from flash then working with it to uncompress the level. I would rather just access the byte directly in Flash memory. I know it is just one byte and this only happens on level load, but it bothers me :wink: How do I just get a pointer to the byte in Flash?

#9

I gave it the once over and did a PR.
I’ve explained most of my changes in the PR message:

Hopefully my changes all make sense.

1 Like
#10

Huge thanks for your help again @Pharap. I really appreciate it.

After looking at my level compression code, do you think it is worth my time doing a writeup on the technique? It isn’t a very difficult compression algorithm, so other people might already be doing the same thing, but I haven’t seen it used yet.

If you didn’t catch it, I use a simple run-length encoding to compress the levels. The first half of a byte is the number of times a tile is repeated and the second half of the byte is the tile. I found that it ended up compressing levels for this type of game down to about 40 bytes instead of 128.

#11

I’m not sure.

There might already be an explanation in the magazine or somewhere else,
but another explanation might not hurt.

Personally I think RLE is quite a trivial idea,
but I’m looking at things from the viewpoint of someone with a lot of experience,
so perhaps it’s going to be more difficult to inexperienced programmers/beginners than I’m expecting.

At the very least, if you also explain how you’re compacting two bits of information (or rather two lots of 4 bits worth of information :P) into a single byte then it might be quite useful for less experienced programmers.

@filmote used RLE in Lode Runner.
In fact the level format is quite complex, as the loading code indicates.
It RLE encodes both rows and columns and uses a prefix byte to indicate how the following date is encoded.
(The source mislabels encoding as ‘encrypting’.)

I was going to say I would have needed to understand what was going on to actually make the changes I made,
but I suppose technically I might not have needed to.

Either way, it’s quite straight forward.

It’s just occurred to me that there might be a minor bug in the level loading code.

It’s possible that column could equal exceed COLUMNS if count is high enough,
which could in turn cause a buffer overrun (i.e. undefined behaviour/nasal demons):

Fortunately you’re generating the levels with a tool,
which means that it’s unlikely that will happen,
but I think it should be simple enough (and relatively cheap) to fix,
just by moving the earlier if(column >= COLUMNS) { ... } code into the for ... i <= count loop (after ++column).

1 Like
#12

I like sokoban games also considerered making my own.

If you don’t mind a bit slower level loading then you can kick out the 600 byte levels[] table by combining all level data to a single byte array and change the following:

load.cpp loadLevel()

const uint8_t * levelData = static_cast<const uint8_t *>(pgm_read_ptr(&levels[level - 1]));

to:

const uint8_t * levelData = Level000; //start of all level data
for (int i = level ; i > 1 ; i--)
  while (*levelData++ != 0);// end of level
1 Like
#13

@rprouse

Or, for a faster option than @Mr.Blinky’s solution with minimal additional overhead,
just change from 0-terminated levels to length-prefixed levels.

(I was actually going to suggest this change earlier,
but I couldn’t think of any specific benefit it would bring.
Packing all the level data into a single array changes that.)

Then the code becomes:

const uint8_t * levelData = LevelData;
for(size_t i = level ; i > 1; --i)
{
	const uint16_t * levelStart = static_cast<const uint16_t *>(static_cast<const void *>(levelData));
	const uint16_t levelSize = pgm_read_word(levelStart);
	levelData += levelSize;
}

It costs an extra byte per level, but it’s much, much faster.
I can’t be bothered to do the maths to figure out how much faster,
but the while loop option is O(N*M) and this is simply O(N),
so that alone should say a lot about its characteristics.

Or, if your levels will never be more than 255 bytes:

const uint8_t * levelData = LevelData;
for(size_t i = (level - 1) ; i > 0; --i)
{
	const uint8_t levelSize = pgm_read_byte(levelData);
	levelData += levelSize;
}

Which then means the level size doesn’t increase at all.

Naturally you’ll have to rewrite your level exporter,
but that shouldn’t be too much of an issue.

Also, in case you’re wondering why @Mr.Blinky used --,
supposedly decrement is faster than increment on AVR chips.
And I changed the loop to use i > 0 because that should take advantage of the compiler’s zero flag to produce slightly less code.
The compiler might already have made that optimisation, but in this case I’d rather be certain.

Also, @Mr.Blinky, your code has a bug:

while (*levelData++ != 0);// end of level

Should be:

while (pgm_read_byte(levelData++) != 0);

Although I’m concerned about what the post increment might do when fed to a macro, so perhaps this:

while (pgm_read_byte(levelData) != 0)
	++levelData;
// Skip past the 0
++levelData;

or this:

while(true)
{
	const uint8_t data = pgm_read_byte(levelData);
	++levelData;
	if(data == 0) break;
}

would be better.

1 Like
#14

Yep I noticed. You beat me correcting it :slight_smile:

It works out fine. But the compiler doesn’t optimize it as well as with the increment outside the macro in your example:

A remark though. The result is the same but is there any preference of using ++levelData instead of levelData++ as a single statement? To me it would be more logical to use the latter.

BTW to give an indication of what a bit slower means, it takes less then 8ms to iterate through all 300 levels. That’s less than half a display frame.

#15

I suspected something like that would happen.
pgm_read_byte is implemented with inline assembly,
and that almost always upsets the optimiser.

Ah yes, I get asked this quite a bit.

People almost always write i++ because that’s what’s been propagated through countless examples in tutorials over the years, but actually that’s the illogical choice.

Taken at face value, if the compiler did no optimisations whatsoever then i++ results in an extra temporary variable and more machine code instructions.

If you were to implement integer manually, you’d have something like this:

class Integer
{
private:
	int value;
	
public:
	Integer() = default;
	constexpr Integer(int value) : value{value} {}

	// Pre-increment
	Integer & operator++()
	{
		value = value + 1;
		return *this;
	}

	// Post-increment
	// Note: the argument is a dummy argument
	// used solely to differentiate between
	// pre-increment and post-increment.
	Integer operator++(int)
	{
		const Integer result { *this };
		this->operator++();
		return result;
	}
};

Note that post increment creates a temporary and then calls preincrement before returning the temporary.
That’s how post-increment is supposed to work.

Thus it’s actually illogical to use i++ over ++i,
because i++ produces a temporary variable that must then be discarded.
++i on the other hand simply modifes the existing variable and does nothing else,
which is the behaviour that you actually want in most cases.

For built in types the compiler will almost always notice that the temporary isn’t needed and optimise it away, but for more complex types (like iterators, which are really common in desktop C++ code, and even certain other embedded systems) there are side effects that can’t be optimised away, so i++ really is more expensive.

However, there’s yet more to it.

For post-increment on built-in types, the standard doesn’t actually specify an ordering for the increment phase and the producing of the original value (see this SO answer).
So actually the compiler has more freedom about when it performs the increment,
which is why post-increment is undefined behaviour in more cases than pre-increment.

(The number of cases where ++i is well defined and i++ isn’t is another reason I prefer to stick to ++i.
You can see some examples of those cases here.)

Also, as I know you like assembly, you might want to take a peek at this old project of mine, using assembly to implement types that perform saturation arithmetic.
It contains some ‘real world’ examples of overloading the pre-increment operators (though it looks like I didn’t get round to implementing post-increment).

Even so, O(n*m) vs O(n) is a big difference in complexity,
and length prefixing can sometimes come in handy for other things,
like reshuffling the order of the levels.

1 Like
#16

I really like this idea @Mr.Blinky and @Pharap. Even without compression, my levels can only be 128 bytes, so length-prefixing the levels makes sense. I’ll modify my level generator and get this in the next release.

1 Like
#17

With the help of @Mr.Blinky and @Pharap, I’ve reduced the memory size enough to add an additional 30 levels. I have created a second release. The initial post in this thread has been updated with links to v0.2.

Thanks @Pharap and @Mr.Blinky.

3 Likes