Programming assignment #3 - 3D Video Game

CS 248 - Introduction to Computer Graphics
Autumn Quarter, 2008
Marc Levoy
Handout #8

Game proposals due Monday, November 3 by 5:00pm
First demos on Friday, November 14
Final demos on Wednesday, December 3
Writeups due on Friday, December 5 by 5:00pm

Your assignment is to write a 3D video game using OpenGL. You are free to design and implement any sort of game you like, as long as it incorporates the required functionality described below. For purposes of this project, we consider a 3D video game to be an interactive 3D computer graphics application that has a challenging goal, is fun to play, and incorporates some concept of scoring or winning and losing. It is not required that your game idea be original, but originality will be rewarded with extra credit. It is also not required that the game be intrinsically three-dimensional; you can take a 2D game and render its components three-dimensionally, converting game pieces to solid models, lighting them, etc. (Of course, games that are intrinsically three-dimensional probably have a greater chance of winning a spot in the competition.) If you have any questions about whether your idea meets the criteria for a 3D video game, please ask the course professor or a TA. Your game proposal (due November 3), and our feedback to you afterwards, should help you in developing your game concept.

You are permitted (and encouraged) to form teams of 2-3 people and partition the work among the team members. The work expected from each team will be proportional to the size of the team. You can use the class newsgroup su.class.cs248 to find prospective team members. Each team should submit a single game proposal, jointly authored by all team members. You may change the composition of your team at any time prior to November 26 (one week before final demos). However, changes after the first demos (on November 14) are strongly discouraged.

You are not required to work on any particular platform. You are welcome to use the myth machines in Gates B08, but you are also welcome to use a laptop (any operating system), or even the Cray supercomputer in your dorm room. If you choose to use a mobile platform, such as a Nokia N95 cell phone (which we can loan you), then we will not expect the same performance or model complexity in your game that one can acheive on a faster platform or a larger screen. However, the fundamental requirements for the project are the same.

Required functionality

• 3D viewing and objects. Your game environment must be a scene consisting primarily of 3D elements, as opposed to only "flat," 2D sprite-based graphics. Your game should provide perspective views of your 3D scene where at least sometimes the viewpoint changes smoothly under some combination of user and program control. To produce these views, you should implement transformation, clipping, and hidden-surface removal of your 3D scene using OpenGL.

• User input. Your game must allow players to interact with the game via keyboard or mouse controls. Alternatively, you can use joysticks or more elaborate user interface devices (provided that you supply the required devices for your program demonstration sessions; see below).

• Lighting and smooth shading. Your game must contain at least some objects that are "lit" using OpenGL's lighting model. For these objects, you'll need to define normal vectors and materials, as well as create one or more light sources. See Chapter 5 of the OpenGL Programming Guide for details on implementing lighting and shading.

• Texture mapping. You must implement texture mapping for at least one of the 3D objects in your video game. Chapter 9 of the OpenGL Programming Guide describes how to implement a variety of texturing techniques. If you want, you can use your paint program from assignment #1 to create 2D texture maps in the .ppm image format, and/or borrow the xsupport source code from assignment #1 to load .ppm files into your game for use as textures.

In addition to these basic requirements, your game should incorporate some of the more advanced computer graphics techniques listed below, depending on the size of your project team. In particular, you are required to implement at least 2*N of these additional techniques, where N is the number of people on your team (i.e. groups of three people need to implement six techniques, individuals working alone are required to implement only two, etc.). Of course, you are encouraged to implement as many of these techniques as you can, depending on the requirements of your particular game engine, as well as using any other ideas you read about or invent on your own. Extra effort will be rewarded with extra credit.

• On-screen control panel. Many 3D video games reserve part of the display area for an on-screen control panel, which may include text or 2D graphical elements for user controls, scoreboards, etc. Flight simulator games often superimpose 2D graphical overlays on the 3D world, thereby creating a "Heads Up Display (HUD)." You can implement a control panel for your game using a variety of techniques in OpenGL, such as orthographic projection and the stencil buffer. Text primitives are not explicitly supported with OpenGL, but GLUT and the window system extensions (GLX, WGL, etc.) both provide commands to help render text.

• View frustum culling. In video games with complex 3D environments, it is necessary to limit the number of 3D primitives drawn each frame in order to maintain interactive rendering rates. One way to do this is to avoid drawing any 3D objects which are outside of the viewing frustum of the camera. A more sophisticated technique is to pre-compute bounding volumes for objects and then test each bounding volume to verify that some part of it intersects the view frustum before drawing its contained objects each frame. Finally, for even greater efficiency, you can organize your objects (and bounding volumes) into a tree-like data structure, sometimes called a hierarchical scene graph. Object hierarchies are discussed in Chapter 7 of the textbook. and view frustum culling is discussed in Chapter 16 of Möller and Haines's book, Real-Time Rendering.

• Level of detail control. Another way to limit the number of 3D primitives drawn each frame is to implement level of detail (LOD) control in your game. One simple method of LOD control involves creating multiple versions of some of your 3D objects, varying in geometric complexity (such as 10, 100, and 1000 polygons). Then, before drawing the objects each frame, you can pick the most appropriate version of the object to render, depending on such metrics as the distance of the object from the viewer, the complexity of the current scene, or a user-selectable detail level. Levels of detail are discussed in section 9.8 of Real-Time Rendering.

• Occlusion culling. Yet another way to maintain good game performance with complex environments is by performing occlusion culling. Similar to view frustum culling, this technique involves using a conservative computation to avoid drawing any parts of the 3D scene which won't be seen by the viewer because they are hidden behind other objects. For static environments such as buildings, you might pre-compute which regions of space (such as rooms) are impossible to see from other regions (due to occluding walls, for example). More information on occlusion culling is in sections 9.5 and 9.7 of Real-Time Rendering. (Don't confuse occlusion culling with simple hidden-surface removal, which is required for your video game.)

• Procedural and physically-based modeling. In addition to using scanned or hand-modeled objects to populate the 3D worlds, some video games use procedurally computed models. Chapter 20 of the textbook describes examples of procedural modeling, including fractally-generated mountainous terrains and L-grammars for generating models of plants. Procedurally generated textures may be used to simulate effects such as fire, smoke, and clouds.

• Collision detection. Video games often contain moving objects which trigger events when they collide, such as projectiles shot at a target. Collision detection can also be used to prevent the user from passing through walls or other objects. You can implement collision detection in a variety of ways; the simplest might involve comparing bounding volumes of objects to decide if they intersect or not. If you have complicated objects, a hierarchical scene graph (see view frustum culling above) may prove helpful to accelerate your collision detection tests. Chapter 14 of Real-Time Rendering describes a number of collision detection techniques.

• Simulated dynamics. Your video game implementation might include modeling dynamic behaviors and physics for objects in the 3D world. For example, the wheels of a vehicle might react realistically as they move over rough terrain, or a ball might bounce differently depending on its velocity, elasticity, and the characteristics of the surfaces it hits. Realistically animated characters in 3D graphics applications are sometimes controlled via simulated dynamics.

• Advanced rendering effects. OpenGL makes it possible to easily implement a wide variety of realistic rendering effects. Some of these effects can be achieved by drawing the scene multiple times for each frame and varying one or more parameters each pass through the scene; these techniques are called "multi-pass rendering." Other techniques combine traditional 3D graphics rendering with 2D image-based graphics. Advanced rendering effects you can add to your video game include soft shadows, reflections, motion blur, depth of field, bump mapping, environment mapping, billboarding, and projective texturing. See chapter 6 and 8 of Real-Time Rendering as well as the pointers on the assignment web page for examples and information on implementing advanced multi-pass and image-based rendering techniques.

• AI. Some video games include computer-controlled agents that require a significant degree of artificial intelligence. Many of the techniques taught in a basic AI course are applicable to video game development, and some links to more detailed information on game AI are included on the course web page for the assignment. If you have any doubts about whether a technique you are using qualifies as "AI" for this assignment, ask us.

• Game level editor. Some video games are accompanied with supplementary computer graphics applications which allow users to design their own game levels (scenes). If you develop your own custom application to construct levels while writing your game, you might consider packaging it as a separate utility program for end-users to enjoy as well!

A few hints

• This project is purposefully designed to be more open-ended than the first two assignments of the course. You will be expected to do a considerable amount of learning on your own, particularly in gaining experience with programming in OpenGL. We will cover the high-level concepts of OpenGL in class, and we have assigned some sections of the OpenGL Programming Guide as reading. There will also be an OpenGL help session on Friday, October 31, at 2:15 in B01. Beyond this, please take advantage of the opportunity to consult the course professor and TAs with questions concerning development of your particular video game. If there are computer graphics techniques not covered in the course that you would like to implement, we will usually be able to point you to an appropriate source of information. In order to assist and inspire you, a web page is available at the URL:

       http://graphics.stanford.EDU/courses/cs248-08/proj3/
  

  This page includes pointers to OpenGL tutorials, information on game development, useful utility programs, and sources for 3D models and other game content. Additional examples of OpenGL code from the programming guide and OpenGL and GLUT distributions are available in the class directory in /usr/class/cs248/assignments/assignment3. Of course, you are responsible for understanding and implementing your own video game code; sharing code or libraries between teams is not permitted. Using source code, libraries, or executables you find on the Internet (or elsewhere) is permitted, but is limited to programming tools and low-level utilities. In particular, borrowing the code that implements basic or advanced game features (as enumerated above) is not allowed. Looking on the Internet for ideas, even looking at sample code you find there, is permitted and encouraged. However, when you do this, we expect you to cite your sources in your writeup.

• Interactive 3D graphics programs such as video games place special demands on computer hardware. If your 3D world is particularly large or complex, you will probably need special graphics hardware in order to get real-time performance. The myth systems in Gates B08 Hall are equipped with recent NVIDIA graphics cards, which deliver excellent 3D graphics performance. If you develop your game on an above average platform, it will probably be useful to add options to optionally disable expensive features. The performance of your video game is important, so do not implement too many expensive rendering features if the gameplay is negatively impacted! There are some pointers on the assignment web page to sources of information on maximizing OpenGL performance.

• Most successful video games include richly detailed 3D models, textures, sounds, and other content for representing the game world and characters. You have several options available in creating the content for your video game:
  • Simple models can be sketched on graph paper, and the coordinates manually typed into your source code.
  • Models can be procedurally generated, as mentioned above.
  • You can use a 3D modeling package and export the model in a format your program can read. The assignment web page contains pointers to several freely available modeling packages.
  • The GLUT library provides functions for drawing simple 3D shapes (sphere, cube, etc.)
  • You can find a wide variety of 3D models, textures, and sounds on the web; see the pointers on the assignment web page. These may need to be converted to a format your program can use; we will provide some example source code for loading models.

• Using source code, libraries, executables, or data you find on the Internet (or elsewhere) is permitted, but is limited to geometric models of characters or props (but not entire environments), textures, sounds, and low-level programming tools (like matrix packages). In particular, borrowing code that implements required (or extra credit) game features is not allowed. Note that sound and networking are not on the list of features you can get credit for, so you are welcome to download packages that help you implement them. All this said, looking on the Internet for ideas, even looking at sample code you find there, is permitted and encouraged. However, when you do this, we expect you to cite your sources in your writeup. We also expect that your video game was developed only for this course, and that it was begun no earlier than the start of this academic quarter.

• OpenGL is window system independent, so an additional toolkit is necessary to provide the necessary windowing and input event management; for this we recommend using SDL or GLUT. GLUT is used for all the examples in recent editions of the OpenGL Programming Guide, and is available for most all common computing platforms. A simple example program and Makefile using OpenGL and GLUT on the myths is available in /usr/class/cs248/assignments/assignment3/example. GLUT offers a very limited set of user interface widgets (little more than menus). If you require slightly more extensive user interface functionality, consider trying the MUI, PUI, or GLUI toolkits; they are easy to use, and are written entirely on top of GLUT and OpenGL. You may recall GLUI was used for assignment 2. Documentation is available on the web (see the assignment web page for pointers). SDL is a little more heavyweight, and removes some of the limitations of GLUT. In addition, SDL will help you with networking code, sound code, and it's cross platform. Check out SDL at http://www.libsdl.org/ for more detail. There's an OpenGL/SDL example available here.

• You are also free to develop your video game on any computer platform that supports OpenGL, provided that you will be able to demonstrate your program at the two required demonstration periods in Gates B08. If your program cannot run on the myths, you will be responsible for bringing a system to those labs on which to run your video game. Versions of OpenGL for most common computing platforms are available for download at sites pointed at from the assignment web page.

• In the course of designing and implementing your video game, keep in mind that CS248 is a computer graphics course. Focus your efforts on the computer graphics techniques underlying the game; don't spend the majority of your time on game design or object modeling if the graphics engine will suffer as a result! Finally, don't make your 3D world or game engine so complicated that interactivity suffers. Your game must be playable!

• We'll be grading your advanced techniques on a bucket system: minus, check-minus, check, check-plus, plus. Your grade on this scale will depend on the difficulty of what was implemented. Stated simply, grades will be proportional to effort. To get an A on this assignment, we need to see outstanding effort on at least one advanced feature. In general, although implementing more features will increase your grade, we prefer that you implement fewer features but do them well, and we will grade accordingly. In a few days, we'll send out a mailing to the class giving examples of the amount of effort we consider "outstanding" for each of the advanced features.

• Finally, as stated during the first class in September, you do not need to implement a shrink-wrappable game in order to get a good grade in this assignment. If your quarter is too busy to spend the next four weeks in Gates B08, then don't. Implement the required functionality and two advanced techniques, one well, and you'll get an A. Every year, many students do this successfully. Be inspired by your colleagues who are gunning for the grand prize, but do not be intimidated. In most years, the winning team starts only after the assignment is released.

Video game submission requirements

The game proposal. Your first milestone is a proposal, due by 5:00pm on Monday, November 3. Your proposal can be brief - 1 page is plenty. Be sure to list all team members. The proposal should clearly state the premise of your game, describe the 3D world you plan to build for it, outline the gameplay, and enumerate the 2*N advanced techniques you plan to implement. If you envision facing any special technical challenges (like predicting collisions between a basketball and a hoop), list them. If you'd like "advanced feature" credit for something you'll be spending a lot of time on, but which is not listed above (like the ability to play against 5,000 networked opponents simultaneously), list those too. If you envision needing any special tools to achieve your goals, like a laser scanner or a motion capture system, tell us how you'll get access to these tools.

Finally, you must include at least one image in your proposal - a sample screenshot of the game in action. We don't care how you produce this image: a scanned pencil sketch will do, or something you whip up in Photoshop, Illustrator, KidPix, or your favorite computer art program. Carefully label the principal components in your image. Sample labels might be: "waterfall [here] will use real dynamics", or "[these] missiles will emit particle system smoke". The purpose of this requirement is to help us understand your proposal, and to help you think about how hard or easy it might be to implement what you propose.

Only one member of a group is required to submit for the team. The submitter should:

1. Know the SUNet IDs of all team members
2. Login to any of the myths (NOT elaines)
3. Create a directory which contains the text of your proposal (plain text preferred, but we'll accept PDF) and the image.
4. Run the submit script /usr/class/cs248/bin/submit, which will ask for the path to the above directory and SUNet IDs of the other team members.
5. Take a deep breath, and start working on the video game.

Submitting a proposal is required, and late submissions will be penalized, but your proposal will not be graded. Neither will you be held to either the list of advanced graphics techniques you enumerate or to the composition of your team. The purpose of this proposal is to motivate you to begin working on the project, and to give us a chance to guide you. We will read and respond (by email) to every proposal. Hopefully, most of these responses will be of the form, "Cool game idea! Full speed ahead!". However, if we see you headed towards the shoals, we'll let you know.

First demos. On Friday, November 14 you will demonstrate your partially complete video game to a member of the CS248 course staff. To show reasonable progress, your 3D world should be largely in place, although perhaps lacking in detail or performance, your "gameplay" should be basically working, and at least some of the required graphics functionality (3D viewing, user input, lighting, and texture mapping) should be implemented. The 2*N advanced techniques need not be in place, except that depending on your game, you might need to have already implemented some of them in order to demonstrate your gameplay. At the demo, we will give you feedback on your game, and we will discuss with you your plans for finishing it.

Signups for these demos will be handled electronically, as usual. You can demo on any platform you like, even a laptop or cell phone as noted earlier. However, all demos must be given in Gates B08. There is no need to freeze your code before the demos. All team members must be present at the demo. Late demos will be permitted, but will be penalized in the usual way. No writeup or submission of source code or other files is required following these demos. In addition to giving you verbal feedback at the demo, we will also grade you. Since you are not submitting code, these grades will based only on what we see during the demo. However, these grades will be simple: minus, check-minus, check, check-plus, plus, depending on the quality of your progress.

Final demos and writeups. Your complete video game will be demonstrated on Wednesday, December 3. Signups will be handled electronically, as usual. No code freezing is required. All team members must be present at the demo. During the demo, make sure you tell us what features you have implemented. Functionality you don't show us or that doesn't work will not be given credit.

Final writeups and code and content submission is due on Friday, December 5 at 5:00pm. To submit your video game files, simply run the script /usr/class/cs248/bin/submit, as you did for the video game proposal. The team member submitting will be prompted for the directory containing all the video game files and SUNet IDs of the other members. Only one submission per team is necessary. Your submission should include your entire game - source, executable, makefiles, models, textures, etc. It should also include a README file which lists your team members, describes how to build and run your video game, and explains the 2*N (or more!) advanced computer graphics techniques you implemented. Also, your README file should include references to any external sources you referred to for inspiration, and it should indicate how your 3D models and other game content were obtained. Remember - no late demonstrations or writeup submissions will be accepted.

Separately from your joint team submission, and privately, each team member should prepare an individual writeup by 5:00pm on December 5 specifying who worked on which features of your game, and what percentage of the total work each team member did. Your writeup should be a single text file. This is to be submitted electronically by running the script /usr/class/cs248/bin/privsub from one of the myths. The script will prompt you for the location of your writeup and the names and SUNet IDs of your teammates. These submissions will be held in the strictest confidence by the course staff.

The video game competition. After the demos are finished, probably around 4:00pm (on December 3), a jury of computer graphics experts from industry and academia will join the CS 248 teaching staff to evaluate your programs as part of a video game competition. Any team may enter the competition; however, participation is not required. The first step will be the selection of roughly 8 finalists. This selection will be performed by the teaching staff immediately following the completion of demos. The second step is the selection of prizewinners, which will be performed by the jury. The composition of the jury will be announced shortly.

There will be one grand prize - an all-expenses-paid trip to Siggraph 2009 in New Orleans next summer, and one second-place prize - dinner for two at Il Fornaio in Palo Alto. In addition, every member of a finalist team will receive a current video game title for the PC platform, generously donated by Electronic Arts. Finally, there will also be a special prize given for the wackiest or most daring submission, but we don't yet know what it will be. (An Xbox was last year's prize in this category.) Depending on the number of entries on mobile platforms, we may create a special category of competition and prizes for them, but this has not yet been decided. If the grand prize is won by a team, it must be split among the team members. The second-place prize will be duplicated as necessary to cover the team. Only one prize for wackiest submission will be awarded. The competition will be accompanied by an amazing party.

As a prerequisite to entering the video game competition, each team must create a web page for their project. The page should have a title, a paragraph describing the game, and links to one or more screen-shots. The links to the full-size screen shots should be by clicking on downsized versions of these images, each 128 pixels tall. After the competition, entrants will be asked to provide compressed "tar balls" or zip files for distribution of their game, along with an indication of the target platform. The distribution should include an executable for at least one platform. Any team that does not wish to enter the video game competition but would like their game distributed is also encouraged to create such a web page. Teams who do not enter the competition do not need to create one.

Good luck, and have fun!