Introduction

Well, let's jump into the technology. First off, thanks to Microsoft guys for DirectDraw. No DirectDraw - no 2D and 3D games for Widows. DirectX allows to access the graphic resources of a computer system on the lowest level (= very fast)
The other good thing about DirectDraw is that it allows you to store pictures and sprites in the graphic card's memory. This way, the pictures don't have to be transfered all the way from the system RAM. All chunks of graphic card memory are called "Surfaces". So far - no problems.

Surfaces

Every game that uses DirectDraw must have at least one DirectDraw Surface - that is what you see on the monitor. As I said, a Surface is nothing, but a chunk of memory that contains the picture data. So, if you know where this "Surface" is (a pointer to this memory location), you can write something to this memory and you'd see changes on your screen.

So if the resolution you chose for the game is 640x480, you will have 640 * 480 pixels, right ? So, if one pixel represents one byte, you'd need 640 * 480 bytes, correct ? I am using the 16 bit color model (the higher the bit number, the more colors can the monitor show, the more memory is required) which means that 1 pixel is made of 2 bytes, rather than 1 byte (16 bits = 2 bytes).
Saddly, we have to multiply the amount of required memory times 2. So our primary surface occuppies 640 * 480 * 2 = 307, 200 bytes ! That's a lot of memory ! But, don't cheer up yet. For smooth animation, we need a backbuffer surface, which is the exact duplicate of the primary surface. Now let's add 'em up - (640 width * 480 height * 2 bitcount) * 2 surfaces = 1.17 MB of graphic RAM is required to run the program.

The Burger

So, what do we do now ? We load the images into memory. To do that, we create a surface for each pic and blit the picture on it ! Let's say we want to put a picture of a mushroom (60 x 30) on the screen. Here are the steps :

1) Init DirectDraw (create The Primary Surface)
2) Create a 60 x 30 Surface
3) Load a picture
4) Blit the picture onto the Surface
5) Blit the Surface onto the Primary Surface
6) Destroy the Surface and The Primary Surface

And this game works the same way. Except, we have more Surfaces to blit. Let's see what surfaces I use :

First, the Background is blitted onto the Backbuffer Surface, then the Sprite and other Objects are drawn over the whole thing. As simple as a hamburger.

Main Loop

Now we've got to set the whole process in motion. How ? I'm using a Windows multimedia timer. It generates an event every n milliiseconds, so we use this event to update the screen. How fast should the timer operate ? Well, the standard refresh rate is 60 frames per second (TV cartoons run at 24 frames per second). There are 1000ms in a second. Therefore, to get a 60 FPS rate, we need to wait 1000ms / 60 = 16.6 ms each time we refresh the screen. So set up your timer with a 17 ms interval, or use Sleep(17) Win32 function.

Gadget Hackwrench

How do we animate Gadget ? Take a look at the original JPEG, I'm using in the game :

You can see that Gadget is walking from right-to left. You might have guessed that we need to perform some transformations before drawing it onto the surface. If Gadget walks to the right, we need to reflect the Surface, if she walks near a tree (she is waaay smaller than the tree) we need to scale the Surface first.

Also, the frames in this animation are not always displayed the way they are. They follow an animation pattern, which is [1, 2, 3, 4, 5, 6, 5, 4, 3, 2] to produce smooth walking animation. In future, I'll append more animation cells for talking etc.

Advanced Overlays

Suppose, you're at Scene 31 (Park Level), where the HQ tree is. What happens if Gadget walks behind the tree ? She'd become partly or totally invisible. How can such effect be achieved ?

1) We could create a sparate Surface with the image of the tree and draw it on top of Gadget. (requires memory for the surface, losing speed when blitting it on top)

2) Do it the way I did ! Ha ! (Read ahead)

To understand overlay masking, you need to know one thing - the bit-operations. It's actually not as complicated as it sounds. All numbers can be represented as bytes. 1 byte can be represented as 8 bits (that are either 0 or 1). A Color can be represented as bits, too ! You can modify these bits with AND, OR, NOT etc operators.

Let's take a look at AND operator and keep in mind, that Black = 0, not Black = 1:

0 and 0 = 0 0 and 1 = 0 1 and 1 = 1

It means, if both colors you're mixing are black, you'll get black as a result. If you mix, say, blue with black, you'll get black anyways. But if you mix, say, blue with red, you'll get anything, but black ! White and black colors are special ones ! Look at their binary values :

White = 11111111 11111111 11111111
Black = 00000000 00000000 00000000

So, if we AND any color with Black, we'll get black. If we AND any color with white - we'll get the same color.

AND =
nifty, eh ? Gadget's covered with a black rectangle !

Now we only have to draw a black'n'white bitmap that contains black shapes that represent areas covering Gadget ! Then AND the sprite with this mask, blit the resulting image onto the background - and voila !

How to AND a pic with another one ?

There are at least two ways (I'm using the first one for now) : Win32 function "BitBlt" it's excellent for combining 2 device contexts (HDC). Not only can you AND them, you can also OR, XOR and INVERT 'em! BitBlt(DestinationBitmap.Canvas.Handle, 0, 0, DestinationBitmap.Width, DestinationBitmap.Height, SourceBitmap.Canvas.Handle, 0, 0, SRCAND) Write an Assembler routine I'm not going to start explaining how to write one, eventhough this routine'd be the fastest of all.. To write such routine, create a loop that gets a byte from the destination source, ANDs it with the source byte and writes it back. If you need help, e-mail me.

Walking The Path (updated : Sept 9. 2001)

Yikes! This algorithm was one of the most complicated parts. Say, you clicked on the path near a tree and you want Gadget to happily jog to this point. It might look like a simple task, but don't forget about the tree (the blue-shaded area represents the region, where the sprites can move) ! Or, in another level there might be a bunch of crates, boxes or trashcans - you can't let Gadget bump into all those things ! To find a good path between two points requires some knowledge of AI (Artificial Intellegence) path-finding algorithms. Let's see if I can explain it in simple terms :

Game releases 0.1 to 0.7 featured rectangular areas, that would let Gadget walk in rectangular regions only (boring and unprofessional). I researched the A* (A-star) and "BestFind" (which I'm going to use) algorithms to make all kinds of walkable areas possible. "BestFind" algorithm, is the fastest one. It usually takes about 245-600 milliseconds to find a good path between 2 points (without bumping into walls !)

Let's start ! So, what is the core of the whole process ? We need :

The starting point is basically where Gadget is right now, and the End point is the location where you want Gadget to go to. A map is just a 2-color bitmap (or 2 dimensional Array) that represents walkable areas. Then we find the path between those 2 points, save each vertex of the path in an array and let Gadget walk it step-by-step.

Now, how do I write the algorithm ? The first thing, you need to understand some basic concepts.

if a point is not surrounded by walls, we can go to any of the 8 surrounding cells (expanding a node)	if we hit a wall, we just ignore the point, and move to another one. Here we expand in only 5 directions.
using the a2+b2=c2 distance formula, we try to find a point that is closer to the End. In this example, it's point B. Forget the other 7 points for now - they are too far away !	Then we expand point closest to the End (Point B). Notice that we only create 5 points E,F,G,H,I, because points above (gray shading) have already been "researched". Point H is the closest one to the End, so we expand it and so forth, until one of the points hits the End.

There is a major difference between Open points and Closed points. An Open point is a fresh point that we haven't expanded yet. After we expand it (creating 8 or less child-points), it becomes a Closed point. We need to maintain a list (use TList in Delphi) that will contain our points (simple records) for each type of those points. So, we end up with an OpenList and a ClosedList. And here's the basic pseudo-code structure of the BestFirst algorithm :

The record that represents a point holds 4 values : X, Y : coordinates, F : distance to the End and Parent : represents from what point it derived. After we find the path, make a short while loop that will get the chain of points from the EndPoint using the "Parent" field. Then, make a loop that takes a vertex from this point chain, assign a character's X and Y coordinates to it and voila !

As you can see, it's a very powerfull and fast search algorithm. Just look at the screenshot left, how long would it take you to find the exit of that maze ? BestFirst did it in 270 milliseconds. If you have any questions with Delphi implementation of BestFirst or A*, e-mail me

Tthese links are quite helpful :
Justin Heyes' Introduction to A* -go there-
Game AI -go there-
Thomas Grubb's Delphi Pathfinding demo -go there-

Classes And Objects

Object-oriented environment is a cool feature when building games. Here is the list of Classes I created for the Game :

"Tag", one of the most important properties, is defined in the very beginning - in the "TGameThing" class. "Tag" is the number of the object in the game. If a thermometer object has a Tag number 23, we can always look up the phrase Gadget would say if you click on it.

More stuff coming soon !