[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

[What do we need?]

Hi shmup-friends,

time for another tutorial. This time I'd like to show you how to build a bullet management system. It will be rather basic, good enough to get you started, efficient enough to not become the bottleneck of your shmup and rather easy to extend.
I did not test any of this code in real life, I wrote all this from scratch in a text editor, so I hope there aren't too many mistakes.

What do we need?

First of all let's sum up what essential features are really necessary:

- bullet descriptor.
This will be a very tiny class holding the essential (!) bullet info.

- bullet container.
Somehow all our thousands of bullets must be stored somewhere.

And we need some ways to

- create bullets
- destroy bullets
- look up bullets
- update (move) all bullets
- render all bullets
- check collisions

Let's take a look at those basic building blocks.

Bullet descriptor

When designing that one you have to consider quite a lot of possibilities. Especially when it comes to different bullet types and different bullet behaviour.
One simple way would be to create a base bullet class, derive different bullet-types from that one and hard-wire the various behaviours and appearances you need:

Code:

                      class bullet_base
                             |
        +--------------------+--------------------+
        |                                         |
      class                                     class
bullet_straight_line                      bullet_seek_player

This one may look promising, but in reality your different bullet patterns will be that complex, that you'd end up implementing tons of specialized classed. It's okay for very simple shmups but besides that I wouldn't recommend it.
At some point during your shmup-development you'll most likely want to integrate some kind of scripting, for many reasons, two of them being "quick modification of patterns without recompilation" and "tired of rewriting all your code because you missed a feature you could have had by implementing scripting in the first place".

That's why I recommend:
let's build one single bullet structure that allows for practically anything without blowing up the class or class hierarchy.

Code:

class Bullet {
  public:
    vec2 position;
    vec2 direction;
    float collision_size;
    unsigned int unique_id;
    integer active;
    Appearance *appearance;
    Behaviour *behaviour;
  public:
    inline void Render(void) {
      appearance->PrepareRenderingOf(this);
    }
    inline void Update(void) {
      if(!behaviour->Update(this)) active=0; // returns false if bullet shall be removed
    }
};

That's it. Okay, you could add some reference to the enemy that spawned the bullet or similar atomic info, but let's try it with that most compact version first.

The idea is to "outsource" potentially complex functionality to other seperated modules. This has many benefits, probably the most obvious being the fact, that we can build arrays of bullets regardless of their logical type, because they are of the same "compiler"-type and of the same internal byte-size. And we could easily change the behaviour of a bullet on-the-fly by just changing the "behaviour"-pointer.

As you can see the Render and Update methods just call the matching methods of the attached Appearance and Behaviour classes, instead of implementing all that inside the bullet itself.

Bullet containers

Now that one is easy. As being said: one benefit of the single-class-bullet-design is that we can stuff all of them in simple arrays.
You could argue that you can do that with derived classes too - but there's a big difference: you could build arrays of POINTERS to your bullets only. But we can use arrays of OBJECTS regardless of their logical type. And that means that we are allowed to build very cache-friendly structures.
Since this is heavily connected with creation and destruction of bullets, we will discuss that more deeply in the next section.

Create, destroy and update bullets

Thanks to our simple bullet class design the creation of different bullets could become as trivial as that:

Code:

Bullet *l_bullet=new Bullet(position,direction,appearance,behaviour);

As opposed to a different new ClassX for every bullet type.
Well, at least in theory it's that simple. In practice it's a bit different since you don't want to use heap-allocation and -deallocation every time a bullet is created or destroyed.

Instead we'll design a bullet-manager that pre-allocates some thousands of bullets (as much as we possibly need), holds the active bullets and exposes some convinient functions for creation and deletion.

Note that the following code does some maybe unusual things, so better skip it, continue reading below and come back later.

Code:

const unsigned int MAX_BULLETS=2000; // inside a common include, at global scope, used at different places

class BulletManager {
  private:
    Bullet *bullets;
    unsigned int *id_index_table; // basically this will be both, a mapping table and a linked list of IDs
    unsigned int active_bullets_count;
    unsigned int next_free_id_slot;
  public:
    BulletMananger(void) :
      bullets(0),
      id_index_table(0),
      active_bullets_count(0),
      next_free_id_slot(0)
    {
      bullets=new Bullet[MAX_BULLETS];
      id_to_index_table=new unsigned int[MAX_BULLETS];
      // initialize the ID-index-table to form a linked list, each entry pointing to the next
      for(unsigned int t=0;t<MAX_BULLETS;++t) id_index_table[t]=t+1;
    }
    ~BulletMananger(void) {
      delete[] id_to_index_table;
      delete[] bullets;
    }
    unsigned int Create(Bullet &p_bullet_description) {
      Bullet &l_new_bullet=bullets[active_bullets_count];
      l_new_bullet=p_bullet_description;
      l_new_bullet.active=1;
      unsigned int l_id=next_free_id_slot;
      l_new_bullet.id=l_id;
      // remember: next_free_id_slot contains the index of the next free ID, see initialization
      // now we store that index to the free ID list for the next bullet that's going to be created later...
      next_free_id_slot=id_index_table[l_id];
      // ... and instead let the table now point to our bullet's array index!
      id_index_table[l_id]=active_bullets_count++;
      return l_id;
    }
    void Update(void) {
      unsigned int l_new_index=0;
      for(unsigned int t=0;t<active_bullets_count;++t) {
        Bullet &l_bullet=bullets[t];
        l_bullet.Update();
        if(l_bullet.active) {
          if(t!=l_new_index) {
            // if a bullet was destroyed before adjust the index-tables
            // and move the bullet down in the array accordingly.
            bullets[l_new_index]=l_bullet;
            id_index_table[l_bullet.id]=l_new_index;
          }
          ++l_new_index;
        } else {
          // when a bullet is removed we have to "fix" the free-IDs-pseudo-linked-list.
          // that's easy: we just let the bullet's slot point to the known next free ID
          // which we stored during bullet creation...
          id_index_table[l_bullet.id]=next_free_id_slot;
          // ... and make that slot the new "next_free" slot (like adjusting the head of a linked list)
          next_free_id_slot=l_bullet.id;
        }
      }
      active_bullets_count=l_new_index;
    }
    inline Bullet& GetBulletByID(unsigned int p_id) {
      return bullets[id_index_table[p_id]];
    }
   
   
};

You simply create a bullet by filling the generic Bullet structure and calling BulletManager::Create. As a result you'll get a unique bullet-ID, at least unique for the life-time of that bullet.

It is very important to note, that you don't get a direct pointer to the bullet's internals! The main reason not to use pointers is due to the fact that we internally use an array of Bullet objects, not Bullet pointers. This is primarily done to keep the bullet-structure cache-friendly and to avoid the risk of dead pointers floating around in the system.

But how do we ensure unique IDs together with deletion and how do we implement efficient look-up of "real" objects by that ID?

That magic is done by the code associated with that obscure "id_index_table" and "next_free_id_slot". You have to get used to the idea that a linked-list doesn't have to be implemented via pointers. In fact: here we essentially got some kind of linked-list that operates on indices. And the indices have two uses: either they point to the next free ID or they point to the concrete bullet object.

Maybe it's easier to understand if I tell you the order in which IDs are generated:

bullet A created: 0
bullet B created: 1
bullet C created: 2
bullet B destroyed, its ID 1 is becoming the first element in the free ID list
bullet D created: 1
bullet E created: 3

Anyway, now looking up a bullet is as easy as calling "GetBulletByID".
Usually you'd use that to reference bullets inside of more complex scripts.

Let's sum up the main benefits of our approach here:

1. the bullets are inside one tight array, regardless of logical type.
2. there are no "gaps" inside the array. During the update-loop dead bullets are automatically sorted out.
3. the IDs remain valid even if the objects are moved around internally to preserve a tight array.
4. the drawing order of the bullets is not changed.
5. it's just a few lines of code

Note:
Usually you just want one such manager-object inside your shmup, but you're allowed to use multiple instances. If you want more than one you must be aware that the IDs created by the manager are only unique as long as only one instance is used. You can overcome this limit by adding/subtracting a per-manager magic-number (multiples of MAX_BULLETS) when using the IDs.

Update bullets in detail

In the above code we already saw the update-loop. But the concrete update-behaviour was still missing. To implement that we have to define a "Behaviour" class which we can assign to bullets:

Code:

class Behaviour {
  public:
    Behaviour(void);
    virtual ~Behaviour(void); // don't forget the virtual keyword
    virtual bool Update(Bullet *p_bullet)=0; // returns false to destroy a bullet
};

As you can see this is a virtual class which just defines a common interface for real behaviours. It's rather slim because for the bullet-management only one thing counts: that we can instruct our behaviour to update one dedicated bullet.
Let's implement a simple working behaviour now:

Code:

class Behaviour_Straight : public Behaviour {
  public:
    Behaviour_Straight(void) : Behaviour() {}
    virtual bool Update(Bullet *p_bullet) {
      p_bullet.position+=p_bullet.direction*5.0f; // move bullet 5 units in its original direction
      return InsideScreen(p_bullet.position);
    }
};

The inner working of this class should be self-explaining.
To get a bullet to use that behaviour you just set its Behaviour-pointer-attribute to point to a Behaviour_Straight-object. Important: one single Behaviour-object can be shared by an arbitrary number of bullets!

As already mentioned, in reality you'll most likely use some scripting system for your bullets, so chances are that you need a "Behaviour_Script" class that's initialized with the necessary script. There appears to be one problem though:
The bullets don't carry around any additional information you may need for your scripts, like some status variables or whatever. Luckily we already have the solution at hand: the bullet ID the bullet-manager takes care of.

The bullet ID is unique for the life-time of a bullet and is in the range 0-MAX_BULLETS. So you can add whatever meta-bullet-info your behaviour may need to store with a bullet by creating an array of info inside the behaviour class:

Code:

class Behaviour_Script : public Behaviour {
  private:
    ScriptBulletContext *bullet_meta_data;
    Script *script;
  public:
    Behaviour_Script(void) : Behaviour() {
      script=new Script("scripfile");
      bullet_meta_data=new ScriptBulletContext[MAX_BULLETS];
    };
    virtual ~Behaviour_Script(void) {
      delete[] bullet_meta_data;
      delete script;
    }
    virtual bool Update(Bullet *p_bullet) {
      if(p_bullet->active==1) {p_bullet->active=2; bullet_meta_data[p_bullet->ID].Reset();}
      return script->Run(p_bullet,bullet_meta_data[p_bullet->ID]);
    }
};

This is all pseudo-code but I hope it shows how it might work. The line

Code:

if(p_bullet->active==1) {p_bullet->active=2; bullet_meta_data[p_bullet->ID].Reset();}

just resets the meta-data of a bullet if that bullet was just spawned. That works because the bullet-manager sets Bullet.active to 1 if a new one is created and it only cares wether active becomes 0. Any other value is ignored and can be used for things like that without harming the manager.

In reality you may want to add more methods to the Behaviour base class, like

Code:

class Behaviour {
  ...
  public:
    virtual void CreateBullet(Bullet *p_bullet)=0;
    virtual void DestroyBullet(Bullet *p_bullet)=0;
};

That way you could implement such (de)initialization functionality more easily. Or other funny stuff like a cluster bomb that's activated on bullet destruction. For this tutorial I tried to keep everything as compact as possible, since it's already becoming rather complex.

Render bullets

This works in basically the same way as the update-system with its Behaviour classes.
Since we want different looking bullets we'll design our "Appearance" class using the classic base/derived class design. The base class is essentially only the common interface that allows us to connect it to a bullet. It's therefore a virtual base-class that doesn't do anything by itself:

Code:

class Appearance {
  public:
    Appearance(void);
    virtual ~Appearance(void); // don't forget the virtual keyword
    virtual void PrepareRenderingOf(Bullet *p_bullet)=0;
    virtual void RenderAllBullets(void)=0;
};

As we all know graphics hardware likes big batches. Therefore it's essential that we group our bullets by their appearance, built a large block of vertices out of those and throw that block at the GPU.
The cool thing is: with our design we can get perfectly ordered arrays of bullet-drawing-info for bullets of the same type (almost) for free.

As you can see the above interface is already prepared for that, the methods "RenderAllBullets" tells it all. Now let's implement a possible "real" appearance class:

Code:

class Appearance_PointSprite : public Appearance {
  struct BulletRenderInfo {
    vec2 position;
    vec2 direction;
    inline void Set(const Bullet *p_bullet) {
      position=p_bullet->position;
      direction=p_bullet->direction;
    }
  };
  private:
    BulletRenderInfo *render_info;
    unsigned int render_info_count;
    GLuint texture_id;
    Shader *shader;   // I won't get into this
  public:
    Appearance(GLuint p_texture_id) :
      render_info(0),
      render_info_count(0),
      texture_id(p_texture_id),
      shader(0)
    {
      render_info=new BulletRenderInfo[MAX_BULLETS]; // remember, our global constant
      shader=new PointSpriteShader(); // just to show HOW it may work, won't go into details
    }
   
    virtual ~Appearance(void) {
      delete[] render_info;
    }
   
    virtual void PrepareRenderingOf(Bullet *p_bullet) {
      render_info[render_info_count].Set(p_bullet->position);
      ++render_info_count;
    }
   
    virtual void RenderAllBullets(void) {
      if(render_info_count) {
        ::glBindTexture(texture_id);
        ::glEnable(GL_BLEND);
        ::glColor4ub(255,255,255,255);
        ::glDisable(GL_DEPTH_TEST);
        ::glDepthMask(GL_FALSE);
        ::glEnable(GL_POINT_SPRITE_ARB);
        ::glPointSize(15.0f);
        ::glVertexPointer(4,GL_FLOAT,sizeof(BulletRenderInfo),render_info);
        shader->Activate();
        ::glDrawArrays(GL_POINTS,0,render_info_count)       
        shader->Deactivate();
        render_info_count=0; // Important! Reset counter for next frame.
      }
    }
};

Fine, but how does the appearance class know which bullets to draw? It never references any of our bullets. Answer: As with the Behaviour-class it's the other way around, each bullet knows its appearance.
That brings us back to our bullet-class:

Code:

class Bullet {
    ....
    inline void Render(void) {
      appearance->PrepareRenderingOf(this);
    }
};

I guess you already know how the rendering loop looks like. We will now extend out BulletManager class by an appropriate method:

Code:

class BulletManager {
  ...
  public:
    void Render(void) {
      for(unsigned int t=0;t<active_bullets_count;++t) {
        bullets[t].Render();
      }
    }
};

After calling BulletManager::Render all active bullets have instructed their attached Appearance-classes to prepare all render-buffers. All that needs to be done is to loop over all those Appearance-objects and to tell them to actually draw themselfs.

Collision checks

For 99% of all bullet types you can get away with either a bullet-bounding-rectangle or a bullet-bounding-sphere collision vs. player-position-point check. For the remaining 1% you could add special check behaviour to your "Behaviour" class.
For the standard checks we just need to add another tiny function to our bullet-manager. Our bullets already carry a "collision_size" attribute and a position, that's all we need:

Code:

class BulletManager {
....
  public:
    unsigned int CheckBulletsAgainstPlayerPosition(const vec2 &p_player_position)
    {
      unsigned int l_hit_count=0;
      for(unsigned int t=0;t<active_bullets_count;++t) {
        const Bullet &l_bullet=bullets[t];
        vec2 l_dif=bullet.position-p_player_position;
        if(l_dif.Length()<bullet.collision_size) {
          ++l_hit_count;
          break; // uncomment this if you want to allow multiple hits on the player
        }
      }
      return l_hit_count;
    };
};

This is one of the most simple approaches. It'll work but there are far more advanced ways to handle collisions. But that's stuff for another tutorial motorherp already covered

Putting it all together

Post-size limit reached
Daniel

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

[Putting it all together]

Putting it all together

Okay, our basic bullet management system is completed. It's not the holy grail, but flexible and simple enough to get you on the right track.
Let's see how to actually use it:

Code:

  // Initialization
  Player player;
  player.position.Set(320.0f,300.0f);
 
  BulletManager bullet_manager;

  GLuint texture_id=LoadTextureFromFile("bullet.png");
  // prepare all the behaviours and appearances we need during that level
  Behaviour *test_behaviour=new Behaviour_Straight();
  Appearance *test_appearance=new Appearance_PointSprite(texture_id);
  ...
  ...
  // Spawn 360 test bullets in the middle of a 640x480 screen
  Bullet l_bullet_prototype;
  // fill the bullet struct with common values for this wave of bullets
  l_bullet_prototype.position.Set(320.0f,240.0f);
  l_bullet_prototype.collision_size=4.0f;
  l_bullet_prototype.appearance=test_appearance;
  l_bullet_prototype.appearance=test_behaviour;
 
  static float l_angle=0.0f;
  const float l_angle_step=3.14f/180.0f;
  for(unsigned int t=0;t<360;++t) {
    // each new bullet gets a different direction
    l_bullet_prototype.direction.Set(cosf(l_angle),sinf(l_angle));
    l_angle+=l_angle_step;
    // let the bullet manager create one such bullet based on our bullet-prototype
    bullet_manager.Create(l_bullet_prototype);
  }
 
  ...
  ...
 
  // per frame operations
  bullet_manager.Update();
  if(player.IsAlive()) {
    if(bullet_manager.CheckBulletsAgainstPlayerPosition(player.position)) {
      player.Die();
    }
  }
  bullet_manager.Render();
  test_appearance->RenderAllBullets();

I hope it helps and doesn't contain too many bugs... Alert me if you find something.

Regards,
Daniel

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

[Reserved]

Reserved for fixes or whatever

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

Cool, nice tutorial Hornet, you've got some nice solutions such as the way you build your render buffers and stuff.  This is really appreciated, I always like a good tutorial and I think they're really good for the website.

After my first read-through I've got one suggestion I'd like to make regarding your behaviour and appearance classes if that's alright.  Specifically its about their virtual nature.  Virtualisation can be a great way of building flexible and extensible programs but that comes at a performance cost.  If my understanding is correct, when calling a non-virtual function the worst that can happen is that you generate an instruction cache miss when the function's instructions are fetched if they're not already in the cache.  When calling a virtual function however the computer has to first fetch the vtable and then fetch the function through the function pointer from said vtable.  If non of this is already cached it will result in two consecutive data cache misses before the normal possible instruction cache miss.  This is further compounded in this case since you first have to fetch the base classes for your Behaviour and Appearance before you can get at their vtable pointer.

Usualy I'd say not to worry about this because the benefits of using virtualisation out-weigh the performance cost.  However in this case since you are looping through arrays of possibly thousands of virtual objects multiple times a frame, then if there are many inherited behviours and apprearances used, or for whatever other reason the computer is unable to cache a lot of this stuff, then you'll be incurring many stalls which could add up to be very significant.

Of the top of my head what I'd suggest is to first try and roll your behaviour and appearance classes into the bullets themselves since they pretty much contain only functionality and no data which should save you one derefence.  Then secondly I'd consider rolling all your different behaviour and appreance implementations into that one class and use a combination of a behaviour/appearance type enum and switch statement to execute the correct implementation.  Although no-where near as elegant, this will remove all virtualisation which should hopefully make it all much more cache friendly.  If you put your mind to it though you can probably find a more elegant solution.

Anyway that's just my suggestion.  Great work, its really appreciated

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

@motorherp

Thanks for not being too harsh with this quick-shot-tutorial

Yes, you're right about virtual functions, they come with a general inevitable performance penalty due to the internal indirection.
But as you already said: the positive aspects outweight the penalty. On today's machines (even devices like iPhones or whatever) you can really forget about that, at least in this situation here, because the overhead of even thousands of indirect function calls won't kill you.

Regarding cache-misses:

Those are there, but the reason isn't the use of virtual functions or the use of the behaviour/appearance pointer by itself. Yes, the vtable has to be touched, but chances are high that it is already cached too in some cache line.

You get cache misses once you use different types of bullets with different behaviour/appearance objects. Because the bullets are not ordered by type you constantly jump from one code section to another.
The question is if that's a big problem. Asuming you use some kind of scripting engine in the background or other more complex stuff: invoking that will kill your cache anyway.

If you want to hardcode everything then your idea to use a switch statement and stuff all in one non-virtual function will indeed provide some speedup, unless the different switch-items aren't too large, then you'll get cache misses again unless you sort by type.

On the other hand it is possible to make the bullet-list self-sorting over multiple frames at very little cost (no, I won't do that now, but maybe tomorrow, I just tried it on paper ). This isn't complicated since new bullets are always appended to the end of the list, they could be swapped into the right place during the update loop.

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

Actualy after posting this it inspired me to do some more research into the issue.  Most of my experience comes from programming for consoles where such issues are usualy more heavily skewed one way or another compared to PC's since for consoles you can often be dealing with tighter caches and cache misses are often very punishing.  Its actualy rather difficult to find good information on this for PC's and general opinion seems to be split between poeple who believe the performance difference bewteen virtualisation and switch statements in this kind of situation is significant and those who beleive that PC's are good enough that you shouldn't be hit too often or hard by the cache misses using virutalisation and since switches will usualy compile to jump tables anyway that the performance is pretty similar.  I guess really whether loosing the elegance of virtualisation for the performance gain you get with it or not is very dependant on the hardware its running on.  The alternative maybe would be to use a more data oriented approach rather than object orientated where bullets are iterated through by behaviour type so that no switch is needed in the behaviour update but this would maybe cause other problems and reduce the simplicity of the code.

To be perfectly honest I'm no longer sure on the best approach, I dont think its so clear cut in the PC world and I dont think I have enough experience in that field to give solid advice.  Therefore the only advice I can give here that I know is good is to use your profiler to identify whether this is a performance issue or not and then play around with different implementations if you really need the speed boost.


Edit:  Ah, I see you beat me to it again .

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

@motorherp

The thing is:
there's no real perfect solution (at least I don't see one). It's either simplicity / elegance / flexibility vs. raw speed. The question is if you really need that raw speed at that area.

In our shmups it's just rather unlikely that things as the bullet loop by itself becomes the bottleneck. Even if you got a few thousands of bullets and your list is totally unordered and always produces L1 cache misses (unlikely), this boils down to maybe some thousand nano-seconds on an avg. desktop PC. Of course this depends on the architecture, but nevertheless: on desktop CPUs this is nothing to worry about at all, and on devices like iPhone or so the GPU will say "nay" earlier when you throw so many blended bullets at it

Yes, just like you I like to squeeze out as much performance as possible out of everything. But I have to admit that it's often just for the sake of "wow, I saved 10 cycles, cool"  Most often it wouldn't have been necessary or this small thing is outweight by some other algorithmical change elsewhere.

Nevertheless: you're still right, this code as is is not the fastest solution.

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

Indeed.  Excellent advice and well said.  I'm fully aware that I tend to get pretty obsessed with these types of things beyond what is healthy for the development of smaller independant projects.  I guess that comes from my general experience of game development working on large commercial titles in big teams where you have the time and need to concentrate on such details.  In my time I've never worked on a game that hasn't required some pretty rigorous optimisation near the end to get it to run in frame so I'm usualy pretty quick to try and identify potential areas that could give worthy gains early on.  When working solo on smaller games then I suppose shear man hours available is much more limiting than performance given what you're usualy working on and hence this kind of obssession can be detrimental.  Its good to have someone pull the reigns on my rantings occationaly to keep things real .  Anyway thanks for your insights, it's been helpful, and I hope I haven't derailed your tutorial too much .

[Tukun]

Tukun

Tukun

Show Tukun's last posts.

Show general stats for Tukun.

• 
• Newbie
• Score: 0
• Posts: 18

Thank you very much for this helpful tutorial. It's a shame there are very few like it to help guide with how to deal with memory management of hundreds to thousands of objects.
I'm somewhat of a newbie at shmup development (and programming in general) so please bare with me. I'd like you to elaborate on this part.

That magic is done by the code associated with that obscure "id_index_table" and "next_free_id_slot". You have to get used to the idea that a linked-list doesn't have to be implemented via pointers. In fact: here we essentially got some kind of linked-list that operates on indices. And the indices have two uses: either they point to the next free ID or they point to the concrete bullet object.

Maybe it's easier to understand if I tell you the order in which IDs are generated:

bullet A created: 0
bullet B created: 1
bullet C created: 2
bullet B destroyed, its ID 1 is becoming the first element in the free ID list
bullet D created: 1
bullet E created: 3

Anyway, now looking up a bullet is as easy as calling "GetBulletByID".
Usually you'd use that to reference bullets inside of more complex scripts.

The biggest problem (I think) with my bullet managment is that I stuff all of my bullets into one array. The bullets have their own ID's, which are never changed, and all created at the same time. They're also all individual objects, so each has its own structure to hold things like position and lifetime relative to the frames from when I switch them "on". Anyway, this presents a problem. I render them all in a loop (skipping the ones which aren't "alive"), but I'm afraid this will slow things down. It also creates gaps, which I also want to avoid. But how will I have Bullet A (which has so-and-so coordinates, *this texture, and blah-blahblah) change things during runtime? Here's the two structs I made similar to my own. Part of a header file.

Code:

struct SHOTDATA{
float uvLEFT,uvTOP,uvRIGHT,uvBOTTOM;  ////coordinates of the texture, on the PNG, which is the sheet that holds all my bullets
int blendnum; ///1 for alpha, 2 for additive, etc
float angular_velocity;    
DWORD delay_color;         ////color of the special effect when bullet spawns



};



struct BULLET
{
////info
float xpos,ypos,zpos,direction,speed,rotation,acceleration; ///critical stuff
SHOTDATA iddata;   ///initialize at bullet creation. Can be changed/updated at runtime.
bool alive;
short idnum;

////functions and stuff
void DrawBullet();
void SetTexture();
void BlahBlahBlah() ///you get the idea
BULLET();

};

BULLET::BULLET()
{
alive=0;
}



const short maxnumberofbullets=500; ///this declaration is global

BULLET allofmybullets[maxnumberofbullets]; ///this declaration is global. 500 bullets are made simultaneously right off the bat before the program even really starts.
SHOTDATA allofmyshotdata[50]; ///this declaration is also global. In this case, I made 50 different types of bullets. Struct description is later down.

//////somewhere else, I fill out my shot data. This data is never changed.
//////the bullet can refer to another segment of allofmyshotdata by changing the index of "iddata" within its structure.
void SetAllBulletData(){
shotdata[0].uvLEFT=0;  //x cord of farthest left side of the bullet on the PNG
shotdata[0].uvTOP=0;   //y cord of the farthest top side
shotdata[0].uvRIGHT=1;  ///I'm using the entire PNG. uv allocation is 0 through 1.
shotdata[0].uvBOTTOM=1;
shotdata[0].blendnum=1; //ALPHA blending
///and so on. I need to find a faster way to do this. I may have 80-150 different types of bullets, each with their own unique style.
////////////////
}




////My bullet creation function should take only a few parameters. This is called only once per bullet in my infinite game loop/script

void CreateShot(float x, float y, float dir, float sp, float rot, float accel, float idnum){

int s=0; ///this exists only within this function. The next time it's called, it's reset to 0.
while(allofmybullets[s].alive==1){s++;} ////skip the bullets which are alive.

///assign data to the array, use index "s", which is confirmed being dead
allofmybullets[s].xpos=x;
allofmybullets[s].ypos=y;
allofmybullets[s].zpos=0;
allofmybullets[s].direction=dir;
allofmybullets[s].speed=sp;
allofmybullets[s].rotation=rot;
allofmybullets[s].acceleration=accel;
//allofmybullets[s].id[idnum]=idnum; ///wrong syntax, I know. Something feels wrong here.
//// I want to say "use this index of the array of "allofmyshotdata" structure.
allofmybullets[s].alive=1;  ///the bullet is marked alive.


}

////here is my render_bullets function, called once per frame in my infinite loop.



void render_all_bullets(){

////lighting and stuff gets set once per frame, before the bullet loop updates stuff
d3ddev->SetFVF(CUSTOM2DFVF);                ///flexible vertex format for 2D bullets, etc
d3ddev->SetRenderState(D3DRS_ZENABLE,FALSE);  
d3ddev->SetRenderState(D3DRS_LIGHTING,FALSE);
d3ddev->SetRenderState(D3DRS_CULLMODE,D3DCULL_NONE);
d3ddev->SetRenderState(D3DRS_LIGHTING,FALSE);
D3DXMATRIX bulletmat; ///still trying to figure out how to play with the matrix to simply transform the vertices on the 2D screen.
    for(static int i=0; i<maxnumberofbullets; i++)
       {
      if(allofmybullets[i].alive) ////if the bullet is alive, do these processes. else, skip it.
{

D3DXMatrixTranslation(&bulletmat,allofmybullets[i].xpos,allofmybullets[i].ypos,0);
d3ddev->SetTransform(D3DTS_WORLD,&bulletmat);

d3ddev->SetStreamSource(0,d3d_vBuffer2Dim,0,sizeof(VERTEX2D)); ///original vertices in the vertex buffer are static. Since this is a prototype,
////I'm only using one bullet, so I don't need to change or move this just yet.
///But I'm afraid if I have to change the UV coordinates of he texture of the bullet,
///I'll have to constantly lock the buffer, set the new data, unlock it, and reset the stream source
///for every bullet. I'm afraid it will eat up ALOT of resources to do that for each bullet, every
///frame.
d3ddev->DrawPrimitive(D3DPT_TRIANGLESTRIP,0,2);///draws one bullet.
///I don't know how to draw multiple bullets with a single draw() just yet, and not sure if it's
///efficient. I recently heard that DrawPrimitive() also has a huge overhead, so I don't know
///what to make of it.



//set the world matrix back to it's original position
D3DXMatrixTranslation(&bulletmat,0,0,0);
d3ddev->SetTransform(D3DTS_WORLD,&bulletmat);
                  }

        }



}

Of course I have to tweak and add a lot of things, like including speed and the math for updating the xy coordinates of each bullet for that. But that's the easy part. I feel like I'm going off on a tangent here though. Especially after reading your tutorial. Sorry if my infrastructure makes you want to pull hairs. I barely know how to properly do this, and it's tutorials like these that really help.

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

[must]

@Tukun
The biggest problem with your code is the way you render your bullets: you don't build big chunks of bullets but instead issue one seperate draw call per bullet. You also change the material all the time.

That is a no go!
Just look at all the overhead (DX function calls, driver calls) you create for each bullet. A texture change is probably the most costy thing you can do to a GPU, you must draw your stuff in big chunks sorted by material and other render-states.

You have to add some pre-render layer where you calculate and record all vertices and triangles for all bullets sharing the same material (texture, shader) in one big linear buffer. That step does not involve any DX function call at all!

Also don't change the transformation matrix for every bullet. Instead either take care that the bullets need no further transformation at this point by using appropriate coordinate system and / or do the transformation yourself when you prepare your vertex buffer.

Afterwards you step through each bullet-material, activate it and send the prepared vertex buffer for that material (containing all triangles for all bullets of that material) to the GPU with one drawing call.

That's what I'm doing inside the PrepareRenderingOf method of my Appearance class above. I stuff all bullet coordinates into one large array,  render_info, and after that is fill with all coordinates I issue one drawing call to render them all at once inside RenderAllBullets via glDrawArrays(GL_POINTS,0,render_info_count).

This is OpenGL but the same rules apply to DX.

Btw.: don't worry, we all went through similar problems once, no need to be ashamed 

[Tukun]

Tukun

Tukun

Show Tukun's last posts.

Show general stats for Tukun.

• 
• Newbie
• Score: 0
• Posts: 18

Hornet600S,
     Thank you for the reply. I think I can grasp the idea of how to organize my bullets with your method. But by the looks of it, yours also makes one big array of bullets. Should I avoid that? And let me try to break this thing down about vertices. The vertices of ALL of the bullets, transformed or not, should all be packed into the vertex buffer, which also eliminates the need for matrices to set the positions of which bullet goes where. I guess this also makes it possible to render all of my bullets within one DrawPrimitive() call. Using DrawPrimitive() once per bullet is a definite no-no, I didn't know that. Thank you very much.
But this presents the problem of actually updating my bullets. I'm afraid that it will use even more resources- but you're the expert here, so please confirm if this is an accurate and efficient way to do this. Here is my new prototype to my render_all_bullets. The bullet manager will be made later.

Code:

for(int i=0; i<maxnumberofbullets; i++){
     if(allofmybullets[i].alive)
                          {
VERTEX2D vertices2D[]={
///this holds the vertices for just one bullet.
///I should probably have a function that does this for me
///if I wanted 120 bullets, I'd have 120*4 of these segmets, right?
///and update only particular elements of this array, based on which bullets are alive?
///This presents a problem. How will I use 1 drawprimitive() to draw all the different kinds of bullets
///if some types of bullets can hold a different blending property?
///should 1 and d3ddev->SetRenderState() and d3d->DrawPrimitive() go with one each TYPE?
        { allofmybullets[i].xpos-8.0f, allofmybullets[i].ypos-8.0f, 0.0f, allofmybullets[i],color,
        allofmybullets[i].uvLEFT, allofmybullets[i].uvTOP },
        { allofmybullets[i].xpos+8.0f, allofmybullets[i].ypos-8.0f, 0.0f,  allofmybullets[i],color,
        allofmybullets[i].uvRIGHT, allofmybullets[i].uvTOP },
        { allofmybullets[i].xpos-8.0f, allofmybullets[i].ypos+8.0f, 0.0f,
        allofmybullets[i],color, allofmybullets[i].uvLEFT, allofmybullets[i].uvBOTTOM},
        { allofmybullets[i].xpos+8.0f, allofmybullets[i].ypos+8.0f, 0.0f,
         allofmybullets[i],color, allofmybullets[i].uvRIGHT, allofmybullets[i].uvBOTTOM},

};

/////////
///update all bullet's positions based on speed, direction, math stuff goes here
/////////



       ///the loop does all of the assigning and updating for me      }

d3ddev->CreateVertexBuffer(4*sizeof(VERTEX2D),0,CUSTOM2DFVF,D3DPOOL_MANAGED,&d3d_vBuffer2Dim,NULL);
//////there doesn't seem to be an "update vertex buffer" function for directx,
//////so it looks like I'll have to cope with making a new vertex buffer
//////and assign the address of all the bullets with that. Is it costly?

////set all of the vertices for the bullets in one call for this frame
        void *vPointer;   
d3d_vBuffer2Dim->Lock(0,0,&vPointer,0);
memcpy(vPointer,vertices2D,sizeof(vertices2D));
d3d_vBuffer2Dim->Unlock();
d3ddev->SetTexture(0,texture_bull); //this buffer holds the sheet with an image of all of my bullets.
                d3ddev->DrawPrimitive(D3DPT_TRIANGLESTRIP,0,2);
    }

Thanks again for the big help. I wish I had a clearer idea of what I need to do with this sort of stuff.

[Odessi]

Odessi

Odessi

Show Odessi's last posts.

Show general stats for Odessi.

• 
• Jr. Member
• Score: 3
• Posts: 59

For what it's worth, I've always found rendering to be the bottleneck - both on desktop and handheld - and that's even with the pretty heavy scripting system that I use.

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

@Tukun.

It's been a long time since I worked on this or did anything with DirectX in fact so I dont know how up to date it is, but here's the RenderManager from GremlinEngine, my own personal DirectX game engine.  A lot of it probably wont make much sense viewed out of context like this or without seeing all the accompanying files, but you should at least be able to extract from this how I build and manage my vertex buffers and render them.



Gremlin::RenderManager.h

Code:

© Daniel Stoneley

//////////////////////////////////////////////////////////////////////////
//
// RenderManager.hpp
//
//////////////////////////////////////////////////////////////////////////


#ifndef D3D_DEBUG_INFO
#define D3D_DEBUG_INFO
#endif


#ifndef __GREMLIN_RENDERMANAGER__
#define __GREMLIN_RENDERMANAGER__


#include <d3dx9.h>
#include <vector>
#include "Sprite.h"
#include "Texture.h"
#include "Effect.h"
#include "Material.h"
#include "..\\Effects\\Effects.h"


namespace Gremlin
{


#define SPRITES_PER_BUFFER 256
#define VBUFFER_SIZE (sizeof(SpriteVertex) * 4 * SPRITES_PER_BUFFER)
#define IBUFFER_SIZE ((VBUFFER_SIZE * 12) / sizeof(SpriteVertex))



//////////////////////////////////////////////////////////////////////////
//
// RenderGroup
//
//////////////////////////////////////////////////////////////////////////

class RenderGroup
{
public:
const Material* m_pMtrl;
SpriteArray m_spriteArray;

inline ~RenderGroup()
{
m_spriteArray.clear();
}
};

typedef std::vector<RenderGroup> RenderGroupArray;





//////////////////////////////////////////////////////////////////////////
//
// RenderManager
//
//////////////////////////////////////////////////////////////////////////

class RenderManager
{
public:
~RenderManager();

void Draw(const SpriteAdv& rInSprite);
void Draw(const Sprite& rInSprite);
void Draw(const SpriteT& rInSprite);

private:
IDirect3DDevice9* m_pDevice;
IDirect3DVertexBuffer9* m_pVBuffer;
IDirect3DIndexBuffer9* m_pIBuffer;

RenderGroupArray m_renderGroups;
RenderGroupArray m_alphaRenderGroups;

u32 m_width;
u32 m_height;

RenderManager() {}

void Initialise(IDirect3DDevice9* pDevice, u32 width, u32 height);
void Release();

void FillIndexBuffer(u32 numSprites);

void DrawBegin();
void DrawEnd();

void DrawGroups(RenderGroupArray& rGroup, bool (*pSortFunc)(const SpriteInstance&, const SpriteInstance&));
void DrawBatch(SpriteArray& rSpriteArray, ID3DXEffect* pFx, u32 spriteOffset, u32 numSprites, float invTexWidth, float invTexHeight);


friend class GremlinEngine;
};

}



#endif

Gremlin::RenderManager.cpp

Code:

© Daniel Stoneley

//////////////////////////////////////////////////////////////////////////
//
// RenderManager.cpp
//
//////////////////////////////////////////////////////////////////////////


#include "RenderManager.h"
#include "../Editor/Editor.h"
#include <algorithm>


namespace Gremlin
{



//////////////////////////////////////////////////////////////////////////
//
// RenderManager
//
//////////////////////////////////////////////////////////////////////////

//
// Destructor
//

RenderManager::~RenderManager()
{
m_renderGroups.clear();
m_alphaRenderGroups.clear();
}


//
// Initialise
//

void RenderManager::Initialise(IDirect3DDevice9* pDevice, u32 width, u32 height)
{
m_pDevice = pDevice;
m_width = width;
m_height = height;

// Initialise render buffers
HRESULT hr = m_pDevice->CreateVertexBuffer(VBUFFER_SIZE, D3DUSAGE_WRITEONLY, D3DFVF_SPRITEVERTEX, D3DPOOL_DEFAULT, &m_pVBuffer, 0);
if(!Log::TestAndLog("IDirect3DDevice9::CreateVertexBuffer", hr, true)) { return; }

hr = m_pDevice->CreateIndexBuffer(IBUFFER_SIZE, D3DUSAGE_WRITEONLY, D3DFMT_INDEX16, D3DPOOL_DEFAULT, &m_pIBuffer, 0);
if(!Log::TestAndLog("IDirect3DDevice9::CreateIndexBuffer", hr, true)) { return; }

// initialise index buffer
FillIndexBuffer(SPRITES_PER_BUFFER);
}


//
// Release
//

void RenderManager::Release()
{
if(m_pVBuffer) { m_pVBuffer->Release(); }
if(m_pIBuffer) { m_pIBuffer->Release(); }

m_renderGroups.clear();
m_alphaRenderGroups.clear();
}


//
// DrawBegin
//

void RenderManager::DrawBegin()
{
u32 numIds = Material::GetNumAssignedIds();

if(numIds != m_renderGroups.size())
{
m_renderGroups.resize(numIds);
m_alphaRenderGroups.resize(numIds);
}

for(u32 i = 0; i < numIds; ++i)
{
m_renderGroups[i].m_pMtrl = 0;
m_alphaRenderGroups[i].m_pMtrl = 0;
}
}


//
// Draw
//

void RenderManager::Draw(const SpriteAdv& rInSprite)
{
SpriteInstance sprite;
sprite.m_colour = rInSprite.m_colour;
sprite.m_srcRect = rInSprite.m_srcRect;

float sinAng = sinf(rInSprite.m_rotation);
float cosAng = cosf(rInSprite.m_rotation);

float left = -rInSprite.m_center.x * rInSprite.m_scale.x;
float leftCosAng = left*cosAng;
float leftSinAng = left*sinAng;

float up = -rInSprite.m_center.y * rInSprite.m_scale.y;
float upCosAng = up*cosAng;
float upSinAng = up*sinAng;

sprite.m_verts[0] = D3DXVECTOR3(rInSprite.m_pos.x + leftCosAng - upSinAng, rInSprite.m_pos.y + leftSinAng + upCosAng, rInSprite.m_pos.z);

float right = (sprite.m_srcRect.right - sprite.m_srcRect.left - rInSprite.m_center.x)*rInSprite.m_scale.x;
float rightCosAng = right*cosAng;
float rightSinAng = right*sinAng;

sprite.m_verts[1] = D3DXVECTOR3(rInSprite.m_pos.x + rightCosAng - upSinAng, rInSprite.m_pos.y + rightSinAng + upCosAng, rInSprite.m_pos.z);

float down = (sprite.m_srcRect.bottom - sprite.m_srcRect.top - rInSprite.m_center.y)*rInSprite.m_scale.y; 
float downCosAng = down*cosAng;
float downSinAng = down*sinAng;

sprite.m_verts[2] = D3DXVECTOR3(rInSprite.m_pos.x + rightCosAng - downSinAng, rInSprite.m_pos.y + rightSinAng + downCosAng, rInSprite.m_pos.z);
sprite.m_verts[3] = D3DXVECTOR3(rInSprite.m_pos.x + leftCosAng - downSinAng, rInSprite.m_pos.y + leftSinAng + downCosAng, rInSprite.m_pos.z);

if(rInSprite.m_blend)
{
m_alphaRenderGroups[rInSprite.m_pMtrl->m_id].m_spriteArray.push_back(sprite);
m_alphaRenderGroups[rInSprite.m_pMtrl->m_id].m_pMtrl = rInSprite.m_pMtrl;
}
else
{
m_renderGroups[rInSprite.m_pMtrl->m_id].m_spriteArray.push_back(sprite);
m_renderGroups[rInSprite.m_pMtrl->m_id].m_pMtrl = rInSprite.m_pMtrl;
}
}


void RenderManager::Draw(const Sprite& rInSprite)
{
SpriteInstance sprite;
sprite.m_colour = rInSprite.m_colour;
sprite.m_srcRect = rInSprite.m_srcRect;

D3DXVECTOR2 transPos(rInSprite.m_pos.x - rInSprite.m_center.x, rInSprite.m_pos.y - rInSprite.m_center.y);
sprite.m_verts[0] = D3DXVECTOR3(transPos.x, transPos.y, rInSprite.m_pos.z);

float width = float(sprite.m_srcRect.right - sprite.m_srcRect.left);

sprite.m_verts[1] = D3DXVECTOR3(transPos.x + width, transPos.y, rInSprite.m_pos.z);

float height = float(sprite.m_srcRect.bottom - sprite.m_srcRect.top);

sprite.m_verts[2] = D3DXVECTOR3(transPos.x + width, transPos.y + height, rInSprite.m_pos.z);
sprite.m_verts[3] = D3DXVECTOR3(transPos.x, transPos.y + height, rInSprite.m_pos.z);

if(rInSprite.m_blend)
{
m_alphaRenderGroups[rInSprite.m_pMtrl->m_id].m_spriteArray.push_back(sprite);
m_alphaRenderGroups[rInSprite.m_pMtrl->m_id].m_pMtrl = rInSprite.m_pMtrl;
}
else
{
m_renderGroups[rInSprite.m_pMtrl->m_id].m_spriteArray.push_back(sprite);
m_renderGroups[rInSprite.m_pMtrl->m_id].m_pMtrl = rInSprite.m_pMtrl;
}
}


void RenderManager::Draw(const SpriteT& rInSprite)
{
SpriteInstance sprite;
sprite.m_colour = rInSprite.m_colour;
sprite.m_srcRect = rInSprite.m_srcRect;
sprite.m_verts[0] = rInSprite.m_verts[0];
sprite.m_verts[1] = rInSprite.m_verts[1];
sprite.m_verts[2] = rInSprite.m_verts[2];
sprite.m_verts[3] = rInSprite.m_verts[3];

if(rInSprite.m_blend)
{
m_alphaRenderGroups[rInSprite.m_pMtrl->m_id].m_spriteArray.push_back(sprite);
m_alphaRenderGroups[rInSprite.m_pMtrl->m_id].m_pMtrl = rInSprite.m_pMtrl;
}
else
{
m_renderGroups[rInSprite.m_pMtrl->m_id].m_spriteArray.push_back(sprite);
m_renderGroups[rInSprite.m_pMtrl->m_id].m_pMtrl = rInSprite.m_pMtrl;
}
}


//
// DrawEnd
//

void RenderManager::DrawEnd()
{
HRESULT hr = m_pDevice->Clear(0, 0, D3DCLEAR_TARGET | D3DCLEAR_ZBUFFER, 0x00000000, 1.0f, 0);
if(!Log::TestAndLog("IDirect3DDevice9::Clear", hr)) { return; }

hr = m_pDevice->BeginScene();
if(!Log::TestAndLog("IDirect3DDevice9::BeginScene", hr)) { return; }

hr = m_pDevice->SetIndices(m_pIBuffer);
if(!Log::TestAndLog("IDirect3DDevice9::SetIndices", hr)) { return; }

hr = m_pDevice->SetStreamSource(0, m_pVBuffer, 0, sizeof(SpriteVertex));
if(!Log::TestAndLog("IDirect3DDevice9::SetStreamSource m_pVBuffer", hr)) { return; }

hr = m_pDevice->SetVertexDeclaration(SpriteVertex::m_pDecl);
if(!Log::TestAndLog("IDirect3DDevice9::SetVertexDeclaration", hr)) { return; }

DrawGroups(m_renderGroups, SpriteInstance::FrontToBack);
DrawGroups(m_alphaRenderGroups, SpriteInstance::BackToFront);

//Stats::UpdateAndRender();

#if EDITOR_MODE
TwDraw();
#endif

hr = m_pDevice->EndScene();
if(!Log::TestAndLog("IDirect3DDevice9::EndScene", hr)) { return; }

hr = m_pDevice->Present(0, 0, 0, 0);
if(!Log::TestAndLog("IDirect3DDevice9::Present", hr)) { return; }
}


//
// FillIndexBuffer
//

void RenderManager::FillIndexBuffer(u32 numSprites)
{
assert(numSprites <= SPRITES_PER_BUFFER);

u16* pIndexData = 0;
HRESULT hr = m_pIBuffer->Lock(0, numSprites*sizeof(u16)*6, (void**)&pIndexData, 0);
if(!Log::TestAndLog("IDirect3DIndexBuffer9::Lock", hr)) { return; }

if(pIndexData)
{
u32 numVerts = numSprites * 4;
for(u32 i = 0; i < numVerts; i += 4)
{
*pIndexData++ = i;
*pIndexData++ = i+1;
*pIndexData++ = i+3;
*pIndexData++ = i+3;
*pIndexData++ = i+1;
*pIndexData++ = i+2;
}

m_pIBuffer->Unlock();
}
}


//
// DrawGroups
//

void RenderManager::DrawGroups(RenderGroupArray& rGroup, bool (*pSortFunc)(const SpriteInstance&, const SpriteInstance&))
{
RenderGroupArray::iterator iter;
for(iter = rGroup.begin(); iter != rGroup.end(); iter++)
{
RenderGroup& rGroup = *iter;

if(rGroup.m_pMtrl)
{
std::sort(rGroup.m_spriteArray.begin(), rGroup.m_spriteArray.end(), pSortFunc);

Effect* pEffect = Effect::Access(rGroup.m_pMtrl->m_effectName);
pEffect->Prepare(rGroup.m_pMtrl);

IDirect3DTexture9* pTex = Texture::Access(rGroup.m_pMtrl->m_textureNames[0]);
D3DSURFACE_DESC desc;
HRESULT hr = pTex->GetLevelDesc(0, &desc);
if(!Log::TestAndLog("Could not get texture description for " + rGroup.m_pMtrl->m_textureNames[0], hr))
{
continue;
}

float invTexWidth = 1.0f / (float)desc.Width;
float invTexHeight = 1.0f / (float)desc.Height;

u32 numSpritesProcessed = 0;
u32 numSpritesLeft = (u32)rGroup.m_spriteArray.size();
while(numSpritesLeft)
{
u32 numSpritesToRender = min(numSpritesLeft, SPRITES_PER_BUFFER);
DrawBatch(rGroup.m_spriteArray, pEffect->m_pFx, numSpritesProcessed, numSpritesToRender, invTexWidth, invTexHeight);

numSpritesProcessed += numSpritesToRender;
numSpritesLeft -= numSpritesToRender;
}
}

rGroup.m_spriteArray.clear();
}
}


//
// DrawBatch
//

void RenderManager::DrawBatch(SpriteArray& rSpriteArray, ID3DXEffect* pFx, u32 spriteOffset, u32 numSprites, float invTexWidth, float invTexHeight)
{
u32 numPasses = 0;
HRESULT hr = pFx->Begin(&numPasses, 0);
if(!Log::TestAndLog("ID3DXEffect::Begin", hr)) { return; }

for(u32 pass = 0; pass < numPasses; ++pass)
{
SpriteVertex* pVerts = 0;
hr = m_pVBuffer->Lock(0, sizeof(SpriteVertex)*4*numSprites, (void**)&pVerts, 0);
if(!Log::TestAndLog("IDirect3DVertexBuffer9::Lock", hr)) { return; }

u32 maxIndex = spriteOffset + numSprites;
for(u32 index = spriteOffset; index < maxIndex; ++index)
{
SpriteInstance& rSprite = rSpriteArray[index];

float uvs[4];
uvs[0] = (rSprite.m_srcRect.left - 0.5f) * invTexWidth;
uvs[1] = (rSprite.m_srcRect.right + 0.5f) * invTexWidth;
uvs[2] = (rSprite.m_srcRect.top - 0.5f) * invTexHeight;
uvs[3] = (rSprite.m_srcRect.bottom + 0.5f) * invTexHeight;

pVerts[0].m_pos.x = rSprite.m_verts[0].x;
pVerts[0].m_pos.y = rSprite.m_verts[0].y;
pVerts[0].m_pos.z = rSprite.m_verts[0].z;
pVerts[0].m_pos.w = 1.0f;
pVerts[0].m_texCoords.x = uvs[0];
pVerts[0].m_texCoords.y = uvs[2];
pVerts[0].m_colour = rSprite.m_colour;

pVerts[1].m_pos.x = rSprite.m_verts[1].x;
pVerts[1].m_pos.y = rSprite.m_verts[1].y;
pVerts[1].m_pos.z = rSprite.m_verts[1].z;
pVerts[1].m_pos.w = 1.0f;
pVerts[1].m_texCoords.x = uvs[1];
pVerts[1].m_texCoords.y = uvs[2];
pVerts[1].m_colour = rSprite.m_colour;

pVerts[2].m_pos.x = rSprite.m_verts[2].x;
pVerts[2].m_pos.y = rSprite.m_verts[2].y;
pVerts[2].m_pos.z = rSprite.m_verts[2].z;
pVerts[2].m_pos.w = 1.0f;
pVerts[2].m_texCoords.x = uvs[1];
pVerts[2].m_texCoords.y = uvs[3];
pVerts[2].m_colour = rSprite.m_colour;

pVerts[3].m_pos.x = rSprite.m_verts[3].x;
pVerts[3].m_pos.y = rSprite.m_verts[3].y;
pVerts[3].m_pos.z = rSprite.m_verts[3].z;
pVerts[3].m_pos.w = 1.0f;
pVerts[3].m_texCoords.x = uvs[0];
pVerts[3].m_texCoords.y = uvs[3];
pVerts[3].m_colour = rSprite.m_colour;

pVerts += 4;
}

m_pVBuffer->Unlock();


hr = pFx->BeginPass(pass);
if(!Log::TestAndLog("ID3DXEffect::BeginPass", hr)) { return; }

hr = m_pDevice->DrawIndexedPrimitive(D3DPT_TRIANGLELIST, 0, 0, numSprites*4, 0, numSprites*2);
if(!Log::TestAndLog("IDirect3DDevice9::DrawIndexedPrimitive", hr)) { return; }

pFx->EndPass();
}

pFx->End();
}

}

Sorry about the dodgy indentation.  The code tags dont always play nicely.  Hope you can extract something usefull out of that.

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

@motorherp

I hope I haven't derailed your tutorial too much

@Odessi

I've always found rendering to be the bottleneck - both on desktop and handheld

Yes, me too.

@Tukun

yours also makes one big array of bullets

big bullet arrays are a good thing

Regarding updates:

Rule #1:
during your bullet-update-code not a single DX function must appear!

Rule #2:
inside your bullet-vertex-buffer-update-loop not a single DX function must appear!

Your update code from above operates on single bullets again.
I tried to modify your code a bit so you get the idea:

Code:

static VERTEX2D big_buffer[BIG_ENOUGH_NUMBER];

// "clear" big_buffer
unsigned int big_buffer_counter=0;

// loop through all bullets
for(int i=0; i<maxnumberofbullets; i++){
  // for all living bullets
  if(allofmybullets[i].alive) {
    // create vertices and add them to the big_buffer
    // note the big_buffer_counter++
    // for each vertex
    big_buffer[big_buffer_counter++]=
      VERTEX2D(
        allofmybullets[i].xpos-8.0f,
        allofmybullets[i].ypos-8.0f,
        0.0f,
        allofmybullets[i].color,
        allofmybullets[i].uvLEFT,
        allofmybullets[i].uvTOP
      );
    big_buffer[big_buffer_counter++]=
      VERTEX2D(
        allofmybullets[i].xpos+8.0f,
        allofmybullets[i].ypos-8.0f,
        0.0f,
        allofmybullets[i].color,
        allofmybullets[i].uvRIGHT,
        allofmybullets[i].uvTOP
      );
    big_buffer[big_buffer_counter++]=
      VERTEX2D(
        allofmybullets[i].xpos-8.0f,
        allofmybullets[i].ypos+8.0f,
        0.0f,
        allofmybullets[i].color,
        allofmybullets[i].uvLEFT,
        allofmybullets[i].uvBOTTOM
      );
    big_buffer[big_buffer_counter++]=
      VERTEX2D(
        allofmybullets[i].xpos+8.0f,
        allofmybullets[i].ypos+8.0f,
        0.0f,
        allofmybullets[i].color,
        allofmybullets[i].uvRIGHT,
        allofmybullets[i].uvBOTTOM
      );
  } // end of bullet-loop
 
  // now big_buffer_counter is
  // 4*nr_of_living_bullets
  // which is the number of all vertices
  // and big_buffer contains all vertices
 
  // NOW do the drawing:
  ...

I actually don't know about DX, but in OpenGL you could now just draw big_buffer.
From your DX-code it looks like you have to request a buffer from DX. You could now either request one of size (big_buffer_counter*sizeof(VERTEX2D)) and copy big_buffer into that, or you could record the number of living bullets in advance and, instead of putting the vertices in that temporary big_buffer, request and lock the DX buffer before the loop and put the vertices directly in it, avoiding a big memcpy.

Note:
I see you want to draw triangle-strips.
You won't get the expected results once you draw more than 1 bullet at once, because the GPU will then try to connect all your bullets...
You either have to add a degenerated triangle or instead build a list of triangles (recommended because easier).
So in your loop you'll have to create 6 (2*3) vertices instead of 4 and switch to D3DPT_TRIANGLE or whatever it's called.

Btw.: there is one important thing you did absolute correct in your code 
You use one texture for all your bullets, good!

[LorenzoGatti]

LorenzoGatti

LorenzoGatti

Show LorenzoGatti's last posts.

Show general stats for LorenzoGatti.

• 
• Jr. Member
• Score: 5
• Posts: 97

The tutorial is particularly brilliant, even for this forum.

Regarding virtual functions vs cache memory, I don't think there would be too many cache faults: realistically, different Behaviour instances might exceed one per bullet type, but most of them would be parametrized from only a few different Behaviour subclasses: a few short functions, maybe even close to each other in memory.
For example, Behaviour_Straight in the example hardcodes a speed of 5.0f: add a variable, and the same class can represent straight movement at any speed.

I once made a self-guided missile behaviour defined by maximum acceleration forward, backwards, sideways and in one arbitrary direction and by maximum acceptable angular and linear velocity.
Only 6 parameters allowed a single update function to cover an enormous range of behaviour: inexorably crawling towards the player (high free acceleration, speed close to the player's one), wide circles with poor handling (low angular velocity, medium to high speed, high forward acceleration and low backwards acceleration), accelerating too fast to be a threat (high forward acceleration and speed), braking to keep a collision course (similar backward and forward acceleration, moderate speed), swerving a bit towards the player from the launch direction and speed (no angular velocity, no longitudinal acceleration, some sideways acceleration), turning before dashing (forward acceleration only, moderate angular velocity, used for bullets that are emitted at very low speed) and so on.

Such a behaviour could be further generalized by smartness switches, like using dead reckoning or the current target position or going for the (possibly predicted) target location or for the midpoint between us and the target.

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

@LorenzoGatti
Thanks for the flowers  Glad you guys like it and find it useful so far.
Regarding your design comments: all true, nothing to add from my side.

[Tukun]

Tukun

Tukun

Show Tukun's last posts.

Show general stats for Tukun.

• 
• Newbie
• Score: 0
• Posts: 18

Code:

    big_buffer[big_buffer_counter++]=
      VERTEX2D(
        allofmybullets[i].xpos+8.0f,
        allofmybullets[i].ypos-8.0f,
        0.0f,
        allofmybullets[i].color,
        allofmybullets[i].uvRIGHT,
        allofmybullets[i].uvTOP
      );

Oh wow! I didn't even know that even possible. With  VERTEX2D();
It's a structure, not a function. When I try something like that, I get "error C2661: 'VERTEX2D::VERTEX2D' : no overloaded function takes 7 arguments".
EDIT: nevermind. Putting two constructors, one empty and one to define everything, fixed this problem.

And here I was, trying to do something really crazy.

Code:

  short bulletcount=32*4;  ///32 bullets, 4 vertices each.
VERTEX2D vertices2D[bulletcount];


for(int i=0; i<bulletcount; i+=2){static float h=1,f=0,f1=0;
vertices2D[i].color=D3DCOLOR_ARGB(255,255, 255, 255); vertices2D[i+1].color=D3DCOLOR_ARGB(255,255, 255, 255);
vertices2D[i].rhw=1; vertices2D[i+1].rhw=1;
vertices2D[i].x=allofmybullets[i].xpos-8; vertices2D[i+1].x=allofmybullets[i].ypos+8;
vertices2D[i].y=allofmybullets[i].ypos-8*h; vertices2D[i+1].y=allofmybullets[i].ypos-8*h;
vertices2D[i].U=f; vertices2D[i+1].U=f+1;
vertices2D[i].V=f1; vertices2D[i+1].V=f1;
h*=-1; if(f1){f1--;}else{f1++;}


}

and copy big_buffer into that, or you could record the number of living bullets in advance and, instead of putting the vertices in that temporary big_buffer, request and lock the DX buffer before the loop and put the vertices directly in it, avoiding a big memcpy.

Unfortunately, that's impossible. the big memcpy() is the only way to put the vertices directly into the buffer (at least that I know of. If there's another way, I'd love to know how).

If I wanted oh say, a 500 bullets cap, I'd do this before the critical runtime.

Code:

d3ddev->CreateVertexBuffer(2*3*maxnumberofbullets*sizeof(VERTEX2D),0,CUSTOM2DFVF,D3DPOOL_MANAGED,&d3d_vBuffer2Dim,NULL);
//here, I declared that d3d_vBuffer2Dim is my vertex buffer for all of my bullets, and created it
//within the device.
//2 triangles per bullet, 3 vertices per triangle(in this case, TriangleList. Each triangle must use
//seperate vertices, unlike STRIP- which shares the last two vertices to draw the next triangle

Since I'm using vertices within the buffer to define my xy coordinates of bullets on the screen and not matrices, I have to actually update the buffer every frame using a void pointer, as opposed to using the D3DX function to simply draw the same bullet over and over (I was going to try to do the latter until I've found out that's really, really bad.)

Code:

///this happens once per frame when I render my bullets.
///after their data, like position, is updated.
///earlier, I declared my vertices. VERTEX2D vertices2D[maxnumberofbullets];
d3d_vBuffer2Dim->Lock(0,0,&vPointer,0);
memcpy(vPointer,vertices2D,sizeof(vertices2D));
d3d_vBuffer2Dim->Unlock();

d3ddev->SetTexture(0,texture_bull);
d3ddev->SetStreamSource(0,d3d_vBuffer2Dim,0,sizeof(VERTEX2D));
d3ddev->DrawPrimitive(D3DPT_TRIANGLESTRIP,0,2);

And then I can use the drawprimitive function to actually draw every bullet in one call.
Is it efficient? Better than what I was going to do before reading this tutorial no doubt. But I can't help but think, "this is costly. There must be a way to update the buffer, instead of copying the memory of all the vertices to the whole thing." Bah, it makes me want to use this OpenGL you've been talking about. But I need to know how to do this.

EDIT: Thank you all very much for your outstanding help. I've managed to implement what I learned from here so far, and went from spawning 50 bullets at 30fps to spawning(and maintaining) 500 bullets at a nice 900fps. I hope what I've learned here will help me make games in the professional world.

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

@Tukun

I didn't even know that even possible. With  VERTEX2D()

Actually, I don't know if it's possible. It depends on how VERTEX2D is implemented, practically all of the code I posted here is just meant to be pseudo-code to point you into the right direction.

And here I was, trying to do something really crazy.

I took a look at that and here's my modified code with some advices:

Code:

  // if this is not const then you cannot create an array with it
  // (at least normally, maybe there are compilers that accept it,
  // bacause the value is known at that point)
  const short bulletcount=32*4;  ///32 bullets, 4 vertices each.
  VERTEX2D vertices2D[bulletcount];

  // move h,f and f1 out of the loop and don't make them static.
  // static has no benefit here, actually it is bad because
  // it will put h,f and f1 on the heap and restrict the
  // compiler when optimizing.
  // Note: h is handled in a few lines.
 
  float f1=0.0f;
 
  // f is never changed in your code, it always remains 0.0f,
  // so we can remove it.
  //float f=0.0f

  // the number 8 in your loop should be replaced by a constant
  // so you can easily change it:
  const float size=8.0f;
 
  // the h in your loop is always multiplied by 8 (or size after
  // our change). Not needed if precalculated once:
  float h=size;

  // the color never changes in your loop.
  // replace it by a const.
  const D3DCOLOR_ARGB col(255,255,255,255);

  // change the i+=2 to ++i and do the second increment
  // inside the loop.
  // Also reconstruct the loop's inner so both vertices are handled
  // one after another instead of interleaved.
 
  for(int i=0; i<bulletcount; ++i) {
    vertices2D[i].color=col;
    vertices2D[i].rhw=1;
    vertices2D[i].x=allofmybullets[i].xpos-size;
    vertices2D[i].y=allofmybullets[i].ypos-h;
    vertices2D[i].U=0.0f; // f was removed, always 0.0f
    vertices2D[i].V=f1;
    ++i;
    vertices2D[i].color=col;
    vertices2D[i].rhw=1;
    vertices2D[i].x=allofmybullets[i].ypos+size;
    vertices2D[i].y=allofmybullets[i].ypos-h;
    vertices2D[i].U=1.0f; // former f+1.0f is always 1.0f
    vertices2D[i].V=f1;
 
    // don't multiply if you don't have to.
    h=-h;
 
    // better don't do boolean or whatever equality checks on floats.
    // instead you can (ab)use the loop counter.
    if(i & 2) f1=0.0f;
    else f1=1.0f;
   
    // or a nice alternative:
    // f1=1.0f-f1;
   
  }

Unfortunately, that's impossible. the big memcpy() is the only way to put the vertices directly into the buffer

You should be able to do without the memcpy this way:

Code:

  // do this BEFORE your loop
  d3ddev->CreateVertexBuffer( 2*3*maxnumberofbullets*sizeof(VERTEX2D),
              0, CUSTOM2DFVF,D3DPOOL_MANAGED,&d3d_vBuffer2Dim,NULL);
  d3d_vBuffer2Dim->Lock(0,0,&vPointer,0);
 
  // now uncomment this line of the code from above:
  // VERTEX2D vertices2D[bulletcount];
  // and write this instead:
  VERTEX2D *vertices2D=(VERTEX2D *)vPointer;
 
  // now do the loop stuff from above
  ...
 
  // when the loop is done unlock the buffer
  d3d_vBuffer2Dim->Unlock();
 
  // and draw it

went from spawning 50 bullets at 30fps to spawning(and maintaining) 500 bullets at a nice 900fps.

Great, congratulations!

[Arpeggiodragon]

Arpeggiodragon

Arpeggiodragon

Show Arpeggiodragon's last posts.

Show general stats for Arpeggiodragon.

• 
• Newbie
• Score: 0
• Posts: 22

Very nice tutorial. Thanks for sharing!


It's actually quite nice to see someone like yourself using a very similar method of storing tightly packed bullets as I've been using for a while now. ( It's always in the back of my mind I wonder if there's some super-efficient secret way of doing this that I haven't thought of yet! -It's almost enough to drive one mad! hehe.. )

The only real difference it looks like is I'm not using shaders and support OpenGL 1.1 so the prepareRendering() is directly replaced by the bullet batching (..I guess that's actually the same now that I think about it), and I have no MAX_BULLETS declared so it can grow or shrink for different levels.

Code:

Bullet* GetBullet(){
//get bullet from the pool
if( free_pool.empty() )
  bullet = bullet_pool.push_back( new Bullet() );
else {
  bullet = bullet_pool[ free_pool.back() ];
  free_pool.pop_back();
  }
  return bullet;
}

void FreeBullet( Bullet* b ) {
  free_pool.push_back( b->GetIndex() );
}

End result being very similar, so I wish I had read this tutorial a few years ago as it would have saved me some trial and error.

Thanks again.

[relsoft]

relsoft

relsoft

Visit relsoft's website.

Show relsoft's last posts.

Show general stats for relsoft.

• 
• jelly
• Editor
• Sr. Member
• Score: 6
• Posts: 434

Nice tute!!!

There is a way to make runtime polymorphish very fast.  What you do is just limit your virtual access on a per-type basis instead of a per entity.  Just set up a container(factory) of each type and call those on update().

Here it is in action (DS homebrew).  Even at 66 mhz with a buggy processor, the system runs quite well.
Code is a little crappy as I made that game in just 2 weeks.

http://rel.phatcode.net/index.php?action=contents&item=Bubble_Fight_EX_DS

I just tested this syatem on my latest DS homebrew(Bullet-hell) and it still works quite fast.
 

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

[compile]

@Arpeggiodragon
@relsoft

Glad you like it

@Arpeggiodragon
I guess it always boils down to very similar implementations once you are no complete newby anymore.
Though yours and mine differ quite a bit: you use independant heap-bullets with two pointer-containers, I did it the one array one memory chunk way. You could support different bullet-C++-classes with embedded behaviour, I don't support virtual functions.
Nevertheless: your's will work just as fine. And the general interface is similar too.

@relsoft
If I get you right you chose to have one container per bullet type? That's yet another way of doing it (actually I used to do that myself). That way you can entirely skip any virtual functions and use template-based-compile-time-polymorphism, that's most likely the fastest way of doing things.
I traded a bit of speed in that area for (IMHO, matter of taste maybe) ease of use and flexibility by designing it so that you only need one single container for everything.
As being sad this isn't the fastest solution. It can maybe speed up by adding a simple sorting of new bullets by their behaviour/appearance (not that difficult).  That way you'd ensure that the same update/render-functions are called in a row, which would make it all more cache friendly.

But after all: such a simple manager will most likely never be the reason for performance problems, so why bother 

edit: typo, template-based-compile-time-polymorphism, not runtime, of course

[relsoft]

relsoft

relsoft

Visit relsoft's website.

Show relsoft's last posts.

Show general stats for relsoft.

• 
• jelly
• Editor
• Sr. Member
• Score: 6
• Posts: 434

I didn't use templates. I still use virtual functions (still runtime). I just limit my access.

Believe me, the DS ARM9 has a bug that instead of 66mhz, you get down to 8 mhz for accessing non-sequential data.

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

@relsoft

the DS ARM9 has a bug that instead of 66mhz, you get down to 8 mhz for accessing non-sequential data

Oh my! Of course, on such a platform every cycle counts.

[Lee Richmond]

Lee Richmond

Lee Richmond

Show Lee Richmond's last posts.

Show general stats for Lee Richmond.

• 
• Newbie
• Score: 0
• Posts: 2

Nice article (modulo a couple of typos in the example code).

It looks as though freeing a bullet will cause all subsequent bullets to be copied into a new position such that the bullet list remains packed (i.e. has no holes). Which means, if only the first bullet in a list of 1000 bullets is removed, 999 copies will be performed. Am I correct?

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

Nice article (modulo a couple of typos in the example code).

Thanks! That (pseudo)code never saw a compiler feel free to PM me a list of typos you found, I'll correct them.

It looks as though freeing a bullet will cause all subsequent bullets to be copied into a new position such that the bullet list remains packed (i.e. has no holes). Which means, if only the first bullet in a list of 1000 bullets is removed, 999 copies will be performed. Am I correct?

Yes, you're correct. "Only first bullet dead" is the worst case. In general this solution performs pretty well though, last not least due to its simplicity.

[Lee Richmond]

Lee Richmond

Lee Richmond

Show Lee Richmond's last posts.

Show general stats for Lee Richmond.

• 
• Newbie
• Score: 0
• Posts: 2

Ah, then it's worth mentioning a little optimisation which results in only exactly one copy per freed bullet, no matter where in the list the bullet was:

Code:

void Deallocate( unsigned index )
{
    id_index_table[bullets[index].id] = next_free_id_slot;
    next_free_id_slot = bullets[index].id;
    bullets[index] = bullets[--active_bullets_count];
    id_index_table[bullets[index].id] = index;
}

void Update()
{
    unsigned index = 0;
    while ( index < active_bullets_count )
    {
        bullets[index].Update();
        if ( !bullets[index].active )
            Deallocate( index );
        else ++index;
    }
}

This is how my particle engine works (minus the bullet id management, which is presented here untested). The idea is to copy whichever bullet is last in the in-use-list over the freed bullet, then decrement the in-use-count. The issue then becomes ordering. While the list will remain packed, the order of bullets in the list will change over time. This is usually fine when bullets rarely overlap or when overlapping isn't an issue due to, for example, blending (such as in my particle system).

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

Yes, I use the exact same approach for additive particles myself (and in the discussion of my other tutorial I wrote about that same technique  )

But for bullets the order is usually very very important, that's why I won't recommend that technique and don't use it myself. Only if there are really just a few bullets and if it's 100% safe to asume they never overlap you can get away with that. Otherwise you will probably get ugly order changes all the time. And it really looks very ugly even when it happens seldomly.

[kdmiller3]

kdmiller3

kdmiller3

Visit kdmiller3's website.

Show kdmiller3's last posts.

Show general stats for kdmiller3.

• 
• Hero Member
• Score: 4
• Posts: 738

Shifting the bullet entries down isn't so bad since you have to sweep through all of them during update anyway.

[CrazyFoo]

CrazyFoo

CrazyFoo

Show CrazyFoo's last posts.

Show general stats for CrazyFoo.

• 
• Newbie
• Score: 0
• Posts: 11

This has been another very useful tutorial for me, however I would like to ask a question or two if possible.
First of all, in the Update() part of the bullet manager near the top of the main for loop with the first conditional statement as follows:

Code:

    void Update(void) {
      unsigned int l_new_index=0;
      for(unsigned int t=0;t<active_bullets_count;++t) {
        Bullet &l_bullet=bullets[t];
        l_bullet.Update();
        if(!l_bullet.active) {
.
.  
.
}   
};

shouldn't the test be if(l_bullet.active) ? At the moment if a bullet is inactive it seems the code does the sort of things it should be doing on active bullets on inactive bullets. When I used the code as stated above in a test it wouldn't work and kept causing runtime errors, after a few hours of going through with the debugger and a little desk checking of the code I changed the test to if(l_bullet.active) instead of if(!l_bullet.active) and it seems to work just fine!

Additionally, please chastise me if I'm being a tad naive, but couldn't this be used as a general entity manager for almost everything in the game that has a sprite, moves and is active? For example instead of a bullet description it could be an 'entity' description with its own appearance and behaviour. The management code would do all the relevant checks/updates etc for enemies, bullets, floating power ups, whatever you wish. It's very very useful and has been extremely helpful for me using the code in this way. Cheers Hornet!

Also thanks in advance if anyone answers my little queries.

Respect,
Lloyd

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

Hi Lloyd,

shouldn't the test be if(l_bullet.active) ?

Yes, you're right of course, thanks for finding that typo. Fixed 

couldn't this be used as a general entity manager for almost everything in the game that has a sprite, moves and is active?

Sure. I made it with bullets in mind but if your game structure allows it, why not use it for other stuff as well.

It's very very useful and has been extremely helpful for me using the code in this way.

I didn't have time to use / try it myself until now (was done from scratch without compiler when I one day felt like writing another tutorial  ), so it's good to hear that you use it with success. Then I'll do so myself in my next shmup-project

[Spiffl]

Spiffl

Spiffl

Show Spiffl's last posts.

Show general stats for Spiffl.

• 
• Newbie
• Score: 0
• Posts: 4

Hi, guys. I'm sorry to resurrect this topic, but I'm sure people are still reading it nowadays anyway, right? Anyway, I'm on my way to understanding what's going on, but I have a really, really basic question... what's a "vec2?" You have two of them right there in the bullet class definition, and though from their descriptions it seems they should just be some sort of real number, you use a "vec2." I tried googling it, too, but no luck

Sorry if this question is really elementary.

EDIT: oh, okay, it seems it's an OpenGL thing? That makes sense, since you've mentioned OpenGL in your other tutorials. Do I need to use OpenGL to do this stuff?

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

oh, okay, it seems it's an OpenGL thing?

No, it's not.
I suppose you found some GLSL info, it uses the same name. GLSL's vec2 does the same thing as the vec2 I am mentioning, but nevertheless the code above itself has nothing to do with OpenGL.

what's a "vec2?"

It's a user defined data type that implements the functionality of a 2-dimensional-vector. In C++ this usually coresponds to a class with 2 floating point attributes and a bunch of methods and operators for the math such a vector normally needs.

This is such a basic tool that I asume everybody has something like vec2 at hands. Since there are tons of 2D vector classes around and since you may also have implemented your own, I simply used a more or less "neutral" name for it. Simply replace all "vec2" in the code by the vector class' name you use.

Search the web for something like "vector 2d class c++" to get more info.

[Spiffl]

Spiffl

Spiffl

Show Spiffl's last posts.

Show general stats for Spiffl.

• 
• Newbie
• Score: 0
• Posts: 4

Okay, I getcha! Yeah, I do already have a class to do that sort of stuff.

I've got another question. The current setup seems to create a circular include dependency. Bullet contains pointers to Appearance and Behavior, but both of these utilize pointers back to Bullet. How can I resolve this? It seems like you guys must have done something I didn't...

Other than this issue, I've read through this whole thread multiple times and feel like I really have a handle on it. Thanks a BUNCH for the great tutorial and ideas, fellas.

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

The current setup seems to create a circular include dependency. Bullet contains pointers to Appearance and Behavior, but both of these utilize pointers back to Bullet. How can I resolve this?

You're right. That's because I inlined some implementation code inside the header files to make the tutorial code more compact.
To resolve this do the following:

- don't include "Bullet.h" in "Appearance.h" and "Behaviour.h"
- instead forward-declarate bullet in those, simple by typing "class Bullet;" somewhere at the top of the files.
- don't use code that calls methods of bullet inside the those files.
- instead put such method-implementations in the coresponding .cpp file - and include Bullet.h in that one!

Thanks a BUNCH for the great tutorial and ideas, fellas.

You're welcome