RuTh's  RuThLEss  HomEpAgE


3D Game DesignEnglish
Programming Links
* INDEX * 3D game to-do list * 3D Engine to-do list ( chapter 1, 2, 3, 4, 5, 6, 7 ) *
* projection formula * transformation matrices * Bresenham algorithm * Scanline Polygonfill algorithm *
* Spieldesign / game design * Troubleshooting 3D * Irrlicht 3D engine * Blender for Beginners *

Polygonesia — 3D-Game Development

This page documents the implementation of a low-fi 3D-engine in Cocoa (Objective C) that will run on a G3 iMac or faster. The 3D-engine will be called RSF, the demo game Polygonesia. Basic knowledge of Cocoa is required.

Polygonesia concept art: This is what I plan the game to look like. Cute, isn't it?

Polygonesia concept art: The hero is defending his house from a dragon in a hilly landscape.

Programming a 3D-Game Engine in Cocoa

Ever heard of Tieskoetter's "The Black Art of Macintosh Game Programming: Programming 3D Games in Macintosh C"? It's an excellent book to get a basic overview of state-of-the-art game programming on the Mac. State-of-the-art of 1995, that is.

Well, mathematics didn't change in the last 10 years, and despite the books's age it still is a good introduction and reference for beginners like me, who up to now believed matrices were something nice to sleep on. They aren't. Suffering delusions from creating my first Cocoa application (a window displaying a spectacularly static triangle) I figured, I merely had to rewrite Tieskoetter's old C code to Objective C and adapt the methods to the corresponding Cocoa libraries. Can't be that difficult. :-) Or, can it? 8-| Let's see what lies ahead on our way to a low-fi 3D-engine!

Overview: 14 Steps to a 3D-Game Engine

  1. Chapter 1 -- Game concept: You define genre, category, setting and start writing the background story. You need to do that first in order to figure out what kinds of interaction and which kind of structure will be needed in your game. Don't skip this, it will help you a lot later with the implementation. I for example go for a time-based RPG adventure in a post-apocalyptic scifi setting (less NPCs to choreograph there), an alien world with cuboid inhabitants; so now for instance 'time-based' tells me, I must provide for some kind of timer in my implementation, etc. done

  2. Chapter 2 -- The Rotating Cube: Okay, now that we have a concept, let's start implementing. Cocoa uses the model-view-controler paradigm.
    1. As always, the first step is a window with a custom NSView and a controller (if you don't know how to do that, please go through a Cocoa tutorial first.) For the model, prepare files for the C objects I propose here to create the program skeleton. Next you get the background info for implementing the model:
    2. We consult ol' Tieskoetter for the necessary arithmetic formulas for 3D projection to display 3D objects. We write code for displaying simple game entities (objects such as cubes), and while we're at it, templates for easier entity creation. At this point, we already include a first optimization, culling of backfacing polygons.
    3. We also need the formulas to manipulate 3D objects efficiently using 3D transformation matrices. Typical 3D-transformations are moving (translation), resizing (scaling) and rotation around three axes.
    4. Last, we set up an NSTimer for the main event loop.
    This is the essential core of your 3D-engine, this is why this chapter seems pretty long. Note that we may change some details later when the camera is added. done
  3. Intermediate result 1: A lone multi-colored three-dimensional rotating cube, drawn with Cocoa's built-in drawing routines (NSBezierPath).

    Intermediate result 1: A lone multi-colored three-dimensional rotating cube,
    drawn with Cocoa's built-in drawing routines (NSBezierPath).

  4. Chapter 3 -- Loading From and Saving To Files: The Cocoa library assists us with data storage, too. We will implement the NSCoder protocol in our C objects and connect the load and save actions to the corresponding menu items. Another advantage of adding this function early is that it lets us load and save test data, so we don't have to rebuild the application everytime we want a different constellation of entities. done

  5. Chapter 4 -- Overwriting the Drawing Method: This chapter is a preparation for the optimization we'll do in chapter 5, hidden-surface-removal. For this optimization we need access to every single pixel to decide whether it has to be drawn or not. Cocoa's NSBezierPath however keeps us from those "bothersome details". That's why we will need to write our own drawFilledPolygon: method (in place of Cocoa's [NSBezierPath fill]). From now on, we will use our drawing methods instead of the built-in ones, although it's very likely that Cocoa's NSBezierPath drawing method internally uses the same Bresenham line algorithm and scanline polygonfill algorithm. done

  6. Intermediate result 2: A lone multi-colored three-dimensional rotating cube, drawn with custom drawing routines.

    Intermediate result 2: A lone multi-colored three-dimensional rotating cube,
    drawn with custom drawing routines.

  7. Chapter 5 -- Hidden Surface Removal: Whole backfacing polygons were already culled in chapter 2. Now, we finally want to skip drawing pixels that are covered by objects standing in front of them. Tieskoetter quickly uses the Painter's algorithm and only describes the better Z-Buffer algorithm that I'll go for in this example. in progress

  8. Chapter 6 -- Clipping: Clipping is another quite complex part: As soon as our gameworld grows, we have to restrict drawing to objects in view, also we obviously don't want to calculate all the overlaps between stuff behind the player etc. Most importantly, this chapter deals with the correct displaying of those polygons which are partially behind and partially within the viewport — Since we use our own drawing methods now, it's now up to us not to draw pixels outside the graphic buffer. nothing yet

  9. Chapter 7 -- The Camera: Up to now, the camera was stuck in the center (the so-called origin) looking down the z-axis. Since moving the camera around in the world complicates calculations, 3D-engines again fall back onto a trick: They just reposition the world around the camera into the opposite direction! That way, we can easily reuse existing transformation methods, but on the other hand, this step calls for an important upgrade in the way game world data is stored. Also, we want camera movement to be controlled by at least the keyboard (NumPad) or, even better, the mouse or a joystick. nothing yet

  10. Chapter 8 -- Complex Entities: Currently, our game engine only supports simple MYEntitys like cubes. But later in the game world, we also want complex game entities that consist of one or several members, MYSubentitys. Those members of an entity are supposed to be attached but moveable; that way we can represent things like a person's arms and legs. in progress

  11. Chapter 9 -- "Textures", Flat Shading: I'll stick with texture-less colored polygons. But I'd like to at least darken or lighten the polygon's color depending on the direction it is facing (N-E-S-W) and its context (day/night, inside/open air). Definitely no individual light sources, no advanced shading, and no drop shadows in this version. nothing yet

  12. Chapter 10 -- Collision Detection: We define walls (slope greater than 100%) as opposed to the ground (slope less than 100%). Detecting and responding to collisions between objects. Detecting and responding to collisions between the camera (= player) and objects. nothing yet

  13. Chapter 11 -- Game Physics: Gravity (falling), realistic walking, flying, jumping, running, climbing, swimming. nothing yet

  14. Chapter 12 -- Game World Interaction: We design templates for game entities (various persons, animals, plants; weapons, tools, crates; buildings, doors, walls); we design movement schemata for game entities (movement of arms and legs while walking, fighting, etc). We implement interactions such as picking up, dropping, attacking or (de)activating (switching, eating, wearing, opening, etc); opening and closing of doors and trapdoors, possibly moving platforms or elevators; we define paths and write scripts defining simple strategies of an artificial intelligence. nothing yet

  15. Chapter 13 -- Sound: Noises accompanying movement (footsteps), collisions, (de)activation of objects and other actions; background music; environmental sounds (wind, machines, birds, wood, water). nothing yet

  16. Chapter 14 -- Gameplay: Templates for the creation of different "dungeons" (levels); randomizer for game world creation; implementation of missions and challenges, antagonist NPCs and their strategies. Multiplayer LAN would be extremely cool... nothing yet

So, this is my to-do list for now. *phew* Use it as an example for your own to-do list and adapt it to your game's needs! I'll try to be somewhat abstract, so you can use the steps for Java, C, C++, Visual Basic, or whatever you like to program in. I am not going to give you the whole Cocoa code for download, sorry, but I'll give you all the objects and methods and describe how it's done.