Introduction to Games Programming
By
Jamil Khatib
Table of contents
By
Jamil Khatib
I. Introduction.
A. Why Games Programming?II. Basics of Graphics.A. Video modes and graphics format.III. The 3rd Dimension.
B. Bit Blitting & Bit Clipping.
C. Sprites.A. Projection of 3D objects on screen.IV. Special Effects.1. Parallel Projection.B. Hidden Surface Removal ( HSR ).
2. Perspective Projection.1. Image space Vs. Object space.C. Ray Tracing & Casting.
2. Painter Algorithm and BSP Trees.
3. Z Buffering Algorithm.A. Illumination, Lighting and Shading.V. Algorithms & Data Structure.
B. Scrolling.
C. Special FXA. Data Structures of the game.VI. Game Intelligence.
B. Cell-based game world representation.
C. Collision Detection.1. Explosive Growth
2. Eliminating Collision Tests
3. Spatial-Test Elimination
4. Axis Sorting
5. The Sector Method
6. Hybrid Techniques
7. Quick Tests
8. Fast and AccurateA. Chasing & Evading.VII. Multi-Player & Multi-tasking Enhancements.
B. Random and Pattern techniques.
C. Searching and Mazes.A. Multi-Tasking & Multi-Threading.VIII. Optimization Techniques.
B. Multi-Player Games.A. Fast Multiplication and DivisionIX. References.
B. Loop Unrolling and Flipping
C. Writing Clean Loops
D. Lookup Tables
E. Assembly Language
Introduction.
"Computer Games are the art of computing."Have you ever played a computer game and wandered how did the game programmer do this and that? And asked your self is it easy to implement a computer game? I will try to answer some of these questions and more.
My main discussion will concentrate on the modern Games specially 3-D Games with a lot of wonderful graphics, sound effects and intelligent enemies that makes you feel the reality of the game.Why Games Programming?
Why not games? If you take a look at the world you will find that a new game comes every day. While, there are just small number of Operating systems, compilers or even word processors and spread sheets programs. So by developing many games one can earn a lot of many because all people around the world need to play. The most important reason why I liked this field is that when I program a single game I’ll cover many other computer programming fields, such as graphics, multimedia programming, some database concepts also a lot of computer hard ware knowledge and the most intrusting fields as the computer intelligence and events simulations.Finally as I said before the PC game is a piece of art.
Basics of Graphics.
Have you seen a PC Game in the text mode? How did you find it? I think it was boring. When we think of a PC game we can not imagine it without a lot of moving objects fighting each other with intrusting sounds.
So the first thing we should know to build a game is some knowledge of the computer graphics art and its algorithms.
Video modes and graphics format.
When we play a game we interact with what we see on the computer screen so the games' programmer should take care of his graphics and the video mode he uses. Most of the computers today have a VGA ( video-graphics array ) card. This card has many modes that differ from each other by the size of the screen in pixels and the number it can display at a time.
When a programmer wants to build his game he or she should choose the best video mode for his application. But what is the best mode for a game some may say he should use a mode with high resolution and maximum number of colors. This what most of the game players think, in contrast, the game should not use such a mode, it should use a moderate mode such as Mode 13h or Mode X . Mode 13h has 320*200 pixels size and 256 colors, while Mode X has 320*240 pixels size. The games programmer use this mode because each pixel in this mode needs only one byte of memory when we use higher resolutions and more colors the size of memory used increases and it become more than 64000 bytes as in Mode X. Programmers know that when the size of the stored data increases the speed of the program decreases.
The PC games should not be slow but also they should have good look, but because in we make many operations on the screen and a lot of creatures will be there the player will not notice that the game has low details or it runs in low resolution.
Since in games we need an ultimate fast execution, there as a good reason to view our creatures in the world game from a pre-drown images. These images are saved in files called graphics files. There are many graphics files around the world, such as: .BMP, .GIF, .JPG, .PCX, .TFF, .CDR to name a few. So, what is the best graphics file to choose? I have chosen the .PCX file format. There are many considerations to have before deciding which format to use.
The first factor is the size of the file compared to the image resolution and number of colors in it. This factor makes us to choose the .JPG file format because it has the minimum size and high number of colors (16 Million colors ) with incredibly very small file with high resolution and its size is no more than 50Kbyte. This because it uses an ultra-high compression. It sounds good, but how about its encoding? Does it need much time to load and encode it from the file? Yes, it does need very much time to encode it, and you can try it just open a .JPG image with 1024*768 and see. So you already knew the next factor, that is the time needed to encode the image. I found that the most usable format is the .PCX format. It can hold a large number of colors with many resolutions. Also it uses a compression algorithm called Run Length Encoding ( RLE ). Shortly, this algorithm detects how many similar pixels with the same color in a single row, then it just puts one of pixel of this color with a counter to determine how many pixels of this color there are. This algorithm produces larger files compared with the .JPG files. So, It is easy to encode the .PCX file very fast with some optimization to the code. This file format is used by many of the games as , 3D Duke, War Craft, and Doom
| if ( X > 0 and X < Screen_Width
and Y > 0 and Y < Screen_Height)
then partially visible goto clip else not in view goto next object |
Almost every sprite engine do its work in just few steps:
The sprite is drawn, digested - I mean it can be modeled from a
real world objects-, scanned or created by some software as the Auto-desk
3D-Studio. Then it is saved into a single file or many files. In either
cases it looks like the figure below.
The animation of the sprite means that each piece of the sprite picture is displayed and then deleted and the next piece is displayed and so on, this gives the player as if the object is moving ( like the cartoons movies ).
There are more details that the sprite engine must consider. When the picture is drawn there should be some places where the background must be visible. To make this, we paint the sprite with two types of colors, visible colors and hidden color. This hidden color is not drawn while the sprite is drawn ( this property consumes most of the time of the sprite engine ). But, before we draw the sprite we should save a snap-shot of the background. This snap-shot is used later to draw the background with its original picture after the removal of the sprite.
To summarize the animation of the sprite is done in three phases as described in the next figure.
Figure -2
There is an important thing to talk bout, it is the sprite structure that holds most of the information about the sprite such as the its location, the current frame that should be drawn and wither the sprite is alive or dead.
A final word, you can not always use the same sprite engine in all your games unless they hold the same game idea. Each game can have its one sprite engine and even more, there can be groups of sprites in the game that use different sprite engines. For example, in my game I have not used the idea of talking a snap-shot of the background I always draw my sprite without taking care about anything.
Figure -1
Figure -2
| Xs = D*x/S*z Ys = D*y/S*z |
Figure -3
Figure -4
In this case it doesn't matter which order you draw the polygons it still won't look right!
There is an extension to the Painter's Algorithm called the Binary Space Partition (BSP) trees. This algorithm helps to solve all the above problems. And it is handy for drawing 3D scenes where the positions of objects are fixed and the user's viewing coordinate changes (flight simulators being a classic example).
BSP's work by building an ordered tree of all the objects in a scene. Let's imagine we live in a 2D world and we have a scene like this:
Figure -5
Now if we were to draw this scene using the painters algorithm we would draw line 1 first, then line 2, finally line 3. Using BSP's we can figure out the order beforehand and create a tree. First we note that any arbitrary point <x,y> can be on either of it's 2 sides or on the line (which can be regarded as being on either of the sides). When we build our tree, we take a line and put all the lines on one side of it to the left and all the nodes on the other side on the right. So for the above example could wind up with the following tree:
1
/
2
/
3Figure 6
Alternatively, we could also wind up with this tree:
| 2
/ \ 3 1 |
Notice that line 2 is the head node, line 3 is on the same side of line 2 as the origin is and line 1 is on the opposite side. But what if line 3 is the head node? What side of it is line 2 on? What you have to do here is split line 2 into TWO lines so that each portion falls nice and neatly onto either side of line 3, so you get a tree like this:
3
/ \
2a 2b
\
1Figure 8 The lines 2a and 2b are portions of the original line 2. If you draw BOTH of them on the screen it will look as though you've drawn the entire original line.
You don't have to worry about balancing a BSP tree, since you have to traverse every node in it every time you draw the scene anyway. The trick is to figure out how to organize the tree so that you get the least number of polygon splits. I tackled this by looking at each polygon yet to be inserted into the tree, calculating how many splits it will cause if it is inserted next and selecting the one which will cause the fewest. This is a very slow way of going about things,
 |
but for most games you only need to sort the tree once when you are developing the game and not during the game itself.
Extending these concepts to 3D is pretty straight-forward. Let's say that polygon 1 is at the top of the BSP tree and we want to insert polygon 2. If all the points in polygon 2 fall on one side or the other of polygon 1 then you insert it into polygon 2's left or right node. If some points fall on one side and the rest fall on the other, then you have to figure out the line of intersection formed by the planes that each polygon lies in and split polygon 2 along this line. Each of these 2 new polygons will then fall on either side of polygon 1.
To draw the objects in a BSP tree you start at the top node and figure out which side of the object your view coordinate is on. You then traverse the node for the other side, draw the current object, then traverse the node for the side the view coordinate is on.
Finally, as you can see the last two algorithms was an object space based algorithms. So, they mostly used in low resources systems and small number of game objects. Although, the latest ID-Software game " Quake " used the BSP tree algorithm as I think.
The Z-buffer is a 2-dimensional array consisting of float values. In this array is eventually stored the Z coordinates of your polygons. For instance, if you drew a Z-buffered triangle that was directly facing the viewer (and was five Z units away), your Z-buffer would look something like this:
Figure -9
Now, if we drew another polygon as big as the screen on this Z-buffer that was 6 units away it would look like this:
The rest of the polygon didn't appear because 5 is closer to the viewer than 6.
Figure -11
The idea behind the Ray casting, is to cast a ray out from the observer point( eye ) through your data representing the world until you hit an object ( instead of emitting trillions of light reays only a few will be transmitted from the player view point ). The object you hit is the object you draw and the distance the ray traveled describes the size to draw the object. You only draw the object one pixel wide (position of where you hit it) and the height is the scaled size. If you do this for every column across the screen with slightly different ray angles (representing the view angle of the player) you get a graphical view much like Castle Wolfenstein game.Algorithm -1 Ray casting algorithm
| // Let the player be at position ( xp , yp )
with a view direction of the view_angle.
// Initialize all variables. // Start the cast -30 degrees from the player’s view direction. Start_angle = view_angle -30; // We must cast 320 rays, one for each column. for ( ray = 0; ray < 320; ray++) { compute the slope of the current ray while( the ray is not done casting) { // Test for vertical intersection. if (not intersected yet with vertical wall ) if ( the ray has hit a block on a vertical boundary ) compute distance from xp,yp to point of intersection save distance }// end if vertical intersection if (not intersected yet with horizontal wall ) if ( the ray has hit a block on a horizontal boundary) { compute distance from xp,yp to point of intersection // At this point the ray has made both a horizontal and a vertical intersection. if ( the horizontal intersection is closer than the vertical intersection ) { compute scale based on horizontal distance and render a sliver of the image } //end if horizontal intersection is closer else { compute the scale based on the vertical distance and render a sliver of the image } //end else vertical intersection is closer }// end ray by LaMothe |
Notes on the algorithm:
Slope =
Figure -1
| I = Ik K Cos q 0 < q < p/2 |
| x = 0
y = 0 while( not finished ) { draw to screen( 0, 0 ) from double_buffer( x, y ) x ++; y ++; }//end while |
Figure -2
| x = 0
y = 0 while( not finished ) { draw to screen( 0, 0 ) using map_far at ( x/4, y/4 ) draw to screen( 0, 0 ) using map_medium at ( x/2, y/2 ) draw to screen( 0, 0 ) using map_near at ( x, y ) x +=4 y += 4 }//end while by Thomas |
| typedef struct Object_type
{ int x,y ; // the position of the object . int vx,vy; //the velocity of the object int type; // type of object : food, weapon, wall, health, player, enemy. char *bmp // A pointer to the bit map that represents the object. int state; //state of the object: alive, dead, exists. int extra; //extra data to represent the object. } object, *object_ptr; |
In this structure the object is represented by its location, its speed as a vector and a pointer to its bit map. Finally there is the most important field, the state field which most of the game logic depends on.
Figure -1
Figure -2
The only problem with the Cell based world is that we can’t put the objects where we want them. They must be within a boundary of a cell.
Collision Detection.
Collision detection is fundamental to most fast-action games. After all, the program has to know when a missile slams into an alien spaceship or when the giant frog leaps onto a player. If coded incorrectly, however, collision detection can take an inordinate amount of time, decrease the animation frame rate, and ruin an otherwise enjoyable game.
- Explosive Growth
There are two main reasons why collision-detection code runs slowly: Either the code performs more collision tests than necessary or the individual collision tests themselves are slow. For the first case, imagine a game with two objects on the fieldof play. You want to determine if the objects have collided. With only two objects, collision detection is easy you simply test whether object1 is touching object2 or object2 is touching object1. One of these tests is obviously redundant if object1 is
touching object2, then object2 is also touching object1.
A game with three objects requires three collision tests: object1 with object2, object1 with object3, and object2 with object3.With four objects the number of tests increases to six. Table 1 shows how many tests must be performed to check from 2 to
20 objects. The numbers were derived from the formula (n2-n)/2, where n is the number of objects; given n objects, you can determine which objects collide by exhaustively performing n2 tests. Since you don't compare an object with itself, you
eliminate n tests, giving n2-n. And since testing object x with object y is the same as testing object y with object x, you eliminate half of the remaining tests, yielding the final formula.
Table -1 Number of collision tests that be performed for the objects.
Objects Collision Tests 2 1 3 3 4 6 5 10 6 15 7 21 8 28 9 36 10 45 15 105 20 190
The algorithm is O(n2) where n is the number of game objects for which you must calculate collision status. This means that increasing the number of active game objects slow the game.
- Eliminating Collision Tests
Techniques for reducing the number of collision tests include game-rule elimination and eliminations based on spatial position such as axis sorting and the sector method.Game rules typically dictate which objects are allowed to collide. Consequently, the programmer can reduce the number of collision tests. For instance, imagine writing a game where the player controls a spaceship that shoots aliens. The programmer makes the rules. He may decide that aliens can't collide with each other and that the player's ship can't collide with its own missiles. Alien missiles probably won't hit aliens. Player missiles won't hit other player missiles and alien missiles won't hit other alien missiles, although perhaps you should allow player missiles to hit other alien missiles.
Now assume that you have 1 player spaceship, 5 player missiles, 20 aliens, and 10 alien missiles all active in the game at a given point in time. That's 36 total objects, which would require 1296 tests (n2) if every object had to be compared with every other object. Our formula reduces that to 630 tests ((n2-n)/2), but taking the game rules into account reduces this number even further.
The game rules dictate that the player spaceship must be tested against each alien (20 tests) and each alien missile (10 tests); the player missiles must be tested against the aliens (100 tests) and the alien missiles (50 tests). That's it--180 tests total. Since aliens, player missiles, and alien missiles can't collide with objects of the same type, 450 tests (71 percent) of the 630 tests are eliminated.The real advantage to this approach can be seen when you add one more alien to the screen. Using the original formula, this would require an increase of 36 tests; but because of the game rules, only six must be added (the alien tested against the player spaceship and each player missile).
- Spatial-Test Elimination
Some game rules require that every object be tested with every other one. In such situations, it's best to use spatial-test elimination techniques.
Spatial-test elimination works by sorting game objects according to their position on the screen or play field (if the play field is larger than the screen itself). Objects are then tested for collisions with other objects near them. Objects farther away are not tested because they could not possibly be colliding.
Spatial elimination requires extra computation to sort the various objects and perform additional bookkeeping. The key is to make the bookkeeping run quickly and eliminate as many tests as possible. When bookkeeping saves more time than it adds, spatial elimination is worth the effort. It is better suited for games in which a large number of objects are active at once. If a game has only a few objects, there aren't many potential collision tests to eliminate, and the added bookkeeping can exceed the gain.
- Axis Sorting
When many sprites are on the screen at one time, they are rarely at the same location. An easy way to eliminate collision tests is to sort the sprites in ascending order using each sprite's x- or y-axis coordinate as a key. To check for collisions, simply test a given sprite with the next few on the list. Stop testing sprites when you reach a sprite further down the list whose location has a key greater than the location of the first sprite, plus its width or height. For example, suppose you have five sprites (as in Table -2) sorted according to their x-coordinates.
Table -3 Sprites sorted in ascending order by x-coordinate.
Sprite Number X-coordinate Sprite Width 1 10 10 2 15 5 3 18 8 4 40 10 5 45 10
First, you'd test sprite #1 with sprite #2, then with sprite #3. At sprite #4, you'd stop because sprite #4 is located at x-coordinate 40 and sprite #1's right side is located at x-coordinate 19 (x-coordinate 10+width of 10-1). Since every sprite after sprite #4 has an x-coordinate greater than sprite #4, there is no need to check any further. You'd then continue with sprite #2, and so on, for a total of four tests. The next algorithm represents this method.
Algorithm -1 Axis Sorting Algorithm
ypedef struct _SPRITE_DATA { struct _SPRITE_DATA * Next;
int Top; /* sprite location */
int Left;
int Width; /* sprite dimensions */
int Height;
} SPRITE_DATA;
/*
Function: CollisionTestSorted
Description:
Tests a linked list of sorted sprites to see if they
potentially overlap. If so, they are collision tested.
*/
void CollisionTestSorted(SPRITE_DATA * SpriteList)
{
SPRITE_DATA *s1, *s2;
int s1Right;
s1 = SpriteList;
while (s1 != NULL)
{
s1Right = s1->Left + s1->Width - 1;
/* Compare s1 with all following sprites until left edge */
/* of a following sprite is located beyond the right */
/* edge of s2. */
s2 = s1->Next;
while (s2 != NULL && (s1Right > s2->Left))
{
CollisionTest(s1, s2);
s2 = s2->Next;
}//end while
s1 = s1->Next;
} //end while
}//end CollisionTestSorted
By Roberts
This method relies on the assumption that sprites are usually distributed across the screen. If the sprites are closely grouped together along the sorting axis, this method will degenerate to the (n2-n)/2 situation.
Sorting sprites according to the y-coordinate is a good choice. Since the y-resolution of the screen is usually less, however, using the x-coordinate tends to spread out the sprites. Generally the type of sorting should depend of the game itself.
A common technique in sorting is to keep a doubly linked list of sprites in sorted order at all times. After the movement routine calculates the sprite's new position for the next animation frame, it moves the sprite forward or backward in the linked list to keep it sorted. Typically, a sprite's position will only move a few pixels per frame, leading to only one or two position changes relative to the other sprites in the linked list. Frequently, no position changes will be needed. Note that general-purpose sorting routines are not usually necessary or even beneficial. Most of the time, the linked list is nearly sorted anyway. General-purpose sorts like quicksort are overkill and can even show their worst-case running times when the objects are nearly sorted.
- The Sector Method
The sector method divides the screen or play field into a grid of sectors. In the simplest case, the screen is divided into quadrants. The programmer determines which sector each sprite is located in according to its position on the screen. Then performing standard collision testing among all the sprites within a given sector. Assuming that sprites are usually well distributed around the screen, most sectors will only contain a few sprites; some may not contain any. For instance, Figure -3 shows 6 sprites on a screen divided into 16 sectors.
Figure -4Sprites #1 and #2 are located in the same sector and would be tested against each other; the same goes for sprites #4 and #5. Sprite #3 is all alone in its sector and would not be tested against anything.
The primary difficulty of the sector method is in handling sprites that fall into more than one sector, sprite #6, for instance. Typically, the sprite is included in all sectors it covers. As long as sprites are smaller than sectors, a single sprite can only be located in one to four sectors. The locations of the sprite's corners determine in which sectors the sprite is located. If sprites can be larger than individual sectors, determining which sectors a sprite covers can involve more calculations.So sector widths and heights should be chosen to be a power of 2 larger than the maximum size of the sprites. This approach makes determining a sprite's sector location much easier because you can simply divide its coordinate values by a power of 2. Dividing by a power of 2 is the same as left shifting the coordinate value, so no slow division instructions or routines need to be invoked. Sectors don't have to be square: The vertical size of a sector can be different than its horizontal size. This makes optimization of the number of sectors versus the sector size to more closely fit the needs of a particular game.
- Hybrid Techniques
Sometimes no single technique can acceptably reduce the number of collision tests. This happens when many sprites cluster around each other. Using both game rules and spatial techniques can help out in these cases. For instance, if you're using the sector technique and find that many sprites end up in the same sectors, use game rules to reduce the number of collision tests among sprites within each sector.
- Quick Tests
Generally, collision-testing methods are either bounding or pixel based. Bounding methods are fast, imperfect tests. Pixel-based methods are more precise, but much slower. Novice game programmers often make the mistake of using pixel-based methods for all collision tests. Even with aggressive test-reduction techniques, a pixel-based collision algorithm can slow a game down if it's used for every test.Bounding methods don't compare actual sprite pixels with each other. Instead, a geometric object, typically a rectangle, is used to represent the sprite object in the test. The rectangle is sized to enclose just the pixels that make up the sprite. The advantage is that a few simple tests can determine whether two rectangles touch.
Figure -5
Algorithm -2 Algorithm for testing two rectangles for overlap.
typedef struct { int Left;
int Top;
int Right;
int Bottom;
} RECT;
/*
Function: CollisionTestRect
Description:
Tests two bounding rectangles to see if they overlap.
Returns TRUE if so, FALSE otherwise.
*/
BOOL CollisionTestRect(RECT * r1, RECT * r2)
{
if (r1->Left > r2->Right || r2->Left > r1->Right ||
r1->Top > r2->Bottom || r2->Top > r1->Bottom)
{
return FALSE;
}
else
{
return TRUE;
}
}//end CollisionTestRect
By Roberts
The test determination takes no more than four comparisons. In fact, since logical expressions are evaluated in a short-circuit fashion in C, most tests will stop before the whole logical expression has been evaluated. The order of the tests in Algorithm -3 is arbitrary. If objects in a specific game are typically above and below one another and collide horizontally, you can put the vertical tests first. Finally, the function call may take up much of the execution time in Listing Two. You can easily make CollisionTestRect into a C preprocessor macro using the ?: ternary operator. This allows the test to be expanded inline, saving the time required for a function call.
The only problem with bounding methods is that they are imperfect. Unless the sprite is shaped very much like a rectangle, for instance, some pixels enclosed by the bounding rectangle won't be a part of your sprite. Those pixels may be a part of your sprite bit map, but they are transparent. Technically, these pixels are not part of the object but will be considered so for the purpose of testing collisions. Thus, a collision might be indicated between two objects when only a few transparent pixels have actually intersected.
Perfect collision detection requires pixel-based collision detection, in which the pixels of the bit map are tested to see if they overlap in the current animation frame. Some methods use an auxiliary buffer, where sprites are drawn into the buffer as they are drawn to video memory and tests are performed as each pixel is drawn. This approach requires a lot of memory, however, and can slow down sprite-drawing code.
Another method uses much less memory by first calculating a collision map for each sprite. A collision map is a bit map with one bit representing each pixel in the original bit map, which could be larger, a 256-color byte-per-pixel bit map, for instance. For each solid pixel in the original bit map, the corresponding bit of the collision map is set to 1; for each transparent pixel, the corresponding bit is set to 0.
The program takes bytes from the two collision maps and aligns them according to the original sprites' positions using shifts and rolls. A logical AND is then performed between the two collision-map bytes. If any bits of the result are set to 1, then nontransparent pixels are colliding. Algorithm -4 shows code that tests two collision maps.
Algorithm -5
Unfortunately, pixel-based collision testing runs slowly. It requires much more code than the bounding-rectangle test, and consequently, more run time. The ideal test would run as fast as the bounding rectangle test but retain the accuracy of the collision map test. Fortunately, this is possible.
typedef unsigned int UINT16; typedef unsigned char UINT8;
typedef struct {
UINT16 Width; /* sprite pixel width / 8 bits per pixel */
UINT16 Height;
UINT8 Data; /* first byte of variable length data */
} COLLISION_MAP;
/*
Function: CollisionTestBitmap
Description:
Tests two objects using COLLISION_MAPs. The upper left corner
of each object is specified with (x1, y1) and (x2, y2).
*/
BOOL CollisionTestBitmap
(
COLLISION_MAP far * Object1,
COLLISION_MAP far * Object2,
int x1,
int y1,
int x2,
int y2
)
{
UINT8 far * Data1;
UINT8 far * Data2;
COLLISION_MAP far * SwapTemp;
int DeltaX;
int DeltaY;
int Shift;
int Skip;
UINT16 WidthCounter1;
UINT16 WidthCounter2;
UINT16 HeightCounter1;
UINT16 HeightCounter2;
UINT8 Object1Data;
UINT8 ShiftRegister;
UINT8 OldObject2Data;
UINT8 NewObject2Data;
UINT8 FinalObject2Data;
assert(Object1 != NULL);
assert(Object2 != NULL);
DeltaX = x2 - x1;
DeltaY = y2 - y1;
/* swap objects to make the algorithm work */
if (DeltaX < 0)
{
SwapTemp = Object1;
Object1 = Object2;
Object2 = SwapTemp;
DeltaX = -DeltaX;
DeltaY = -DeltaY;
}//end if
Data1 = (UINT8 far *) &(Object1->Data);
Data2 = (UINT8 far *) &(Object2->Data);
HeightCounter1 = 0;
HeightCounter2 = 0;
/* skip rows off the object with the least Y-value */
if (DeltaY > 0)
{
Data1 += Object1->Width * DeltaY;
HeightCounter1 += DeltaY;
}//end if
else if (DeltaY < 0)
{
Data2 += Object2->Width * -DeltaY;
HeightCounter2 -= DeltaY;
}//end else
Shift = DeltaX % 8; /* amount to shift object 2 data to right */
Skip = DeltaX / 8; /* number of bytes to skip at beginning of */
/* object 1 data line */
while (HeightCounter1 < Object1->Height &&
HeightCounter2 < Object2->Height)
{
/* potentially skip a few bytes 'cause obj 1 is to left of obj 2 */
WidthCounter1 = Skip;
Data1 += Skip;
WidthCounter2 = 0;
OldObject2Data = 0;
while (WidthCounter1 < Object1->Width &&
WidthCounter2 < Object2->Width)
{
/* get data */
Object1Data = *Data1++;
NewObject2Data = *Data2++;
/* shift object 2 data to correct delta X differential */
ShiftRegister = ((UINT16) OldObject2Data << 8) |
(UINT16) NewObject2Data;
ShiftRegister >>= Shift;
FinalObject2Data = ShiftRegister & 0xFF;
/* return if we have a collision */
if (Object1Data & FinalObject2Data)
{
return TRUE;
}//end if
OldObject2Data = NewObject2Data;
WidthCounter1++;
WidthCounter2++;
}//end while
/* correct pointers at end of line */
Data1 += Object1->Width - WidthCounter1;
Data2 += Object2->Width - WidthCounter2;
HeightCounter1++;
HeightCounter2++;
}//end while
/* we got through all that with no collision */
return FALSE;
}//end CollisionTestBitmap
by Dave Roberts
- Fast and Accurate
Quick elimination is the secret to fast collision detection. Most collision tests indicate a negative result. If a game runs at a frame rate of 20 frames per second (fps) and two objects collide about once a second, that's only one collision every 20 animation frames. Even if there are many objects on screen that collide fairly frequently, a given object doesn't collide with most of the others. Therefore, it makes no sense to use an accurate but slow collision-test method for every test. A bounding-rectangle collision test can determine that two objects aren't anywhere near each other as well as a pixel-based method, and is much faster. The only problem is that it will sometimes falsely indicate a collision when transparent pixels of the sprite within the bounding rectangle overlap.Using both a bounding-rectangle test and a pixel-based test in tandem yields both speed and accuracy. First, the combined algorithm performs a bounding-rectangle test. If the sprites don't collide (the usual case), then the bounding-rectangle test indicates a negative result very quickly and the program proceeds to the next pair of sprites. If the bounding-rectangle test indicates a collision, however, the program performs a pixel-based test to determine whether the bounding-rectangle test was correct. The pixel-based test runs much more slowly than the bounding-rectangle test, but it is invoked infrequently.
| //Let px,py be the player’s position and ex,ey
be the enemy’s position
while( game is running ) { // the X component if ex > px then ex ++ if ex < px then ex - - //the Y component if ey > py then ey ++ if ey < py then ey - - } By LaMothe |
| //Let px,py be the player’s position and ex,ey
be the enemy’s position
while( game is running ) { // the X component if ex > px then ex - - if ex < px then ex ++ //the Y component if ey > py then ey - - if ey < py then ey ++ } By LaMothe |
| // Let pattern be an array that holds the transnational
information for ten different patterns.
while ( game is running ) { //Is the creature done with current pattern ? if ( creature is done with pattern ) { //select new pattern current_pattern = pattern[rand % 10] } creature’s position = old position + next element in current pattern increment pattern index } By LaMothe |
| DO
{ move forward keeping the wall on your right if you come to a junction turn right if you come to a dead end turn completely around } until out of maze By LaMothe |
All today Operating system provide this feature and so many programs can run simultaneously under these OS’s such as a spread sheet and a word processor can run together under the Mac OS, OS/2 and Windows95. But in games we do not care if our game runs together with a spreadsheet program or with a word processor because even if the OS can do this the human can not. So what we are not interested in is this kind of multi-tasking. Instead we need to execute more than one portion of the game at once. This type of Multi-tasking is called Multi-Threading.
Figure -1
The idea behind the multi-player games is that each player has his own game running on his machine, and this game send all events that the player do to all other players games. Also it receives the events of the other players and the game deal with these events as if they are inputs like the player’s keystrokes. The events that are send to the other players can be the players keystrokes or the states of the other players then these events are processed on the local machine. But the most important thing is synchronize the events update between all players.
Figure -2
Powers of two are 2 4 8 16 32 64 128 256 .....
For instance, let say we are going to plot a pixel in mode 13h. To plot in mode 13h, you copy the color to the screen offset x +y * 320. 320 is the same as 64 + 256. So instead of:
screen[y * 320 + x] = color;
we can:
screen[((y >> 8) + (y >> 6)) + x] = color;
This is much faster then multiplication because binary shifts are simple
operations, as opposed to multiplications, which are complex operations.
Loop
Unrolling and Flipping
Then you put code in a loop, you have to optimize it more then most
other code, because any slow operation is going to be multiplied many times.
Two ways to do this is loop unrolling and flipping.
Loop unrolling means repeating lines of code inside a loop. For instance,
| for(i=0;i<=20;i++)
{ ships[i].alive = TRUE; } With unrolling: new_index = 0; for(i=0;i<=20;i+=2) { ships[new_index++].alive = TRUE; ships[new_index++].alive = TRUE; } By Berube |
Loop flipping allows us to get rid of one of those jump instructions for each time around, and a conditional jump the first time. It is taking a loop that tests at the top and changing it so that it tests at the top.
| new_index = 0;
for(i=0;i<=20;i+=2) { ships[new_index++].alive = TRUE; ships[new_index++].alive = TRUE; } |
| new_index = 0;
i=0 do { ships[new_index++].alive = TRUE; ships[new_index++].alive = TRUE; i+=2; } while(i<=20); By Berube |
| void Loops(int x0, int y0, int x1, int y1)
{ int u, v, x, y; for ( x = x0; x < x1; x++ ) { for ( y = y0; y < y1; y++ ) { u = width * (x - x0) / (x1 - x0); v = height * (y - y0) / (y1 - y0); } } }
|
| void Loops(int x0, int y0, int x1, int y1)
{ int u, v, x, y; for ( x = x0; x < x1; x++ ) { u = width * (x - x0) / (x1 - x0); // ß for ( y = y0; y < y1; y++ ) { v = height * (y - y0) / (y1 - y0); } } }
|
In 3D games program we use a lookup tables for the most of the trigonometric functions ( Sin, Cos, Tan …. ) because their calculations are the slowest part of the computing and they are needed in they ray casting rotation and many other parts of the game. Any thing you see that is used many times in your program you can put it in a lookup table.
Also instead of pre-calculating these values at the beginning of the
program you can even pre-calculated at the design time and save them to
a file an load it to the memory.
The next code demonstrates the calculation or sin and cos function
and load it in a lookup table.
| float sin_table[360], cos_table[360];
for ( index = 0; index < 360 ; index++) { sin_table[index] = sin( index * 3.14/180); cos_table[index] = cos( index * 3.14/180); }//end for by LaMothe |
So why we don’t write our programs with it ?
The answer is easy, that it is hard to debug it, and harder to read it. Therefore not all functions should be written in assembly only critical functions that slow the game such as graphics and sound functions ( bit blitters, ray casters, scrolling functions and hardware related functions ).
Don’t forget that every body need to play and to have fun, so how much you work how much the people will enjoy.
Contact me at my E-mail
