Jump to content
Sign in to follow this  
  • entries
    298
  • comments
    1135
  • views
    232383

(No applicable title)

Sign in to follow this  
HopeDagger

100 views

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=Template
FrameWidth=32
FrameHeight=32
Rows=4
Columns=8
Type=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!)

Sign in to follow this  


11 Comments


Recommended Comments

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].

Share this comment


Link to comment
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]

Share this comment


Link to comment
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.)

Share this comment


Link to comment
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.

Share this comment


Link to comment
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)?

Share this comment


Link to comment
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);
}
}

Share this comment


Link to comment
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.

Share this comment


Link to comment
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!

Share this comment


Link to comment
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].

Share this comment


Link to comment
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!

Share this comment


Link to comment
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.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!