Tag Archives: Javascript

Multiplayer Snake – Part II – Learning hard things the hard way

Holy crap. The first draft of snake.js was finished quickly, and is available for play here.  The mechanics of the game are super simple, start it up and a board is presented to you with a pale pink snake racing down towards a lime green dot.  Use the arrow keys to move the snake in the direction you want it to turn.  Every time you hit a green dot your snake grows one block longer.  Hit a wall and you die.  Hit your own body and you die.  The game has just about zero syntactic sugar for the user, which is to say, it’s not built to be user-friendly.  Readers of this blog will know by now that I tend to abhor this kind of design.  In this case, I have built the game as an intermediate step in pursuit of a very different end product, and so I do not expect it to be played by anyone; it is not designed to stand on its own, I have included the url here to give the reader some background for the rest of the post.


Immediate challenges: 

I ran into trouble early on in development, when I asked a friend to test the game for me.  She started it up in firefox and reported that her inputs were not registering.  Whoops! After a little rooting around, I tracked down the problem to Firefox’s implementation of the HTML5 specification: when the browser registers a keydown event, the spec calls for a “KeyIdentifier” attribute to come with the event object, detailing which key was hit.  Chrome did it fine, Firefox did not. Not the end of the world, I just added a translation layer into the code, so that now the lower-level “which” attribute is read, and its counterpart is called from a dictionary to find the right input, which then feeds into the game.  Super! A bug squashed!


Now for the fun part, to port it to a multiplayer game.  

Oops.  Turns out that making a game multiplayer is hard. Not hard like writing snake was hard, which (at least for me, and for the first time) it was.  But hard like a hard problem in computer science. Turns out that making a game multiplayer requires coordinating state across several systems in real time, and fast.  What does that mean?

Recalling last post’s digression into the MVC pattern, remember that the way the snake game works is to have a Controller object take inputs from a user, modify a Model of our data, and build a View of the information for the user.  This works fine when there is one user for whom this information must be coordinated, on one system.  But once one of those conditions changes, everything goes to hell.  

Backing up a second, think about how we might make a turn based game like tic-tac-toe multiplayer.  There are approximately two options we could try: first, have each of the two systems (each player’s browser) hold the model, and update it each time the other’s controller object broadcasts a user’s move, which would change where each model should be.  Using TCP (or a TCP based protocol like WebSockets), this is pretty easy, and pretty reliable; TCP ensures that every message sent arrives at its destination, and that it arrives in the order in which it was sent, relative to all others.  That’s pretty cool.  Trust me, it is.  But there’s something fundamentally broken about each player having the model locally, because it violates the idea of a model, which calls for there to be one, and only one True state of things.  Using a TCP protocol just masks this violation, by ensuring that nothing happens until all the controllers have coordinated what the One True Model is, and updating their own accordingly.  For two player tic-tac-toe then, imperfect MVC is fine, or at least, it’s acceptable.  

Ok, now let’s try that with snake.  If each player has its own model of the game locally, and that model is considered canonical (again, a fundamentally broken concept) then no player input may be processed into the model, or from the model into the view (remember, data goes User->Controler->Model->Controller->View->User) until the clients have had a chance to bring everyone else up to speed.  In a turn based game that’s not the end of the world.  Browser’s are serper derper fast, and WebSockets are pretty fast, and together they’re fast enough to coordinate models between each turn fast enough to not be a pain in the ass to players in something like Chess, Checkers, or Tic-Tac-Toe.  But Snake is not a turn based game.  Snake is in real time.  If we force the browsers to coordinate their two models every time the game tries to cycle, it will slow down.  It will suck.  

That would be annoying, and with a game as twitchy as Snake (you need to move rill fast to avoid hitting things) the game is pretty much ruined if you force it to be coordinated between multiple endpoints across a network.  

In fact, it’s a little worse than it sounds.  Remember what we said earlier: the game as we’ve been considering it is actually a corrupted form of MVC, in which there are multiple, potentially conflicting sources of truth.  Making snake step through turns ruins the gamer’s experience, but doesn’t fundamentally destroy the concept of the game.  (Although one could fairly make the case that a game like Snake is no longer itself when it ceases to be a quick twitch-reflex testing game, I’ll leave that decision to the reader for now.)  In other words then you could still play multiplayer web based snake, it would just be kind of crappy.  But now what happens when state somehow changes in one model, and not the other?  Impossible! Our models are coordinating with each other each step, how could they fall truly out of sync?  Well, the trivial case here is a cheater.  Our code is in Javascript, in the browser, and it would be relatively simple for a user to change the game as instantiated to change how his computer understood what was happening in the game.  That kind of mismatch would get ironed out eventually (as long as the game protocol was built robustly enough), but the game states only have to be broken once for the game to be altered entirely.  In other words, it would only take a user one malicious edit to cause his computer to believe that the other player was dead, and for it to report that he had won.  Sorting that out would be basically impossible.  Some answer could be arrived at by the server, but it would be extraordinarily difficult for that answer to be reliable.  That is to say, even if we could make a final ruling, it would be arbitrary, since each browser’s model is considered “TRUE”.  

The solution to this problem is to keep the model the way God intended it to be, singular and unified and held in a third party server.  This is the second of the two models for building the game that I mentioned waaay at the beginning of this article.  The only way to make really truly sure that no player irrevocably cheats the other is to make the server the sole and final arbiter of reality.  From the perspective of the game on either user’s end, the server is the alpha and the omega.  It instantiates a game model, and then accepts inputs from the users, modifies the game accordingly, and reports back to them what reality looks like now.  Sound familiar?  This is the way MVC code is actually really truly supposed to be organized: One Model – I can’t stress that enough – ONE MODEL – is handled by one controller, and fed into however many views you want.  The number of views does not matter.  The superbowls happens the same way whether you have one tv displaying a view of reality, or ten, or ten million.  But what if you tried to have ten superbowls, each of which purported to be simultaneously the same thing as all the others, as well as the gospel truth of what a “The Superbowl” was?  Well basically then you’d have politics.  Depending on how you feel about politics, they’re fine in the political realm, but we don’t want that crap in our computer programs.  

What does all of this mean for you – dear reader?  Well first it means that with apologies, I must withhold from you a multiplayer snake game.  Some reasonable approximation of such a game is still very much possible, but some serious design decisions will have to be made first if I want to make one worth playing.  At this point I’m putting the odds of that at around ~30%.  Not the end of the world, but probably not going to happen in the short-medium term future.  

Our next post will take us away from Javascript for a little while, and into the world of Python.  Stay tuned. 


Multiplayer Snake – Part I

For the next few days I will be working on a multiplayer snake game for the browser.

I love a select few simple arcade games.  Tetris and Snake are my favorites (in that order); but as much as I like to play them I have a surprisingly hard time reasoning about their design.  I understand how to play the games, and in fact how to optimize my game play, which is to say, how to play them well.  (I mostly stopped playing snake when I gave up my last Nokia phone, but I continue to play Tetris, a lot.  I’m surprisingly good at it.)  But as much as I like and understand the games themselves I have never had a good handle on how their engines work.  Because they’re so opaque to me, I have decided to take some time over the next few days to implement both games in Javascript, using the HTML5 canvas, and no external libraries.  For the record, that means no game libraries, no Underscore, no jQuery – nothing but the browser the way god made it. 

Snake seems the easier of the two to design, so I’ve started on that game first.  I’m hosting the game on GitHub, here.  

Elevator Pitch: 

Snake is a game in which a user directs a string of blocks around the screen and attempts to “eat” a randomly placed food object, which will make the string grow longer, while avoiding crashing the snake’s head into its body or one of the four walls. 


High Level Implementation:

The game is implemented in an HTML5 Canvas node, which is a “dumb” canvas which can be colored in by Javascript using arbitrarily complex logic.  At the beginning of each game, a string of blocks will be randomly instantiated on the screen, moving at a constant speed in a randomly selected direction (right, left, up, down).  Since the canvas is a dumb element, it cannot reason about the objects drawn on top of it. All the canvas knows is that it exists, and certain transformations it is supposed to make to any additional drawing done on top of it (eg flip the cursor upside down and then keep painting black on to the screen).  Therefore, the developer has the job of keeping the computer’s understanding of the game synchronized with the viewer’s understanding of the game.  In practice, this means the developer has to update the “model” of the game so that it matches the “view” of the game.  These two elements are in turn controlled by a “controller” element (creative huh?), in what is known in computer science as the “Model-View-Controller” (MVC) architectural pattern.  MVC is considered the correct way to architect code, because it makes certain good things easy to do, and certain bad things hard to do.  MVC will get its own blog post in the future.  


Detailed Implementation:

The MVC pattern described above means that the code is split into three main components.  (I say components because even though they are basically Classes, Javascript does not have classes – it is a classless language.  Slurps soup at restaurants, doesn’t shut up when you kick it under the table, really really classless.)  

  1. Models:
    1. Blocks: Rectangular blocks form the basis for most of this game; they are given a color, size, and location coordinates, and then empowered to show or hide themselves to the viewer, depending on certain circumstances.  The snake, board, and food items will all be made up of these blocks.
    2. Snake: the snake is composed of an array of blocks, with a few extra methods to make my life easier, including the ability to move itself around the board and grow when it needs to (ie when it “eats” something).  Every time the game cycles, the snake’s tail disappears, and is replaced by a new block at the snake’s head.  The old block is deleted from memory, and its visual counterpart is erased from the screen, and the new one is added to the snake’s “model”, and painted onto the screen.  This makes moving the snake an absolute pleasure.  The idea of figuring out where each new block would go each time the snake moved had scared the crap out of me previously, and this way all I have to figure out is where two blocks were (the head and the tail) and where one new one needs to be relative to one of those.  It’s insanely simple, and it works nicely. 
    3. Grid: the board on which the snake moves is composed of a grid, which is held in memory as an array of arrays of objects with location and occupancy status information embedded in them.  This makes collision testing relatively straightforward: to check whether the snake hit something, all we have to check is whether its head is in the same x and y coordinates as our other occupied blocks; these are for the most part simply the outer edge of grid-squares, the snake’s body itself, and whatever food square we place on the map.  This makes collision detection easier and more efficient than scanning the entire board and checking for overlapping spaces.  In fairness, this only works because we’re using a grid; objects of arbitrary shape and size would have to be scanned for using a more sophisticated system.
    4. View: the board view is an object with extremely simple behavior.  It’s sole purpose in life is refreshing the canvas for our viewers, to make sure it reflects the models we’ve established earlier.  It’s really good at doing that.  Like, really good at it.  Nice job Board View.
    5. Controller:  This is where things get hairy.  The game’s controller should be relatively straightforward to reason about, and eventually it will be implemented correctly.  As of now however the implementation is imperfect, and so I will first describe the Controller as it should be, and then as it currently is. 
      1. Controller (proper): the controller’s job in life is to take user inputs and modify the game’s model, and then alert the view that it needs to update the model, which the view will then take care of doing.  Imagine the controller as a middle manager at a newspaper, who’s job is to take the pictures and stories his journalists created and feed them to the people who will handle their layout and printing.  The controller is also responsible for taking in information from the newspaper’s owners, so he can tell his journalists what stories to create.  The controller’s job then is to control the intake and processing, and response flow of information from and back to users.  That’s quite a mouthful, but a simple idea.  The Controller takes things in, and tells different parts of the application what to do with them.  Cool.
      2. Controller (as it is now): The controller as of now is blown all to hell.  I’m racing to finish a first draft of the game, and so I’ve decided to keep the deep internals of the game working correctly while fudging the implementation of its high-level machinery to just get things working.  As of now, that means basically that I’m the controller.  Kind of makes sense, no?  Until I have time to properly think through how the game should flow, I’m building those pieces piecemeal and as needed.  This is not the end of the world, and from the user’s perspective, if my coding is good enough, there should be no difference.  But it is problematic for several reasons (one being my coding may not be good enough – we’ll see), which will be discussed in depth in my MVC post – if it ever gets written.  So for now, think of the game as being architected on the MVM pattern – Model-View-Moshe.  Awesome, now you know how the program works! What fun!!!


The game is not yet published, since the first prototype isn’t yet complete.  It will be by tomorrow though, and I will publish a working link to a basic version of the game, probably hosted through heroku.  

Not enough for you? Fine, here’s a teaser: I also spent some of last week building a realtime chat server using Python, the code for which is also up on GitHub here.  My plan is to finish implementing the Snake game, and before I get to Tetris to port Snake to a multiplayer version, coordinated in real time through the server.  You’ll know when it’s ready.  Especially if you’re sitting next to me. But also if you continue reading this blog.  If you’ve read this far in this post, I’m guessing you’ll see that one when it comes out too.  

Thanks for listening!




Some interesting Javascript CRUD

For my first week at Hacker School, I built a small Javascript library to help manage (relatively) large data sets in the browser. Most web apps use relatively primitive tools to manage data. Collections of objects are usually dumped into global scope, and either looped through or called using human-usable namespaces as needed. It’s the type of data management we all do in our first programs, and it’s generally good enough for the browser, where most data doesn’t persist between sessions.

Partly, this comes from the insanely (full presentation here http://fr.slideshare.net/marcusf/nonblocking-io-event-loops-and-nodejs) high overhead associated with network IO. Pulling information off of a server and into your browser takes an unbelievably long time, in computer terms, and so developers try to minimize the amount of information they move for any given session. This means first that most webapps have relatively little data to work with at any given time, and second that even if they did, their developers are usually wise to spend most of their efforts speeding up other areas of their website. For most websites, that is, managing local data is not the bottleneck.

Fine, bad data management practices are reasonable to expect in this context, and they’re not so harmful. But there are still very good reasons to avoid them. To begin with, the amount of data handled by the browser has been growing over time, and is likely to continue to grow. Manually calling objects as you need them may be possible today, but there is no guarantee that it will be tomorrow. Second, using consistent, predictable patterns in your code makes it easier to collaborate with other developers, and to extend the code yourself later. This isn’t rocket science. (But it is computer science!) The less hard-coding you do in your code the better, and wrapping your data up with abstraction layers is a great way to make your life easier.

With this in mind, I wrote JsCRUD.js. It’s a small library (currently ~120 sloc) that’s designed to wrap up the browser’s localStorage (or sessionStorage) object, to make it possible to Create, Read, Update, and Delete records more easily and faster than it is now.

The library works by creating a set of indices, which track which objects contain which types of values, and then defining a set of functions which serialize and store (and later, retrieve) your objects in one of the browser’s key-value stores. The library is not yet finished, but it will be shortly.

The project led to a few fascinating discoveries. First, when building the library’s querying tool (readRecord), it became immediately intuitive that it would be easiest to find objects based on a model that the user passes in. I realized partway through writing the feature that this is the same exact paradigm used by MongoDB. This makes a ton of sense, since they’re doing almost exactly the same thing as JsCRUD, at least at the user-interface layer.

The second thing the project seems to be showing me is that web developers don’t seem to be very enthusiastic about their data. Specifically, most of the people I’ve spoken to about the project are either hostile or indifferent to the idea that they should manage their data actively, instead of keeping everything reasonably well scoped and calling things manually. For what it’s worth, I’m not sure they’re wrong. I made my case above for why I think data should be more carefully managed (to be clear: data should be managed, not memory) by the developer. But I also think that the web as it’s built now works pretty well, and that it makes sense for developers to focus their energies on the core of their work, relying on faster browser engines to compensate for imperfect design. I happen to really like databases, and I think there’s real value in making your data more robustly queryable than it often is.

In fact, the HTML5 specification agrees with me on this point, which is why the IndexedDB API exists. It’s a pretty cool tool. There is also a legacy API in most databases, WebSQL, which exposes an SQLite database to Javascript in the browser. The latter system is no longer included in the HTML spec, and probably for good reason. SQL is an amazing language that gives developers incredibly good control over their data, but at the cost of forcing them to switch languages and paradigms for various functionality within their system. That’s fine when users have a ton of data and complicated data needs. But in the browser most data is still orders of magnitude smaller than on the desktop, let alone big enterprise systems, meaning that the friction incurred by switching back and forth between languages makes less sense.

What does all of this mean to you? First, keep an eye on your data in web applications. If you’re managing any large number of records, there may be value in using some system that permits you to manage them in a logical way. You may be able to get away with brute-forcing it for now, but that approach doesn’t always scale, and besides, it’s kind of ugly. Second, get to know your browser’s APIs. HTML5 and Javascript have a surprisingly large and powerful ecosystem of tools built right into the browser, and if you understand how they work you can get a lot more power out of your code.

Feel free to check out my project on GitHub. Fork it if you like, and by all means feel free to mess around with the code, and offer changes if you think you can improve it.