Tuesday, 26 April 2011

Light propagation with CA

I plan to make a 2d rpg. I have looked at several different variations of calculating field of view (this used to be a good summary, but seems to be unavailable at the moment), but I did not really like any of them. Somehow they seemed to be too sharp, too "digital" - something is either visible or not.

I wanted a fov calculation that gave more natural results, and I thought that simulating light propagation would be a good candidate. Since the game world would be a 2d grid, the idea of using a cellular automaton to calculate light propagation came to my mind, and I started experimenting with it.

After a few ours of planning and coding, I got the results that satisfied my need:

How does it work? Every cell in the grid has two attributes. The first attribute is transparency: if a cell is transparent, light can propagate through it, otherwise it can only receive light. This value represents wether the cell in the game world is blocking the light, it is not updated by the automaton.

The second attribute is the strength of the light in that cell. In my implementation it is a floating point value between 0.0 and 1.0. This value is updated during every iteration, the new value is the average of the cell and the neighbouring cells. If the cell is blockling the light, it's value is not included in the averaging, so that they do not light other cells, even thought they can receive light.

I have used 4 neighbours in my implementation. The drawback of this is that the corners are in shadow. This could be easily solved by using 8 neighbours, but that increases the computational costs. Another improvement could be using RGB colours instead of the simple light strength, this way more interesting effects could be achieved.

Strictly speaking this might not count as a calculation of field of view, but it achieves a similar effect. I think this method could give a good atmosphere to a game, especially to games with stealth / horror elements. (Imagine walking down a corridor, when suddenly your torch goes out, and everything becomes totally dark... and then you hear a noise...)

I have implemented this method in processing.js, it is available here, you can experiment with it in the browser. The mouse cursor is the source of the light. In the beginning every cell is a wall, blocking the light. You can 'carve' empty cells into the grid by holding the left mouse button, or build back the walls with the right mouse button. The source code is available here.

No comments:

Post a Comment