RE: [boost] Re: circular_buffer?

From: Reid Sweatman (reid_of_diamonds_at_[hidden])
Date: 2001-02-27 16:10:37

In that situation, I usually find it much more efficient to allocate a
vector of the size I want (the vector will never change size), and two
stacks.  To initialize the mechanism, I create the vector with default
objects, then push all the possible vector indices onto one of the stacks,
which becomes my free pool.  As I actually create real objects in the
vector, I pop an index from the pool, assign object data to the object in
that location using the vector [] operator and the index, then push the
index onto the other stack, which is my active object stack.  Killing an
object is just the reverse, and you needn't assign default values to the
unused vector location, because you're only going to access it when its
index comes back off the free pool stack, anyway.  All this is really
trivial to do with STL objects.  One fillip:  the "in-use" stack I usually
implement as a vector instead of a stack, because in some usages it can be
important to access the objects in a particular order, and the STL stack is
a little restrictive about that for my taste.

This is the fastest way I've found of doing it, so long as you need to visit
each object currently in use at least once, in which case you just use an
iterator to traverse the in-use stack.  No allocations, no deallocations.  I
was once handed the rain module from a game that gary_at_sierra would recognize
to incorporate into another game that shall remain nameless due to NDA.  In
the original game the rain was pretty sparse, and it remained so when I
incorporated it, no matter how fast I told it to run.  It was CPU-bound by
the allocation/deallocation and a very brain-dead way of finding active
things in the vector.  I rewrote it as I've described, and had so much rain
you couldn't see anything else in the frame, even with the raindrops' alpha
set practically transparent.  Give it a shot.  I'd send you the pertinent
module, but again, unfortunately, NDA, and I don't have the property rights,
anyway.  But I've described the method, and it's pretty simple.

Reid Sweatman
Software Engineer

> -----Original Message-----
> From: boost_at_[hidden] [mailto:boost_at_[hidden]]
> Sent: Tuesday, February 27, 2001 11:49 AM
> To: boost_at_[hidden]
> Subject: [boost] Re: circular_buffer?
>
>
> Actually, neither of these is what I'm looking for.
>
> Basically, (as a hobby) I am writing yet another shoot-em-up game. The
> tried and true technique for managing bullets, ship thrust, bullet
> holes etc.  is to have a "ring buffer" or
> "circular buffer" with a fixed maximum size.
>
> You want a maximum of, say, 1000 bullets on the screen. As soon as the
> ship fires the 1001st bullet, the 1st bullet "disappears". In terms
> of the buffer, asssuming it has a fixed size of "1000". When you add
> the 1001st entry, it overwrites the 1st entry.
>
> The advantages are twofold:
> 1. You want to limit the number of artifacts anyway - having more
> than 1000 bullets, for example, would slow down the frame rate
> 2. It is efficient because it never needs to allocate memory.
>
> It's pretty easy to do - but I was hoping for an "STL-friendly"
> version so that I can write
>
>
> std::for_each(bullets.begin(), bullets.end(), draw_bullet);
> std::for_each(bullets.begin(), bullets.end(), animate_bullet);
>
> etc.
>
> and
>
> void ship::fire_bullet()
> {
>    g_bullets.push_back(bullet(initial_bullet_velocity_));
> }
>
> the idea being that g_bullets.capacity() would never increase unless
> you explicitly called reserve().
>
> So in the above example, I would want the push_back call to just
> silently overwrite the oldest bullet, if the buffer was full.
>
> Of course, a ring buffer like this is also useful for many network
> protocols that keep "sliding windows" of messages that might need to
> be resent etc. Most protocols define a "maximum" size of such a
> window - again, any error would occur only if you couldn't find an
> entry in the buffer at a later point, not when you are inserting a
> new entry (and thus possibly overwriting the oldest entry).
>
> These are the type of problem domains a ring_buffer or
> circular_buffer would be used in.
>
> Paul Hollingsworth
> http://PaulHollingsworth.com
>
> --- In boost_at_y..., Howard Hinnant <hinnant_at_t...> wrote:
> > There were two ideas floating around:
> >
> > 1.  A circular_buffer that would extend its capacity when necessary
> > (similar to vector and deque).
> >
> > 2.  A circular_buffer that would throw an exception if the capacity
> was
> > exceeded.
> >
> > Which one (or both?) are you interested in?
> >
> > Personally I'm only interested in #1, and am willing to donate the
> > interface to an existing implementatation (taken pretty much from
> vector
> > and deque).  Unfortunately I can not donate the implementation
> itself,
> > but I would be happy to participate in and discuss design decisions
> on
> > such an implementation.
> >
> > -Howard
> >
> > boost_at_P... wrote on 2/24/01 6:30 PM
> > >Hi everyone,
> > >A while back there was a thread talking about a circular_buffer
> > >class. Does anyone know what happened?
> > >
> > >It would find it to be very useful.
>
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>