Wanting an engine to work with~

[tldr]

Even with 2000+ particles, the naive one-to-many circle vs circle collision step of my sim was only 2% of my frame time.  Applying the 6000 transformation matrices and drawing those 2000 particles, on the other hand, is some 20% of the frame.

Never optimize before profiling.

[Mjonir]

Quadtrees are great for collision detection. They are extremely efficient (O(log n), but don't quote me on this), and are much better than a) per-pixel and b) a lot of bounding boxes. The Wikipedia article has a pretty diagram on how it would work. Since collision detection should be the main overhead of the engine, you should experience quite good performance when using a quadtree-based approach.

I thought a bit about quadtrees a while ago. In the specific case of danmakus, I think a real quadtree would take too much time putting every bullet in the right box because we have a lot of objects moving quickly. Moreover most of the time we're not interested in bullet vs bullet collisions but one isolated object vs a lot of grouped objects. It'd be a waste of time to optimize the collision between all those bullet. It'd also be a waste to create and delete boxes over and over in the tree. A better solution would be a quad-tree, but with a fixed size, so that the sorting phase of the quad tree is faster, but it still improves things a lot. The actual depth of the tree I have no idea though, you'd have to experiment and see. I think something around a depth of 8 looks good to me, but I've no idea really.

Even with 2000+ particles, the naive one-to-many circle vs circle collision step of my sim was only 2% of my frame time.  Applying the 6000 transformation matrices and drawing those 2000 particles, on the other hand, is some 20% of the frame.

Never optimize before profiling.

I agree, and pretty much everything I said is purely theoretical, I haven't tested anything performance-wise yet because I'm way too busy implementing features first.

However, I think that even if you should not optimize before profiling, you should prepare the job a little when it's possible. Knowing in advance where you could optimize and make it easier when you'll have to do it, because if you've got to rewrite half of your code to optimize something, that's really poor design and it could have been easily avoided with no added work.

[anonl]

Even with 2000+ particles, the naive one-to-many circle vs circle collision step of my sim was only 2% of my frame time.  Applying the 6000 transformation matrices and drawing those 2000 particles, on the other hand, is some 20% of the frame.

How is that measured? For collision detection you want peak time per frame, not an average.

Space subdivision isn't critical, as long as you divide objects into collision groups. 200 player shots vs. 100 enemies (200x100) is a lot faster than (200+100)². I wanted to allow player shot vs. enemy shot collisions (200x2000) which gets slow fast, so I further subdivide into a uniform grid.

[tldr]

gprof, which is free, as long as you can compile with a descendant of gcc.  It's a sampling profiler, so yes I'm working off of average, not single frame traces for peak time.  But, I'm using a test script that is designed to stress the system 100% of the time, so it's not like the long-term average time is being artificially deflated by trivial frames.

If you're using C# you might be able to use PIX, but I've never used that on Windows / C# so YMMV.  Not sure if there are any other analogous free profiling tools for C# worth using.

If you are doing a lot of collisions (like bullet-bullet collision instead of just bullet-object collision) it may be worth spending time trying to squeeze performance out of it.  But that's why you profile first.  Profiling my sim told me to look at overhead, so as an exercise I did and in about 2 hours last night I was able to improve performance 20% by putting in some simple caching, switch from double to float on GL calls, switch from list<>  to vector<>, etc.  Now runs at 55 frames during the stress test.

[rfw]

I thought a bit about quadtrees a while ago. In the specific case of danmakus, I think a real quadtree would take too much time putting every bullet in the right box because we have a lot of objects moving quickly. Moreover most of the time we're not interested in bullet vs bullet collisions but one isolated object vs a lot of grouped objects. It'd be a waste of time to optimize the collision between all those bullet. It'd also be a waste to create and delete boxes over and over in the tree. A better solution would be a quad-tree, but with a fixed size, so that the sorting phase of the quad tree is faster, but it still improves things a lot. The actual depth of the tree I have no idea though, you'd have to experiment and see. I think something around a depth of 8 looks good to me, but I've no idea really.

I agree, and pretty much everything I said is purely theoretical, I haven't tested anything performance-wise yet because I'm way too busy implementing features first.

However, I think that even if you should not optimize before profiling, you should prepare the job a little when it's possible. Knowing in advance where you could optimize and make it easier when you'll have to do it, because if you've got to rewrite half of your code to optimize something, that's really poor design and it could have been easily avoided with no added work.

In theory, I'd say with the quadtree approach, you could use it as a replacement for a bounding box -- i.e. you have the root node of the quadtree which specifies origin coordinates, then that's free to move around as it wishes and if the player's root node intersects with the bullets, you perform further collision checking. I suppose you could memoize for different bullet types so you don't have to algorithmically regenerate a quadtree over and over again, or even compile bullet images to a quadtree and have the engine load that.

Also, why not have bullets collide with each other (optionally, e.g. adding BULLET to a Bullet's collision mask attribute)? Sounds like an interesting danmaku experience to me :derp:

gprof, which is free, as long as you can compile with a descendant of gcc.  It's a sampling profiler, so yes I'm working off of average, not single frame traces for peak time.  But, I'm using a test script that is designed to stress the system 100% of the time, so it's not like the long-term average time is being artificially deflated by trivial frames.

If you're using C# you might be able to use PIX, but I've never used that on Windows / C# so YMMV.  Not sure if there are any other analogous free profiling tools for C# worth using.

If you are doing a lot of collisions (like bullet-bullet collision instead of just bullet-object collision) it may be worth spending time trying to squeeze performance out of it.  But that's why you profile first.  Profiling my sim told me to look at overhead, so as an exercise I did and in about 2 hours last night I was able to improve performance 20% by putting in some simple caching, switch from double to float on GL calls, switch from list<>  to vector<>, etc.  Now runs at 55 frames during the stress test.

Isn't PIX an Xbox profiler? IIRC VS2010 comes with a built-in profiler, which I've used with my (non-danmaku) engine (though it was practically useless due to the huge amount of IronPython-C# interoperability I have). I'm not sure if the Express editions have one, though.

Also, I propose Wriggle renames the topic to A Theoretical Discussion on the Implementation of Danmaku Engines :3

[Mjonir]

In theory, I'd say with the quadtree approach, you could use it as a replacement for a bounding box -- i.e. you have the root node of the quadtree which specifies origin coordinates, then that's free to move around as it wishes and if the player's root node intersects with the bullets, you perform further collision checking. I suppose you could memoize for different bullet types so you don't have to algorithmically regenerate a quadtree over and over again, or even compile bullet images to a quadtree and have the engine load that.

Hmm, I read a few time but didn't understand. Could you develop a little, preferably with an example? Sorry ^^'

Also, why not have bullets collide with each other (optionally, e.g. adding BULLET to a Bullet's collision mask attribute)? Sounds like an interesting danmaku experience to me :derp:

My Danmagine can do that already :p

It's an option people are not likely to use very often, but objects can go into multiple collision layers. Actually, making player bullet and enemy bullet collide is the same thing as making enemies kill the player when touched (collision-wise). You could also do enemy bullet vs enemy bullet collisions easily by a similar mechanism (which already exists too)

My engine might still look ugly (because I didn't have time to do a nice demo), but it's becoming quite powerful under that ()

[rfw]

Hmm, I read a few time but didn't understand. Could you develop a little, preferably with an example? Sorry ^^'

My Danmagine can do that already :p

It's an option people are not likely to use very often, but objects can go into multiple collision layers. Actually, making player bullet and enemy bullet collide is the same thing as making enemies kill the player when touched (collision-wise). You could also do enemy bullet vs enemy bullet collisions easily by a similar mechanism (which already exists too)

My engine might still look ugly (because I didn't have time to do a nice demo), but it's becoming quite powerful under that ()

Here's a crappy diagram (image only ~60KB, and I think it's fine to include inline -- link it if you don't think so, mods):



I'm going to whip up a prototype of the algorithm in Python and check how well it performs against per-pixel and straight, full viewport quadtrees.

An alternative is to use convex hulls only and use SAT.

[WriggleNightbug]

Well today I was able to make quite a bit, and I finnaly figured out how to draw many objects and danmaku patterns, I even made a playable character with focus movement and all that stuff, but one problem I have is that I cant get these different class instances to interact much, since their all defined in the main class, the game.

the player cant use the playershoot classes' ShootBullet method that makes them active for example, because when  I try to use the main classes bullet array it tells me that an array or method of that name doesnt exist, and global stuff doesnt seem to work on anything in XNA, so yeah, new problem to fix XD getting global variables and arrays so that Player and Boss classes can use the Bullet and Bomb classes to shoot and use them.

[Mjonir]

Here's a crappy diagram (image only ~60KB, and I think it's fine to include inline -- link it if you don't think so, mods):



I'm going to whip up a prototype of the algorithm in Python and check how well it performs against per-pixel and straight, full viewport quadtrees.

An alternative is to use convex hulls only and use SAT.

Wow, I see now, what you did there is quite original!

But what about circles then? Circular-ish shapes are used very often in danmakus, and they are very cheap to test. Wouldn't it be a waste to approximate a circle by AABB? You'd have to treat the circles as a special case, and from that it'd become so complicated that I have no idea how it would perform :p

However by going this way, you'd end up in only AABBs. I've read this a while ago, from what I remember it's basically a way to greatly speed up things when you've got only AABBs by putting all of that in an array, sorting it and then only testing neighbours.

With this you could potentially end up with a very fast collision detection. If you complete your algorithm and test it, please tell me the result, it's a really interesting technique

[rfw]

However by going this way, you'd end up in only AABBs. I've read this a while ago, from what I remember it's basically a way to greatly speed up things when you've got only AABBs by putting all of that in an array, sorting it and then only testing neighbours.

Essentially, it is that technique, but in quadtree form to optimize searching. Hopefully, it won't cost O(n?) in the worst case scenario, like the AABB array technique, but rather, by my half-assed guessing, O(n log n).

But what about circles then? Circular-ish shapes are used very often in danmakus, and they are very cheap to test. Wouldn't it be a waste to approximate a circle by AABB? You'd have to treat the circles as a special case, and from that it'd become so complicated that I have no idea how it would perform :p

Screw circles, they should learn to be squares like the rest of us :3

Well today I was able to make quite a bit, and I finnaly figured out how to draw many objects and danmaku patterns, I even made a playable character with focus movement and all that stuff, but one problem I have is that I cant get these different class instances to interact much, since their all defined in the main class, the game.

the player cant use the playershoot classes' ShootBullet method that makes them active for example, because when  I try to use the main classes bullet array it tells me that an array or method of that name doesnt exist, and global stuff doesnt seem to work on anything in XNA, so yeah, new problem to fix XD getting global variables and arrays so that Player and Boss classes can use the Bullet and Bomb classes to shoot and use them.

Would you mind showing me/us your code? I can review it for you and tell you what you should and shouldn't do (it's nice to have some sort of structure rather than just a hodge-podge of things all glued together with paste, and, the fact you're using globals makes me lean towards the latter).


Also, a moderator should split this thread so we stop intruding on Wriggle :V

[WriggleNightbug]

Essentially, it is that technique, but in quadtree form to optimize searching. Hopefully, it won't cost O(n?) in the worst case scenario, like the AABB array technique, but rather, by my half-assed guessing, O(n log n).

Screw circles, they should learn to be squares like the rest of us :3


Would you mind showing me/us your code? I can review it for you and tell you what you should and shouldn't do (it's nice to have some sort of structure rather than just a hodge-podge of things all glued together with paste, and, the fact you're using globals makes me lean towards the latter).


Also, a moderator should split this thread so we stop intruding on Wriggle :V

Well here's what my game looks like:

I have a main class that created for my by XNA, it does all the drawing and processes, it has the usual framework much similar to Danmakufu, I start by making some classes, like: Bullet, Player, Frame, etc. I create instances of these classes in the main game class:

Player GamePlayer;
Frame GameFrame;

and with bullets:

static int MaxBullets;
Bullet[] BulletArray = new Bullet[MaxBullets]

and then in initialize I do a for statement to really create them all, so basically every bullet has a variable I can call to in other methods, as their part of a big array, and I can draw and update all of them, the bullets have a method that looks kinda like this:

public void Shoot(Texture2D texture, float speed, float angle)
{
       Active = true;
       Speed = speed;
       etc...
}

That method makes the bullet active and gives it what it needs, but because the array used to access each instance is in the main class, classes like Player and Boss can't access it and thus can't create bullets...D=

[rfw]

Well here's what my game looks like:

I have a main class that created for my by XNA, it does all the drawing and processes, it has the usual framework much similar to Danmakufu, I start by making some classes, like: Bullet, Player, Frame, etc. I create instances of these classes in the main game class:

Player GamePlayer;
Frame GameFrame;

and with bullets:

static int MaxBullets;
Bullet[] BulletArray = new Bullet[MaxBullets]

and then in initialize I do a for statement to really create them all, so basically every bullet has a variable I can call to in other methods, as their part of a big array, and I can draw and update all of them, the bullets have a method that looks kinda like this:

public void Shoot(Texture2D texture, float speed, float angle)
{
       Active = true;
       Speed = speed;
       etc...
}

That method makes the bullet active and gives it what it needs, but because the array used to access each instance is in the main class, classes like Player and Boss can't access it and thus can't create bullets...D=

Easily solved -- give Player and Boss a property that can access the BulletArray field, e.g. when you initialize them, add a bulletArray parameter to the constructor so you can use this._bulletArray. As it's a reference, changing it from within Player makes the BulletArray field in the game class change too.

Alternatively, you can singletonize the Game class so it can be accessed from anywhere, or give Player and Boss an _game field so they can access the core game class.

[WriggleNightbug]

Easily solved -- give Player and Boss a property that can access the BulletArray field, e.g. when you initialize them, add a bulletArray parameter to the constructor so you can use this._bulletArray. As it's a reference, changing it from within Player makes the BulletArray field in the game class change too.

Alternatively, you can singletonize the Game class so it can be accessed from anywhere, or give Player and Boss an _game field so they can access the core game class.

So its possible to refference the class itself by singletonizing it? like Game.BulletArray[FindLowest]?

Speaking of which would my method FindLowest used to find the inactive bullet with the lowest ID be global too? how do I do that? this seems pretty useful.

[rfw]

So its possible to refference the class itself by singletonizing it? like Game.BulletArray[FindLowest]?

Speaking of which would my method FindLowest used to find the inactive bullet with the lowest ID be global too? how do I do that? this seems pretty useful.

You generally don't want to singletonize anything if you can avoid it, as singletons are globals in disguise and globals are bad. Also, you can implement FindLowest as a member function, so it would work like this.BulletArray[this.FindLowest()].

Never ever use globals.

[WriggleNightbug]

You generally don't want to singletonize anything if you can avoid it, as singletons are globals in disguise and globals are bad. Also, you can implement FindLowest as a member function, so it would work like this.BulletArray[this.FindLowest()].

Never ever use globals.

Hmmm...I tried referencing the main game class and using "this.", but I usualy get something along the lines of "that method doesn't exist" or "That doesnt belong here" I even made a variable in the constructor for Boss that represents the main class and then when I use "Main.BulletArray[FindLowest]" it tells me I cant use the array or the method because its protected, how do you create a member function?

[tldr]

Isn't PIX an Xbox profiler? IIRC VS2010 comes with a built-in profiler, which I've used with my (non-danmaku) engine (though it was practically useless due to the huge amount of IronPython-C# interoperability I have). I'm not sure if the Express editions have one, though.

PIX is indeed an xbox360 profiling tool, but from what I hear it's been generalized to work on Windows with C# through the XNA toolkit.  If you're working with C# it makes sense to look into what it can do for you.

As for C++ code, the VS2010 profiler only comes with a commercial-grade license which is at minimum $700, which is a little out of reach for hobbyist programming.  gprof on the other hand is Free, but requires an instrumented binary compiled by gcc/mingw with the -pg flag.  That said, writing gcc-compliant code is generally desirable.  Plus, mingw(gcc 4.5) binary version spanks msvc binary by at least 10% for my project.

[rfw]

Alright, here's an implementation of my unanchored quadtree collision detection theory:

http://pastebin.com/nusmwsZf

No benchmarks yet, so I have no idea about the performance.

Keep in mind this is a narrowphase algorithm, so you'll still need a broadphase algorithm, such as spatial hashing.

[WriggleNightbug]

Well today I had the clever idea of putting the PlayerBullet array in the Player's class and the Bullet arrays for each separate enemy depending on how many bullets they need, but then I realised that even though that works for drawing and shooting, it's gonna be tricky to make colissions... Such as bullets to hitbox, Bombs to bullets, etc.

So yeah I can't sneak my way out of this one, I need to learn better methods to make classes interact better.

[WriggleNightbug]

Well today I decided to try something new, if it was too risky to mess around with the main class that does all the game drawing and updating, that I would make a class called Manager, and get it do all the connecting between classes, whenever a class is made their given a variable that's used to call Manager's methods like FindLowest and such, it seems to work because now Player can tell bullets to use the method Shoot, unfortunately when I passed all the draw commands from Manager onto the main class nothing was drawn.

My guess is that when I made a variable in Manager that could call the main class, and used it to load a graphic withing Manager (which didn't bring up any errors) the graphic never really loaded, Either a silly mistake on my part or I may need to rethink this trough...

So a class that's used to with interact all the other classes, hold BulletArrays and hold the Player and Boss instances, good idea?

[WriggleNightbug]

Well today I decided to try something new, if it was too risky to mess around with the main class that does all the game drawing and updating, that I would make a class called Manager, and get it do all the connecting between classes, whenever a class is made their given a variable that's used to call Manager's methods like FindLowest and such, it seems to work because now Player can tell bullets to use the method Shoot, unfortunately when I passed all the draw commands from Manager onto the main class nothing was drawn.

My guess is that when I made a variable in Manager that could call the main class, and used it to load a graphic withing Manager (which didn't bring up any errors) the graphic never really loaded, Either a silly mistake on my part or I may need to rethink this trough...

So a class that's used to with interact all the other classes, hold BulletArrays and hold the Player and Boss instances, good idea?

Oh hey its because my BulletArray was set to a maximum of 0...Oops.

[Gc]

PIX is indeed an xbox360 profiling tool, but from what I hear it's been generalized to work on Windows with C# through the XNA toolkit.  If you're working with C# it makes sense to look into what it can do for you.

http://mynameismjp.wordpress.com/samples-tutorials-tools/pix-with-xna-tutorial/

Could have been posted sooner but...