Now, the smarter methods involve using quad-trees, arrays, graphs -- essentially any method to minimize the search path given a region.
Let's assume the following:
- Memory is cheap
- Small world
- Looks right preferred over perfection
Given that, let's work on the 2D problem (some games can be represented as 2D problems in a 3D environment -- for example, if the number of objects to collide on the y-axis is little, and the level spans quite a distance on the x & z axis). And, we'll use this example. Let us assume that we have access to a big array, about 1024x1024 which can be used to represent a view of the world from the top.
Each element of the array can be thought of as a pointer to a sprite object. All that we have to do is then "render" the level onto this bitmap of pointers. It'll tell us exactly what object is colliding with which other object. I'm currently using this in one of my games since some sprites have very odd/ever changing shapes. Also, this must not be a new/clever technique since other games have over-sized morphing objects.
But, here comes the interesting part: we have hardware to do rasterization. If we only had 4 objects, we could assign each object to a specific element (RGBA) and render the scene from above without the land/useless detail. Any time a pixel is shared between two objects, then it could be used to raise a red flag. The more clever may want to use the individual bits (but since everything is done in floating-point, I'm not sure how exact the colors 1,2,4,... are when normalized. Also, the other problem is that the bitmap has to be brought back to the host -- which uses quite a bit of bandwidth.
On the other hand, rasterizing on the CPU takes away time that would normally be used for AI/other game logic.
For those who want the most speed, they should read the articles on quad-trees, etc. in Game Programming Gems. These provide smarter/proven ways of doing collision detection than this little rant.
No comments:
Post a Comment