Tricks of the Game-programming Gurus

Mentioned 5

This book explains the concepts and ideas behind the development of a flight simulator, a 3-dimensional walk-through game, and the utilities used to manipulate video, audio and input devices.

More on

Mentioned in questions and answers.

I need to speed up a program for the Nintendo DS which doesn't have an FPU, so I need to change floating-point math (which is emulated and slow) to fixed-point.

How I started was I changed floats to ints and whenever I needed to convert them, I used x>>8 to convert the fixed-point variable x to the actual number and x<<8 to convert to fixed-point. Soon I found out it was impossible to keep track of what needed to be converted and I also realized it would be difficult to change the precision of the numbers (8 in this case.)

My question is, how should I make this easier and still fast? Should I make a FixedPoint class, or just a FixedPoint8 typedef or struct with some functions/macros to convert them, or something else? Should I put something in the variable name to show it's fixed-point?

The original version of Tricks of the Game Programming Gurus has an entire chapter on implementing fixed-point math.

Basically, I want to use a line algo to determine which cells to check for collisions for my raycaster.

Bresenham isn't great for this as it uses a unified-thickness approach, meaning that it ignores cells that aren't at least half-covering the line. Not great at all, because it means that some segments of my line aren't being checked for intersections with the cells, leading to errors.

I can't seem to find any "thick-line" algorithms, can anyone help me find one?

Red: Bad. Green: Good!
Green: What I would like.
Red: What I currently have and don't want.

You could find all the intersections your ray has with the horizontal grid lines, and then mark all the cells on a row that either have an intersection point on one side, or are between the two cells with the intersections on the row.

Finding the intersections can be done by starting from the origin, advancing the point to the first intersection (and marking the cells in the process), finding out the vector that takes you from an intersection to the next (both these operations are basic similar triangles (or trig)) and then advancing column by column until you've gone far enough. Advancing column by column involves one vector addition per column, and a small loop to fill in the cells between the ones with intersections. Replace "mark" with "process" if you're processing the cells on the fly - this algorithm is guaranteed to mark each cell only once.

The same could be done with the vertical lines, but grids are generally stored in horizontal slices so I chose that. If you're using trig, you'll need to handle straight horizontal lines with a special case.

By the way, as far as I know, this is how old grid-based raycaster "3D" games (like Wolfenstein 3D) were done. I first read about this algorithm from this book, eons ago.

I'm writing a Python-module which should provide an easy OOP interface to low-level GUI platforms. To achieve this, a wrapper class needs to be created that is used by the classes in the module.

This is the (yet) class-diagram for the basic implementation.

class diagram

This question is actually not about the design of the package, but if you have questions to it or have an idea what might be better, I won't mind any comments/critics.

The DrawArea class is the glue between the low-level platform and the classes in the package. Events usually start here, as the wrapper should recognize mouse-/keyboard-events and inform it's children about it.

Now, as you can see, the DrawArea class needs to implement some functions to render basic elements onto the GUI. Now, I'd like to get to know about the magic behind rendering circles, rounded rectangles, lines (with a thickness) and about anti-aliasing. One reason for it is that I'm simply interested into that topic, the other is that I'd like to deliver an implementation with the package. (Will be written in C/C++, I'm pretty sure Python would be tot slow for such rendering operations, isn't it?)

Now my questions:

  1. Are there any good references for how to render circles, ellipses, rounded rectangles, or lines (with a thickness, the one-pixel-line is easy..)?
  2. Are there any good references for how to implement anti-aliasing?
    • E.g., is anti-aliasing done while rendering an element or applied after all rendering-operations have been done?
  3. Would it be better to use something like a Path class that will be rendered? I.e. a vectorized representation of the form that should be rendered. That would have the advantage to render any kind of 2-dimensional forms, but I don't know how to implement it. Are there good references for rendering vector-graphics?

Anti-Grain Geometry - High Fidelity 2D Graphics - A High Quality Rendering Engine for C++ is a programming library, which is my favourite choice for rendering vector graphics.

You might like to make a wrapper of it (take a look at documentation ), look into sources or ...

Jump to Research section where you can find a lot of information how to do : "High Fidelity 2D Graphics - A High Quality Rendering". Brazier lines and other topics are mentioned there. My favourite section is "Texts Rasterization Exposures" about sub-pixel rendering.

If you are interested how to optimize drawing lines, polygons etc even on C+assembly level,

Here as example of one of many 2D Computer Graphics algorithms:

can someone point me to some methods for perspective ray casting. I have seen ray splitting techniques. What other casting methods are available? Which one is easiest to implement?

Follow this Ray-Casting Tutorial For Game Development And Other Purposes by F. Permadi. It describes the easiest method. It was also described in the Tricks of the Game-Programming Gurus book by André LaMothe.

I've implemented it several times. Takes ~1K lines of code or less (depending on your programming language and how advanced you want your raycaster to be). Basic school math.