summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authormichi_cc <michi_cc@openttd.org>2012-04-17 19:43:43 +0000
committermichi_cc <michi_cc@openttd.org>2012-04-17 19:43:43 +0000
commit6f9668330e198a8100aabdc09f612a48887c5c07 (patch)
tree2d49b956ec689c9b10624ab3c328b70c80e761b4 /src
parent32ab630bda765ba6eb7283d06df88d783ce17865 (diff)
downloadopenttd-6f9668330e198a8100aabdc09f612a48887c5c07.tar.xz
(svn r24132) -Change [FS#4713]: Improve randomness of tile order in the tile loop. (monoid)
Diffstat (limited to 'src')
-rw-r--r--src/genworld.cpp1
-rw-r--r--src/landscape.cpp47
-rw-r--r--src/misc.cpp2
-rw-r--r--src/saveload/afterload.cpp4
4 files changed, 35 insertions, 19 deletions
diff --git a/src/genworld.cpp b/src/genworld.cpp
index 8594cd4e6..78fa6e3e7 100644
--- a/src/genworld.cpp
+++ b/src/genworld.cpp
@@ -159,6 +159,7 @@ static void _GenerateWorld(void *)
SetGeneratingWorldProgress(GWP_RUNTILELOOP, 0x500);
for (i = 0; i < 0x500; i++) {
RunTileLoop();
+ _tick_counter++;
IncreaseGeneratingWorldProgress(GWP_RUNTILELOOP);
}
diff --git a/src/landscape.cpp b/src/landscape.cpp
index caa75ef27..a4b12f857 100644
--- a/src/landscape.cpp
+++ b/src/landscape.cpp
@@ -712,32 +712,43 @@ CommandCost CmdClearArea(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32
TileIndex _cur_tileloop_tile;
-#define TILELOOP_BITS 4
-#define TILELOOP_SIZE (1 << TILELOOP_BITS)
-#define TILELOOP_ASSERTMASK ((TILELOOP_SIZE - 1) + ((TILELOOP_SIZE - 1) << MapLogX()))
-#define TILELOOP_CHKMASK (((1 << (MapLogX() - TILELOOP_BITS))-1) << TILELOOP_BITS)
+/**
+ * Gradually iterate over all tiles on the map, calling their TileLoopProcs once every 256 ticks.
+ */
void RunTileLoop()
{
+ /* The pseudorandom sequence of tiles is generated using a Galois linear feedback
+ * shift register (LFSR). This allows a deterministic pseudorandom ordering, but
+ * still with minimal state and fast iteration. */
+
+ /* Maximal length LFSR feedback terms, from 12-bit (for 64x64 maps) to 22-bit (for 2048x2048 maps).
+ * Extracted from http://www.ece.cmu.edu/~koopman/lfsr/ */
+ static const uint32 feedbacks[] = {
+ 0xD8F, 0x1296, 0x2496, 0x4357, 0x8679, 0x1030E, 0x206CD, 0x403FE, 0x807B8, 0x1004B2, 0x2006A8
+ };
+ const uint32 feedback = feedbacks[MapLogX() + MapLogY() - 12];
+
+ /* We update every tile every 256 ticks, so divide the map size by 2^8 = 256 */
+ uint count = 1 << (MapLogX() + MapLogY() - 8);
+
TileIndex tile = _cur_tileloop_tile;
+ /* The LFSR cannot have a zeroed state. */
+ assert(tile != 0);
- assert((tile & ~TILELOOP_ASSERTMASK) == 0);
- uint count = (MapSizeX() / TILELOOP_SIZE) * (MapSizeY() / TILELOOP_SIZE);
- do {
- _tile_type_procs[GetTileType(tile)]->tile_loop_proc(tile);
+ /* Manually update tile 0 every 256 ticks - the LFSR never iterates over it itself. */
+ if (_tick_counter % 256 == 0) {
+ _tile_type_procs[GetTileType(0)]->tile_loop_proc(0);
+ count--;
+ }
- if (TileX(tile) < MapSizeX() - TILELOOP_SIZE) {
- tile += TILELOOP_SIZE; // no overflow
- } else {
- tile = TILE_MASK(tile - TILELOOP_SIZE * (MapSizeX() / TILELOOP_SIZE - 1) + TileDiffXY(0, TILELOOP_SIZE)); // x would overflow, also increase y
- }
- } while (--count != 0);
- assert((tile & ~TILELOOP_ASSERTMASK) == 0);
+ while (count--) {
+ _tile_type_procs[GetTileType(tile)]->tile_loop_proc(tile);
- tile += 9;
- if (tile & TILELOOP_CHKMASK) {
- tile = (tile + MapSizeX()) & TILELOOP_ASSERTMASK;
+ /* Get the next tile in sequence using a Galois LFSR. */
+ tile = (tile >> 1) ^ (-(int32)(tile & 1) & feedback);
}
+
_cur_tileloop_tile = tile;
}
diff --git a/src/misc.cpp b/src/misc.cpp
index d82c456e0..c967d5369 100644
--- a/src/misc.cpp
+++ b/src/misc.cpp
@@ -59,7 +59,7 @@ void InitializeGame(uint size_x, uint size_y, bool reset_date, bool reset_settin
_pause_mode = PM_UNPAUSED;
_fast_forward = 0;
_tick_counter = 0;
- _cur_tileloop_tile = 0;
+ _cur_tileloop_tile = 1;
_thd.redsq = INVALID_TILE;
if (reset_settings) MakeNewgameSettingsLive();
diff --git a/src/saveload/afterload.cpp b/src/saveload/afterload.cpp
index 7cb9f0ff0..b800fe087 100644
--- a/src/saveload/afterload.cpp
+++ b/src/saveload/afterload.cpp
@@ -483,6 +483,10 @@ bool AfterLoadGame()
TileIndex map_size = MapSize();
+ extern TileIndex _cur_tileloop_tile; // From landscape.cpp.
+ /* The LFSR used in RunTileLoop iteration cannot have a zeroed state, make it non-zeroed. */
+ if (_cur_tileloop_tile == 0) _cur_tileloop_tile = 1;
+
if (IsSavegameVersionBefore(98)) GamelogOldver();
GamelogTestRevision();