Game Development of .Nettrix: GDI+ and Collision Detection - Optimizing the Number of Calculations
(Page 6 of 22 )
As the number of objects in the game grows, it becomes increasingly difficult to perform all the necessary calculations, so you’ll need to find a way to speed things up. Because there’s a limit to how far you can simplify the calculations, you need to keep the number of calculations low.
The first method to consider is to only perform calculations for the objects that are currently on screen. If you really need to do calculations for off-screen objects, you’ll perform them less frequently than those for on-screen objects.
The next logical step is to attempt to determine which objects are near, and then to calculate the collisions only for those. This can be done using a zoning method. A simple approach is to break a large area down into successively smaller pieces and only check the portions that are important, refining your collision-detection algorithm and decreasing the area you’re testing as you go along. This is a very common approach in complicated games like Doom or Quake. However, if most of your objects are fixed on the screen and have the same size, you can calculate the collisions using tiled game fields (this is sometimes called zoning). This is very common with 2-D games (more about this in later chapters). In this situation, if you have many objects but need to test only one against all others (such as a bullet that may hit enemies or obstacles), you can simply divide the screen in zones and test for special collisions in a particular zone only.
We’ll discuss each of these approaches in the following sections.
Tiled Game Field The tiled game field approach is the zone method taken to the limit; there’s only one object per area in the zone, and you use a two-dimensional array where each position on the array refers to a tile on the screen. When moving objects, all you have to do is to check the array in the given position to know if there’ll be a collision. In this chapter, you do a simple variation of this method, using a bit array where each bit maps to a tile on the screen. This approach is possible because you only want to store one piece of information—whether the tile is empty or not. If you need to store any extra data about the object (for example, an identifier about the object type), you have to create an integer array to store numbers, and create a mapping table in which each number represents a specific type of object (as you do in the next chapter). Figure 1-16 shows a tiled game where each screen object is held in an array.
Figure 1-16. In a tiled game field, you have an array that maps to screen objects.
Zoning with Bits If you have a game with many objects but infrequent collisions, you can minimize the number of calculations dividing your screen in zones, and only calculate collisions for objects that are on the same zone. Zones are generally set up according to the number of “collision areas” you want to check, so they’re generally independent of a screen’s resolution. To divide a game field in zones, you create an array to store information about each zone’s y and x axis. So, if you divide your screen into 64 zones (8×8), you need one array with 8 elements to store information about the y axis of each zone, and another array with 8 elements to store information about the x axis of each zone. Figure 1-17 shows an example of such zoning.
If all you want to know is whether a certain zone contains an object (disregarding which one), you can use bytes (instead of arrays) to store the zone information, where each bit will represent a zone on screen; this is called zoning with bits. You can divide your screen in zones according to the number of bits on each variable used: 64 (8×8) zones with a byte, 256 (16×16) zones in an int16, 1024 (32×32) zones in an int32, and so on.
Using the zoning with bits method, at each game loop you reset the variables and, for each object, you process any movement. You then calculate the zone of each object (multiply the current position of the object by the number of zones on each axis and divide by the width or height of the screen), and set the bit corresponding to the result at the x-axis variable and at the y-axis variable, accordingly. You have to set a second bit if the sum of the position and the size of the object (width for x axis, height for y axis) lies in another zone.
Figure 1-17. Dividing a screen into 64 zones
If when checking the variables you see that the bit in both variables is already set, then there’s an object in your zone, so you check all the objects to find out which one it is. Using this method, if you have 15 objects on the screen, and only one collision, you have to do only one check against a given number of objects (14 in the worst case of this scenario), instead of 15 tests with 14 objects. This method has some drawbacks:
- You don’t know which object set the bit, so you have to test all the objects looking for the collision.
- Some “ghost objects” are created when crossing the bit set for the x zone by one object with the bit set for the y zone by another object, as depicted by Figure 1-18.
Figure 1-18. Using zone bits, if you have big objects (lilke the bricks), there'll be lots of "ghost objects."
This method is most useful when you want to test a group of objects against other objects (for example, bullets against enemies on screen); if you need to test all the objects against each of the others, you’d better use zoning with arrays of bits, as described in the next section.
Zoning with Arrays of Bits If you have a limited number of objects on screen, you can use two arrays, instead of variables, to define your zones. Each object will correspond to a specific bit in the array elements, so you use byte arrays to control 8 objects, int16 arrays to control 16 objects, and so on, and create a mapping table linking each bit with a specific object. The size of each array will define the number of pixels in a zone for each dimension. For example, creating two arrays each with 10 positions in a 640×480 resolution, you’ll have zones measuring 64 pixels wide by 48 pixels high.
You use the same idea as the previous method to define the zone (or zones) in which each object may be, and then check to see if both x and y array elements aren’t empty. If they aren’t zero, and the bits set in both arrays are the same, then you know for sure that there’s another object near you (not a ghost object), and only check for collision with the one that corresponds to the bit set. An example of this is shown in Figure 1-19.
Figure 1-19. Using zone arrays, you can keep track of which objects are in each zone. The legend shows the bit set in each array element for each object.
 This chapter is from Beginning .NET Game Programming in C#, by David Weller, et al., (Apress, 2004, ISBN: 1590593197). Check it out at your favorite bookstore today.
Buy this book now. |
Next: Extending the Algorithms to Add a Third Dimension >>
More .NET Articles
More By Apress Publishing
/ 8 
