HTML and CSS Reference
In-Depth Information
Bottlenecks in an Update Loop
Most commonly, when it comes to performance, the biggest bottlenecks in an update loop can be found in two places.
The first one is the painting routine because painting pixels on the screen is an extremely expensive process, as you'll
remember from the last chapter. The second one is the physics calculations.
The reason why you have spent a considerable amount of time learning the definition of framerate and how
to define a proper update loop is because both will aid you in the implementation of a rock-solid and extremely
performant update routine that separates the paint process from other calculations.
That being said, let's shift focus to the topic at hand. Minimizing or completely eliminating the impact of a
performance bottleneck is not an easy task. Many times it requires several days of intense profiling or searching
(or even inventing) the right algorithm. Keep in mind that micro-optimizations will only result in micro-improvements.
Real performance gains can only be made when you tackle the elephant in the room: the slowest and most CPU/GPU
demanding parts of the routine.
Back in the day, computers came with CGA cards, which included a color depth of 4-bits (16 different colors)
at a maximum of 640×200 pixels, and 16 kilobytes of video memory. Even though they were revolutionary at the time,
they lacked the necessary features to support scrolling in hardware, which meant that scenes had to be redrawn in
software, frame by frame. Additional limitations of processing power meant that making side-scrolling games was
practically impossible.
In order to overcome this limitation, John D. Carmack (one of the Founders of ID Software and creator of games
such as Wolfestein, Doom, and the Quake series) invented a technique called Adaptive Tile Refresh (ATR) that
combined the “extra” space in EGA cards and used them as double-buffers in combination with an extremely popular
technique that we nowadays refer to as dirty rectangles.
Dirty Rectangles
From web browsers to video streaming algorithms to videogames, the use of dirty rectangles has been and continues
to be one of the most efficient graphical algorithms that can be used to repaint small changes within a bigger image.
Best of all, the algorithm itself is quite simple to understand and implement.
The concept behind dirty rectangles is that usually on certain types of applications there is no need to repaint the
entire image when there is a small variation (such as a character moving, or an object appearing or disappearing). In
order to deal with this problem, you can think of an image as a grid. When something changes, you flag the affected
cells as modified; when it's time to repaint, you only have to repaint the flagged cells. Obviously, the reason why there
is a possibility of using algorithms like dirty rectangles in HTML5 Canvas applications is because the canvas object
works in immediate mode; whatever you draw on the screen will stay there until you draw something else on top of it,
or you clear the screen.
One possible way to implement this algorithm consists of subdividing the screen into many columns and rows,
and then when all of them are drawn on the screen, you mark them as “unmodified.” When some other object within
the screen moves, you need to calculate which of the cells are affected and mark them as “modified” or add them to
a list of “modified cells.” When the update loop is triggered again, the only thing you have to do is to cycle the list of
modified cells and re-draw those cells. Figure
8-1
explains how this would work in practice.
