Re: [boost] Re: circular_buffer?

From: Paul Hollingsworth (boost_at_[hidden])
Date: 2001-02-28 01:49:32

Hi Reid,
After puzzling over what you said, I think I understand the problem that
you're solving.

You're talking about being able to free objects in any order, not just the
order in which they were "inserted".

I was just talking about a simple sliding window implementation, mandating
that you pretty much can't delete objects to free up space.

But your mechanism is much more general, and useful for my game ;-)

It is a fantastic solution! Thank you!

Paul Hollingsworth
http://PaulHollingsworth.com
----- Original Message -----
From: "Reid Sweatman" <reid_of_diamonds_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Tuesday, February 27, 2001 3:10 PM
Subject: RE: [boost] Re: circular_buffer?

> 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/
> >
> >
> >
>
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>