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.