Cool, It Works! - Issue 02 - Linked Lists, Overloading Operators, Sprites, & More by (01 September 1999) | Return to The Archives

Let's Get Going!

OK, let's get a few things cleared up here right from the beginning... I use OpenGL for graphics, and the DirectX API for everything else .. currently, I am actively using DirectSound and DirectInput, but eventually I will also use DirectPlay for networking (hopefully). I have tried to use Direct3D in the past, and after my head exploded, I tried OpenGL and have never looked back (well, once, but we won't talk about that).
The engine itself is NOT an FPS. I'm making a sort of 3D version of Gauntlet ... the way I've always wanted it to be is if you go into Quake2, go into NOCLIP, fly up to the roof and look down ... that's how I want the engine to look. Lightmaps, models for enemies, nice textures ... but from a top-down perspective. This means that we won't be talking about BSP's or VIS processes .. well, there will be some VIS processes eventually, but I can't imagine they'll mirror anything being done in FPS games. Something very simplistic should cover our needs just fine.
I also code in C++ using Microsoft Visual C++ 6.0 : Professional edition. I use MFC where I think it's appropriate (like in the level editor). And no, I'm not changing. ;)
So to get the most out of this column, you should have a decent grasp of C++ and OpenGL ... I don't think you'll need to know much DirectSound or DirectInput ... I don't know if we'll touch on those directly...

Basics

In this edition, we're going to cover some of the basics of what I've done. These will lay the groundwork for future things that we'll talk about so this is important. But I think if you're interested in this kind of thing, this won't be boring at all. Honest.

Linked Lists

The way I see it, linked lists are the basis of most things in a game engine. It's a good way to represent lists of things that can grow or change radically. Now, linked lists are pretty simple structures ... and what I've done is I've created some data types to make their use super simple. I call them "t_list" and "t_listIT". t_list represents a list of objects, and t_listIT is my iterator class to loop through those objects. For reference, here is the source for these classes...
Click here to view 2-src1.h
This source basically covers everything you need to make and iterate through forward-only linked lists. I could have made it so you could loop backwards too (by keeping a "void* m_pprev;" variable in t_item, but my engine won't use it so the overhead isn't worth it).
A quick note : I sometimes make classes like this through "typedef struct" and sometimes I do it through a proper "class" declaration ... it just sort of depends on what the situation is and how the class is going to be used. If it bothers you, close your eyes.
The reason I would bother to make classes like these? Well, I used to just write code each time I needed a linked list ... but that was bad for 2 reasons ...
1. It was repeated code all over the place. That always sucks for maintainence and it makes code hard to read.
2. It was easy to make a mistake and have to spend an hour debugging a weird problem only to find out that you screwed up the linked list code. This way, everything is in one spot ... everybody uses these linked list classes. If one works, they ALL work. That's very nice for peace of mind.
So ... on to the show. A real basic overview on how I use these is as follows ...
Suppose I have a class called "TLight". These represent point lights like in Quake. I have a variable number of these in my map ... to hold a list of lights, I would just add this to my games data ...

    t_list list_lights;

That's it. That is my linked list for holding point lights. To add a light into the list, I use code like this...

    TLight* l_plight = (TLight*)list_lights.Add(new TLight);

You'll notice that I have to cast the return value. This is because t_list maintains a list of void pointers. This allows it to be generic and maintain lists of anything. The trade-off is that I have to cast return values and a few other things. Not a big deal ...
Now, the reason I capture the return value into a pointer is so I can change the contents of the light after it gets added to the list. So I can set it's brightness or whatever ... it's not necessary and just...

    list_lights.Add(new TLight);

...is really enough if you just want to jam a basic, generic light into the list.
Now, when I have to loop though the lights in the level, how do I do that? With the iterator class ... like so...

       t_listIT IT(&list_lights);
       TLight* l_plight;

       while(!IT.IsEnd()) {

    	l_plight = (TLight*)IT.GetDataPtr();
    	// do whatever you need to do with the light here
    	IT.Next();
       }

Simple. Bloodless. Remember, you have to do a similar loop to this to delete the RAM that you allocate when you add things to the list above. Something like this...

       t_listIT IT(&list_lights);
       TLight* l_plight;

       while(!IT.IsEnd()) {

    	l_plight = (TLight*)IT.GetDataPtr();
    	delete l_plight;
    	IT.Next();
       }

       list_lights.DeleteAll();

This is how I do all of my linked lists, and so far, it's working well.

Operator Overloads

These were a mystery to me for quite a while. Then I started to get into them, and they are quite useful. I don't think they necessarily make your code any faster, but they definitely make it a lot cleaner! For example, say you have a simple vertex class ... something like...

    typedef struct tag_vtx {
    	float x, y, z;
    } t_vtx;

Now, in your code you have a case where you want to add 2 vertices together. You might write something like this...

    t_vtx l_vtxResult;

    l_vtxResult.x = vtx1.x + vtx2.x;
    l_vtxResult.y = vtx1.x + vtx2.y;
    l_vtxResult.z = vtx1.x + vtx2.z;

Now. You can easily make an operator overload here for "+" and simplify this code and make it a lot more readable. First, modify the t_vtx struct like so...

    typedef struct tag_vtx {
    	float x, y, z;

    	inline tag_vtx operator+(tag_vtx &_vtx) {
    		tag_vtx l_vtx;
    		l_vtx.x = x + _vtx.x;
    		l_vtx.y = y + _vtx.y;
    		l_vtx.z = z + _vtx.z;
    		return l_vtx;
    	}
    } t_vtx;

With that done, you can change that code to look like this...

    t_vtx l_vtxResult;
    l_vtxResult = vtx1 + vtx2;

This may look like a small thing, but multiply this over the size of a large project and you can begin to see where the returns come from. You can also do things a little more exotic ... like creating an "=" operator to allow you to assign strings to vertices ... add the operator...

    typedef struct tag_vtx {
    	float x, y, z;

    	inline tag_vtx operator=(CString _cs) {
    		char string[80], seps[] = " ";
    		::strncpy(string, (LPCSTR)_cs, 80);
    		x = ::atof(strtok(string, seps));
    		y = ::atof(strtok(NULL, seps));
    		z = ::atof(strtok(NULL, seps));
    		return *this;
    	}
    } t_vtx;

...put something like this in your code...

    vtx1 = "0 0 64";

...and your vertex will be created properly. I use this more than you might think.

Managers

From the start of my engine, I've been keeping an eye on RAM consumption. I know how fast that can get out of control. So one of the first things I did was create something I refer to as "managers". What a manager is, is a class that keeps track of what has been loaded into RAM and what hasn't. I have separate managers for graphics, sounds, models, etc ...
The theory is as follows, using graphics as the example...
Anytime something needs a graphic, it asks the graphics manager for it. The graphics manager first searches it's linked list of already loaded graphics to see if it's there. If it is, it passes back a pointer to it. Otherwise, it loads it from the disk, adds it to the list and passes the pointer back.
The end result is that no graphic is ever loaded into RAM twice. If 100 things all want to use the same graphic, they all use pointers to the same chunk of RAM.
This may seem simple, but it's an important concept. The interface for getting a graphic loaded is the same throughout the entire engine/editor, the code being executed to load graphics is always the same code (if it breaks, I'll know it!), and it's pretty clean when reading the code ...

Sprites

So, enough internals. You want to get something on the screen right? How about a sprite? Ok, then... The way I do sprites is pretty simple ... 2 triangles arranged to form a square with a graphic texture mapped on top of it. But the trick to sprites, is that they always have to face the camera straight on ... like the monsters in Doom ... so how do we do that ...
Well, I've read lots of formulas for how to get a viewing vector to a specific point in space and so on ... but that made my head hurt. So after some thinking I came up with this ...
If you set up the vertices of the sprite so that it faces due north, you can just rotate it by the opposite of the cameras pitch and yaw (just put negative signs in front of them). That's it. It works, trust me. Sprites will always face you head on and you won't have to mess with complicated formulas...

Next Time

Well, I think next time we'll get into a few other data structures I've concocted, masking/translucency/animating textures and maybe file packages (like Quake PAK files) ... See ya then!

Article Series:

> - Cool, It Works! - Issue 01 - Introduction
> - Cool, It Works! - Issue 02 - Linked Lists, Overloading Operators, Sprites, & More
> - Cool, It Works! - Issue 03 - Files, Texture Effects, Coronas, & More
> - Cool, It Works! - Issue 04 - Handling Textures & Effects
> - Cool, It Works! - Issue 05 - 32-Bit GL Textures & Log Files

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.