Message Board
| Message Board > C/C++ > Checking if an object collides with another |
| December 27, 2007, 20:02 | |
|
Htbaa
Perl 368 posts 
|
First of all: check worklog In my wonderful KrasEngine I maintain a list with all my objects. An object is the players ship, the enemies, bullets, explosions, or in other words, basically everything. KrasEngine will first execute the eventhandler() method from every object. In this method I can let an object respond to user input. After all objects have executed this method they will all execute the logics() method. This method allows me to move my objects, let them check if they get hit by another object (!), will handle animation and movement. Finally there is a rendering() method. For all objects this one is the same, but it can be overloaded if necessary. This method will paste their graphic to the screen at their own positions. So basically we have this: 1. Handle events 2. Handle logics 3. Display on screen 3 times a frame KrasEngine will iterate through the list of objects to perform the needed actions. This is all very fast. In the logics() method I can check if a bullet for example collides with an enemy. If written a function that checks if a object collides with the given object. In my bullet class I only want to check if it collides with an enemy. So therefore every class has an identifier. I've written a function that'll iterate through the list of objects which have the same identifier as specified. If it matches the pointer to the object is stored inside a list. Lets say there are 50 objects. 20 Objects are enemies. 20 Objects are bullets. The other 10 are just dummy data. They haven't got to do anything with the bullets or enemies, but will be checked when iterating through the list. If in every frame every bullet is checking for a collision with the objects identified as enemy it will request a list of objects that are specified as enemies. To get this list a function is called that will iterate through all the objects, returning only the pointers to the enemy objects. This function compares 50 objects, of which only 20 will match. This happens every frame, for every bullet. So we have 20 bullets calling this functions. That means 20 bullets * 50 objects = 1000 checkups. Every bullet object will get a list with 20 enemy objects. Which is good for 20 bullets * 20 enemies = 400 checkups. So in total, every frame has to do 1400 checkups. This could be reduced to 400 checkups, with the first checkup being 1400. But for that I'll have to cache the results. Which will be risky because the cache also has to reset as soon as an object gets killed. To reset this cache I'll have to bind an object to it's cache. I don't know how yet, but It should be doable. The main thing I'm concerned about it that when testing I get a couple of extreme frame drops. These started as soon as I added collision detection. Although they won't show up every time they do pop up. Is my method just not efficient enough or am I over reacting? I must say that I'm also putting stuff to STDOUT every frame, lots of stuff, maybe that could be a problem as well? Any thoughts? Just ran a quick test: 1000 enemies on screen and the framerate dropped to 30fps. Not too bad if you ask me. [Edited on December 27, 2007 by Htbaa] ____________ blog.htbaa.com |
| # | |
| December 27, 2007, 22:52 | |
|
Sandman
F3n!x0r 1194 posts 
|
I recommend keeping a list for every objecttype and keep it up to date, that will save you a lot of iterating. Much depends on how you are checking a single collision, as well. I don't have much experience with 3D collision detection, but if I imagine it correctly, like 2D, a box collision is fastest, by use of a matrix? You'll probably know that anyway. If you have a complex collision detection, perhaps you could do a preliminarily check first, like a box of outer-sphere collision detection. ____________ BennuWiki Yes, my avatar has grey borders in IE (so get a decent browser) ROOFLEZ ROOFLEZ |
| # | |
| December 28, 2007, 00:57 | |
|
Htbaa
Perl 368 posts
|
I'm using a simple box collision right now. I will add circular and pixel perfect collision later on. I will take a look on how to keep up different lists with different objecttypes that will also stay up to date. Because accessing pointers to objects that don't exist anymore isn't cool :-). ____________ blog.htbaa.com |
| # | |
| December 28, 2007, 22:59 | |
|
Htbaa
Perl 368 posts
|
I was wondering, if I declare a member of my base class static, the same member is used in subclasses. So for example, Code: class basecls { protected: static int a; }; int basecls::a = 10; class subclass : public basecls { public: int get_a(){return ++a;} }; subclass test = subclass(); std::cout << test.get_a() << std::endl; will result in 11. Which I understand, but basecls being the base class, shouldn't static int a be a new static member for subclass? I was thinking on letting every class have a static list of objects that are from the same class. But adding this to the baseclass will result in a list with all objects that use basecls as base class. Is there a way to use a static member in the baseclass, but make it new for every new type subclass? Else I'll have to add the same routines to my subclasses to update their static list with available objects of that class. Edit: Would it be possible for me to achieve this when my base class is pure virtual? Meaning I can't create objects of that type. It would mean that I'm forced to have every subclass at least 1 method (the pure virtual method from the base class) but I can live with that. Every game object does need to have logic() :-) Edit 2: Well, I tried out the pure virtual method. It doesn't have to be pure virtual. I just have to redeclare the static data member in my subclass. I don't really like the solution but I will try it tomorrow. Yesterday I ran a test with 1000 enemies all checking if they were colliding with the player (just for test purposes, it's of course more efficient to let the player check if he collides with an enemy). And the frame rate got very bad. So it's really something that I need to figure out. Or else I can not call it KrasEngine! [Edited on December 29, 2007 by Htbaa] ____________ blog.htbaa.com |
| # | |
| December 29, 2007, 13:22 | |
|
Sandman
F3n!x0r 1194 posts
|
Declaring the list in the subclass would indeed work and I'm unsure if it's possible using the baseclass. And if you make it virtual, it cannot have a variable, can it? Hm static yes hm, but then you'd have the same problem. Oh well, sublasses work. ;-)
____________ BennuWiki Yes, my avatar has grey borders in IE (so get a decent browser) ROOFLEZ ROOFLEZ |
| # | |
| December 29, 2007, 14:57 | |
|
Htbaa
Perl 368 posts
|
Hmmm. Too bad that it's not possible to automatically redeclare a static data member when another class inherits from the base class. I guess my engine should keep track of multiple lists then. Grr, this is going to get messy!
____________ blog.htbaa.com |
| # | |
| December 30, 2007, 00:50 | |
|
Htbaa
Perl 368 posts
|
Well, I think a map with lists is going to be the solution. Like this: Code: std::map<int, std::list<KEObject *> > objects; // Bullet type id objects[TYPE_BULLET] = std::list<basecls *>(0); This will also take a lot of extra stuff to look at, but I'll be able to do all the stuff in the base class. Next problem arising is that I'll be having different lists. But all objects need to be rendered in the right order. So, how are we going to sort multiple list and let them become one? I could say stuff them all together in 1 list and than do the sorting. But I can't think of that being very efficient as well. Although I'm sure it's better than having to iterate through a list to return objects of a specified kind for every object that needs to do collision detection. ____________ blog.htbaa.com |
| # | |
| December 30, 2007, 01:10 | |
|
Sandman
F3n!x0r 1194 posts
|
Yes, this is better. And for the order: have a list of objects based on priority and another one based on the "z" value of the objects. Like we are discussing in IRC now...oh well.
____________ BennuWiki Yes, my avatar has grey borders in IE (so get a decent browser) ROOFLEZ ROOFLEZ |
| # | |
Message Board > C/C++ > Checking if an object collides with another