Skip to main content
GameDev.net gamedev.net
🔒 Locked

Circular buffer usage

Started by pressgreen Jun 29, 2013 at 6:01 PM 6 replies 3.2k views
Original Post
pressgreen
pressgreen

So i am reading about the Circular Buffer. I personally have never used one but it seemed intriguing. Could some one share some scenarios for its optimal usage vs regular delineated buffer, for those of you that are familiar with its usefulness. Like when is it appropriate vs not appropriate?

J-GREEN

Greenpanoply
Paradigm Shifter
Paradigm Shifter

Use it when you want a double-ended queue rather than an array. Input buffers are a good use case for this (you read from one end and new data [i.e. fresh input] is added at the other end).

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley
Mussi
Mussi

Lets say you have a game with a rewind functionality, where your character can travel back in time. You'll most likely have a cap on how far one can rewind. At any point in time, you'll have to know the x steps taken before the current step. Now imagine how easy this becomes with a circular buffer smile.png.

SillyCow
SillyCow

Having a circular buffer prevents you from allocating new memory.

It also prevents memory fragmentation.

Both of these problems will cause performance drops.

Any task that involving queues where performance is an issue will benefit from a circular buffer.

They are also in use in hardware and embedded programming.

Here, memory allocation (new / malloc ) is sometimes not available.

My Oculus Rift Game: RaiderV My Android VR games: Time-Rider& Dozer Driver My browser game: 
Paradigm Shifter
Paradigm Shifter

Yeah, as I said anything a double ended queue is good for is ideal (as long as the queue has a fixed maximum size - although it can be resized of course. For efficiency reasons you will probably prefer a buffer size which is a power of 2 so you can use logical AND rather than modulo arithmetic to wrap the buffers).

More use-cases:

Message system (read messages from front of queue add new messages to the back of the queue).

Bubble Bobble (Puzzle Bobble? Maybe?) scrolling-type games where new tiles are added to the top of the screen and tiles are removed from the bottom of the screen.

Rewind buffer (already mentioned)

Text window with limited history (already mentioned)

Undo buffer with limited undo

etc.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley
prh99
prh99

I know they are used in LZMA and LZSS compression as way to create a sliding window for the algorithm and in various aspects of digital signal processing.

Patrick
Khatharr
Khatharr
Circular queues are common when decoding audio, which is an example of a producer/consumer queue like Night mentioned.
void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.