15_game.txt

:chap_num: 15
:prev_link: 14_event
:next_link: 16_canvas
:load_files: ["code/chapter/15_game.js", "code/game_levels.js"]

= Project: A Platform Game =

[quote,Iain Banks,The Player of Games]
____
All reality is a game.
____

(((Banks+++,+++ Ian)))(((project chapter)))(((simulation)))My initial
fascination with computers, like that of many kids, originated with
computer ((game))s. I was drawn into the tiny computer-simulated
((world))s which I could manipulate and in which stories (sort of)
unfolded. More, I suppose, because of the way I could project my
((imagination)) into them, than because of the possibilities they
actually offered.

I wouldn't wish a ((career)) in game programming on anyone—much like
in the ((music)) industry, the discrepancy between the many eager
young people wanting to work in it and the actual demand for such
people creates a rather unhealthy environment. But writing games for
fun is amusing.

(((jump-and-run game)))(((dimensions)))This chapter will walk through
the implementation of a simple ((platform game)). Platform games (or
“jump and run” games) are games that expect the ((player)) to move a
figure through a ((world)), which is often two dimensional and viewed
from the side, and involve lots jumping onto and over things.

== The game ==

(((minimalism)))(((Palef+++,+++ Thomas)))(((Dark Blue (game))))Our
((game)) will be roughly based on
“http://www.lessmilk.com/games/10[Dark Blue]”(!tex (_www.lessmilk.com/games/10_)!) by Thomas Palef. I chose this game
because it is both entertaining and minimalist, and can be built
without too much ((code)). It looks like this:

image::img/darkblue.png[alt="The game Dark Blue"]

// FIXME Make this explanation work for the grayscale paper book

(((coin)))(((lava)))The dark ((box)) represents the ((player)), whose
task it is to collect the yellow boxes (coins) while avoiding the red
stuff (lava?). A ((level)) is completed when all coins have been
collected.

(((keyboard)))(((jumping)))The player can walk around with the left
and right arrow keys, and jump with the up arrow. Jumping is a
specialty of this game character. It can reach several times its own
height, and is able to change direction in mid-air. This may not be
entirely realistic, but it helps give the player the feeling of being
in direct control of the on-screen ((avator)).

(((fractional number)))(((discretization)))(((artificial
life)))(((electronic life)))The ((game)) consist of a fixed
((background)), laid out like a ((grid)), with the moving elements
overlaid on that. Each field on the background grid is either empty,
solid, or ((lava)). The moving elements are the player, coins, and
pieces of lava that move. Unlike the artificial life simulation from
link:07_elife.html#elife[Chapter 7], the positions of these elements
are not constrained to the grid—their coordinates may be fractional,
allowing smooth ((motion)).

== The technology ==

(((event handling)))(((keyboard)))We will use the ((browser)) ((DOM))
to display the game, and read user input by handling key events.

(((rectangle)))(((background (CSS))))(((position
(CSS))))(((graphics)))The screen- and keyboard-related code is only a
tiny part of the work we need to do to build this ((game)). Since
everything looks like colored ((box))es, drawing is uncomplicated: we
create DOM elements, and use styling to give them a background color,
size, and position.

(((table (HTML tag))))We can represent the background as a table, since it
is an unchanging ((grid)) of squares. The free-moving elements can be
overlaid on top of that, using absolutely positioned elements.

(((performance)))In games and other programs that have to animate
((graphics)) and respond to user ((input)) without noticeable delay,
((efficiency)) is important. Though the ((DOM)) was not originally
designed for high-performance graphics, it is actually better at this
than you would expect. We saw some ((animation))s in
link:13_dom.html#animation[Chapter 13]. On a modern machine, a simple
game like this performs well even if we don't think about
((optimization)) very much.

(((canvas)))In the link:16_canvas.html#canvas[next chapter], we will
explore another ((browser)) technology, the `<canvas>` tag, which
provides a more traditional way to draw graphics, working in terms of
shapes and ((pixel))s, rather than ((DOM)) elements.

== Levels ==

(((dimensions)))In link:07_elife.html#plan[Chapter 7] we used arrays
of strings to describe a two-dimensional ((grid)). We can do the same
here. It will allow us to design ((level))s without first building a
level ((editor)).

This would be what a simple level look like:

// include_code

[source,javascript]
----
var simpleLevelPlan = [
  "                      ",
  "                      ",
  "  x              = x  ",
  "  x         o o    x  ",
  "  x @      xxxxx   x  ",
  "  xxxxx            x  ",
  "      x!!!!!!!!!!!!x  ",
  "      xxxxxxxxxxxxxx  ",
  "                      "
];
----

Both the fixed ((grid)) and the moving elements are included in the
plan. The “x” characters stand for ((wall))s, space characters for empty
space, and exclamation marks for fixed, non-moving lava tiles.

(((level)))The “@” defines the place where the ((player)) starts. Every “o” is a
((coin)), and the equals sign (“=”) stands for a block of ((lava))
that moves back and forth horizontally. Note that the ((grid)) for
these positions will be set to contain empty space, and another data
structure is used to track the position of such moving elements.

(((bouncing)))We'll support two other kinds of moving ((lava)): the
pipe character (“|”) for vertically moving blobs, and “v” for
_dripping_ lava—vertically moving lava that doesn't bounce back and
forth, but only moves down, jumping back to its start position when it
hits the floor.

A whole ((game)) consists of multiple ((level))s, though which the
((player)) must move, collecting all ((coin))s in each. After touching
((lava)), the current level is restored to its starting position, and
the player may try again.

[[level]]
== Reading a level ==

(((Level type)))The following ((constructor)) builds a ((level))
object. Its argument should be the array of strings that define the
level.

// include_code

[source,javascript]
----
function Level(plan) {
  this.width = plan[0].length;
  this.height = plan.length;
  this.grid = [];
  this.actors = [];

  for (var y = 0; y < this.height; y++) {
    var line = plan[y], gridLine = [];
    for (var x = 0; x < this.width; x++) {
      var ch = line[x], fieldType = null;
      var Actor = actorChars[ch];
      if (Actor)
        this.actors.push(new Actor(new Vector(x, y), ch));
      else if (ch == "x")
        fieldType = "wall";
      else if (ch == "!")
        fieldType = "lava";
      gridLine.push(fieldType);
    }
    this.grid.push(gridLine);
  }

  this.player = this.actors.filter(function(actor) {
    return actor.type == "player";
  })[0];
  this.status = this.finishDelay = null;
}
----

(((validation)))For brevity, the code does not check for malformed
input, such as a ((level)) plan without a player start position. It
assumes that it is given a proper level plan.

(((array)))A level stores its width and height, along with two
arrays—one for the ((grid)), and one for the _((actor))s_, the dynamic
elements. The grid is represented as an array of arrays, where each of
the inner arrays represents a horizontal line, and each square
contains either null, for empty squares, or a string indicating the
type of the square—`"wall"` or `"lava"`.

The ((actor))s array holds objects that track the current position and
((state)) of the dynamic elements in the ((level)). Each of these is
expected to have a `pos` property giving its position (the
((coordinates)) of its top left corner), a `size` property giving its
size, and a `type` property that holds a string that identifies the
element (`"lava"`, `"coin"`, or `"player"`).

(((filter method)))After building the grid, we use the `filter` method
to find the ((player)) actor object, and store it in a property of the
level. The `status` property tracks whether the player has won or
lost. When this happens `finishDelay` is used to keep the level active
for a short period of time, so that a simple ((animation)) can be
shown. (Immediately resetting or advancing the level would look
cheap.) This method can be used to find out whether a ((level)) is
finished:

// include_code

[source,javascript]
----
Level.prototype.isFinished = function() {
  return this.status != null && this.finishDelay < 0;
};
----

== Actors ==

[[vector]]
(((Vector type)))(((coordinates)))To store the position and size of an
actor, we will return to our trusty `Vector` type, which groups an x
and y coordinate into an object.

// include_code

[source,javascript]
----
function Vector(x, y) {
  this.x = x; this.y = y;
}
Vector.prototype.plus = function(other) {
  return new Vector(this.x + other.x, this.y + other.y);
};
Vector.prototype.times = function(factor) {
  return new Vector(this.x * factor, this.y * factor);
};
----

(((times method)))(((multiplication)))The `times` method scales a
vector by a given amount. It will be useful when we need to multiply a
speed vector by a time interval, to get the distance traveled during
that time.

(((map)))(((object,as map)))The `actorChars` object was used by
the `Level` constructor to associate characters with constructor
functions. It looks like this:

// include_code

[source,javascript]
----
var actorChars = {
  "@": Player,
  "o": Coin,
  "=": Lava, "|": Lava, "v": Lava
};
----

(((lava)))(((bouncing)))Three characters map to `Lava`. The `Level`
constructor passes the actor's source character as second argument to
the constructor, and the `Lava` constructor uses that to adjust its
behavior (bouncing horizontally, bouncing vertically, or dripping).

(((simulation)))(((Player type)))The player type is built with the
constructor below. It has a property `speed` that stores its current
speed, which will help simulate momentum and gravity.

// include_code

[source,javascript]
----
function Player(pos) {
  this.pos = pos.plus(new Vector(0, -0.5));
  this.size = new Vector(0.8, 1.5);
  this.speed = new Vector(0, 0);
}
Player.prototype.type = "player";
----

Because a player is one and a half square high, its initial position
is set to be half a square above the position where the “@” character
appeared. This way, its bottom aligns with the bottom of the square
it appeared in.

(((Lava type)))(((bouncing)))When constructing a dynamic `Lava`
object, we need to initialize the object differently depending on the
character it is based on. Dynamic lava moves along at its given speed
until it hits an obstacle. At that point, if it has a `repeatPos`
property, it will jump back to its start position (dripping). If it
does not, it will invert its speed and continue in the other direction
(bouncing). The constructor only sets up the necessary properties—the
method that does the actual moving will be written
link:15_game.html#actors[later on].

// include_code

[source,javascript]
----
function Lava(pos, ch) {
  this.pos = pos;
  this.size = new Vector(1, 1);
  if (ch == "=") {
    this.speed = new Vector(2, 0);
  } else if (ch == "|") {
    this.speed = new Vector(0, 2);
  } else if (ch == "v") {
    this.speed = new Vector(0, 3);
    this.repeatPos = pos;
  }
}
Lava.prototype.type = "lava";
----

(((Coin type)))(((animation)))`Coin` actors are simple. They mostly
just sit in their place. But to liven up the game a little, they are
given a “wobble”, a slight vertical motion back and forth. To track
this, a coin object stores a base position as well as a `wobble`
property that tracks the ((phase)) of the bouncing motion. Together,
these determine the coin's actual position (stored in the `pos`
property).

// include_code

[source,javascript]
----
function Coin(pos) {
  this.basePos = this.pos = pos.plus(new Vector(0.2, 0.1));
  this.size = new Vector(0.6, 0.6);
  this.wobble = Math.random() * Math.PI * 2;
}
Coin.prototype.type = "coin";
----

(((Math.random function)))(((random number)))(((Math.sin
function)))(((sine)))(((wave)))(((pi)))To avoid a situation where all
coins move up and down synchronously, the starting phase of each coin
is randomized. We will be using `Math.sin` (a sine wave) to model the
motion, so we multiply the value returned by `Math.random` by 2π,
which causes it to take a random position on that wave. If none of
this makes sense to you, don't worry, it is not necessary to
understand it to follow the chapter.

We have now written all the parts needed to initialize a level.

// include_code strip_log

[source,javascript]
----
var simpleLevel = new Level(simpleLevelPlan);
console.log(simpleLevel.width, "by", simpleLevel.height);
// → 22 by 9
----

== Encapsulation as a burden ==

(((programming style)))(((program size)))(((complexity)))Most of the
code in this chapter does not worry about ((encapsulation)). This has
two reasons. Firstly, encapsulation takes extra effort. It will make
programs bigger and require additional concepts and interfaces to be
introduced. Since there is only so much code you can throw at a reader
before their eyes glaze over, I've made an effort to keep the program
small.

(((interface)))Secondly, the various elements in this game are so
closely tied together that if the behavior of one of them changed, it
is unlikely that any of the others would be able to stay the same.
Interfaces between the elements would end up encoding a lot of
assumptions about the way the game works. This makes them a lot less
effective—whenever you change one part of the system, you still have
to worry about the way it impacts the other parts, because their
interfaces wouldn't cover the new situation.

Some _cutting points_ in a system lend themselves well to separation
through rigorous interfaces , others don't. Trying to encapsulate
something that isn't a suitable boundary is a sure way to waste a lot
of energy. When you are making this mistake, you'll usually notice
that your interfaces are getting awkwardly large and detailed, and
that they need to be modified often, as the program evolves.

(((graphics)))(((encapsulation)))(((graphics)))There is one thing that
we _will_ encapsulate in this chapter, and that is the ((drawing))
subsystem. The reason for this is that we will ((display)) the same
game in a different way in the link:16_canvas.html#canvasdisplay[next
chapter]. By putting the drawing behind an interface, we can simply
load the same game program there, and plug in a new display
((module)).

[[domdisplay]]
== Drawing ==

(((DOMDisplay type)))The encapsulation of the ((drawing)) code is done
by defining a _((display))_ object, which displays a given ((level)).
The display type we define in this chapter is called `DOMDisplay`,
because it uses simple ((DOM)) elements to show the level.

(((style attribute)))We will be using a ((style sheet)) to set the
actual colors and other fixed properties of the elements that make up
the game. It would also be possible to directly assign to the
elements’ `style` property when we create them, but that would produce
more verbose programs.

(((class attribute)))The following helper function provides a short way to
create an element and give it a class.

// include_code

[source,javascript]
----
function elt(name, className) {
  var elt = document.createElement(name);
  if (className) elt.className = className;
  return elt;
}
----

A display is created by giving it a parent element to which it should
append itself, and a ((level)) object.

// include_code

[source,javascript]
----
function DOMDisplay(parent, level) {
  this.wrap = parent.appendChild(elt("div", "game"));
  this.level = level;

  this.wrap.appendChild(this.drawBackground());
  this.actorLayer = null;
  this.drawFrame();
}
----

(((appendChild method)))We used the fact that `appendChild` returns
the appended element to create the wrapper element and store it in the
`wrap` property in a single statement.

(((level)))The level's ((background)), which never changes, is drawn
once. The actors are redrawn every time the display is updated. The
`actorLayer` property will be used by `drawFrame` to track the element
that holds the actors, so that they can be easily removed and
replaced.

(((scaling)))(((DOMDisplay type)))Our ((coordinates)) and sizes are
tracked in units relative to the ((grid)) size, where a size or
distance of one means one grid unit. When setting ((pixel)) sizes, we
will have to scale these coordinates up—things would be ridiculously
small at a single pixel per square. The `scale` variable gives the
amount of pixels a single unit takes up on the screen.

// include_code

[source,javascript]
----
var scale = 20;

DOMDisplay.prototype.drawBackground = function() {
  var table = elt("table", "background");
  table.style.width = this.level.width * scale + "px";
  this.level.grid.forEach(function(row) {
    var rowElt = table.appendChild(elt("tr"));
    rowElt.style.height = scale + "px";
    row.forEach(function(type) {
      rowElt.appendChild(elt("td", type));
    });
  });
  return table;
};
----

[[game_css]]
(((style sheet)))(((CSS)))(((table (HTML tag))))As mentioned earlier, the
background is drawn as a `<table>` element. This nicely corresponds to
the structure of the `grid` property in the level—each row of the grid
is turned into a table row (`<tr>` element). The strings in the grid
are used as class names for the table cell (`<td>`) elements. The
following CSS helps the resulting table look like the background we
want:

[source,text/css]
----
.background    { background: rgb(52, 166, 251);
                 table-layout: fixed;
                 border-spacing: 0;              }
.background td { padding: 0;                     }
.lava          { background: rgb(255, 100, 100); }
.wall          { background: white;              }
----

(((padding (CSS))))Some of these (`table-layout`, `border-spacing`,
and `padding`) are simply used to suppress unwanted default behavior.
We don't want space between the ((table)) cells, or padding inside
them, and we set the table's approach for computing the width of its
columns to a simple, predictable variant (the way tables are laid out
in HTML is a complicated thing).

(((background (CSS))))(((rgb (CSS))))(((CSS)))The `background` rule
sets the background color. CSS allows colors to be specified both as
words (`white`) and with a format like `rgb(R, G, B)`, where the red,
green, and blue components of the color are separated into three
numbers from 0 to 255. So in `rgb(52, 166, 251)` the red component is
52, green is 166, and blue is 251. Since the blue component is the
largest, the resulting color will be blueish. You can see that in the
`.lava` rule, the first number (red) is the largest.

Drawing the ((actor))s is done by creating a ((DOM)) element for each,
and setting its position and size based on the actor's properties. The
values have to be multipled by `scale` to go from game units to
pixels.

// include_code

[source,javascript]
----
DOMDisplay.prototype.drawActors = function() {
  var wrap = elt("div");
  this.level.actors.forEach(function(actor) {
    var rect = wrap.appendChild(elt("div", "actor " +
                                           actor.type));
    rect.style.width = actor.size.x * scale + "px";
    rect.style.height = actor.size.y * scale + "px";
    rect.style.left = actor.pos.x * scale + "px";
    rect.style.top = actor.pos.y * scale + "px";
  });
  return wrap;
};
----

(((position (CSS))))(((class attribute)))Giving an element more than one
class is done by separating the class names with spaces. In the
((CSS)) code shown next, the `actor` class gives the actors their
absolute position. Their type name is used as an extra class to give
them a color (lava actors use the same class as lava grid squares,
which we defined earlier):

[source,text/css]
----
.actor  { position: absolute;            }
.coin   { background: rgb(241, 229, 89); }
.player { background: rgb(64, 64, 64);   }
----

(((graphics)))(((optimization)))(((efficiency)))When it updates the
display, the `drawFrame` method first removes the old actor graphics,
if any, and then redraws them in their new positions. It may be
tempting to try and reuse the ((DOM)) elements for actors, but to make
that work, we would need a lot of additional information flow between
the display code and the simulation code. We'd need to associate
actors with DOM elements, and the ((drawing)) code must remove
elements when their actors vanish. Since there will typically only be
a handful of actors in the game, redrawing all of them is is not
expensive.

// include_code

[source,javascript]
----
DOMDisplay.prototype.drawFrame = function() {
  if (this.actorLayer)
    this.wrap.removeChild(this.actorLayer);
  this.actorLayer = this.wrap.appendChild(this.drawActors());
  this.wrap.className = "game " + (this.level.status || "");
  this.scrollPlayerIntoView();
};
----

(((level)))(((class attribute)))(((style sheet)))By adding the level's
current status as a class name to the wrapper, we can style the player
actor slightly differently when the game is won or lost, by adding a
((CSS)) rule that only takes effect when the player has an ((ancestor
element)) with a given class.

[source,text/css]
----
.lost .player {
  background: rgb(160, 64, 64);
}
.won .player {
  box-shadow: -4px -7px 8px white, 4px -7px 8px white;
}
----

(((player)))(((box shadow (CSS))))After touching ((lava)), the
player's color turns dark red, suggesting scorching. When the last
coin has been collected, we use two white box shadows, one to the top
left and one to the top right, to create a white halo effect.

[[viewport]]

(((position (CSS))))(((max-width (CSS))))(((overflow
(CSS))))(((max-height (CSS))))(((viewport)))We can't assume that
levels always fit in the viewport. That is why the
`scrollPlayerIntoView` call is needed—it ensures that, if the level is
sticking out outside of the viewport, we scroll that viewport to make
sure the player is near its center. The following ((CSS)) gives the
game's wrapping ((DOM)) element a maximum size, and ensures that
anything that sticks out is not displayed. We also give it a relative
position, so that the actors inside of it are positioned relative to
its own top left corner.

[source,text/css]
----
.game {
  overflow: hidden;
  max-width: 600px;
  max-height: 450px;
  position: relative;
}
----

(((scrolling)))In the `scrollPlayerIntoView` method, we find the
player's position, and update the wrapping element's scroll position,
by manipulating it's `scrollLeft` and `scrollTop` properties, when the
player is too close to the edge.

// include_code

[source,javascript]
----
DOMDisplay.prototype.scrollPlayerIntoView = function() {
  var width = this.wrap.clientWidth;
  var height = this.wrap.clientHeight;
  var margin = width / 3;

  // The viewport
  var left = this.wrap.scrollLeft, right = left + width;
  var top = this.wrap.scrollTop, bottom = top + height;

  var player = this.level.player;
  var center = player.pos.plus(player.size.times(0.5))
                 .times(scale);

  if (center.x < left + margin)
    this.wrap.scrollLeft = center.x - margin;
  else if (center.x > right - margin)
    this.wrap.scrollLeft = center.x + margin - width;
  if (center.y < top + margin)
    this.wrap.scrollTop = center.y - margin;
  else if (center.y > bottom - margin)
    this.wrap.scrollTop = center.y + margin - height;
};
----

(((center)))(((coordinates)))(((readability)))The way the player's
center is found shows how the methods on our `Vector` type allow
computations with objects to be written in a rather readable way. To
find the actor's center, we add its position (its top left corner) and
half its size. That is the center in level coordinates, but we need it
in pixel coordinates, so we then multiply the resulting vector by our
display scale.

(((validation)))Next, a series of checks verify that the player
position isn't outside of the allowed range. Note that sometimes this
will set nonsense scroll coordinates, below zero or beyond the
element's scrollable area. This is okay—the DOM will constrain them to
sane values. Setting `scrollLeft` to -10 will cause it to become zero.

It would have been slightly simpler to always try to scroll the player
to the center of the ((viewport)). But this creates a rather jarring
effect. As you are jumping, the view will constantly shift up and
down. It is more pleasant to have a “neutral” area in the middle of
the screen, where you can move around without causing any scrolling.

(((cleaning up)))Finally, we'll need a way to clear a displayed level,
to be used when the game moves on to the next level or resets a level.

// include_code

[source,javascript]
----
DOMDisplay.prototype.clear = function() {
  this.wrap.parentNode.removeChild(this.wrap);
};
----

(((game,screenshot)))We are now able to display our tiny level:

[source,text/html]
----
<link rel="stylesheet" href="css/game.css">

<script>
  var simpleLevel = new Level(simpleLevelPlan);
  var display = new DOMDisplay(document.body, simpleLevel);
</script>
----

ifdef::tex_target[]

image::img/game_simpleLevel.png[alt="Our level rendered",width="7cm"]

endif::tex_target[]

(((link (HTML tag))))(((style sheet)))(((CSS)))The `<link>` tag, when used
with `rel="stylesheet"`, is a way to load a CSS file into a page. The
file `game.css` contains the styles necessary for our game.

== Motion and collision ==

(((physics)))(((animation)))Now we get to the point where we can start
adding motion—the most interesting aspect of the game. The basic
approach, taken by most games like this, is to split ((time)) into
small steps, and for each step, move the actors by a distance
corresponding to their speed (distance moved per second) multiplied by
the size of the time step (in seconds).

(((obstacle)))(((collision detection)))That is easy. The difficult
part is to deal with the interactions between the elements. When the
player hits a wall or floor, they should not simply move through it.
The game must notice when a given motion causes an object to hit
another object, and respond accordingly—for walls, the motion must be
stopped, for coins, the coin collected, and so on.

Solving this for the general case is a big task. You can find
libraries, usually called _((physics engine))s_, that simulate
interaction between physical objects in two or three ((dimensions)).
We'll take a more modest approach in this chapter, handling only
collisions between boxes, and handling them in a rather simplistic
way.

(((bouncing)))(((collision detection)))(((animation)))Before moving
the ((player)) or a block of ((lava)), we test whether the motion
would take it inside of a non-empty part of the ((background)). If it
does, we simply cancel the motion altogether. The response to such a
collision depends on the type of actor—the player will stop, whereas a
lava block will bounce back.

(((discretization)))This approach requires our ((time)) steps to be
rather small, since it will cause motion to stop before the objects
actually touch. If the time steps, and thus the motion steps, are too
big, the player would end up hovering a noticeable distance above the
ground. Another approach, arguably better but more complicated, would
be to find the exact collision spot, and move there. We will take the
simple approach, and hide its problems by ensuring the animation
proceeds in small steps.

(((obstacle)))(((obstacleAt method)))(((collision detection)))This
method tells us whether a ((rectangle)) (specified by a position and a
size) overlaps with any non-empty space on the background grid:

// include_code

[source,javascript]
----
Level.prototype.obstacleAt = function(pos, size) {
  var xStart = Math.floor(pos.x);
  var xEnd = Math.ceil(pos.x + size.x);
  var yStart = Math.floor(pos.y);
  var yEnd = Math.ceil(pos.y + size.y);

  if (xStart < 0 || xEnd > this.width || yStart < 0)
    return "wall";
  if (yEnd > this.height)
    return "lava";
  for (var y = yStart; y < yEnd; y++) {
    for (var x = xStart; x < xEnd; x++) {
      var fieldType = this.grid[y][x];
      if (fieldType) return fieldType;
    }
  }
};
----

(((Math.floor function)))(((Math.ceil function)))It computes the set
of grid squares that the body ((overlap))s with by using `Math.floor`
and `Math.ceil` on its ((coordinates)). Remember that ((grid)) squares
are one by one unit in size. By ((rounding)) the sides of a box up and
down, we get the range of ((background)) squares that the box touches.

image::img/game-grid.svg[alt="Finding collisions on a grid",width="3cm"]

If the body sticks out of the level, we always return `"wall"` for the
sides and top, and `"lava"` for the bottom. This ensures that the
player dies when falling out of the world. When the body is fully
inside the grid, we loop over the block of ((grid)) squares found by
((rounding)) the ((coordinates)), and return the content of the first
non-empty square we find.

(((coin)))(((lava)))(((collision detection)))Collisions between the
((player)) and other dynamic ((actor))s (coins, moving lava) are
handled _after_ the player moved. When the motion has taken the player
into another other actor, the appropriate effect—collecting a coin or
dying—is activated.

(((actorAt method)))This method scans through the array of actors,
looking for an actor that overlaps the one given as an argument.

// include_code

[source,javascript]
----
Level.prototype.actorAt = function(actor) {
  for (var i = 0; i < this.actors.length; i++) {
    var other = this.actors[i];
    if (other != actor &&
        actor.pos.x + actor.size.x > other.pos.x &&
        actor.pos.x < other.pos.x + other.size.x &&
        actor.pos.y + actor.size.y > other.pos.y &&
        actor.pos.y < other.pos.y + other.size.y)
      return other;
  }
};
----

[[actors]]
== Actors and actions ==

(((animate method)))(((animation)))(((keyboard)))The `animate` method
on the `Level` type gives all actors in the level a chance to move.
Its `step` argument is the ((time)) step in seconds, `keys` is an
object with information about the current position of the arrow keys.

// include_code

[source,javascript]
----
var maxStep = 0.05;

Level.prototype.animate = function(step, keys) {
  if (this.status != null)
    this.finishDelay -= step;

  while (step > 0) {
    var thisStep = Math.min(step, maxStep);
    for (var i = 0; i < this.actors.length; i++)
      this.actors[i].act(thisStep, this, keys);
    step -= thisStep;
  }
};
----

(((level)))(((animation)))When the level's `status` property has a
non-null value (which is the case when the player has won or lost), we
must count down the `finishDelay` property, which tracks the time
between the point where winning or losing happens and the point where
we want to stop showing the level.

(((while loop)))(((discretization)))The `while` loop cuts the time
step we are animating into suitably small pieces. It ensures that no
step larger than `maxStep` is taken. For example, a `step` of 0.12
second would be cut into two steps of 0.05 second, and one of 0.02.

(((actor)))(((Lava type)))(((lava)))Actor objects have an `act`
method, which gets as arguments the time step, the level object, and
the `keys` object. Here is a simple one, for the `Lava` actor type,
which ignores the key object:

// include_code

[source,javascript]
----
Lava.prototype.act = function(step, level) {
  var newPos = this.pos.plus(this.speed.times(step));
  if (!level.obstacleAt(newPos, this.size))
    this.pos = newPos;
  else if (this.repeatPos)
    this.pos = this.repeatPos;
  else
    this.speed = this.speed.times(-1);
};
----

(((bouncing)))(((multiplication)))(((Vector type)))(((collision
detection)))It computes a new position by adding the product of the
((time)) step and its current speed to its old position. If no
obstacle blocks that new position, it moves there. If there is an
obstacle, the behavior depends on the type of the ((lava))
block—dripping lava has a `repeatPos` property, to which it jumps back
when it hits something. Bouncing lava simply inverts its speed
(multiplies it by -1) in order to start moving in the other direction.

(((Coin type)))(((coin)))(((wave)))Coins use their `act` method to
wobble. They ignore collisions, since they are simply wobbling around
inside of their own square, and collisions with the ((player)) will be
handled by the _player_'s `act` method.

// include_code

[source,javascript]
----
var wobbleSpeed = 8, wobbleDist = 0.07;

Coin.prototype.act = function(step) {
  this.wobble += step * wobbleSpeed;
  var wobblePos = Math.sin(this.wobble) * wobbleDist;
  this.pos = this.basePos.plus(new Vector(0, wobblePos));
};
----

(((Math.sin function)))(((sine)))(((phase)))The `wobble` property is
updated to track time, and then used as argument to `Math.sin` to
create a ((wave)), which is used to compute a new position.

(((collision detection)))(((Player type)))That leaves the ((player))
itself. Player motion is handles separately per ((axis)), because
hitting the floor should not prevent horizontal motion, and hitting a
wall should not stop falling or jumping motion. This method implements
the horizontal part:

// include_code

[source,javascript]
----
var playerXSpeed = 7;

Player.prototype.moveX = function(step, level, keys) {
  this.speed.x = 0;
  if (keys.left) this.speed.x -= playerXSpeed;
  if (keys.right) this.speed.x += playerXSpeed;

  var motion = new Vector(this.speed.x * step, 0);
  var newPos = this.pos.plus(motion);
  var obstacle = level.obstacleAt(newPos, this.size);
  if (obstacle)
    level.playerTouched(obstacle);
  else
    this.pos = newPos;
};
----

(((animation)))(((keyboard)))The motion is computed based on the state
of the left and right arrow keys. When it would cause the player to
hit something, the `playerTouched` method on the level, which handles
things like dying in ((lava)) and collecting ((coin))s, is called.
Otherwise, the object updates its position.

Vertical motion works in a similar way, but has to simulate
((jumping)) and ((gravity)).

// include_code

[source,javascript]
----
var gravity = 30;
var jumpSpeed = 17;

Player.prototype.moveY = function(step, level, keys) {
  this.speed.y += step * gravity;
  var motion = new Vector(0, this.speed.y * step);
  var newPos = this.pos.plus(motion);
  var obstacle = level.obstacleAt(newPos, this.size);
  if (obstacle) {
    level.playerTouched(obstacle);
    if (keys.up && this.speed.y > 0)
      this.speed.y = -jumpSpeed;
    else
      this.speed.y = 0;
  } else {
    this.pos = newPos;
  }
};
----

(((acceleration)))(((physics)))At the start of the method, the player
is accelerated vertically to account for ((gravity)). The gravity,
((jumping)) speed, and pretty much all other ((constant))s in this
game, have been set by ((trial-and-error)). I tried out various values
to see how they felt.

(((collision detection)))(((keyboard)))(((jumping)))Next we check for
obstacles again. If we hit an obstacle, there are two possible
outcomes. When the up arrow is pressed, _and_ we are moving down
(meaning the thing we hit is below us), the speed is set to a
relatively large, negative value. This causes the player to jump. If
that is not the case, we simply bumped into something, and the speed
is reset to zero.

The actual `act` method looks like this:

// include_code

[source,javascript]
----
Player.prototype.act = function(step, level, keys) {
  this.moveX(step, level, keys);
  this.moveY(step, level, keys);

  var otherActor = level.actorAt(this);
  if (otherActor)
    level.playerTouched(otherActor.type, otherActor);

  // Losing animation
  if (level.status == "lost") {
    this.pos.y += step;
    this.size.y -= step;
  }
};
----

(((player)))After moving, the method checks for other actors that the
player is colliding with, and again calls `playerTouched` when it
finds one. This time, it passes the actor object as second argument,
because if the other actor is a ((coin)), `playerTouched` needs to
know _which_ coin is being collected.

(((animation)))Finally, when the player died (touched lava) we set up
a little animation that causes them to “shrink” or “sink” down, by
reducing the height of the player object.

(((collision detection)))And here is the method that handles
collisions between the player and other objects:

// include_code

[source,javascript]
----
Level.prototype.playerTouched = function(type, actor) {
  if (type == "lava" && this.status == null) {
    this.status = "lost";
    this.finishDelay = 1;
  } else if (type == "coin") {
    this.actors.splice(this.actors.indexOf(actor), 1);
    if (!this.actors.some(function(actor) {
      return actor.type == "coin";
    })) {
      this.status = "won";
      this.finishDelay = 1;
    }
  }
};
----

When ((lava)) is touched, the game's status is set to `"lost"`. When a
coin is touched, that ((coin)) is removed from the array of actors,
and if it was the last one, the game's status is set to `"won"`.

(((splice method)))(((array,methods)))(((array,indexing)))(((indexOf
method)))The `splice` method is used to cut a piece out of an array.
You give it an index and a number of elements, and _mutates_ the
array, removing that many elements after the given index. In this
case, we remove a single element, our coin actor, whose index we found
by calling `indexOf`. If you pass additional arguments to `splice`
their values will be inserted into the array at the given position,
replacing the removed elements.

This gives us a level that can actually be animated. All that's
missing now is the code that _drives_ the animation.

== Tracking keys ==

(((keyboard)))For a ((game)) like this, we do not want keys to take
effect once per press. Rather, we want their effect (moving the player
figure) to continue happening as long as they are pressed.

(((preventDefault method)))We need to set up a key handler that stores
the current state of the left, right, and up keys. We will also want
to call `preventDefault` for those keys, so that they don't end up
((scrolling)) the page.

(((trackKeys function)))(((key code)))(((event
handling)))(((addEventListener method)))The function below, when given
an object with key codes as property names and key names as value,
will return an object that tracks the current position of those keys.
It registers event handlers for `"keydown"` and `"keyup"` events, and
when the key code in the event is present in the set of codes that it
is tracking, update the object.

// include_code

[source,javascript]
----
var arrowCodes = {37: "left", 38: "up", 39: "right"};

function trackKeys(codes) {
  var pressed = Object.create(null);
  function handler(event) {
    if (codes.hasOwnProperty(event.keyCode)) {
      var down = event.type == "keydown";
      pressed[codes[event.keyCode]] = down;
      event.preventDefault();
    }
  }
  addEventListener("keydown", handler);
  addEventListener("keyup", handler);
  return pressed;
}
----

(((keydown event)))(((keyup event)))Note how the same handler function
is used for both event types. It looks at the event object's `type`
property to determine whether the key state should be updated to true
(`"keydown"`) or false (`"keyup"`).

[[runAnimation]]
== Running the game ==

(((requestAnimationFrame function)))(((animation)))The
`requestAnimationFrame` function, which we saw in
link:13_dom.html#animationFrame[Chapter 13], provides a good way to
animate a game. But its interface is quite primitive—using it requires
us to track the time at which our function was called the last time
around, and call `requestAnimationFrame` again after every frame.

(((runAnimation function)))(((callback function)))(((function,as
value)))(((function,higher-order)))Let's define a helper function that
wraps those boring parts in a convenient interface, and allows us to
simply call `runAnimation`, giving it a function that expects a time
difference as argument and draws a single frame. When the frame
function returns the value `false`, the animation stops.

// include_code

[source,javascript]
----
function runAnimation(frameFunc) {
  var lastTime = null;
  function frame(time) {
    var stop = false;
    if (lastTime != null) {
      var timeStep = Math.min(time - lastTime, 100) / 1000;
      stop = frameFunc(timeStep) === false;
    }
    lastTime = time;
    if (!stop)
      requestAnimationFrame(frame);
  }
  requestAnimationFrame(frame);
}
----

(((time)))(((discretization)))I have set a maximum frame step of 100
milliseconds (one tenth of a second). When the browser tab or window
with our page is hidden, `requestAnimationFrame` calls will be
suspended until it is shown again. In this case, the difference
between `lastTime` and `time` will be the entire time in which the
page was hidden. Advancing the game by that much in a single step will
look silly, and might be a lot of work (remember the time-splitting in
the link:15_game.html#actors[`animate` method]).

The function also converts the time steps to seconds, which are an
easier quantity to think about than milliseconds.

(((callback function)))(((runLevel function)))The `runLevel` function
takes a `Level` object, a constructor for a ((display)), and
optionally a function. It display the level (in `document.body`), and
lets the user play through it. When the level is finished (lost or
won) it clears the display, stops the ((animation)), and if an
`andThen` function was given, calls it with the level's status.

// include_code

[source,javascript]
----
var arrows = trackKeys(arrowCodes);

function runLevel(level, Display, andThen) {
  var display = new Display(document.body, level);
  runAnimation(function(step) {
    level.animate(step, arrows);
    display.drawFrame(step);
    if (level.isFinished()) {
      display.clear();
      if (andThen)
        andThen(level.status);
      return false;
    }
  });
}
----

(((runGame function)))A game is a sequence of ((level))s. Whenever the
((player)) dies, the current level is restarted. When a level is
completed, we move on to the next level. This can be expressed by the
following function, which takes an array of level plans (arrays of
strings) and a ((display)) constructor:

// include_code

[source,javascript]
----
function runGame(plans, Display) {
  function startLevel(n) {
    runLevel(new Level(plans[n]), Display, function(status) {
      if (status == "lost")
        startLevel(n);
      else if (n < plans.length - 1)
        startLevel(n + 1);
      else
        console.log("You win!");
    });
  }
  startLevel(0);
}
----

(((function,higher-order)))(((function,as value)))These functions show
a peculiar style of programming. Both `runAnimation` and `runLevel`
are higher-order functions, but not in the style we saw in
link:05_higher_order.html#higher_order[Chapter 5]. The function
argument is used to arrange things to happen at some time in the
future, and neither of the functions returns anything useful. Their
task is, in a way, to schedule actions. Wrapping these actions in
functions gives us a way to store them as a value, so that they can be
called at the right moment.

(((asynchronous programming)))(((event handling)))This programming
style is usually called _asynchronous_ programming. Event handling is
also an instance of it, and we will see much more of it when working
with tasks that can take an arbitrary amount of ((time)), such as
((network)) requests in link:17_http.html#http[Chapter 17], and in-
and output in general in link:20_node.html#node[Chapter 20].

(((game)))(((GAME_LEVELS data set)))There is a set of
((level)) plans available in the `GAME_LEVELS` variable (!tex (downloadable from
http://eloquentjavascript.net/code[_eloquentjavascript.net/code_])!).
This page feeds them to `runGame`, starting an actual game:

// start_code

[sandbox="null"]
[focus="yes"]
[source,text/html]
----
<link rel="stylesheet" href="css/game.css">

<script>
  runGame(GAME_LEVELS, DOMDisplay);
</script>
----

ifdef::html_target[]

See if you can beat those. I had quite a lot of fun building them.

endif::html_target[]

== Exercises ==

=== Game over ===

(((lives (exercise))))(((game)))It is tradition for ((platform game))s
to have the player start with a limited number of _lives_, and
subtract one life each time they die. When out of lives, the game
restarts from the beginning.

(((runGame function)))Adjust `runGame` to implement lives (have the
player start with 3).

ifdef::html_target[]

// test: no

[focus="yes"]
[source,text/html]
----
<link rel="stylesheet" href="css/game.css">

<script>
  // The old runGame function. Modify it...
  function runGame(plans, Display) {
    function startLevel(n) {
      runLevel(new Level(plans[n]), Display, function(status) {
        if (status == "lost")
          startLevel(n);
        else if (n < plans.length - 1)
          startLevel(n + 1);
        else
          console.log("You win!");
      });
    }
    startLevel(0);
  }
  runGame(GAME_LEVELS, DOMDisplay);
</script>
----

endif::html_target[]

!!solution!!

(((lives (exercise))))(((runGame function)))The most obvious solution
would be to make `lives` a variable that lives in `runGame`, and is
thus visible by the `startLevel` ((closure)).

Another approach, which fits nicely with the spirit of the rest of the
function, would be to add a second ((parameter)) to `startLevel` that
gives the amount of lives. When the whole ((state)) of a system stored
in the arguments to a ((function)), calling that function provides an
elegant way to transition to a new state.

In any case, when a ((level)) is lost, there should now be two
possible state transitions: if that was the last life, we go back to
level zero with the starting amount of lives. If not, we repeat the
current level with one less life remaining.

!!solution!!

=== Pausing the game ===

(((pausing (exercise))))(((escape key)))(((keyboard)))Make it possible
to pause (suspend) and unpause the game by pressing the Escape key.

(((runLevel function)))(((event handling)))This can be done by
changing the `runLevel` function to use another keyboard event
handler, and interrupting or resuming the animation whenever the
Escape key is hit.

(((runAnimation function)))The `runAnimation` interface may not look
like it is suitable for this, at first glance, but it is, if you
rearrange the way `runLevel` calls it.

(((variable,global)))(((trackKeys function)))When you have that
working, there is something else you could try. The way we have been
registering keyboard event handlers is somewhat problematic. The
`arrows` object is currently a global variable, and its event handlers
are kept around even when no game is running. They _((leak))_ out of
our system, you could say. Extend `trackKeys` to provide a way to
unregister its handlers, and then change `runLevel` to register its
handlers when it starts, and unregister them again when it is
finished.

ifdef::html_target[]

// test: no

[focus="yes"]
[source,text/html]
----
<link rel="stylesheet" href="css/game.css">

<script>
  // The old runLevel function. Modify this...
  function runLevel(level, Display, andThen) {
    var display = new Display(document.body, level);
    runAnimation(function(step) {
      level.animate(step, arrows);
      display.drawFrame(step);
      if (level.isFinished()) {
        display.clear();
        if (andThen)
          andThen(level.status);
        return false;
      }
    });
  }
  runGame(GAME_LEVELS, DOMDisplay);
</script>
----

endif::html_target[]

!!solution!!

(((pausing (exercise))))An ((animation)) can be interrupted by
returning `false` from the function given to `runAnimation`. It can be
continued by calling `runAnimation` again.

(((closure)))To communicate the fact that the animation should be
interrupted to the function passed to `runAnimation`, so that it can
return `false`, you can use a variable that both the event handler and
that function have access to.

(((event handling)))(((removeEventListener method)))(((function,as
value)))When finding a way to unregister the handlers registered by
`trackKeys`, remember that the _exact_ same function value that was
passed to `addEventListener` must be passed to `removeEventListener`
to successfully remove a handler. Thus, the `handler` function value
created in `trackKeys` must be available to the code that unregisters
the handlers.

You can add a property to the object returned by `trackKeys`,
containing either that function value, or a method that handles the
unregistering directly.

!!solution!!