Welcome, Guest. Please Login or Register.  • Help
SMF Underground
+ SHMUP-DEV » SHMUP DEV FORUMS » Assistance
|-+ Need help managing (hundreds of) objects simultaniously

Pages: [1]   Go Down
0 Members and 1 Guest are viewing this topic. Topic Tools  
Read February 08, 2011, 02:04:14 AM #0
Tukun

Need help managing (hundreds of) objects simultaniously

Suppose I wanted to make a bullet hell game, like a shoot-em-up.
If I wanted a hundred bullets or more in my screen at the same time, managing all of them individually would be a torturous task.
But I want them each to have individual behaviours.
What if I wanted to make a "standard" bullet, with its own texture and data to hold its own direction, coordinates, etc. that I can call upon any time.
What would be the most efficient way to manage this?

I also need to be able to make such a thing quickly. Say, anywhere between 30 to 400 bullets at any given frame. With the background completely functional and rendered a completely separate way. With its own textures and so on.


I'm trying to make two functions, but I just can't get a grip on how to do it so they properly treat the bullets.

The first function is bullet_create. This will be called only once, and within the parameters I want to put the XY coordinates, and the direction/speed.
The second function is render_all_bullets. This one should take no parameters, but should draw all of the bullets created by bullet_create. It should also be in my infinite loop, meaning it should be between my DirectDevice9::BeginScene and DirectDevice9::EndScene functions.

I have the textures, vertices, and physics down. But I don't know how to get render_all_bullets to draw all of the bullets created by the bullet_create function.
If I use a loop to create 5 (or however many) bullets at once, I should have no problem putting in nothing more than the xy/direction/speed parameters of the bullet_create() function.
But I can't figure out how to control them without putting in some sort of identfication to pass to render_all. Any advice how to deal with this puzzle?
I'm using DirectX9 SDK and msdn for reference. I'm coding this all in C++ with Visual Studio.

I know there are people here who made bullet hell shoot-em-ups. Some advice and tips would really help, and an example would probably be the best.
So far, the best thing I've made was a structure that holds all of my bullet's info. But again, I don't know how to pass this to render_all_bullets, which shouldn't take any parameters because, well, it'd be torture to indivitually type 50,000 bullets for one game session.
Offline  
Read February 08, 2011, 09:02:30 AM #1
Hornet600S

Re: Need help managing (hundreds of) objects simultaniously

Hi and welcome!
I am writing a tutorial that adresses your questions. Perhaps I get it done today.


"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Read February 08, 2011, 09:37:51 AM #2
motorherp

Re: Need help managing (hundreds of) objects simultaniously

Hiya Tukun, welcome to the forums.  

It sounds like what you need here is a bullet manager class.  I used to have a tutorial around here somewhere about bullet management but unfortunately it seems to have been buried in the recent forum re-structuring.  It might be worth searching for if you're interested but if I remember correctly that tutorial quickly got bogged down with details on how to go about maintaining correct render order which if I remember rightly never quite worked 100 percent anyway.  So anyway, I'll give you a quick overview on the kind of thing you'll need to write.

The objective will be to write a management class which provides the following benefits:

  • The manager should keep track of and take ownership of all bullets such that the user does not have to concern themselves with their memory management, lifetime, and common frame by frame tasks which should be automated.
  • It should be able to quickly and efficiently create new bullets and destroy existing bullets at any time and in any order.
  • It should be able to iterate through all added bullets quickly and efficiently to perform common tasks on each.

Depending on your needs you might need to add more features/constraints to the above list but this should at least get you started.

Therefore you'll need a class which contains some form of list of all created bullets so that it can iterate through them each frame to perform common tasks such as rendering.  Secondly you should be able to efficiently add new bullets to this list and also be able to efficiently remove bullets from any point in the list.  Lastly this list should be coded in such a way that it is quick to step through every bullet in that list.

The way I deal with this problem is to either use a fixed array of bullet structures, or if you dont want a hard cap to the total number of bullets you can have at any one time then I use an stl vector since these can be expanded (although be aware that causing the vector to expand will be slow and so you should aim to create a vector big enough to contain your maximum bullet count from the start).  You should have an Initialise function called once at the start of your level/game which creates the array and assigns its memory, and then a Shutdown function called once at the end of the level/game to free up the memory assigned for bullets.  For a fixed array this might look something like:

Code:
void BulletManager::Initialise(unsigned int maxBulletCount)
{
  m_bulletArray = new Bullet[maxBulletCount];
}

void BulletManager::Shutdown()
{
  delete []m_bulletArray;
}

Creating all your bullets and assigning their memory in advance like this has several advantages.  For a start memory operation are slow, so by doing it this way you get all your bullet memory operations out of the way during non critical phases of the game (during level load and shutdown rather than mid-play), so that during game-play you can add and remove bullets without needing to use any memory ops.  This makes bullet addition and removal quick which was one of our desired manager features in the list.

Secondly, creating all our bullets in a single array like this means that they are all placed next to each other in system memory (as opposed to creating memory for bullets as and when they are needed which would scatter their memory locations across the system).  This means that we can then iterate through all the bullets quickly since we will be making maximum use of the systems memory cache as opposed to jumping around all over the place in memory which would occur if we did seperate bullet memory allocations which would result in many cache miss stalls.  This satisfies the last point on our list of features.

Since you've created all your bullets up front you now just need to deal with which are active and which are currently available.  First of all you could add a 'bool' in your bullet structure to track its active status, therefore when you iterate through your bullet array to render them for example, you would only render if this bool was true.  When a bullet is created this bool is set to true and to destroy a bullet all you need to do is simply set this bool to false.

You'll also need a way to quickly find free bullets for when you wish to create a new bullet.  The way I usualy do this is to have a second array in the manager which stores the indexes of all free bullets.  When a new bullet is required, the last index on this list is popped off to get the next free bullet which is then set to active and initialised with the desired position and velocity.  When a bullet needs to be destroyed its active bool is set to false and its index is pushed back onto the free bullet index array.  For example this might look something like:

Code:
unsigned int BulletManager::AddBullet(const vec2& pos, const vec2& vel)
{
  if(numFreeBullets == 0)
  {
    return INVALID_BULLET_INDEX;
  }

  unsigned int bulletIndex = m_freeBulletIndexArray[--m_numFreeBullets];
  Bullet& newBullet = m_bulletArray[bulletIndex];
  newBullet.pos = pos;
  newBullet.vel = vel;
  newBullet.active = true;

  return bulletIndex;
}

void BulletManager::RemoveBullet(unsigned int bulletIndex)
{
  if(m_bulletArray[bulletIndex].active == true)
  {
    m_bulletArray[bulletIndex].active = false;
    m_freeBulletIndexArray[m_numFreeBullets++] = bulletIndex;
  }
}

Hope that helps



Edit: Damn you is quick on the keys Hornet600S hehe.  Looking forward to the tutorial.  There was another one around here once I wrote on this subject but I'm not sure its worth resurrecting, I seem to remember it got a bit off course and wasn't the best solution anyway.


« Last Edit: February 08, 2011, 09:40:18 AM by motorherp »

Offline  
Read February 08, 2011, 12:44:19 PM #3
Hornet600S

Re: Need help managing (hundreds of) objects simultaniously

@motorherp
 Smiley Yeah, I wondered why there was no tutorial already, I thought there was and wanted to point Tukun to it, was kind of surprised I didn't see one and thought I just was wrong. So it got lost during the site's reconstruction?

Anyway, I think that's one of those topics where a 2nd tutorial won't be too redundant, since there are so many ways to do it.
I'm mabye 70% done with writing, but somehow it becomes a bit hard-core... For example the algorithm I use to map IDs to bullets is very difficult to explain. Coders that are familiar with the concepts can certainly follow, but I also want newbies to understand it.
Not too easy Tongue

I hope it turns out okay. Continueing...


"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Read February 08, 2011, 01:40:31 PM #4
motorherp

Re: Need help managing (hundreds of) objects simultaniously

More tutorials are always a welcome addition, I'm looking forward to it.  Like you say, there's usually many different ways of tackling loads of issues so it'll be good to see someone elses persepctive.  In fact I'm currently using a slightly different method myself since I wasn't happy with the way the above method I posted disregards bullet creation order which results in messy rendering.  I've tried to solve that particular issue before which you can see in that tutorial I wrote which became buried but I was never really happy with that one.  Instead this time I've implemented a kind of vector / linked list hybrid storage method which allows iteration through the bullets in their creation order when needed whilst still dodging most cache misses.  It also still supports a faster creation order irrespective iteration for methods which aren't affected by creation order such as collision culling etc.  I've not throroughly put it through its paces yet though so only time will tell if it works as well as I hope it might.

PS: Yes the other tutorial I wrote got lost in the reconstruction.  Its still here somewhere, just buried.
« Last Edit: February 08, 2011, 01:46:28 PM by motorherp »

Offline  
Read February 09, 2011, 06:40:13 AM #5
Tukun

Re: Need help managing (hundreds of) objects simultaniously

Thank you very much for the insightful posts.
There are still many things I need to know, but this definitely helped.
I like the idea of not having a bullet cap, it sounds like stl vectors are probably my best bet. I haven't used them, though, so I don't know much about them. But I don't know if it will slow things down compared to a static array, and if so- how much.

Another thing that has been bothering me is the technical side of dealing with actually changing the values of positions and drawing it out. I'm still fairly new to DirectX as well, so I'm not sure what I should avoid as far as what eats up on my resources.

Right now I have an array of structures that stores all of my info for all of my bullets. That is, the textures, the xy/uv coordinates, vertices, blending info, all that stuff. allofmybullets[500], where the first index is my first bullet, etc... Basically what you explained earlier.
But I do know several things. Changing things within directX takes time. So all of my textures, vertices, all non-critical stuff need to be loaded before run-time actually starts, and I'm trying to avoid doing unnecessary things.
But I haven't a clue with how to deal with a part of that aspect. Changing the bullet's positions on the screen, for example. Should I load the vertex buffer once and use matrices to change the XY coordinates of each bullet on the screen? I heard that's cheap because it uses simple multiplication for that. Or should I update the vertex buffer multiple times every frame for each bullet? It sounds costly because I have to lock the buffer every time I do it. Funny thing is, even if I wanted to use matrices to deal with 2D bullets, I don't even know how to apply them. Using transformed vertices makes a problem that doesn't allow me to fix it with matrices, since they're already transformed, they don't go through the pipeline and allow me to manage them. But by going through the pipeline, I'm going to have to deal with going through all of the math that makes them appear in front of the screen, because I just put them into a 3D world and want them 2D.

Another thing that's been bothering me is, just as you said is organization and managment. I want to have as few commands to the device as possible. That is, all of the bullets with *these coordinates of *this texture- draw them, update blending properties and textures, draw all of the new bullets while skipping the ones you just drew.

This feels impossible to deal without some sort of chaos. I guess I know why they call it a bullet hell Cheesy.
Offline  
Read February 09, 2011, 08:21:09 AM #6
Hornet600S

Re: Need help managing (hundreds of) objects simultaniously

Hi guys, I completed that tutorial, hopefully without too many bugs and hopefully understandable...
Don't spare with criticism  Wink


"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Read February 09, 2011, 09:40:22 AM #7
VectorVanDoom

Re: Need help managing (hundreds of) objects simultaniously


Right now I have an array of structures that stores all of my info for all of my bullets. That is, the textures, the xy/uv coordinates, vertices, blending info, all that stuff. allofmybullets[500], where the first index is my first bullet, etc... Basically what you explained earlier.
that could provoke cache misses, its better to have the kind of data, which needs can be accessed at once for all bullets, consecutive in memory. e.g. updating the bullet positions requires x, y, speed and direction, to keep it simple, but not texture i guess. this pointer would get needlessly loaded into the cache when the nessecary data is accessed, because its part of that line of bytes in memory. in the same vein it can be a good idea to keep loops short, that are run a many times, and have more loops, eg. one for moving the bullet, one for collision check, on for drawing the sprite, run certain code, bcause thats loaded into cache too. one has to decide weather it makes actual sense, or its more efficient to reuse the x/y coordinates for all these procedures at once, but mess up the instruction cache. hope i didnt confuse anything or anyone for that matter.
Offline  
Read February 09, 2011, 10:40:18 AM #8
motorherp

Re: Need help managing (hundreds of) objects simultaniously

Take a look at Hornets tutorial Tukun, there's a lot of good stuff in there which should help you out.  In particular pay attention to how he builds his render buffers.  What's important here is to minimise the number of draw calls you make to graphics card since each call has a significant overhead which can quickly bottleneck your rendering.  Graphics cards are much more adept at handling fewer larger draw calls than more but smaller draw calls.  Therefore try to build a single vertex buffer for all your bullets which share the same texture and send them all off to draw with one call rather than telling each bullet to draw individualy.

To answer your other question, although I'm not using DirectX at the moment, when I was building my DX bullet hell engine I seem to remember I used transformed vertices and built the vertex buffer each frame.  I'm not sure if that's strictly the fastest way to do it but my engine could easily cope with rendering many multiples of thousands of bullets at once without slow down so I guess its not an issue.

« Last Edit: February 09, 2011, 10:45:16 AM by motorherp »

Offline  
Read February 09, 2011, 08:50:33 PM #9
Tukun

Re: Need help managing (hundreds of) objects simultaniously

advice from a pro

I need to know this. did you use a void pointer , update/set the vertices, and d3ddev->CreateVertexBuffer() to update the buffer every frame?
It seams like it can use a lot of memory, even if you are using the same address for the buffer. It makes the term "CreateBuffer" a bit misleading. Anyway, I need to know if that's what you did.
my engine could easily cope with rendering many multiples of thousands of bullets at once without slow down so I guess its not an issue.
I REALLY need to know how you did that. Maybe I should take a look at your code so I can learn from it?Cheesy At best, I can't go past making 30 without my fps going down to 40-ish
« Last Edit: February 09, 2011, 08:52:23 PM by Tukun »
Offline  
Read February 09, 2011, 10:21:54 PM #10
motorherp

Re: Need help managing (hundreds of) objects simultaniously

I posted some code from my own DX engine in the bullet manager tutorial thread since you were talking about vertex buffers there.  Probably should have posted it here to prevent de-railing the tutorial but I didn't see your post here first.  I might split that thread later.  Anyway, take a look and see if you can get anything from it.


Offline  
Pages: [1]   Go Up
Jump to:  

Page created in 0.093 seconds with 17 queries.