Please note that I don't update this web site anymore. You can visit my new personal blog at www.williamwilling.com.

Static Render Lists

Thursday, May 19, 2005

Trichromix uses what I call a static render list to make rendering more manageable. The idea of render lists is far from earth-shattering, it's not even new, but I found the use of render lists quite convenient.

Essentially, a static render list is a collection of pointers to the bitmaps that need to be rendered plus their screen coordinates. From this, you can probably derive that I'm talking strictly about two dimensions here. I call the render list static, because you determine the size of the render list before you use it, i.e. at compile-time. There is something to be said for creating a dynamic render list that allows adding and deleting visual elements at run-time, but a static render list has a couple of advantages, which I will get to in a moment.

Implementation

Before I go into the pros and cons of static render lists, let me show you the C++ code to implement them.

class Bitmap;

class RenderListItem
{
    Bitmap* Bitmap;
    int X, Y;
};

typedef std::vector RenderList;

That's all there is to it. Just a list of bitmaps we want to draw and information on where to draw them.

Using the render list

As I said, you determine the amount of visual elements the render list will hold before you compile your code. Once the render list is created, you can refer to each render list item by index. Suppose, for example, that we want to draw two visual elements: a background and a button. I'm going to assume the bitmaps are already loaded. The code would look like this.

RenderList renderlist(2);

renderList[0].Bitmap = &backgroundBitmap;
renderList[1].Bitmap = &buttonBitmap;
renderList[1].X = 150;
renderList[1].Y = 100;

Now, if someone presses the button, you need to change the bitmap. That's very easy to do.

renderList[1].Bitmap = &buttonPressedBitmap;

Note that I didn't set the coordinates again. All you have to do is change the bitmap pointer and the next time the render list gets rendered, the button looks pressed. Rendering the visual elements in the render list is trivial. Just iterate over the list and draw each bitmap.

for (RenderList::const_iterator it = renderList.begin(); it != renderList.end(); ++it)
    DrawBitmap(*it->Bitmap, it->X, it->Y);

Improving the code

Using hard-coded indices doesn't really add to the flexibility and maintainability of your code, so we'd be wise to get rid of them. C++ provides an easy solution: enums. Since C++ allows us to use enumeration values as if they are integers, we can use them as named indices.

enum VisualElements
{
    Background,
    Button,
    ElementCount
};

RenderList renderList(ElementCount);

renderList[Background].Bitmap = &backgroundBitmap;
renderList[Button].Bitmap = &buttonBitmap;
renderList[Button].X = 150;
renderList[Button].Y = 100;

This way it's very easy to refer to items in the render list. Notice the enumeration value of ElementCount. Since C++ always starts enumerating at 0 and increases by 1 for each value (unless specifically told otherwise), making ElementCount the last enumeration value gives us an easy way to determine the number of render list items we need.

A full, working demo

You can download my render list demo (.zip, 137KB) to see a working example of static render lists. You'll find most of the code of interest in Application.cpp. You can see in void Application::ToggleEarth() how I determine the application's state using the render list. This isn't something you'd normally do, but from time to time it can be convenient. More on this in a minute.

I wrote and compiled the code using Visual Studio.NET 2003. Although I haven't tested the demo with other compilers or on non-Windows platforms, it should be trivial to port. The only Windows-specific code is in the function bool Error(const string&) found in Error.cpp. If you replace the entire body with something like throw FatalException(errorMessage); or, if you find that to drastic, return true; you should be good to go.

The demo uses SDL for graphics and input handling, so you need to have it installed properly if you want to build the demo. I'm going to assume you know how to compile and link against SDL. If not, then you'll just have to look at the code without being able to run the demo. The source code is far more interesting than the compiled binary anyway.

Usefulness

It may not seem like static render lists help you much. After all, you can just as easily create a function that renders bitmaps based on the state of the game model. However, render lists give you a couple of advantages:

  • You can specify the bitmaps you want to draw at any time.
  • You only have to change the state when it's different from the last time you rendered.
  • You don't have to keep render state in your game model.
  • Using render lists is completely optional.

Let's say you are programming an RTS with units walking all around the playing field. To increase usability you decide that a unit should light up whenever the player hovers the mouse cursor over the unit. This means that you need to respond to mouse movement, determine whether the cursor is positioned over a unit and, if it is, render a different bitmap for that unit. I suspect most programmers wouldn't actually call DrawBitmap() right there in their event handling code. That could lead to all kinds of problems with the ordering of the bitmaps.

However, with render lists, you can change the bitmap that needs to be drawn in the event handler without a problem. The actual drawing doesn't take place until later, so there are no ordering issues. You don't need an extra function that will be executed right before rendering takes place to determine which bitmap to draw. Furthermore, you can 'overwrite' the bitmap with minimal overhead. Maybe, after you've determined the mouse cursor is hovering over a unit, you discover that the unit is currently selected and that you need an entirely different bitmap for that. You can just change the bitmap again, without the need to put the code that tests for hovering into a big if-clause. If you were drawing the bitmap right away, this would be way too slow, but with render lists this painter algorithm drawing style is no problem. In short, you can put the drawing instructions wherever it makes most sense.

Also, you don't have to clutter the code of your game model with state information that is relevent only to the view. Whether a unit is hovered or not is (presumably) of no consequence to the game itself. Yet, if you don't want to call DrawBitmap() from you mouse movement handler, you will need to keep the visual state of the unit somewhere and a likely solution is to put an extra variable in your Unit class. This means you end up with code that relates to the view only within your game model and that's not very nice. If you use a render list, this isn't necessary. Which bitmap to draw is now a matter of the view and the game model never needs to know.

Finally, note that using a render list is completely optional. You aren't forced to put all your bitmaps into a render list if it doesn't make sense. If you're game involves a lot of creating and destroying of visual elements, then a static render list is not a good option. Fortunately, there is nothing stopping you from by-passing the render list and drawing to the display surface as usual. Better yet, you can draw the parts that use bitmaps dynamically in the normal way and use a render list for other areas, like the HUD. You can also have multiple render lists, if you so please.

Caveats

There are of course some trade-offs, some of which I already touched upon. Here is a list of things you need to keep in mind. The first item in the list is actually the only real downside of static render lists, the other items just need some additional code to solve.

  • You shouldn't use static render lists when you create and destroy visual elements all the time.
  • You can't change the z-ordering of the visual elements dynamically.
  • The bitmap pointer of the RenderListItem may be invalid.

Since the number of visual elements a render list holds is static, it won't do you much good in scenes that are visually highly dynamic. For example, games where you have to blow up things are not likely to benefit much from a static render list. You could get around this by creating a large static render list that can hold the maximum amount of visual elements on screen and then mark the destroyed ones as invisible, but it probably wouldn't be worth the trouble.

In the code I've given you, the z-ordering of the visual elements is determined by their indices into the render list. The first element in the list is drawn at the bottom, the second on top of that, and so on. In most cases this isn't a problem; if you can specify in your code which elements will be visible on the screen, you can usually determine their z-order beforehand, too. However, if you are writing something like a point-and-click adventure game, you might need a bit more flexibility in this area. It wouldn't be too hard to adjust the above code to allow this, but to keep things simple and because most of the time you won't need it, I left dynamic z-ordering out.

As always with C++, you need to give careful thought to the issue of ownership. Each RenderListItem object keeps a pointer to a bitmap, but if that bitmap goes out of scope before the render list does, you have a dangling pointer and a serious problem. There is no way to detect this in your code, so you will just have to make sure render lists survives the bitmaps they can contain. You could use a shared_ptr from the Boost library or you could write your own bitmap manager to deal with the problem. Since you run into this issue whether you use render lists or not, I'm just going to assume you have your own way of dealing with this already.

In conclusion

Static render lists are great for rendering GUIs and HUDs or for 2D games that don't have a lot of visual action going on, like puzzle games or adventure games. If you have never used a static render list, it might not seem like much of an improvement, but the proof of the pudding is in the eating. A static render list is easy to implement and easy to use, so there is nothing in the way to keep you from experimenting with them. The code I provided is quite minimal and there is a lot of room for extending the render lists with the functionality you need. If you find a nice application of render lists or if you run into trouble using them, please leave a comment.

Back to blog index

Comments

Wouter Lindenhof says:

Actually, there is a easy way to solve the out-of-scope problem with you're going rampage by destroying and creating visual elements. Instead of saving a reference, you save a number. The GraphicsEngine should have acces to all bitmaps since they belong to them. The Graphics Engine will check each run if the bitmap does exist by checking the list and not the memory location. I found out that a game infrastructure should be like a database, this way you have more control and when things are missing you won't have any problem since you don't access the data it self. The only _HUGE_ drawback is that the time needed to calculate increases. But since applications using DirectDraw are using the processor for 99% for converting to bitmap for GraphicsCard you will notice a slight but most likely no impact on system performence.

Thursday, May 19, 2005 3:01 PM


Joost Ronkes Agerbeek says:

I'm not completely sure I understand what you're proposing. Are you suggesting that a function like GraphicsEngine::LoadBitmap will return an integer an you then render the bitmap by calling GraphicsEngine::DrawBitmap(int)? If so, then what do you mean by "time needed to calculate"? What is it you need to calculate? If you just use a vector to store the bitmaps, you can use bitmap numbers as indices. You could look up a bitmap in constant time.

Thursday, May 19, 2005 3:18 PM


GBGames says:

Regarding enumerations: They are not strictly another name for integers, but the way you use them is fine. http://www.parashift.com/c++-faq-lite/newbie.html#faq-29.18 That one and the one under it say that you can use enumerations to do this: int n = EnumeratedThing1; but you can't do this: EnumeratedThing n = 1; This is a great post, and I will definitely think about using SRLs in the future. I use the Kyra Sprite Engine now, and I think it does something similar in a dynamic way, but I can see how they would be useful.

Thursday, May 19, 2005 5:44 PM


Wouter Lindenhof says:

The suggestion you made was correct. The idea I has was making the game more like a database. This makes it easier the handle. However in a database you don't have refences with data. Instead you have to search each and every time for the data with the number you got. Since this is less direct it requires a few more calculation. Do it with every 'reference' and it will gain some time.

Friday, May 20, 2005 1:44 PM


Joost Ronkes Agerbeek says:

I still don't understand what you need to calculate. If you create a struct containing a pointer to the resource and a boolean that indicates whether the resource still exists, you can just put instances of the struct in a vector and return the index. When somebody retrieves the bitmap, you get the struct out of the vector (which is fast), check the boolean value and return the pointer. It seems to me that the overhead is negligable. I think the system you propose has some problems if you need true resource management, but lack of speed isn't one of them. In fact, I think you have effectively solved the problem of invalid pointers without introducing noticable overhead.

Friday, May 20, 2005 3:17 PM

Tell me what you think

Since I'm not updating this site anymore, I disabled comments. You can visit me at my new site: www.williamwilling.com.