Bokosan – a reverse Sokoban

Bokosan is a reverse Sokoban where boxes are on a goal position and the player needs to pull them away while avoiding deadly spikes and falling into pits.

The game has 20 levels, single player mode, time challenge mode with online leaderboard, customizable player appearance, sound, 4 music tracks (6 in full version) and a few more features.

It is an entry for the js13kgames gamedev competition, where the goal is to create a web browser game using only JavaScript/CSS/HTML, with final size (after ZIP compression) below 13 kB, in a month. It was created for the 2015 jam for the theme “reverse”.

This year I worked together with my brother, Zsolt, he composed the music and created most of the levels.

Play it here.

Graphics

I’ve decided to go with raster graphics, stored in PNG with low color count and replacing colors in code if needed. I’ve tried several other methods to store graphics (putting each sprite in a string, etc.) but the overhead for decoding was just too big.

(The image is scaled down, click here for full version.)

The final PNG contains the Jostix font by Ray Larabie (only uppercase letters, numbers, punctuation marks), 13 tiles, 9 character animation frames and 3 other graphics; it is 700×48 pixels, 20 colors and the final size is 1600 bytes after TinyPNG compression.

It might worth to note that for character animation I used oldschool tricks of mirroring and rotating to reduce the frames. I have only drawn the standing and step with right foot frames and then “stand, step, stand, mirrored step” sequence. Also, I just rotated the “walking up” frames for the “walking right”, as well as the “walking down” for “walking left”. For pulling I did the same but used one frame only and played the sounds of steps.

The colors of customizable parts of the character (hard hat, shirt, pants) are replaced during render (and not on the sprite sheet) as each entry in the challenge leaderboard can be different.

Quick note: when opening an HTML from local disk and accessing its contents in JavaScript, like reading pixels of an image (rather than putting in DOM and showing to user, or using drawImage()) the Cross Origin protection kicks in and prevents the operation. Although when opening from a web server there is no such problem, this feature can be disabled but it’s strongly not recommended. Worth to note that JS engines track the data they handle so reading a canvas where a drawImage() copied a portion of a protected image will result in an error as well.

Sound effects

For the sound effect we used jsfxr to generate them.

I have added a few minor optimizations for jsfxr before compressing the source via Closure Compiler, and after that manually edited the compressed code to be more suitable for ZIP.

Music

The music was created entirely by my brother, Zsolt.

I have created a small tracker that implements the basic features of an XM, handles only one pattern and loops it, but also have a map that describes which channels should be played on which loop (and also an option for intro that will be only played once at the beginning) – this way a song can be made up of a short period of music but can be dynamic and changing on each loop. Also created a converter that reads an XM file and creates the JavaScript arrays for the player, so Zsolt could use MilkyTracker to compose.

The samples were produced using jsfxr just like the sound effects (they are actually in the same array) and are altered on the fly for player needs (changing playback speeds to create the notes).

I have also created a frontend for playback later, check it out.

Level design

The levels were by designed mostly by Zsolt, with a few exceptions.

They are stored as simple strings – ZIP is really good at compressing text.

The levels are locked by default. Only the already solved and the next two unsolved are unlocked, as an attempt to prevent the player from getting stuck on one level.

And as the steps are counted for each level it is just natural that achievement hunters appear, so we added an “A+” badge for them for completing the level with at most the minimal steps we completed them during development, displayed in the level selector.

Challenge mode

There is a challenge mode with online leaderboard showing the name, time and character profile picture for each record.

There are 6 challenges, each consist of 3-4 already completed levels, the player plays them one after the other and the time is recorded and shown on the leaderboard.

Statistics

The game collects statistics about each play: play time, moves made, pulls done, levels started, levels finished.

The statistics is stored on the server side, the games recevies the current snapshot of the statistics and the one from a minute before, and then interpolates them during the next minute – this makes the display much more active.

I loved to see the numbers rolling during the vote period, unfortunately the statistics are no longer available on the jam website. [Although I made a few screenshots, but I could not find them yet.]

Server side

The server keeps track of challenge leaderboards and statistics. It does not do anything more, really.

Compression

I basically go with the idea of writing readable code and leaving the low level optimization and compression to the tools.

Most of the time this works just fine as for a really simplified example…

if (x == 3)
{
    return true;
}

return false;

… is exactly…

return x == 3;

… but the former can be read more easily and the tool will rewrite it to the latter anyways.

For code compression I used Google Closure Compiler in two phases: first is the advanced optimization without whitespace removal, then the whitespace removal. This leaves a chance for (easier) manual/scripted optimization to be more suitable for the next tool (ZIP in this case).

The spritesheet is compressed using TinyPNG.

I used as few files in the compiled version as possible, as each file adds at least 130 bytes to the final ZIP file – this can be a lot and it increases with file name length.

For the final ZIP file the rules dictate to be a standard ZIP file, so no 7zip or other advanced formats are permitted.

To optimize the final ZIP I used AdvanceCOMP’s AdvZIP which basically recompresses an existing ZIP file but keeps compatibility.

About 90% of the build process – starting from readable code to entry ZIP – was automated in a build script. This way I could track the effect of each changes on the final size. The rest was manual editing of code just before Closure Compiler whitespace removal.

Fun fact: the last ZIP before the submitted one was 13313 bytes, 1 byte over the limit. I saved that byte by changing the player name input from “Player name:” to “New name:”.

Final thoughts

I think Bokosan is the most polished game I’ve created until today (alone or in a team), it has the most content and feels the most complete. It also got a lot of positive feedbacks and it was really fun to catch my collagues playing it, trying to get the “A+” badge on all levels.

However, the game has not ranked in the Top 10 in Desktop nor Mobile category, in Server category it finished at 6th place and in Facebook special on 3rd place.

A huge thank you to Andrzej Mazur for organizing js13kgames competition once again, Ray Larabie for the Jostix font, and Markus Neubrand for Jsfxr!

untitled13

In 2012 I found the js13kgames game development competition where the goal is to submit a HTML-CSS-Javascript game which is not more than 13 kB (13312 bytes) ZIPed, developed between 13th August and 13th September. It is also required to publish the uncompressed game code on GitHub – this way one can prove they created the game and more importantly: others can learn from it.

This last part was what got me, I was really curious how others fit games in such a small space – what later turned out to be much more than it looked on the first sight.

As the competition was already halfway or was over when I found it (I can’t really recall) I could only examine others’ entries and decide I will participate next year, in 2013. I also tried to gather some ideas and set up a concept before the competition start date – strictly not a line of code was written.

There is a theme each year (which is optional but worth bonus points if honored), for 2013 it was bad luck – and I skipped it entirerily…

Okay and now about my entry.

My concept was to create a 2 player networked tower defense/tower attack game.

I must admit I am really bad at naming things, I just called the main (and only) client side file 13312.js and not long before the deadline I came up with the exceptionally uncreative name untitled13.

Of course to fit in 13 kB entries usually do not use existing engines, they are written from scratch – a thing I don’t mind at all, I’ve been always curious about the details and liked the control one has when starts from the ground up.

For graphics and animations I decided to go with a fixed color palette and dynamically generated content. All the objects consist of one or more layers rendered by a function that takes a string that describes a series of commands and their parameters. It turned out only two commands were necessary, a “draw a closed polygon filled with a color” and a “draw an alpha overlay” for shadows. The parameters were simply X and Y coordinates of the points, represented as characters in the base64 character set (64 distinct values), multiplied by the size of sprite. (For example: sprite size is 64×32, string is “AAAzjj”, therefore the coordinates are 0;0, 0;25, 35;17).

The map consists of starting points for the attacker, paths for the units to walk on, path intersections with switches, a few objective tiles for crystals the defender has to defend and concrete blocks to build the towers upon. There are three types of monsters with different parameters (speed, health) and three towers with different parameters (attack type, damage).

The networking approach is pretty simple but the most interesting part: the initial state is known to both players (the map is fixed in the entry version, in later versions it is randomized but the seed is shared), the mechanics are known as well and the actions can be described easily. So I came up with the idea to run a whole game instance for both players, create delayed action queues for them and synchronize them. When one player clicks a button the action is added to their queue with the configured delay, sent to the other player’s game, and a bit later executed on both instances at the same moment.

To get this working I needed reliable advancement of simulation steps, one that is not affected by skipped frames. I created a tick() method that steps the simulation by exactly one time slice (one simulation step), so when a frame is requested by the browser I calculate how many tick should have happened up until then since the last frame and call tick() that many times. (I usually go with this method to keep games frame rate independent – skipped frames are less worse than game slowing down.)

As both players are running the same game (only playing different sides), are aware of every details (only hidden from them), all events are happening at the exact same time, the game should play out identically for both of them. Later I learned this is called simultaneous simulation and it is the core of great games like Age of Empires, Starcraft and a lot more.

In this form however there is a serious flaw. There is no guarantee that the actions will reach the other player before they are due, it is blindly trusted that it will. For example: Let the action queue delay be 10 frames. The defender clicks to build a tower at frame #100, this will be executed at frame #110. If the network lag is say 7 frames then the other player gets the notification at frame #107, still 3 frames before execution, the tower gets built at frame #110 in both instances and shoots the attacker just before it reaches the crystal. But if the network lag is more than the queue delay, say 13 frames then at frame #110 the tower gets built in one instance, then the notification arrives at frame #113 for the other player, tower gets built at frame #113 when it’s already too late, the crystal was reached and the game is over. In the defender’s instance the crystal is saved, in the attacker’s the crystal is destroyed – the game is out of sync.

To address this the other instance must be notified about no action as well periodically to make sure nothing is missed. And when there is no info, the game should pause and wait until it arrives. This is a feature I had no time to think through and implement before submitting my entry.

The server part is running in node.js (my very first application) and it is very basic, it just matches the players by their IDs and passes the messages between them.

Random minor thoughts: The map is a hexagonal grid, which made finding neighbour tiles for concrete block and fog calculation ugly, but it looks so much better than a square grid – although it is handled like that. The map has fog to hide tiles that are too far away from units/towers. The UI is usable but confusing and unhelpful at first.

The project is on GitHub, the version I submitted is in the js13kgames-2013-entry branch. I like to commit often (and to have descriptive commit messages) so the submitted version had 381 commits, but for some reason I have not uploaded the final ZIP file, it was around 11255 bytes of 13312, so I used up 84.5% of the limit.

The game was better received than I expected, it ranked 1st place in Server category and 9th place in Desktop category.

The competition had awesome prizes including various licenses for game engines and gamedev related services, ebooks, physical books and vouchers. It was organized by Andrzej Mazur who tirelessly did an epic job, I’d like to thank him again for organizing and hosting this event, finding sponsors, arranging prizes and of course organizing the event annually since then, so thank you Andrzej!

Check out js13kgames.com for previous and upcoming competitions.

Multiplayer gaming, part 1: Sync the future!

Last year I was writing a little game intended to be run in the browser. I was writing it in pure javascript (i.e. no graphics or whatsoever was stored, everything was dynamically generated) for the js13k Games 2013, it is the Untitled 13 (can be played here).

One of the base concepts was to build a multiplayer game. It was challenging despite I’ve written some basic games, also mulitiplayer ones, I’ve never tried to write a real-time strategy game yet (not counting a quick POC). The synchronization of the game between players was the most interesting part of it, and therefore my favorite one. I was not intended to sync the whole game state (map, objects, internal states, etc.) continuously as this can easily become a huge set of data even for tiny games at high refresh rates so I decided I will come up with a better, more resource-friendly solution.

I’ve been thinking about the game: it has some mechanics, player events events and also their effects on the gameplay and concluded one could be separated from the other – of course it turned out that I was not the first who came up with this approach. So instead of syncing everything, I was thinking about synchronizing just the map in its starting state and a list of events.

All these events were always originated from the players (i.e. buy an item, toggle a switch) or from the game mechanics (i.e. an enemy is close enough to be fired on, an object loses health, objects collide). As the game on both ends are always identical the result of mechanics should be always identical too, therefore all I left to deal with were the events from the players.

So basically all I was doing is this: my game had so-called “ticks” that were the updates for the game internal states (this event was happening with a guaranteed interval, i.e. 15 times per seconds, or if late (due to lack of CPU resources or bad timing) all the affected ticks ran anyways to catch up), and when a player did an action (i.e. clicked a switch) I stored a record in a queue about it and a “process this on the nth tick” property. I’ve also sent this record over the network to the other player. This way I introduced a slight delay (this nth tick was always about 300 milliseconds in the future) but during this delay I sent the event to the other player and when the nth tick came both players made the change on their isolated environment in the exact same moment (speaking in game time) and therefore both ends have seen the same new state, the game is deterministic.

Later I’ve learned – in a Gaffer on Games post and in another one about network programming in Age of Empires (both are must reads!) – this is a so called simultaneous simulation approach with one big difference. The handling of the lag on the network. This was the worst thing during the development and tests of the game. As I’ve been syncing future events if the notification got stuck somewhere between the players it could easily come later than it must have been executed. As the tick it was intended to be run at was passed (and the other player have executed at that time) the game became out of sync. And this is bad, really bad. (I’ve made some efforts to handle this, but these turned the game code much more complicated, i.e. to be sure that important events happen on both sides I added them as an event to the queue (and sent that over the network), that’s why the little creatures pause for a while before exploding at the target markers. But this is bad, don’t do this. Keep reading for a simpler solution instead.)

In a real simultaneous simulation the players should be aware of the lag in the propagation of events so instead of just saying “here, run this on the nth tick” there needs to be a “I have nothing for you to run on the nth tick, carry on”. And if the other player does not specify what to do (or not to do) on the nth tick when it comes the simulation should pause while it is unsure about what to do. Which is not nice but far much better than becoming out of sync. Obviously working with 15 ticks per seconds and expecting the network to transfer the data for the next tick is nearly impossible (talking about transmitting over the internet as this would permit about a 66 milliseconds deadline on a client1-server-client2 route, also sending at least 15 events every second) and would result frequent pauses, and that would be really annoying. So instead of scheduling events for any tick of the game a rule should be applied to limit the ticks that can accept events. Saying events can be scheduled only for every 5th ticks reduces the count of transmitted packets dramatically, also extends the deadline to a more sane value.

Also, when a pause occurs due to network lag the rule of scheduling could change i.e. not every 5th but every 10th tick should accept events. And likewise when the network seems reliable for a long time this number could decrease.

But this topic will be covered in another post, first I’ve to try this approach. Although I think this should work nicely as games like Age of Empires and Warcraft used this method pretty reliably.

Recommended reading:

Development for Game Boy (Color)

I have to say, the Game Boy is a pretty impressive platform!

With a 4 MHz 8-bit CPU, 8 kB RAM and 8 kB video RAM it has strict limitations but some nice perspectives at the same time.

It was a rather unexpected fact to me that the 160×144 pixels screen is refreshed at 60 FPS (!) and the device has a 4 channel sound system with mono speaker (but stereo headphone jack). It has also hardware-level tile storing (8×8 or 8×16 tile data, the pixel data) and tile mapping (32×32 tiles map, that’s 256×256 pixels on this bad boy:) ) function. Also, the background-scrolling is implemented in hardware, at any given time 20×18 tiles (160×144 pixels) are visible but 32×32 tiles (256×256 pixels) are in the video RAM.

Documentations I find useful and any work I do will be stored in a git repository on GitHub: https://github.com/gheja/gameboydev/

This post was migrated and edited a bit from my old blog where it was posted on 30th March, 2013.