Michael J. McGuffin and Anand Agarawala
University of Toronto
May 2005
A course project for CSC 2529: Computer Animation (Prof. Karan Singh)
Note that the logo image above uses "Space Girl" artwork from the Graffiti Transformation Project 2004 for the Harbourfront and Cecil Community Centre of Toronto.
This report describes a real-time 3D interactive game where a single human user controls a team of multiple virtual characters (in this case, the characters are vehicles). The goal of the game is for the user's team of characters to fight a team of enemy characters controlled by the computer. To direct characters, the user manually controls a single character at a time (in user time), and iteratively travels back in (virtual) time, optionally switching to a different character, to progressively layer and/or re-record the behaviour of the user's characters.
This project was inspired by a desire for interactive games that could combine elements of multi-player cooperative play without having multiple users. In particular, we wish to combine (1) the simple, engaging, low-level control of first-person perspective gameplay, with (2) the ability to orchestrate and coordinate the actions of multiple characters by a single user. As an example, in our chosen domain of action games with vehicles that attack each other, we envision a user who can attack an enemy in one vehicle, while simultaneously witnessing a second vehicle (whose behaviour had also been controlled by the user) also attack the same enemy.
Controlling multiple characters at the same time (in user time) would either require a prohibitive number of degrees of freedom, or require the user to control characters by issuing high-level commands (such as how a general would command an army), neither of which were attractive strategies to us. Instead, to retain the first-person perspective, we decided to have the user control one character at a time, and allow the user to "travel back in (virtual) time" to control a different character. During control of this different character, any input recorded for other characters in previous iterations would simply be replayed. Thus, the game could be thought of as an animation system, where the user animates characters in real time, and also where the user layers the animation, one character at a time.
Following discussion with professor Singh, we decided that another desirable feature would be to allow the user to control characters with as much or as little explicit detail as desired. In other words, the user should not be required to control all the characters on the user's team. The user may want to only control one character for a certain interval of time, during which other teammates should automatically follow along or perform some other appropriate actions, and the user need only travel back in time and switch to another character if they want to overwrite its autonomous actions with manually specified actions.
It is interesting to note that a time travel metaphor has been used in user interfaces for managing files [1] [2], where, for example, files cease to exist when they are deleted, but can still be retrieved if the user travels "back in time".
Although we have not had a chance to try them out, some of the other members in our lab described existing commercial games to us that incorporate time travel, corrective rewinding in time, or time warping (e.g. "bullet time") in the gameplay. These include "Zelda: Ocarina of Time", "Prince of Persia: Sands of Time", "Max Payne", and "Day of the Tentacle". Judging by the descriptions given to us, however, none of these games use time travel in the same way that we wish to use it.
Time travel is a common theme in science fiction literature, and many have wondered about the paradoxes that can arise if, for example, a time traveller were to travel back in time and prevent himself from building a time machine, or kill his parents before he is born, etc. (http://en.wikipedia.org/wiki/Grandfather_paradox) Such paradoxes cannot happen in our design for gameplay, because it is conceptually the user who travels back in time to affect the behaviour of characters, rather than characters who travel back in time carrying memory and state from the future.
Despite this, there is the potential in our design for time travel by the user to cause problems. Changing the behaviour of a character X can cause the enemy characters to react in different ways, making the previously recorded behaviour of character Y inappropriate or ineffective. For example, if the user first controls Y to shoot at enemy E, and then travels back in time to control X, enemy E may then chase X, leaving Y to shoot at what is now empty space. Although the user can iteratively correct such problems by again travelling back in time and adjusting the behaviour of characters, this could cause frustration if required too frequently.
Furthermore, discussions with professor Singh brought up the notion that time travel of characters would also be interesting to think about. For example, a game could be designed where characters can travel through wormholes to distant locations in time and/or space, which would raise issues such as: can a character encounter themself in the past, and how are cause-effect paradoxes to be dealt with in a consistent manner? Such wormholes could also be designed to only be available at certain locations in time and/or space, and possibly require the spending of "time travel points" that the user would have to accumulate beforehand.
The following email message records various ideas produced by an early meeting between one of us (McGuffin) and professor Singh:
Date: Tue, 18 Jan 2005 18:12:05 -0500 (EST)
From: Michael McGuffin
To: Karan Singh
Subject: CSC 2529 project: game with time-travel - notes from meeting
As requested, here are some notes I made following our meeting
on Monday (yesterday), to discuss my potential course project
involving a game where a single user can iteratively travel back
in time to control multiple characters / vehicles.
1. Motivated by desire to achieve elements of cooperative play,
with only a single physical user
2. Potential disadvantage compared to multi-user cooperative play:
may be too predictable, since a single user controls all the
characters on his team, rather than playing with teammates
who may do surprising things
3. Potential source of unpredictability: playing out the actions
of a second character can cause the environment around a first
character to change, making the first character's actions
irrelevant.
Example: during 1st iteration, the actions of character 1 are
played out, e.g. shooting at some enemy X.
During 2nd iteration, the actions of character 2 are played out,
which may cause X to act or move differently (e.g. X may chase
character 2), hence character 1 may end up shooting at an
empty position, because X is somewhere different from during
the 1st iteration.
Over time, the user's new input create changes that snowball
in effect, creating an increasingly large divergence from
the events of the previous iteration, rendering the other
character's behaviours increasingly inappropriate.
This "butterfly effect" might prevent the user from playing
out any single character too far into the future.
The user would have to jump back in time within some temporal
window to tweak and coordinate the behaviours of other characters.
4. Note that the user can be thought of as an animator,
and as they play, they are "authoring an experience".
Travelling back in time allows the user to replay their
authored experience and see it through the eyes of another
character, while simultaneously authoring that other
character's behaviours.
It's also interesting to consider an animation system
where the cursor on the time-line can be scrubbed forward
or backward, but never stopped or paused. A game with
time-travel can be thought of as such an animation system.
The user can rewind, but as soon as they "let go" of the
temporal cursor, time starts marching forward.
(Karan hypothesized that users of such systems would
compensate for this behaviour by always rewinding a little
further back than their target point for recording new action.)
This might not be useful for doing traditional animations,
where character poses must be defined,
but it could be appropriate for high-level authoring of
"experiences", where a low-level set of behaviours has
been pre-designed for the user.
5. Suggested feature: when no input (either live or recorded)
is available for a given character, have the computer
play out the character's actions autonomously,
preferably as a function of what the other characters
are doing. For example, if the user controls character 1,
and character 2 hasn't been given any actions to play out yet,
then character 2 should perhaps follow along side character 1
and shoot at the same targets as character 1.
The user is free to travel back in time, during a later iteration,
to change character 2's behaviours, overwriting the autonomously
generated ones, or may leave the autonomously generated actions
as they are, or only overwrite certain temporal intervals of actions.
So, for example, the user may play out character 1 up until
5 minutes into the game, go back to the start and play out
character 2 10 minutes into the game. During this second
iteration, character 1 would act as the user made
it act for the first 5 minutes of the 1st iteration,
after which autonomous behaviour would take over.
Two reasons why you would want automatic control are
- You always want the story to be coherent, and at least somewhat
natural looking. You don't want characters to freeze or hover
just because they run out of user input.
- In a game, you may want 10 characters to travel a long distance,
and then get to some climax or critical point in the story.
The user may only want to guide 1 character over the long distance
and have the other teammates follow autonomously,
but at the climax the user may then want fine control and play
out each character separately.
Comparing this to real-time strategy games, such as Red Alert
or Warcraft (?) or Diablo (?), such games allow high-level control
of groups of characters, but not (AFAIK) fine-grain individual control
(which would be unworkable if *every* character had to be
manually controlled, since there are so many characters).
However, what if the user had the
ability to switch between high-level, 3rd person, god-like control of
groups of individuals, and low-level, 1st person, individual control
(during which other individuals would act out autonomously) ?
6. More challenging than (5) would be a feature that takes
previously input actions, and adjusts them in the face of
changes in other characters' actions.
This could eliminate, or at least alleviate, the divergence phenomenon (3).
This would be easier if the input from the user were high level
(e.g. chase X, shoot at Y, aim at landmark Z)
rather than low level (increase forward speed 5 %,
rotate to the right 10 degrees).
7. Rather than have time travel controls external to the game arena
(e.g. controlled at a meta-level by widgets outside the game viewport),
why not have time-travel mechanisms within the game, e.g. have
wormhole portals within the 3D scene.
Thus, to jump in time, the user's *character* must be made to fly into
or jump through the portal, rather than the *user* simply hitting some
special button.
Such portals or wormholes may be only at certain spatial locations,
and/or may only appear at certain times.
Just as pac-man and other games have spatial wormholes that jump the
character from one location to another, one could imagine wormholes
that jump through time, or that jump through time and space.
Furthermore, just as some 2D games have a wrap-around arena
(corresponding to the surface of a torus), it might be interesting
to have time wrap around periodically.
When a character travels through a wormhole into the past, do they
play along side their old self ? Thus, by travelling 10 times
through the wormhole, they create 9 copies of themself ?
Note that when it is the user, rather than the character,
moving back in time, it seems natural to expect that the number
of characters should not change.
However, if the character travels back in time, perhaps
they could encounter themself in the past,
and kill themself (or their father ??)
and somehow create a causal paradox.
Just as many games have a "health" value (0-100%) associated
with characters, which can be increased by consuming special
"health" or "life" tokens,
the characters may have a limited capacity to travel through time,
measured in seconds of gameplay, and may need to consume time
travel tokens (or time machine fuel) if they run out of capacity
to travel through time.
-mike
The following email message gives a specification of what we planned to implement:
Date: Mon, 7 Feb 2005 18:08:36 -0500 (EST) From: Michael McGuffin To: Anand Agarawala Subject: draft of letter to karan describing project Anand: change the 1st line of the 1st paragraph if you end up sending the below. Karan, As discussed, Anand and I will implement a game where a single user has a team of characters (vehicles) that they control, one at a time, that fights against a team of enemy characters (vehicles). Fighting is done by shooting projectiles. The user can jump back in time and switch from one vehicle to another to orchestrate their motions and actions. Characters on the user's team that have no user input available, as well as enemy characters, will behave autonomously, given the behaviour of the other characters around them (e.g. the user's characters will follow characters that the user is or has controlled, enemies will chase or evade, etc.) Here's a list of some other elements/features of the game we plan to implement. - height field terrain, with water. Time permitting, we'll also have sky, and clouds that the user can fly into/through. - vehicles: helicopters and boats. Time permitting, also submarines and tanks. - projectiles: missiles (dumb and/or target seeking). Time permitting, also torpedoes, bullets, laser beams. - passive buildings on the ground. Time permitting, also fixed turrets on the ground that shoot at enemies. - simple explosions (fireballs). Time permitting, also splashes, smoke, and fire. - time permitting: remotely detonated bombs, which the user can drop and then later detonate. - time permitting: audio (sound effects for explosions etc.) - time permitting, we'll also implement "worm holes" which are special locations in the 3D scene that a character can move into to travel back in time and to a different location. For "regular" time travel (i.e. not involving wormholes), where the user (not a character) travels back in time, our design works as follows. At any point during game play, the user can invoke a special mode for time travel. When in this mode, the user sees: the battle scene through one character's eyes, and a time line (horizontal slider). The slider allows the user to scrub back from the current point in time to any point in the past, up to the start of the game, by dragging left or right. The thumb of the slider can also be opened up into a popup menu, which the user can drag up or down in to select a different character through which to see the battle scene. Once the user has selected their desired point in time and desired character, they dismiss this mode to go back to game play. Time permitting, in the special mode described above, the slider's thumb menu will also contain a selection for a "god" character which can be selected to view the battle scene from an arbitrary point of view that the user can select. The god character is only intended to be used in the special time travel mode, not during game play. When viewing the battle scene through the god character, the other characters' current positions will be visible, as well as motion curves of their trajectory through space. We suspect this would help the user scrub the point in time they want to play forward from. Time permitting, the time line will be decorated with icons and colour to show the occurrence of critical events, such as characters being destroyed, and when the user's input stream starts or stops versus when autonomous behaviour takes over.
The prototype was implemented in C++ using standard POSIX routines, STL, OpenGL, and GLUT, and runs on both linux and Microsoft Windows. (The only part of the code that is not portable are the sound effects, which are currently implemented with WIN32 calls, and hence only work on Microsoft Windows). Various pieces of code were re-used from previous projects by the authors, such as classes for storing points, vectors, matrices, 3D cameras, etc.
Stand-Alone Terrain Editor
To create a height-field terrain for the game, a stand-alone editor for the terrain was written.
The height field is initially flat. A soft (cos2(r)) brush with variable radius can be placed anywhere on the height field, and the brush can be applied to modify the region under the brush. The longer the brush is applied (i.e. "held down"), the greater the effect of the brush. The brush can also be dragged over the height field.
The brush can be used in one of four modes: raising the height field, lowering the height field, smoothing the height field, or randomizing the height field (i.e. making the terrain look rougher). Raising and lowering are performed with the left and middle mouse buttons, respectively, in which case dragging the mouse creates ridges or valleys. Smoothing and randomizing are performed with hotkeys, which can be held down for repeated application.
The terrain editor also renders the surface of the water as a semi-transparent quad, whose height can be changed interactively. We had originally planned to include submarines as another vehicle in the game, hence we were interested in editing and visualizing the underwater environment as well as the above-water environment.
The terrain editor can also read and write height field files, that are loaded by the game.
Above: one of the terrains made for the game, consisting of a grid of 200x200 height values, rendered as a mesh of 199x199x2=79202 triangles.
Above: the same terrain, with the water level lowered to reveal more of the landscape. The two red circles are the brush for editing the height field.
Above: the same terrain, seen from under the water level.
Agents and Input Streams
The vehicles (helicopters and boats), buildings, missiles, and explosions are each implemented as a class, and all these classes derive from a common Agent base class. The two most important methods of Agent are update(), which is called once during each simulation time step, and which updates the internal state (i.e. position, velocity, behaviour, etc.) of the agent, and draw(), which renders the agent in its current state.
In the case of vehicles that can be controlled by the user, update() is passed a pointer to an inputStream, which stores a list of time-stamped and time-ordered input events. The update() method for the agent will either (a) consume whatever input event (e.g. accelerate forward, turn right, fire missile) may be in the inputStream for the current time step, OR (b) if the user has not explicitly controlled the vehicle during the current time step, the vehicle uses its automatic behaviour routines to decide what to do (e.g. pursue an enemy, etc.)
When the user takes control of a vehicle, the input events from the user are stored in the inputStream for that vehicle, overwriting whatever events may have been stored in a previous iteration. Then, if the user later travels back in time and switches to a different vehicle, the inputStream for the first vehicle can still be fed back in to the first vehicle, essentially re-playing the user's actions.
Storage of Keystates
The initial states of the agents, along the the input streams, together allow the simulation engine to recreate the state of the game at any point in time. However, simulating forward from the initial state may be time-consuming, and we want the user to be able to quickly jump back to any point in time. Even worse, we want the user to be able to smoothly slide back and forward to any point in the past, e.g. by controlling a slider, and see the state of the game update in real time. To support such behaviour, we need to store snapshots (or "keystates") of the state of the game at many points in the past. Each keystate must contain the state of each of the agents, so that the game can be quickly rendered at any keystate. The memory required for such keystates was a concern for us, because it has the potential to grow without limit as the game progresses. We considered multiple strategies for storing these keystates.
The most naïve strategy is to store a keystate for every frame, i.e. every time step. Although this is the most memory-intensive approach, it is also the simplest, and hence we implemented this first. As it turns out, this was sufficiently efficient for our prototyping purposes, hence we have not yet improved this aspect of the code. In the screenshots in the Results section below, an estimate of the memory currently consumed by all the keystates is displayed at the top of the window. As long as the user does not play for more than a few minutes, memory requirements do not pose a problem.
We have also considered more efficient strategies, however. One would be to store a keystate every N frames, and re-generate the game state at any time by simulating forward from the most recently stored keystate. If N is sufficiently small, such forward simulation could be done without noticeable delay.
Another possibility comes from the observation that, during selection of a point of time in the past, the user needs to see the game state update in real time, however this may only require that keystates store information relevant to rendering the game, and not necessarily information relevant to simulating the game forward. Thus, position, orientation, and other data that agents need to render themselves could be stored every N1 frames, whereas state information for autonomous behaviour could be stored less often, only every N2 frames, where N1 < N2. Then, when the user is smoothly sliding back and forward in time (e.g. with a slider), we simply snap to the nearest renderable keystate (stored every N1 frames). Because renderable keystates would require less memory than a full keystate, some memory would be saved. We estimated, however, that using this strategy would significantly complicate the code, while only reducing memory consumption by less than 50 %.
Note that all of the strategies considered so far still result in unbounded memory consumption, albeit at different rates. Probably the best strategy would be to adaptively downsample the points in time at which keystates are stored. For example, if a simple slider is used to select points in time, and the slider is only 1000 pixels long, then the user cannot select with a granularity finer than 1/1000th of the time elapsed in the game. Thus, the code could be designed to never store more than 1000 keystates. During initial gameplay, the game would store one keystate for every frame, but once 1000 keystates have been stored, the code would start to delete keystates and save new keystates less often, effectively reducing the density of keystates. The could probably be accomplished with some relatively simple code, e.g.
const integer MAX = 1000; // max number of keystates stored
.
.
.
keyStateList.append( currentState );
if ( keyStateList.size() > MAX ) {
// compute the ideal interval of time between keystates
float delta_t = totalTimeElapsed / MAX;
integer i = 1; // skip over the 0th key state
while ( i < keyStateList.size() && keyStateList.size() > MAX ) {
if ( keyStateList[i].time - keyStateList[i-1].time < delta_t ) {
The (i-1)th and ith keystates are too close together in time
keyStateList.delete( i );
}
else i = i + 1;
}
}
One minor disadvantage of the above approach is that we can no longer index into keyStateList simply using the frame number. Instead, a binary search, or hash table, would have to be used to find the key state closest to a given time. Binary searching would probably yield acceptable performance, since the size of the list is bounded above, and log2(1000) < 10.
Intersection Testing
Currently, there are no intersection tests performed between vehicles, or between vehicles and the terrain. There are, however, tests performed to find collisions between missiles and the terrain, or missiles and vehicles.
The most elaborate intersection test implemented was between missiles and the terrain. For this test, a ray is projected from the nose of the missile, and tested against the terrain. If an intersection point is found within the distance that the missile would normally be translated during the timestep, then the missile is replaced with an explosion at the intersection point.
Although the terrain is modelled as a mesh of triangles, the mesh is defined over a height field, which allowed us to implement a fast, non-hierarchical intersection test for arbitrary rays. The ray is projected down onto the ground plane of the height field, and the order in which the ray encounters cells of the grid is determined using an algorithm akin to Bresenham's line-drawing algorithm. Within each cell, a test is performed for intersection between the (unprojected) ray and the 2 triangles in that cell. The first triangle found to intersect the ray corresponds to the intersection point on the terrain. Early exiting is done if the ray leaves the bounding box of the terrain. The entire ray-terrain test requires O(N) time, if the terrain is NxN cells.
Audio
Sound effects for the game (e.g. missiles being fired, and explosions) were synthesized using one of the author's (McGuffin) mouth, and captured and edited by the other author. These sounds are played back during gameplay.
Models
Models for the vehicles were created in Alias Maya and exported as Wavefront object (OBJ) files. These are read in by the game using Nate Robins' glm.{h,cpp} utility code for OBJ files (http://www.pobox.com/~nate).
Other models in the game were implemented programmatically. Buildings are rendered as axis-aligned boxes, missiles are drawn as wireframe arrows, and explosions are drawn as semi-transparent, low-resolution "glutSolidSphere()"s.
The game also draws a texture-mapped "sky box" around the terrain, with images of mountains and clouds, and draws the surface of the water with an image textured on it.
Hotkeys and mouse motion are used to accelerate and rotate the currently controlled vehicle in different directions. The space bar fires a missile.
Clicking down with the left mouse button invokes a pop-up, semi-transparent time slider widget, which is composed of a linear slider and a menu of vehicles. Using this widget, the user may rewind to any point in the past and also select any vehicle to switch to, all in a single drag of the mouse. During dragging along the time slider, the rendering of the 3D scene is updated in real time to show the selected point in time, from the perspective of the selected vehicle. Below is an early conceptual sketch of this widget, followed by the implemented time slider.
Because forward simulation cannot be done instantaneously, and because keystates are only stored in the past, we only allow the user to time travel into the past. Thus, when the time slider is popped up, the thumb on the slider is always initially at the right extremity of the slider (corresponding to the present). Because the GLUT library does not support warping of the mouse cursor position (which, in any case, is ill-advised in UI design guidelines), the thumb on the slider and cursor in the menu do not appear under the mouse cursor. Instead, they move in a relative fashion, as the mouse is dragged. Unfortunately, this means the mouse cursor may hit the edge of the screen before the slider's thumb reaches the extremity of the slider. To correct this, the user must drag in the opposite direction to the other extremity, essentially resetting the offset between cursors, and then drag back to the desired location.
We hypothesize that users will usually want to either drag along time, or drag within the menu of vehicles, but not do both simultaneously. Thus, to ease interaction with the time slider widget, we employ a trick inspired by Kobayashi and Igarashi [3], where each drag event vector is projected onto the largest axis-aligned component of the vector, and thus only affects either the slider's thumb or the menu's cursor. If the user drags mostly horizontally, only time is affected, and if the user drags mostly vertically, a different vehicle is selected without changing time.
Once the time slider is popped down, all keystates stored after the selected time are deleted, and simulation and gameplay continue forward from the selected time. Information in the input streams, however, is never deleted, but only overwritten as the user inputs new events to the vehicle under user control.
By switching between different vehicles, the user can see the game from any vehicle's point of view. In addition, the user may also hit a hotkey to go into a special 3rd-person "overview camera" mode (which we informally call "god mode"), where the user can freely move the camera around the 3D scene, and watch the vehicles and other agents play out the game.
The user can also turn on rendering of motion paths. The motion paths show all the positions of the vehicles recorded in the keystates, and tick marks along them give an indication of each vehicle's orientation at different times. Invoking the time slider with motion paths turned on, the user can scrub back in time, and see the vehicles move backward along their motion paths. The screenshots in the Results section below show these motion paths and the tick marks along them.
Both the 3rd-person overview camera mode and the motion paths are useful for debugging and demonstration of the system. It's plausible, however, that they would also be useful to the user during gameplay, to make it easier to identify and select key points in time.
Below are some screenshots of the game.
Thanks to professor Karan Singh for contributing ideas to this project during multiple conversations. Thanks also to John Buchanan, of Electronic Arts, for providing reactions to a description of the project during a visit of his to University of Toronto. Thanks also to members of the DGP lab (including Michael Pratscher, Jack Wang, Noah Lockwood, and Michael Wu) who pointed us to existing commercial games that incorporate time travel or time warping in the gameplay.
[1] E. Freeman and S. Fertig. Lifestreams: Organizing your Electronic Life. AAAI Fall Symposium: AI Applications in Knowledge Navigation and Retrieval, 1995.
[2] Jun Rekimoto. Time-machine computing: A time-centric approach for the information environment. Proceedings of ACM UIST 1999, pp. 45--54. http://doi.acm.org/10.1145/320719.322582
[3] Masatomo Kobayashi and Takeo Igarashi. Considering the Direction of Cursor Movement for Efficient Traversal of Cascading Menus (TechNote). Proceedings of ACM UIST 2003, pp. 91--94. http://doi.acm.org/10.1145/964696.964706