The technique of total prescale in the lighting algorithm for a 2D 2D tile game
Hello! My last game is an isometric walker, one of the features of which is the “exploration” of the territory: initially the map is black and the player opens this “fog of war” as the game progresses. Moreover, the visibility of the tiles depends not only on the distance to the character, but also on the environment: the cells behind opaque walls are not visible, even if you go to a stop, and, for example, the bush shrinks the visibility of the cells behind it by 50%.
In order not to load the processor by frame-by-frame ray tracing (to determine which cell is currently visible as far as possible), I used a rather interesting “total pre-calculation” method - the main parameters for virtually all possible situations are considered before playing a large matrix, and during the game it remains only access it by choosing the desired values.
What do I mean by preliminary calculations:
')
The hero is placed in the cell of the origin (0; 0). For each cell within the visibility of the screen (with a margin, within two screens), various game parameters are counted, including a list of cells that the segment crosses from the origin to its center:
To be more precise, such lists are counted for each of the 4 corners of each cell:
All this data is recorded in the "matrix of appearances" M.
How it works? Each object in the game has an “opacity” parameter - a value from 0 to 1, a percentage of the view being blocked. In the game, to find out how visible the tile (xt; yt) is relative to the position of the hero (x0; y0), I need to:
1. Refer to the matrix element Mt = M [xt-x0; yt-y0]
2. Calculate how visible each of the corners of this tile is (and the corners that are blocked by the tile itself (xt; yt), so there are 2 or 3) are not taken into account: for this, I read the vector of tiles from Mt that occur on the way to the corner and I multiply the "degrees of visibility" of all the objects that are in them (and yes, as soon as an object with zero visibility is encountered, the passage through the list can not be continued).
3. The degree of visibility of the tile Vt = arithmetic average of the appearances of each of its corners.
So I do for each of the tiles in a certain area around the hero when something changes (the position of the hero or objects).
The calculation in the corners instead of one center of the tile is carried out to smooth artifacts, when a cell is slightly blocked by some opaque wall with its end, but because of this the cell becomes completely invisible.
The method, as you understand, is not entirely accurate (compared to honest "analog" ray tracing), but it gives good values. Discreteness is noticeable, the less visually the smaller cells in the game.
How much performance will increase the preliminary calculation of all parameters in the “matrix of appearances” (compared to determining parameters on the fly) will depend on the language, but essentially all geometric calculations are replaced by the operation of accessing the matrix / vector element. On my AIR, the speed gain varies from 7 to 11 times (depending on the degree of loading of the map area with objects)
The same matrix can be used to determine the illumination of a cell, when some objects can emit light, and some block it. The algorithm here is exactly the same.
(coins have a slight glow)
Demonstration of changing the visibility of tiles in dynamics:
Thanks for attention!
In order not to load the processor by frame-by-frame ray tracing (to determine which cell is currently visible as far as possible), I used a rather interesting “total pre-calculation” method - the main parameters for virtually all possible situations are considered before playing a large matrix, and during the game it remains only access it by choosing the desired values.
What do I mean by preliminary calculations:
')
The hero is placed in the cell of the origin (0; 0). For each cell within the visibility of the screen (with a margin, within two screens), various game parameters are counted, including a list of cells that the segment crosses from the origin to its center:
To be more precise, such lists are counted for each of the 4 corners of each cell:
All this data is recorded in the "matrix of appearances" M.
How it works? Each object in the game has an “opacity” parameter - a value from 0 to 1, a percentage of the view being blocked. In the game, to find out how visible the tile (xt; yt) is relative to the position of the hero (x0; y0), I need to:
1. Refer to the matrix element Mt = M [xt-x0; yt-y0]
2. Calculate how visible each of the corners of this tile is (and the corners that are blocked by the tile itself (xt; yt), so there are 2 or 3) are not taken into account: for this, I read the vector of tiles from Mt that occur on the way to the corner and I multiply the "degrees of visibility" of all the objects that are in them (and yes, as soon as an object with zero visibility is encountered, the passage through the list can not be continued).
3. The degree of visibility of the tile Vt = arithmetic average of the appearances of each of its corners.
So I do for each of the tiles in a certain area around the hero when something changes (the position of the hero or objects).
The calculation in the corners instead of one center of the tile is carried out to smooth artifacts, when a cell is slightly blocked by some opaque wall with its end, but because of this the cell becomes completely invisible.
The method, as you understand, is not entirely accurate (compared to honest "analog" ray tracing), but it gives good values. Discreteness is noticeable, the less visually the smaller cells in the game.
How much performance will increase the preliminary calculation of all parameters in the “matrix of appearances” (compared to determining parameters on the fly) will depend on the language, but essentially all geometric calculations are replaced by the operation of accessing the matrix / vector element. On my AIR, the speed gain varies from 7 to 11 times (depending on the degree of loading of the map area with objects)
The same matrix can be used to determine the illumination of a cell, when some objects can emit light, and some block it. The algorithm here is exactly the same.
(coins have a slight glow)
Demonstration of changing the visibility of tiles in dynamics:
Thanks for attention!
Source: https://habr.com/ru/post/315970/
All Articles