Gameplay in HTML5: Game Models

Homework #4 review

Instructor's solution

http://EpsilonDelta.us/UW_GameplayHTML5/Homework/Solutions/4

MVC: the Model-View-Controller pattern

The challenge

Modeling Spin

Game description

In Spin we will have an array of "tiles" in a grid. Each will be characterized by a color scheme and by an angle that will be used to draw a spot on the tile that orbits its center.
There will be a "current" location, and the tile at that location will be the one animating. The player will have the ability to change this location, and when she does so, the previously current tile will change to a different color scheme.

The tiles array

Objective

Set up the tiles data structure as a two-dimensional array of simple objects. Provide accessors to this and a text console display of the array.

Setup

The model setup will take a params object as an argument, specifying the dimensions of the array, as well as the number of color schemes.
app.spin.model =
    (function()
     {
    //-------------------------------------------------------------------------

         var tilesHoriz,
             tilesVert,
             numColors,
             tiles;
         
    //=========================================================================

         function setup( params )
         {
             var x, y,
                 column,
                 tile;
             tilesHoriz = params.tilesHoriz;
             tilesVert = params.tilesVert;
             numColors = params.numColors;
             tiles = [];
             for ( x = 0; x < tilesHoriz; ++x )
             {
                 column = [];
                 for ( y = 0; y < tilesVert; ++y )
                 {
                     tile = { colorNum: 0, angle: 0.0 };
                     column.push( tile );
                 }
                 tiles.push( column );
             }
         }
            

Accessors

         function getDimensions( )
         {
             return { horiz: tilesHoriz, vert: tilesVert };
         }
         
    //-------------------------------------------------------------------------

         function getTiles( )
         {
             return tiles;
         }
         
    //-------------------------------------------------------------------------

         function getTile( loc )
         {
             return tiles[ loc.x ][ loc.y ];
         }
            

Printing the tile array

For testing and debugging, we want a print function that shows the tile array in the console log. It builds lists of strings and joins them, which is a bit more efficient than concatenating strings.
         function print( )
         {
             var lines = [],
                 lineParts,
                 x, y;
             for ( y = 0; y < tilesVert; ++y )
             {
                 lineParts = [];
                 for ( x = 0; x < tilesHoriz; ++x )
                 {
                     lineParts.push( printTile( tiles[ x ][ y ] ) );
                 }
                 lines.push( lineParts.join( ' ' ) );
             }
             console.log( lines.join( '\n' ) );
         }
         
    //-------------------------------------------------------------------------

         function printTile( tile )
         {
             var parts = [];
             parts.push( '[' );
             parts.push( tile.colorNum.toString() );
             parts.push( ', ' );
             parts.push( tile.angle.toPrecision( 4 ) );
             parts.push( ']' );
             return parts.join( '' );
         }
            

Calling the model's setup

In SpinScreen.js we set the model's parameters. For now we just hard-code some numbers.
         function run( )
         {
             var modelParams;
             if ( firstRun )
             {
                 init( );
                 firstRun = false;
             }
             modelParams = { tilesHoriz: 8, tilesVert: 8 };
             modelParams.numColors = 5;
             app.spin.model.setup( modelParams );
         }
            

Example

Example 1

The current location

Objective

Create a curLoc variable representing the current tile location. Provide methods for changing the location.

Clamp and wrap utility functions

  • Two functions are used often enough to warrent inclusion in a Util.js module:
  • Both take a number x and a range low to high and return x if it is already in that range; otherwise they return a number that is. (Especially with integers, our ranges are inclusive at the low end and exclusive at the high end.)
  • clamp simply pulls the number into the range, so if x is less than low, say, it returns low:
    app.util.clampInt = function( x, low, high )
    {
        return Math.max( low, Math.min( x, high - 1 ) );
    }
                    
  • wrap is more like a modulus function, cycling through the range. So if x is low - 1, for instance, it returns high - 1, and if x is high, it returns low:
    app.util.wrap = function( x, low, high )
    {
        var diff = high - low;
        while ( x < low )
            x += diff;
        while ( x >= high )
            x -= diff;
        return x;
    }
                    

Setup of curLoc

Our array of tiles is two-dimensional, so we can use a vector object for the location.
         var tilesHoriz,
             ...
             curLoc;
         
         function setup( params )
         {
             ...
             curLoc = { x: 0, y: 0 };
         }
            

Moving

         function move( direction )
         {
             var newLoc;
             switch ( direction )
             {
             case "left":
                 newLoc = app.vector.add( curLoc, { x: -1, y: 0 } );
                 break;
             case "right":
                 newLoc = app.vector.add( curLoc, { x: 1, y: 0 } );
                 break;
             case "up":
                 newLoc = app.vector.add( curLoc, { x: 0, y: -1 } );
                 break;
             case "down":
                 newLoc = app.vector.add( curLoc, { x: 0, y: 1 } );
                 break;
             }
             newLoc.x = app.util.clampInt( newLoc.x, 0, tilesHoriz );
             newLoc.y = app.util.clampInt( newLoc.y, 0, tilesVert );
             moveTo( newLoc );
         }

    //-------------------------------------------------------------------------

         function moveTo( newLoc )
         {
             //The originally active tile changes color when we leave it.
             var tile = tiles[ curLoc.x ][ curLoc.y ],
                 colorNum = tile.colorNum;
             if ( app.vector.equal( newLoc, curLoc ) )
                 return;
             colorNum = app.util.wrap( ++colorNum, 0, numColors );
             tile.colorNum = colorNum;
             curLoc = newLoc;
         }
            

Showing the current location in the printout

         function print( )
         {
             var lines = [],
                 lineParts,
                 x, y,
                 current;
             for ( y = 0; y < tilesVert; ++y )
             {
                 lineParts = [];
                 for ( x = 0; x < tilesHoriz; ++x )
                 {
                     current = (x === curLoc.x) && (y === curLoc.y);
                     lineParts.push( printTile( tiles[ x ][ y ], current ) );
                 }
                 lines.push( lineParts.join( ' ' ) );
             }
             console.log( lines.join( '\n' ) );
         }
         
    //-------------------------------------------------------------------------

         function printTile( tile, current )
         {
             var parts = [];
             parts.push( current ? '<' : '[' );
             parts.push( tile.colorNum.toString() );
             parts.push( ', ' );
             parts.push( tile.angle.toPrecision( 4 ) );
             parts.push( current ? '>' : ']' );
             return parts.join( '' );
         }
             

Example

Example 2

Clamp/wrap option

Objective

With clamping, if the current location is at [ 0, 0 ], then moves left or up do nothing. We can provide an option to switch to wrapping, so that, for example, a move left from [ 0, 0 ] goes to the right end of the board ([ tilesHoriz-1, 0]).

The clampMoves variable

         var tilesHoriz,
             ...
             clampMoves;
         
    //-------------------------------------------------------------------------

         function move( direction )
         {
             ...
             if ( clampMoves )
             {
                 newLoc.x = app.util.clampInt( newLoc.x, 0, tilesHoriz );
                 newLoc.y = app.util.clampInt( newLoc.y, 0, tilesVert );
             }
             else
             {
                 newLoc.x = app.util.wrap( newLoc.x, 0, tilesHoriz );
                 newLoc.y = app.util.wrap( newLoc.y, 0, tilesVert );
             }
             moveTo( newLoc );
         }

    //-------------------------------------------------------------------------

         function getClamping( )
         {
             return clampMoves;
         }

    //-------------------------------------------------------------------------

         function setClamping( clamp )
         {
             clampMoves = clamp;
         }

            

Example

Example 3

Updating the angle

Objective

The tile at the current location will have its angle property updated at a constant speed.

Setup

The rotation rate and the initial time will be passed in as parameters.
         var tilesHoriz,
             ...
             rotationRate,
             lastTime;
         
    //=========================================================================

         function setup( params )
         {
             ...
             rotationRate = params.rotationRate;
             lastTime = params.time;
         }
            

Update

We will add a public update method to our model, which should get called regularly.
         function update( time )
         {
             //The active tile's rotation is incremented
             var deltaT = time - lastTime,
                 tile = tiles[ curLoc.x ][ curLoc.y ];
             lastTime = time;
             tile.angle += deltaT * rotationRate;
         }
            

Example

Example 4

Modeling Beach

Game description

In Beach we will have balls entering the screen from the sides and moving under the influence of inertia and gravity. They will also bounce off the ground and in response to mutual collisions.

The ball list

Objective

  • Set up the balls data as a list and provide access and a text console display.
  • Create methods for adding and removing balls.
  • Set up the dimensions of the game area (the "board").
  • In the model, the unit of length is the radius of a ball and the Y-axis points up, with 0 representing the ground.

Setup

The dimensions of the game board, as well as the initial ball speed will be supplied as parameters.
app.beach.model =
    (function()
     {
    //-------------------------------------------------------------------------

         var balls = [],
             boardSize,
             initSpeed,
             rng = app.shRandom;

    //=========================================================================

         function setup( params )
         {
             balls = [];
             boardSize = { width: params.boardWidth,
                           height: params.boardHeight };
             initSpeed = params.initBallSpeed;
         }
            

Accessor

         function getBalls( )
         {
             return balls;
         }
            

Printing the ball list

         function print( )
         {
             var lines = [],
                 lineParts,
                 i,
                 numBalls = balls.length;
             lines.push( "Balls:" );
             for ( i = 0; i < numBalls; ++i )
             {
                 lines.push( "  " + printBall( balls[ i ] ) );
             }
             
             console.log( lines.join( '\n' ) );
         }

    //-------------------------------------------------------------------------

         function printBall( ball )
         {
             return "Position: " + app.vector.toString( ball.position, 4 ) +
                 " Velocity: " + app.vector.toString( ball.velocity, 4 );
         }
            

Adding a ball

The addBall method takes a string argument ("left" or "right") and creates a ball just off that side of the board, with a velocity that directs it onto the screen.
         function addBall( side )
         {
             var x, y,
                 velX, velY,
                 ball;
             //Start ball on upper 2/3 of board
             y = (rng.real() * boardSize.height * 2.0/3.0)  +
                 boardSize.height * 1.0/3.0;
             //Restrict vertical component of velocity to +/-0.8 of speed.
             velY = (rng.real() * 1.6  -  0.8) * initSpeed;
             velX = Math.sqrt( initSpeed * initSpeed  -  velY * velY );
             if ( side === "left" )
             {
                 x = -0.9;
             }
             else
             {
                 x = boardSize.width + 0.9;
                 velX = - velX;
             }
             ball = {
                 position: { x: x, y: y },
                 velocity: { x: velX, y: velY }
             };
             balls.push( ball );
         }
            

Removing a ball

The splice method removes items from a list.
         function removeBall( index )
         {
             balls.splice( index, 1 );
         }
            

Example

Example 5

Linear motion

Objective

Update the positions of the balls. No forces are applied, so the balls maintain constant velocity. If a ball exits off the side of the board, remove it.

Update

         function update( time )
         {
             var deltaT = time - lastTime,
                 i, numBalls,
                 ball,
                 deltaPos;

             lastTime = time;

             i = 0;
             while ( i < balls.length )
             {
                 ball = balls[ i ];

                 deltaPos = app.vector.scalarMul( deltaT, ball.velocity );
                 ball.position = app.vector.add( ball.position, deltaPos );

                 if ( (ball.position.x < -1.0) ||
                      (ball.position.x > boardSize.width + 1.0) )
                 {
                     removeBall( i );
                 }
                 else
                 {
                     ++i;
                 }
             }
         }
            

Example

Example 6

Gravity

Objective

Apply gravity to change the velocity of balls over time.

Setup

Gravity is a constant vector, supplied as a parameter to the model.
             modelParams.gravity = { x: 0.0, y: -10.0 };
            

Application during update

         function update( time )
         {
             var deltaT = time - lastTime,
             ...
             deltaV = app.vector.scalarMul( deltaT, gravity );
             for ( i = 0, numBalls = balls.length; i < numBalls; ++i )
             {
                 ball = balls[ i ];
                 ball.velocity = app.vector.add( ball.velocity, deltaV );
             }
         }
            

Example

Example 7

Collision detection and response: principles and mathematics

Overview

  • Collision detection involves determining whether two shapes are touching or overlapping.
  • Collision detection algorithms generally return some or all of the following information:
    • Whether there was (or will be) a collision (a boolean).
    • The time of the collision, especially if the detection is a priori (looking ahead).
    • The point of contact.
    • A plane (or normal vector to a plane) that separates the shapes.
    • The depth of penetration if the shapes overlap. Most commonly for a posteriori detection (where we determine whether a collision has occurred).
  • Possible responses to collisions include:
    • Destruction or damage to either or both objects.
    • Sound effects.
    • Changes in the velocities of the objects.

Convexity

  • Almost all collision-detection algorithms require that the shapes be convex.
  • A shape is convex if the line segment between any two points in the shape lies completely within the shape.
  • Lines, planes, balls, triangles, squares, and regular polygons are all convex.
  • Doughnuts, Y-shapes, Ms. Pac-Man with her mouth open, etc., are not convex.
  • If you need to detect collisions with non-convex shapes, you need to break them up into smaller convex parts and test those individually.

Lines, half-planes, and balls

Defining a line

In the Vectors lecture, I explained how the equation v·w = 0, where v is fixed, defines a line. In fact, this works for v·w = C, where C is any constant.
One of the most useful ways to define a line is in terms of a normalized vector n and a constant C.
If we have two points p1 and p2 on a line, we can obtain n = normalize( perp( p1 - p2 ) ).
If we have n and a point p on a line, we can obtain C = n·p. So given n and C, the points satisfying n·p = C are on the line.
This line divides the plane into two half-planes. We will focus on the one defined by n·p <= C, so that the normal points outward, away from interior of the half-plane. (If we are interested in the other half-plane, replace n with -n.)

Distance of a point from a line

The distance of a point p from a line defined by n and C is simply d = |n·p - C|, and the sign of n·p - C tells us in which half-plane the point lies.

Defining a ball

A ball (a circle and its interior) is best defined by its center, c, and radius, R.

Detecting collision of a ball and a half-plane

A ball given by c and R is in contact with the half-plane given by n and C if n·c <= (C + R).
Why? If n·c - C <= 0, then the center of the ball is in the half-plane. And if n·c - C > 0, then the distance of the center of the ball to the line is d = n·c - C <= R.
Example:
The ground might be defined by n = [ 0, 1 ] and C = 0. Let the radius of a ball be R = 1. If the ball's center is c = [ cx, cy ], then the test for collision is cy <= 1.

Detecting collision of two balls

If ball 1 has center c1 and radius R1, and ball 2 has center c1 and radius R2, then they are in contact if |c1 - c2| <= R1 + R2.

Elastic collisions

Overview

As noted earlier, there are many possible responses to collisions. One of the most important is having the objects bounce off each other, retaining all of their kinetic energy. (I.e., a negligible amount of that energy is converted to heat, sound, etc.) The details depend in part on the relative masses of the objects.
We will consider two extreme cases. The first is a ball bouncing off a half-plane, where the latter is considered to be fixed, i.e. of near-infinite mass. The second is two balls of equal mass colliding.

Reflection

Consider a line L with a normal n (the constant, C, won't matter here), and a vector v. It is useful to ask about the vector v' obtained by reflecting v symmetrically about L.

Since vectors have length and direction, but not position, this is equivalent to reflecting v off L like a light ray reflecting off a mirror (or a ball bouncing off a wall).

Rearranging the vectors yet again, we represent v' = v + w, where w = v' - v needs to be determined.

We can see that w is parallel to n. Let d be half the length of w, so w = 2dn. Let θ be the angle between n and v. It can be seen that d = - cos(θ)|v|. (Note that in this instance θ > π/2, so cos(θ) < 0.) Since |n| = 1, d = - n·v. Putting this all together,
v' = v - 2(n·v)n.

Example:
If n = [ 0, 1 ] and v = [ vx, vy ], then
v' = [ vx, vy ] - 2(vy)[ 0, 1 ] = [ vx, (vy - 2vy) ] = [ vx, - vy ].

Ball meets ball

Suppose ball 1 is at c1 and moving with velocity v1 when it collides with ball 2 at c2, which has velocity v2. Assume that the balls have equal mass. How will their velocities change in an elastic collision?

In physics problems like this, it is often useful to convert to a frame of reference where the center of mass of the system is stationary. In this case that means the balls have equal but opposite momentum. Since they have the same mass, this means that they have equal but opposite velocities.

To convert to a new reference frame, we add a fixed velocity w to all velocities in the system. (You can think of this as moving the origin of our "laboratory" at the negative of that velocity.) So let the transformed velocities be u1 = v1 + w and u2 = v2 + w. We require that u1 = -u2. A little algebra will show that w = (-1/2)(v1 + v2). Our situation now looks like this:

After the collision the law of conservation of momentum requires that they still have equal but opposite velocities. Conservation of energy requires that their speeds (the magnitudes of their velocities) be the same as before.

Notice the line tangent to the balls at their point of collision. What is its normal? It is easy to see that its direction is along the line connecting the centers of the balls, so
n = normalize( c1 - c2 ).

Locally each ball is nearly flat and so each ball acts as if it has collided with a flat surface. We already know how to compute the resulting velocities:
u1' = u1 - 2(n·u1)n
and
u2' = u2 - 2(n·u2)n = u2 + 2(n·u1)n

Let Δv = 2(n·u1)n. We can apply this velocity change in the original reference frame. For
v1' = u1' - w = (u1 - Δv) - w = (u1 - w) - Δv = v1 - Δv.
And similarly, v2' = v2 + Δv.

Conveniently, we can compute Δv using the original velocies. We have u1 = v1 + (-1/2)(v1 + v2) = (1/2)(v1 - v2), so
Δv = (n·(v1 - v2))n.

More information

  • David Geary's Core HTML5 Canvas: Graphics, Animation, and Game Development covers collision detection in Chapter 8, including the Separating Axis Theorem (SAT).
  • Gino van den Bergen, Collision Detection in Interactive 3D Environments, 2004 Elsevier (ISBN 1-55860-801-X) covers the SAT and the Gilbert-Johnson-Keerthi (GJK) algorithms. The emphasis is on 3D, but these can be applied in 2D as well.

Bounces

Objective

Detect when a ball hits the ground and "reflect" it back up.

In update

         function update( time )
         {
             ... //adjust positions
             checkForBounces( );
             ...//gravity
         }
            

Bounce code

We detect the collision of the ball and ground and reflect the ball elastically.
         function checkForBounces( )
         {
             var numBalls = balls.length,
                 i, ball;

             bounces = [];
             for ( i = 0; i < numBalls; ++i )
             {
                 ball = balls[ i ];
                 if ( ball.position.y < 1.0 )
                 {
                     ball.position.y = 1.0;
                     ball.velocity.y = - ball.velocity.y;
                     bounces.push( i );
                 }
             }
         }
            

Example

Example 8

Collisions

Objective

Detect when a ball hits another ball and modify their velocities accordingly.

Collision code

         function checkForCollisions( )
         {
             var numBalls = balls.length,
                 i, ball0,
                 j, ball1,
                 separation, normSep,
                 distSqr,
                 relVel,
                 dot, deltaV;

             collisions = [];
             for ( i = 0; i < numBalls; ++i )
             {
                 ball0 = balls[ i ];
                 for ( j = i + 1; j < numBalls; ++j )
                 {
                     ball1 = balls[ j ];
                     separation =
                         app.vector.subtract( ball0.position, ball1.position );
                     distSqr = app.vector.lengthSqr( separation );
                     if ( distSqr > 4.0 ) //distance > 2 radii: no collision
                         continue;
                     normSep = app.vector.normalize( separation );
                     relVel =
                         app.vector.subtract( ball0.velocity, ball1.velocity );
                     dot = app.vector.dot( normSep, relVel );
                     if ( dot >= 0 ) //already rebounding from collision
                         continue;
                     deltaV = app.vector.scalarMul( dot, normSep );
                     ball0.velocity =
                         app.vector.subtract( ball0.velocity, deltaV );
                     ball1.velocity = app.vector.add( ball1.velocity, deltaV );
                     collisions.push( [ i, j ] );
                 }
             }
         }
            

Accessors

Outside systems (e.g. display or audio) might want a list of bounces and collisions, at least to know if any occurred. So:
         function getBounces( )
         {
             return bounces;
         }

    //-------------------------------------------------------------------------

         function getCollisions( )
         {
             return collisions;
         }
            

Printing bounce and collision lists

         function print( )
         {
             var lines = [],
                 lineParts,
                 i,
                 numBalls = balls.length,
                 numBounces = bounces.length,
                 numCollisions = collisions.length,
                 bounce, collision;

             lines.push( "Balls:" );
             for ( i = 0; i < numBalls; ++i )
             {
                 lines.push( "  " + printBall( balls[ i ] ) );
             }
             if ( numBounces > 0 )
             {
                 lineParts = [];
                 for ( i = 0; i < numBounces; ++i )
                 {
                     bounce = bounces[ i ];
                     lineParts.push( bounce.toString() );
                 }
                 lines.push( "Bounces: " + lineParts.join( ", " ) );
             }
             if ( numCollisions > 0 )
             {
                 lineParts = [];
                 for ( i = 0; i > numCollisions; ++i )
                 {
                     collision = collisions[ i ];
                     lineParts.push( "(" + collision[ 0 ].toString() +
                                     ", " + collision[ 1 ].toString() + ")" );
                 }
                 lines.push( "Collisions: " + lineParts.join( ", " ) );
             }

             console.log( lines.join( '\n' ) );
         }
            

Example

Example 9

Screen dimensions and model parameters

Objective

Both Spin and Beach have setup parameters that depend on the size and/or shape of the game board on the screen. Determine these layouts.

HTML

      <div id="beachScreen" class="screen beach">
        <div id="beachBoard"></div>
        <nav>
          <button type="button" name="mainMenu">Exit</button>
        </nav>
      </div>
      
      <div id="spinScreen" class="screen spin">
        <div id="spinBoard"></div>
        <nav>
          <button type="button" name="mainMenu">Exit</button>
        </nav>
      </div>
            

CSS

(We will create canvas elements soon. Might as well style them now, too.)
#beachBoard,
#spinBoard
{
    position: absolute;
    left: 0;
    top: 0;
    width: 100%;
    height: 90%;
}

#beachBoard canvas,
#spinBoard canvas
{
    position: absolute;
    left: 0;
    top: 0;
    width: 100%;
    height: 100%;
}
            

Spin layout

If the board is close to square, set the layout to 8x8 tiles. Otherwise set the long side to 8 tiles and compute the other dimension based on the aspect ratio.
         function run( )
         {
             ...
             modelParams = determineLayout( );
             ...
         }
         
    //-------------------------------------------------------------------------

         function determineLayout( )
         {
             var boardDiv = $("#spinBoard"),
                 width = boardDiv.width(),
                 height = boardDiv.height(),
                 aspectRatio = width / height;
             if ( (aspectRatio > 0.75) && (aspectRatio < 1.33) )
             {
                 return {
                     tilesHoriz: 8,
                     tilesVert: 8
                 };
             }
             else if ( aspectRatio < 1.0 )
             {
                 return {
                     tilesVert: 8,
                     tilesHoriz: Math.max( Math.floor( 8 * aspectRatio ), 1 )
                 };
             }
             else
             {
                 return {
                     tilesHoriz: 8,
                     tilesVert: Math.max( Math.floor( 8 / aspectRatio ), 1 )
                 };
             }
         }
            

Beach layout

We will see later how to get the radius of the ball graphic. For now we will hard-code it and compute the board dimensions in these units.
         function run( )
         {
             ...
             modelParams = determineLayout( );
             ...
         }
         
    //-------------------------------------------------------------------------

         function determineLayout( )
         {
             var boardDiv = $("#beachBoard"),
                 width = boardDiv.width(),
                 height = boardDiv.height(),
                 ballRadius = 32; //app.beach.view.getBallRadius();
             return {
                 boardWidth: width / ballRadius,
                 boardHeight: height / ballRadius
             };
         }
            

Example

Example 10

Homework #5

http://EpsilonDelta.us/UW_GameplayHTML5/Homework/Homework_5.html