Hey.

I use this as my collision checking and it works but I guess in the long run it will be rather slow with hundreds of objects. I've searched the internet at times to improve this but I'll ask here too for opinions.

How would one improve such code, can someone give me some pointers/directions what I should be looking at to reduce the amount of iterations?

///////////////////////////////////
//// COLLISION
it->SetX(it->GetX() + it->GetVelX());

if(it->CheckMapCollision())
	it->isColliding = true;

float tx = ((it->GetX()) / (TILE_SIZE_W / 2.0f) + ((it->GetY()) / (TILE_SIZE_H / 2.0f))) / 2.0f;
float ty = ((it->GetY()) / (TILE_SIZE_H / 2.0f) - ((it->GetX()) / (TILE_SIZE_W / 2.0f))) / 2.0f;
int hx = tx * TILE_SIZE_H - it->GetColW() / 2;
int hy = ty * TILE_SIZE_H - it->GetColH() / 2;

for(std::vector<CProp>::iterator nit=Prop.begin();nit!=Prop.end();++nit)
{
	float ntx = ((nit->GetX()) / (TILE_SIZE_W / 2.0f) + ((nit->GetY()) / (TILE_SIZE_H / 2.0f))) / 2.0f;
	float nty = ((nit->GetY()) / (TILE_SIZE_H / 2.0f) - ((nit->GetX()) / (TILE_SIZE_W / 2.0f))) / 2.0f;
	int nhx = ntx * TILE_SIZE_H - nit->GetColW() / 2;
	int nhy = nty * TILE_SIZE_H - nit->GetColH() / 2;

	if(it->Collide(hx,hy,it->GetColW(),it->GetColH(),nhx,nhy,nit->GetColW(),nit->GetColH()))
	{
		it->isColliding = true;
	}
}

if(it->isColliding)
{
	it->SetX(it->GetX() - it->GetVelX());
}

it->SetVelX(0);

///////////////////////////////////
it->isColliding = false;
///////////////////////////////////

it->SetY(it->GetY() + it->GetVelY());

if(it->CheckMapCollision())
	it->isColliding = true;

tx = ((it->GetX()) / (TILE_SIZE_W / 2.0f) + ((it->GetY()) / (TILE_SIZE_H / 2.0f))) / 2.0f;
ty = ((it->GetY()) / (TILE_SIZE_H / 2.0f) - ((it->GetX()) / (TILE_SIZE_W / 2.0f))) / 2.0f;
hx = tx * TILE_SIZE_H - it->GetColW() / 2;
hy = ty * TILE_SIZE_H - it->GetColH() / 2;

for(std::vector<CProp>::iterator nit=Prop.begin();nit!=Prop.end();++nit)
{
	float ntx = ((nit->GetX()) / (TILE_SIZE_W / 2.0f) + ((nit->GetY()) / (TILE_SIZE_H / 2.0f))) / 2.0f;
	float nty = ((nit->GetY()) / (TILE_SIZE_H / 2.0f) - ((nit->GetX()) / (TILE_SIZE_W / 2.0f))) / 2.0f;
	int nhx = ntx * TILE_SIZE_H - nit->GetColW() / 2;
	int nhy = nty * TILE_SIZE_H - nit->GetColH() / 2;

	if(it->Collide(hx,hy,it->GetColW(),it->GetColH(),nhx,nhy,nit->GetColW(),nit->GetColH()))
	{
		it->isColliding = true;
	}
}

if(it->isColliding)
{
	it->SetY(it->GetY() - it->GetVelY());
}

it->SetVelY(0);
//// COLLISION
///////////////////////////////////

Cheers

There's probably no need to worry about it right now if there isn't a performance issue yet.

What you can do is to not check collision against every other object. Do some spatial partitioning and you can cut down the amount of objects to check against drastically.

Example: Divide world intro collision grid, only check against objects in same collision grid cell (and maybe the ones close in case of border crossing).

Rendering 101 objects and the world runs at about 5200 frames per second. Checking collision along with those 101 objects and world is about 5000 frames per second, though FPS doesn't tell much really but there's 200 FPS decrease with collision.

Thanks for the "spatial partitioning" term, didn't really know what I should be looking for. No idea though how to do that "divide world to collision grids" yet, though my world is cut into 32x32 tile chunks I might be able to implement it with that system. I guess my world collision check is pretty good since it only checks collision with nearby tiles. Gotta read some articles off the net on weekend on that how to do it with objects.

Thanks again

Checking collision along with that is about 5000 frames per second, though FPS doesn't tell much really but there's 200 FPS decrease with collision.

So you're saying that your frame time has gone down from under a millisecond to under a millisecond. Don't worry about it. Ignore FPS; what you need to measure is frame duration. And if it's under a millisecond it is not a problem.

This type of trivial collision detection with axis-aligned comparisons should scale to tens of thousands of objects before you start seeing a slow down. At that point, a coarse partitioning system will help you out.

This type of trivial collision detection with axis-aligned comparisons should scale to tens of thousands of objects before you start seeing a slow down. At that point, a coarse partitioning system will help you out.

The game will at maximum most likely have 500-1000 object collision checks.

So I guess I'll skip (for now) the collision improving (though I've figured out already a few improvements to save performance on some rare cases). I took a note though on the partitioning incase I run into performance issues. For some reason I've always been so fixated on FPS when programming games, so any decrease on FPS makes me always look for any improvement heh. Gotta look at frame duration in the future...

As others have noted, it doesn't look like there's currently any performance issue, so this should be fine.

There are several interesting techniques which involve doing a bit of extra work to organise your objects into some kind of order/structure which allows you to more efficiently perform this kind of collision query. There are lots of ways of doing this, ranging from complex structures to very simple ones (e.g. keeping a list of objects sorted by their X position and only checking the objects nearby in this list).

These techniques generally require a bit of work to maintain the structure as objects move around, and how effective they are depends on a lot of factors (like how many objects there are, how much they move, how clustered together they are, how many queries you will perform each frame etc). These factors may even make a particular technique slower than the basic approach in some cases. Often, a simple approach like what you have can be perfectly fine.

As others have noted, it doesn't look like there's currently any performance issue, so this should be fine.

Mind me asking what the down-vote was for? =)

EDIT: Explained via PM that it was a misclick. No worries!

Hmm now that I think of my fps independant code.. it might a bit poor so to say. I don't like to start a new topic so I hope I can put this here.. I've been using this to keep the game independant on framerate..

I tried checking collision on +2000 objects and my game dropped to 2 FPS from 5000 without any rendering...

I think this is the problem. I havent much changed this code in years:

EDIT: I have i7 4770k CPU (overclocked), that loop below for keep "framerate computing-wise" stable is probably killing my game's performance on multiple collision checks as the checks are done within the ComputeSprites();

void CGame::GameLoop()
{
    int mainControl, loopTicks;
    int oldTicks, delay;

    while(isRunning)
    {
        oldTicks = Core.GetTicks();

        TickTiming();

        Core.CheckSystemEvents(isRunning);

        loopTicks = TickTime-TickTimeLast;
        for(mainControl=0;mainControl<loopTicks;++mainControl) // frame independant code
        {
            Ticks += 1;
            mainTickCounter += 1;

            CheckKeyPressed();

            Core.GetMouse(mx,my);

            Core.ClearBuffer();

            UpdateCamera();

            ComputeSprites();

            Core.key_mouse1_doubleclick = false;
        }

        RenderFrame(); //RenderFrameS

        //delay = (1000/MAX_FPS)-(Core.GetTicks()-oldTicks);
        //if(delay > 0)
        //    Core.Delay(delay);
    }
}

What's the question? If you're saying that "actually, my code is too slow to run on 2000 objects" then that's fair enough - ways to consider optimising your initial code include

• only perform the 2 separate axis checks when you know you have a collision (i.e. set X and Y, see if it collides, and if so, reset and try along each axis separately)
• make sure your GetX, GetY, and Collide functions are all inlineable
• sort props by their rightmost X extent - you can then quit out of the loop as soon as the current prop's rightmost extent is less than it's leftmost extent as you know none of the others will be relevant (this is essentially part of the Sweep and Prune algorithm)
• break out of the loop as soon as you set isColliding to true - you already know you hit something, so no need to check all the others

If the question is about the structure of your main loop, then you've left out most of the important information (such as what all those functions do).

I tried checking collision on +2000 objects and my game dropped to 2 FPS from 5000 without any rendering... I think this is the problem.

In addition to what Kylotan said...

1) Will your game have close to 2000 objects, or did you just try a high number to see? In your initial post you mentioned "hundreds". Every game can be slowed down to a crawl if you tell it to do too much. If the game is too slow at 2000+ objects, and fine at 200, that's fine if all you need is 200.

2) Don't guess where the problem is. Use a profiler (google if you aren't familiar), and know. Profiling will also allow you to measure and verify that changes you make actually help.