Game engine design

[rorozero]

Hi, I just started getting into game programming (read through the lazy foo's tutorial up to multithreading) and I'm a little stumped.

I'm trying to make a basic 2d game engine (a platformer). I've already got most of it done, but I think I did the collision in a pretty crappy way.

First though, here's the basic template i use for all the objects in the game

class obj{
public:
double x, y; //x and y co-ordinates
SDL_Rect colbox; //collision box
float frame, imgspeed; //current animation frame and speed which it cycles through images

Sprite* CurrentS; //current sprite

obj(int a=0, int b=0, float spd=.01); //constructor
virtual void Step(); //What the object does each frame
virtual void Input(); //How the object handles input
};

Right now I just have two objects derived from this, Guy(The player) and a box he can stand on
The way I handle collision is I store each object in a vector (vector <*obj>) of its type. So I would store each Guy object in a vector called GuyList and each block in a vector called BlockList.
For the Guy object, it checks each frame if there is a block underneath it.
I used the follow code for collisions:

obj* CollP(int xx, int yy, vector<obj*> vec){

for(unsigned int i=0; i<vec.size(); i++){
//Check the contents of the entire vector for a collision (every instance of a particular object)

int leftR, rightR, topR, bottomR;
bool hcol=0, vcol=0;
SDL_Rect R;

R=(*vec[i]).colbox;
leftR= R.x;
topR= R.y;
rightR= R.x+R.w;
bottomR= R.y+R.h;

if(((xx<=rightR)&&(xx>=leftR))){hcol=1;}
//check for a horizontal collision
else{hcol=0;}

if(((yy>=topR)&&(yy<=bottomR))){vcol=1;}
//check for a vertical collision
else{vcol=0;}

if((vcol==1)&&(hcol==1)){
//if there is both a horizontal and vertical collision
return (vec[i]);
}
}
}

Basically the function checks each instance of a particular object to see if its collision box occupies a certain point. (for example, if I wanted to see if any Blocks occupied the spot (10,10), I would pass 10 for the x and y values and BlockList as the obj* vector)

My question is basically this, is there someway I can check if there is a block object underneath the Guy object without checking the x and y values of every Block object?

One other thing, could anybody recommend a book about game engine design (or anything you might think could help me out)

[shacktar]

My question is basically this, is there someway I can check if there is a block object underneath the Guy object without checking the x and y values of every Block object?

If the blocks are static (in the sense that they don't move) then you could use a std::map which maps an (x,y) pair to a block.

//note: code is not optimized

#include <map> //for std::map
#include <utility> //for std::pair

typedef std::pair<double, double> xyPair; //in your code, you put x,y as doubles, but should they be ints?

std::map< xyPair, obj* > blockMap;

//populates the block map
void InitBlockMap()
{
     //add a block
     obj* aBlock = new obj;
     aBlock->x = 50.0;
     aBlock->y = 75.0;

     xyPair aPair(aBlock->x, aBlock->y);

     blockMap[aPair] = aBlock;

     //add another block
     obj* anotherBlock = new obj;
     anotherBlock->x = 120.0;
     anotherBlock->y = 17.0;

     xyPair anotherPair(anotherBlock->x, anotherBlock->y);

     blockMap[anotherPair] = anotherBlock;
}

//gets the block at (x,y) if possible
obj* GetBlockAt(double x, double y)
{
     xyPair checkPair(x, y);

     if( blockMap.find( checkPair ) != blockMap.end() )
     {
          return blockMap[checkPair];
     }
     else
     {
          return 0; //NULL
     }
}

[rorozero]

It seems like that would only work if the blocks were one pixel large and don't have a collision box. If each individual pixel the Guy object is able to stand on is stored in this map, the map could get very large. I'd imagine that searching a giant map for a particular pixel would take longer than my current method of looking at every Block object and comparing a point with its (32 by 32) collision box. Is there something I'm missing?

[Intrexa]

Maps are a type of data structure that are optimized for random access. Increasing the number of elements in a map does not increase the time it takes to find any particular element. If you made a hash that returns a key for a specific location, then you could check a map very quickly by seeing if a block is at that key.

If this is a side scroller, have the screen keep a list of every block that is on screen at once. Check it against that list. If having a list of onscreen blocks isn't feasible, you could make quadrants, every xxx pixels is a new quadrant, at the start of the level each block gets placed in the proper quadrant, you would only need to check the quadrant the player is in, and the surrounding quadrants.

[helios]

Maps are a type of data structure that are optimized for random access. Increasing the number of elements in a map does not increase the time it takes to find any particular element.

Yes, it does. Specifically, the time grows logarithmically.

I believe a k-d tree would be most efficient for this situation. k-d trees are designed to quickly search for points that are near (by some definition of "near") a given point in space.

[shacktar]

Pardon me, I misunderstood. I thought that you wanted to identify a block by a particular coordinate pair as opposed to getting a block and then doing collision detection with it.

To avoid linear searching through all the blocks, you will have to partition the level somehow.

For instance, you could partition the level into a grid of cells. Each cell would store a collection of blocks that are inside of it. You may have to cut blocks into 2 or 4 such that one block is not in multiple cells. Or, you could make the size of the cells align on the width of the largest block such that block-cutting doesn't occur. Now, in a given frame, you simply determine which cell(s) the player is in, get the blocks from those cells, and do collision detection on only those. You can imagine in a level with 10,000 blocks, if there are say on average 5 blocks/cell, then each frame you would be looking at only around 20 blocks (approx. assuming the player is intersecting with 4 cells).

Another method is to recursively subdivide the scene using a BSP tree or quad tree. This is essentially the dynamic version of the above method. Instead of having cells each with a set width/height, you have a tree of rectangles/squares of increasingly finer resolutions. With this method, you can stop the subdivision if there are no blocks in the current rectangle/square. So, let's say the sky takes up the top half of the level and let's say there are no blocks in the sky. Then, when you're recursively subdividing the scene in a quad tree, for example, you would notice there are no blocks, and the sky would then take up just two leaf nodes. This can add up to big savings in the size of the data structure. So, for this method, in a given frame, you would drill down the tree to determine which nodes intersect the player (remember the nodes are squares/rectangles of differing sizes) . Then, you would enumerate over the blocks in each node. Again, you may have to cut a block and place the pieces in one, two, or four quad tree nodes to avoid block duplication.

http://en.wikipedia.org/wiki/Binary_space_partitioning
http://en.wikipedia.org/wiki/Quadtree

EDIT: kind of ninja'd, but this did take a while to write

[rorozero]

thanks shacktar, I completely forgot about quad trees, that's exactly what I needed.