How to handle the overlapping of source lights in a 2.5D browser game
Drawing sprites (images) on the browser canvas is a very efficient process. We can rely on it as long as we don’t abuse it.
Due to the 2.5D nature (perspective) of Lost In Maze, it is not possible to draw just a part of the canvas: there is always some missile flying among trees, for example. At each loop, we have to redraw the whole canvas with sprites in a sequence that respects the perspective of the scene.
Drawing everything at each loop may demand too much from the system. Considering that, Lost In Maze was designed to run at 30 FPS (frames per second), and uses some smart algorithms to no not stress the system.
Actually, it runs very smoothly. Each loop of the game takes only one or two milliseconds to run (in Chrome). The computer processors do not heat up (they stay below 60 °C) and the player experience is the same as when old versions were running at 60 FPS.
Check Can Browsers Actually Run At 60 FPS? if you want to know more about browser performance for games.
In Lost In Maze there are three modes for lighting. We may call them Daylight mode, Torch mode and Bonfire mode.
In daylight mode there are no lighting effects. Even when there are bonfires in the picture. It is just drawing the sprites.
In Torch mode, the environment is dark. There is only one source of light. It is the torch that the avatar carries. As the avatar is always placed in the center of the game canvas, the center of light is also always in the center of the game canvas; it doesn’t matter whether the avatar is standing or “moving”.
I bet you know how to do that. It is just drawing the game canvas, like in the Daylight mode, and then drawing a shadow layer (translucent radial dark gradient) over it.
It is a small paradox. Applying light means darken the picture. In fact, we apply shadow, not light.
The shadow layer may be created on the client (browser) with a formula similar to the one used to create the shadow for bonfire:
It is a piece of cake. We only have to ensure that the darkness cover all the borders of the game canvas, and that the most clear part is in the center of it.
In Bonfire mode the environment is dark and there is at least one bonfire at the scene. So its light may overlap with the light of the avatar’s torch and with the light(s) of other bonfire(s). Notice that a bonfire light is attached to the environment; it moves in the game canvas when the avatar is “moving”. Even when a bonfire is not part of the scene, if its position is next to the scene, its light must be considered.
What troubles Bonfire mode is handling (efficiently) the overlapping of lights.
Time for a small convention: from now on we will talk only about applying shadows and overlapping shadows, because that is what we are really doing on the game canvas. We are not lighting the game canvas we are darkening it.
Following the principle of Baby Steps, let’s start with a solid and simple foundation to study, this raw scene:
Then we simply draw a shadow for each bonfire. We will be using a smaller bonfire shadow (270 x 270 pixels) because it is better for understanding.
A shadow alone is OK. But the overlapping of shadows is a mess. The center among three bonfires should be absolutely clear, but it is absolutely dark.
It is not a bug of the program. The program is correctly overlapping shadows. The problem is that what we need is overlapping lights, not shadows! Using shadows is just a workaround!
For efficiency, the far best we have is the canvas method drawImage. But using it alone produces the naive shadow overlapping that we saw.
I scratched my head a lot and have found out two solutions. The first is simple and funny. The second is fast and produces a more desirable lighting effect for Lost In Maze.
The shadow layer
Both solutions need a shadow layer. That is the canvas were all shadows are composed (overlapped). After composing the shadows, we draw the shadow layer over the game canvas.
The shadow layer must match the dimensions of the game canvas. Or, for optimization, be a proportional exact reduction of it.
Overlapping shadows — the first solution
As the second solution is better, this time we will not see the optimized version of the solution, but its fundamental concepts only.
Red, Green, Blue and Alpha
You know this subject, but I must present it.
Any digital image is a matrix of pixels. But, roughly speaking, its representation in memory (which is what we handle) is NOT a matrix of pixels. It is an array of values of type uint8 (any integer number in the range zero to 255).
We “package” the numbers in the array, four by four, creating an imaginary sequence of pixels. The first number of the package is the value for Red, the second is the value for Green and the third is the value for Blue. The fourth number is the value for transparency, called Alpha.
When Alpha is zero, the pixel is absolutely transparent. When Alpha is 255 the pixel is opaque.
In case you want to make experiments with this subject, there are some useful websites, like BobSprite.
Reversing the shadows
The pixels of our shadow images follow this pattern: Red, Green, and Blue are always zero. Alpha is the ruler. When Alpha is 255 the pixel is absolutely black. When Alpha is zero, the pixel is absolutely translucent (no shadow at all).
The drawImage method is so nice (simple and fast) that we resist to abandon it outside, in the cold rain. So… let’s use it :)
We need to call this function to reverse the Alpha (value) of each pixel of shadow images:
Below we see Alpha reversing in action. The darker the pixel is, the lighter it becomes after the Alpha reversing.
For example, pixel [0,0,0,230] (dark) becomes [0,0,0,25] (clear).
Composing the reversed shadows and finishing
The shadow layer must start blank (no shadow). We draw the bonfire reversed shadows on it by calling drawImage (method of canvas).
Above we see the shadow layer after the bonfire reversed shadows are drawn on it. But the shadow layer is not ready yet. We must reverse its Alphas! Below we see the shadow layer ready to be drawn on the game canvas.
And this is the final result:
As a special bonus, the first solution automatically takes care of the naked areas (remember?). It is part of the magic when we reverse Alpha values!
What do you think? Piece of cake?
Overlapping shadows — the second solution
The second solution was born as the natural evolution of the first solution. Without heavy optimizations, just reversing the Alpha values of the shadow layer consumes around 15 milliseconds per loop. Clearly it is a no-go.
The irony is that, with heavy optimizations, we don’t need to rely on the drawImage method to compose shadows on the shadow layer. In fact, now, calling drawImage would confuse and slow the processing. We will be manipulating pixels 99% of the time.
Overlapping translucent pixels (of shadows)
In the first solution, the drawImage method calculates and applies the resulting Alpha of shadow (translucent) pixels that overlap. Our job was just reversing the Alphas.
Now it is our job to define the resulting Alpha. Therefore, the first thing we must do is to define the formula to be used.
Are we going to sum the Alphas? Consider the average Alpha? The reverse of the average Alpha?
The resulting alpha value of two shadow pixels that overlap shall be the smaller alpha value of both.
Note: I am not a computer graphics engineer. The rule above is just a simple pragmatic formula that works fine.
Solving the big bottleneck
The big bottleneck of pixel manipulation is the size of the images, reading the image pixels and the repetition of the procedures.
We handle repetition of the procedures by memorizing everything that makes sense to be memorized:
- really relieves the processing
- does not consume much memory
- is not clumsy to be memorized (and remembered)
We handle the size of the images by making the size of each image 100 times smaller. You read it well. I said ONE HUNDRED times smaller. We do this by reducing by ten the width and the height of the image.
You might be thinking that this reduction can’t be good; it is too much aggressive; some side effect must happen. I would reply that we are not reducing the image of a tiger. We are reducing a dark, translucent gradient that will be smoothed (it is desirable) by the process of reducing and expanding. But you are right about the side effect. We will see in details: the problem and the fix!
We deal with the slowness of the method getImageData by using it very few times in the whole game.
Some random notes
The program loses performance each time the runtime has to guess the type of some value.
Manipulating arrays of pixel data is expensive. My pragmatic way to tell the runtime which is the type of the array (no need guessing) is working with arrays that the runtime already know, like the data of the canvas ImageData.
The method getImageData is slow, much slower than the method putImageData.
If you are going to use getImageData for a lot of pixels NEVER read pixel by pixel by calling getImageData FROM some loop. It is very slow. The fast way is reading all the ImageData once and then iterate on the resulting data (array).
The second solution — in details
First we will see the code for shadowing when the avatar is standing. After we will see that side effect caused by the reduction of the shadow layer, that only happens when the avatar is “moving”.
Note: as we are seeing code snippets, “use strict” does not appear although its present at the top of the source code files.
We create the shadow layer: a 78 x 64 pixels canvas. Each dimension is exactly 10 times smaller than the respective dimension of the Lost In Maze game canvas (780 x 640 pixels).
We store as global variables the shadow layer itself, it’s 2D context, its ImageData and its array of pixel values (ImageData.data).
We use the shadow of the torch to create the default state for the shadow layer. We only need the data (array of pixel values).
The last preparation step is creating data of the reduced bonfire shadow. The original bonfire shadow is 540 x 540 pixels. The reduced bonfire shadow is 54 x 54 pixels.
If the current loop of the game is not in Daylight mode, the program calls the drawLighting function.
Note: the fact that we draw shadows to represent light effects is a private detail of the lighting module, the rest of the program needs not to be involved in such subject. That’s why the interface functions of the lighting module are called initLighting and drawLighting.
We reset the shadow layer using the data of the torch shadow (that is always in the center of the game canvas — easy). Notice that we are not using the canvas method clearRect or drawImage, because we are not working exactly on the 2D context of the shadow layer. We are directly manipulating its array of pixel values.
Drawing bonfire shadows implicates creating a list of the bonfires (and respective coordinates) that are in the scene or are near enough for lighting the scene. This part is a bit complicated and related to the Lost In Maze mechanics. We will skip the analysis of the function drawBonfireShadows and we will focus the analysis of the function pasteBonfireShadow, that is responsible for pasting a bonfire shadow on the shadow layer, object of our study.
We don’t need to blur the shadow layer. But blurring it results in a nicer light effect. Another irony: the less important procedure takes the biggest code snippet.
Using the canvas method “blur” is not acceptable, because it creates blank pixels near the edges.
This blur algorithm is dirty, reckless. It should be constructed with two arrays. One with the original pixels, just for reading. And a blank one just for store the resulting blurred pixels.
I made a lot of attempts and chose this because it was faster and, for my surprise, produced better shadows.
The second solution — the side effect and the fix
As I said before, reducing the shadow layer has a side effect. Any reduction would cause this side effect, but the more radical the reduction is, greater is the side effect. The side effect only happens when the avatar is moving.
This part is not complicated but requires that we focus our attention.
We know that the shadow of a bonfire must match the bonfire. When the avatar “moves” one pixel to the left, on the game canvas, it is the environment that moves one pixel to the right. So, the shadow of the bonfire must move one pixel to the right (matching the new position of the bonfire). Easy, right?
Hence, all we need to do is place the shadow layer (the canvas where torch and bonfire shadows are composed) one pixel to the right on the game canvas, right?
Wrong. The shadow layer, when expanded, has the same size of the game canvas. It must match the game canvas. It is not supposed to be displaced!!
What should be displaced one pixel to the right are the bonfire shadows INSIDE the shadow layer. The torch shadow must keep centered inside the shadow layer, like the avatar is centered in the game canvas.
Good. So when the avatar moves one pixel to the left we place the torch shadow in the center of the shadow layer (as always) and we place each bonfire shadow one pixel to the right. No big deal. What is the problem? — you ask me.
The problem is this: we are (for reasons of efficiency) working with REDUCED images. We place a reduced bonfire shadow one pixel to the right on the reduced shadow layer. For now everything is fine. But when the shadow layer is expanded ten times each side to cover the game canvas, that one pixel to the right becomes ten pixels to the right!!! Therefore, each bonfire shadow will miss its correct position to the respective bonfire by nine (ten minus one) horizontal pixels.
Trying to fix that, we displace the reduced bonfire shadow one pixel to the right on the reduced shadow layer ONLY when the avatar walks ten pixels to the left (on the normal game canvas), keeping the proportion. OK. It is much better now, but it is not good yet:
- the environment starts moving, but each bonfire shadow stays on the same place
- when the environment completes ten pixels of displacement, each bonfire shadow suddenly jumps ten pixels and matches exactly its bonfire
- go to step ‘1’
The fix is simple: the reduced shadow layer is (and will always be) only one, but we need a few reduced bonfire shadows to match the moving avatar displacements in the range zero to nine pixels. Consider horizontal, vertical and diagonal displacements.
According to our example, one of these (sibling) bonfire shadows must be displaced one pixel to the right.
The trick is displacing each bonfire shadow BEFORE reducing it.
And, of course, this few tens of reduced bonfire shadows are worth to memorize.
The fix in brief details
- We store the standard 540 x 540 pixel raw bonfire shadow as image.
- The bonfire shadows that will be really using are all 560 x 560 pixels. This dimension means we can place the standard bonfire shadow in the center and there is a margin of 10 pixels on each edge.
- This margin near the edge is used to match the avatar displacement. When he walks one pixel to the left, here we draw the standard bonfire one pixel to the right, before reducing it!!!
- Also, the reduced bonfire shadows will be 56 x 56 pixels.
- We had no problem when the avatar displacement was a round multiple of 10 pixels (like 0, 10, 20, 30, etc.). The problem is 3, 5, 11, 16…
- The bonfire shadow that we need when the avatar walks 13 pixels to the left is exactly the same when he walks 3 pixels to the left, or 23, 33, 43, 53…
- We need not and should not to store up front all possible shadows We provide the bonfire shadows under demand.
Note: the original 540 x 540 bonfire shadow we store as image, because we will draw it to create the 560 x 560 bonfire shadows. All the (reduced) other we store only as array of pixel values (ImageData.data).
These algorithms are relatively easy to implement once you know the tricks.
About efficiency: on a decent desktop (not a gamer one) Lost In Maze takes 1 or 2 milliseconds to execute each loop in Daylight mode. And takes 2 or 3 milliseconds to execute in Bonfire mode (the heaviest one). I am very satisfied.
Please, let me know if you have any doubt.