(No applicable title)

posted in Gauntlets of Recursion (+3)

Published August 04, 2006

Keep the Progress Alive!

More movement forward made today. Not massive strides, but taking one step at a time on a daily basis definitely adds up quickly. Being used to RAD development with languages like Delphi and C#, C++ development feels much slower, but simultaneously has a more gratifying feeling associated with it. Weird. I'll have to get used to it. [smile]

Collisions

The basic collision system is in, supporting two levels of precision. The first checks the Manhattan distance between the sprites, skipping any further levels if the check yields a distance greater than the combined sizes of the sprites. The next level is a bounding box check, which is currently as deep/precise as it goes. I intend to add pixel-based detection later on if it's needed, but it may not be needed.

Right now the detection-checking algorithm is VERY inefficient. It simply checks each sprite against all others, so for 250 sprites that's C(250,2), which is something like 31,000 collision checks. Eee! Someone -- sooner rather than later -- I'll develop a sector/segment system that will allow sprites to only check for collisions against other potentially relevant sprites, instead of the whole batch.

Sprite Types (or Templates)

I've always wanted a nice flexible system for all of the various entities, sprites, and actors in my games. I loathe all of the hardcoding I've had to do for Skirmish Online when defining the various types of sprites (Players, Bullets, Particles, etc). Now I scribble up a text file like so:

[Mr. Rogers]Image=TemplateFrameWidth=32FrameHeight=32Rows=4Columns=8Type=PLAYER

Bam. This INI-esque format lets me define fields relatively on-the-go, so I can throw in cool stuff like particle types for the particle engine, with fields like R/G/B, alpha, blend-mode, velocity, and other goodies. All without recompiling! [smile]

(Oh, and I threw in an FPS counter for fun. Don't mind the unoptimized framerate!)

Previous Entry Do you have me on your RSS feed?

Next Entry Untitled

0 likes 11 comments

Comments

Programmer16

lol, I don't think your 250 sprite collision detection is going to be much of a bottleneck. My pathfinding is currently checking every sprite and even with 500 entities it doesn't drop below 350 frames.

I only have one thing to complain about and that is the fact that you use single-letter variable names[headshake].

August 04, 2006 11:03 PM

HopeDagger

Quote:Original post by Programmer16
lol, I don't think your 250 sprite collision detection is going to be much of a bottleneck. My pathfinding is currently checking every sprite and even with 500 entities it doesn't drop below 350 frames.

What do you use to store the lists of sprites? I'm using a std::vector<> and the 31K iterations is killing the framerate.

Quote:I only have one thing to complain about and that is the fact that you use single-letter variable names[headshake].

Temporary (short-scope) variables get shorter names. Loop counters are traditionally single-characters, and the Sprite* 'S' only exists within that loop. No reason to introduce long names to something that is only required for under 10 lines. [smile]

August 05, 2006 07:51 AM

Programmer16

By my calculations, it should actually be like 62500 iterations.

Well, part of your problem is that you're checking every sprite against every other sprite. Your sprites can only move so far, they're not moving constantly (possible, but not likely), and they can only move in 1 (or possible 2 directions if you allow diagonal.)

So, instead of checking each one against the other, this is how I would have it set up:


enum DIRECTION
{
    WEST = 0,
    NORTH,
    EAST,
    SOUTH,
/*  NORTHWEST,
    NORTHEAST,
    SOUTHEAST,
    SOUTHWEST,*/
    DIR_COUNT,
};

void GetNeighbor(int& nColumn, int& nRow, int nDirection)
{
    switch(nDirection)
    {
    case NORTH:
        {
            --nRow;
            break;
        }

    case EAST:
        {
            ++nColumn;
            break;
        }

    case SOUTH:
        {
            ++nRow;
            break;
        }

    case WEST:
        {
            --nColumn;
            break;
        }
    }
}

void Entity::Move(int nDirection)
{
    int nColumn = m_nColumn;
    int nRow = m_nRow;

    GetNeighbor(nColumn, nRow, nDirection);

    for(Each Each Entity In Your List)
    {
            if(nColumn,nRow is off the map/screen)
                continue;

            if(Entity Is At nColumn,nRow)
                continue;

            // check stuff here
    }
}

Or something really close to that. You could also do a pixel-based detection instead of a column,row based.

HTH!

(Btw, I suggest the direction/GetNeighbor system to everybody. I can take my 8 directional pathfinding and use it with my 4 directional game by only modifying 1 line (how many directions there are.)

August 05, 2006 03:16 PM

HopeDagger

Quote:Original post by Programmer16
By my calculations, it should actually be like 62500 iterations.

I'm getting 31,125. 250! / (2! * 248!), right? Either way, it's a big number. [smile]

Quote:Well, part of your problem is that you're checking every sprite against every other sprite. Your sprites can only move so far, they're not moving constantly (possible, but not likely), and they can only move in 1 (or possible 2 directions if you allow diagonal.)

So, instead of checking each one against the other, this is how I would have it set up:
*** Source Snippet Removed ***

You're still having every sprite loop through every other sprite per movement, which is already what I'm doing. It's the iterating itself that's killing performance, not the collisions checks therein.

August 05, 2006 03:48 PM

Programmer16

Quote:Original post by HopeDagger
Quote:Original post by Programmer16
By my calculations, it should actually be like 62500 iterations.

I'm getting 31,125. 250! / (2! * 248!), right? Either way, it's a big number. [smile]

Quote:Well, part of your problem is that you're checking every sprite against every other sprite. Your sprites can only move so far, they're not moving constantly (possible, but not likely), and they can only move in 1 (or possible 2 directions if you allow diagonal.)

So, instead of checking each one against the other, this is how I would have it set up:
*** Source Snippet Removed ***

You're still having every sprite loop through every other sprite per movement, which is already what I'm doing. It's the iterating itself that's killing performance, not the collisions checks therein.

It should be just 250*250, because unless you iterate some special way, the outer loop's itor will match the inner loops itor at one point (meaning that no entities are excluded from iteration.)

I don't understand why it's killing your performance then, because my code is almost exactly like the code I posted, and I have 500 entities. Are you positive that it's not the collision check?

Are you using continue to skip back to the beginning of the loop (skipping other checks, code, and such)?

August 05, 2006 04:25 PM

HopeDagger

Quote:Original post by Programmer16
It should be just 250*250, because unless you iterate some special way, the outer loop's itor will match the inner loops itor at one point (meaning that no entities are excluded from iteration.)

Take 4 unique sprites for example. There are 6 combinations of 2 colliding sprites, via: 4! / (2! * 2!) which is 6. If you just did 4*4 you'd get 16, which is way more iterations than is necessary.

Quote:I don't understand why it's killing your performance then, because my code is almost exactly like the code I posted, and I have 500 entities. Are you positive that it's not the collision check?

Positive. I even took out the collision-check code and just left in the iterations, with the same result. I'm using:


	// Go through all sprites, checking for collisions against all sprites AFTER them in the list
	for(vector<Sprite*>::iterator S=spriteList.begin(); S != spriteList.end(); S++)
	{		
		vector<Sprite*>::iterator it;
		for(it=S+1; it != spriteList.end(); it++)
		{
			//TestCollisions(*S, *it);
		}		
	}

August 05, 2006 06:19 PM

Programmer16

Ok, that's why I was confused with the math, I wasn't thinking about offsetting the inner-loop's iterator.

Anyway, back to my original post, why are you checking ALL of your sprites? Only the ones that are moving should need to be checked.

It seems that you're thinking along the lines of a "constantly check for collision" whereas I'm thinking "check for collision while moving." Meaning, that if SpriteA doesn't move, you don't need to see if he collides with SpriteB, but if SpriteB moves, you need to see if he collides with SpriteA.

If that doesn't help any then I am completely stumped.

August 05, 2006 07:50 PM

HopeDagger

Quote:Original post by Programmer16
Anyway, back to my original post, why are you checking ALL of your sprites? Only the ones that are moving should need to be checked.

It seems that you're thinking along the lines of a "constantly check for collision" whereas I'm thinking "check for collision while moving." Meaning, that if SpriteA doesn't move, you don't need to see if he collides with SpriteB, but if SpriteB moves, you need to see if he collides with SpriteA.

Oh, I know. I have several optimizations planned. I never really said that I was at a loss for improving performance, merely that right now it's far from ideal, hehe. [smile]

Thanks for your suggestions/ideas, though!

August 05, 2006 10:54 PM

Programmer16

Quote:Original post by HopeDagger
Quote:Original post by Programmer16
Anyway, back to my original post, why are you checking ALL of your sprites? Only the ones that are moving should need to be checked.

It seems that you're thinking along the lines of a "constantly check for collision" whereas I'm thinking "check for collision while moving." Meaning, that if SpriteA doesn't move, you don't need to see if he collides with SpriteB, but if SpriteB moves, you need to see if he collides with SpriteA.

Oh, I know. I have several optimizations planned. I never really said that I was at a loss for improving performance, merely that right now it's far from ideal, hehe. [smile]

Thanks for your suggestions/ideas, though!

Ah, I see[smile].

I did however, forget to mention your use post-increment. While not an incredibly bad thing, or even a giant bottleneck, during several/tens of thousands of iterations, the copy operation that it requires might be something to think about. I rarely ever use it over the pre-increment (I'm not sure that's the right word, but I just woke up and that's all I can think of.)

Anyway, IMHO, the only time the post-increment operator should be used when you'll need a copy of the information cached and returned beforing incrementing (e.g. assigning an ID to someone via the equals operator. m_nID = CurrentID++)

If, I'm just pointing out the obvious, you can go ahead and slap. Just figured I'd mention it[smile].

August 06, 2006 01:38 AM

HopeDagger

Quote:Original post by Programmer16
I did however, forget to mention your use post-increment. While not an incredibly bad thing, or even a giant bottleneck, during several/tens of thousands of iterations, the copy operation that it requires might be something to think about. I rarely ever use it over the pre-increment (I'm not sure that's the right word, but I just woke up and that's all I can think of.)

Anyway, IMHO, the only time the post-increment operator should be used when you'll need a copy of the information cached and returned beforing incrementing (e.g. assigning an ID to someone via the equals operator. m_nID = CurrentID++)

If, I'm just pointing out the obvious, you can go ahead and slap. Just figured I'd mention it[smile].

Is there really a speed difference between the two? I wasn't aware of that. I'll see if it helps at all. Thanks!

August 06, 2006 07:59 AM

Programmer16

I don't really think it would be a problem, I just thought maybe it was worth mentioning. According to others, it wasn't lol.

August 06, 2006 08:35 AM

You must log in to join the conversation.

Don't have a GameDev.net account? Sign up!

HopeDagger

Author

(No applicable title)

Comments

HopeDagger

Latest Entries

Flickdown?

Gundown Progress.

Apple-flavoured brain dump.

Becoming a game. Gradually.

Engine Status: Ready to rip.

Further immersion into the world of iPhone develop

Engine machen.

Whisked away into the world of Mac.

An impassioned return to gamedev!

Electromagnetic Adventures

(No applicable title)

Comments

HopeDagger

Latest Entries

Flickdown?

Gundown Progress.

Apple-flavoured brain dump.

Becoming a game. Gradually.

Engine Status: Ready to rip.

Further immersion into the world of iPhone develop

Engine machen.

Whisked away into the world of Mac.

An impassioned return to gamedev!

Electromagnetic Adventures

Reticulating splines