summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorrubidium <rubidium@openttd.org>2014-09-20 12:11:15 +0000
committerrubidium <rubidium@openttd.org>2014-09-20 12:11:15 +0000
commit4c45db295e9a59f0a2604b40aea462d277e2a499 (patch)
tree49cc0cbdab16a9b262b59a653678fbc99a205c0f
parentc4fcc8d2aaac791f3a93c2433e6d30b4dc0e535a (diff)
downloadopenttd-4c45db295e9a59f0a2604b40aea462d277e2a499.tar.xz
(svn r26860) -Codechange: improve worst case performance of terraforming (O(n^2) -> O(n log n)) and let memory usage scale to the amount of tiles affected instead of allocating memory for the worst case scenario (patch by ic111)
-rw-r--r--src/terraform_cmd.cpp117
1 files changed, 26 insertions, 91 deletions
diff --git a/src/terraform_cmd.cpp b/src/terraform_cmd.cpp
index 98ac1d365..ce871a407 100644
--- a/src/terraform_cmd.cpp
+++ b/src/terraform_cmd.cpp
@@ -21,40 +21,20 @@
#include "table/strings.h"
+#include <map>
+#include <set>
+
#include "safeguards.h"
-/*
- * In one terraforming command all four corners of a initial tile can be raised/lowered (though this is not available to the player).
- * The maximal amount of height modifications is achieved when raising a complete flat land from sea level to MAX_TILE_HEIGHT or vice versa.
- * This affects all corners with a manhatten distance smaller than MAX_TILE_HEIGHT to one of the initial 4 corners.
- * Their maximal amount is computed to 4 * \sum_{i=1}^{h_max} i = 2 * h_max * (h_max + 1).
- */
-static const int TERRAFORMER_MODHEIGHT_SIZE = 2 * MAX_TILE_HEIGHT * (MAX_TILE_HEIGHT + 1);
-
-/*
- * The maximal amount of affected tiles (i.e. the tiles that incident with one of the corners above, is computed similar to
- * 1 + 4 * \sum_{i=1}^{h_max} (i+1) = 1 + 2 * h_max + (h_max + 3).
- */
-static const int TERRAFORMER_TILE_TABLE_SIZE = 1 + 2 * MAX_TILE_HEIGHT * (MAX_TILE_HEIGHT + 3);
-
-struct TerraformerHeightMod {
- TileIndex tile; ///< Referenced tile.
- byte height; ///< New TileHeight (height of north corner) of the tile.
-};
+/** Set of tiles. */
+typedef std::set<TileIndex> TileIndexSet;
+/** Mapping of tiles to their height. */
+typedef std::map<TileIndex, int> TileIndexToHeightMap;
+/** State of the terraforming. */
struct TerraformerState {
- int modheight_count; ///< amount of entries in "modheight".
- int tile_table_count; ///< amount of entries in "tile_table".
-
- /**
- * Dirty tiles, i.e.\ at least one corner changed.
- *
- * This array contains the tiles which are or will be marked as dirty.
- *
- * @ingroup dirty
- */
- TileIndex tile_table[TERRAFORMER_TILE_TABLE_SIZE];
- TerraformerHeightMod modheight[TERRAFORMER_MODHEIGHT_SIZE]; ///< Height modifications.
+ TileIndexSet dirty_tiles; ///< The tiles that need to be redrawn.
+ TileIndexToHeightMap tile_to_new_height; ///< The tiles for which the height has changed.
};
TileIndex _terraform_err_tile; ///< first tile we couldn't terraform
@@ -68,14 +48,8 @@ TileIndex _terraform_err_tile; ///< first tile we couldn't terraform
*/
static int TerraformGetHeightOfTile(const TerraformerState *ts, TileIndex tile)
{
- const TerraformerHeightMod *mod = ts->modheight;
-
- for (int count = ts->modheight_count; count != 0; count--, mod++) {
- if (mod->tile == tile) return mod->height;
- }
-
- /* TileHeight unchanged so far, read value from map. */
- return TileHeight(tile);
+ TileIndexToHeightMap::const_iterator it = ts->tile_to_new_height.find(tile);
+ return it != ts->tile_to_new_height.end() ? it->second : TileHeight(tile);
}
/**
@@ -87,26 +61,7 @@ static int TerraformGetHeightOfTile(const TerraformerState *ts, TileIndex tile)
*/
static void TerraformSetHeightOfTile(TerraformerState *ts, TileIndex tile, int height)
{
- /* Find tile in the "modheight" table.
- * Note: In a normal user-terraform command the tile will not be found in the "modheight" table.
- * But during house- or industry-construction multiple corners can be terraformed at once. */
- TerraformerHeightMod *mod = ts->modheight;
- int count = ts->modheight_count;
-
- while ((count > 0) && (mod->tile != tile)) {
- mod++;
- count--;
- }
-
- /* New entry? */
- if (count == 0) {
- assert(ts->modheight_count < TERRAFORMER_MODHEIGHT_SIZE);
- ts->modheight_count++;
- }
-
- /* Finally store the new value */
- mod->tile = tile;
- mod->height = (byte)height;
+ ts->tile_to_new_height[tile] = height;
}
/**
@@ -118,15 +73,7 @@ static void TerraformSetHeightOfTile(TerraformerState *ts, TileIndex tile, int h
*/
static void TerraformAddDirtyTile(TerraformerState *ts, TileIndex tile)
{
- int count = ts->tile_table_count;
-
- for (TileIndex *t = ts->tile_table; count != 0; count--, t++) {
- if (*t == tile) return;
- }
-
- assert(ts->tile_table_count < TERRAFORMER_TILE_TABLE_SIZE);
-
- ts->tile_table[ts->tile_table_count++] = tile;
+ ts->dirty_tiles.insert(tile);
}
/**
@@ -247,8 +194,6 @@ CommandCost CmdTerraformLand(TileIndex tile, DoCommandFlag flags, uint32 p1, uin
int direction = (p2 != 0 ? 1 : -1);
TerraformerState ts;
- ts.modheight_count = ts.tile_table_count = 0;
-
/* Compute the costs and the terraforming result in a model of the landscape */
if ((p1 & SLOPE_W) != 0 && tile + TileDiffXY(1, 0) < MapSize()) {
TileIndex t = tile + TileDiffXY(1, 0);
@@ -282,10 +227,8 @@ CommandCost CmdTerraformLand(TileIndex tile, DoCommandFlag flags, uint32 p1, uin
* Pass == 0: Collect tileareas which are caused to be auto-cleared.
* Pass == 1: Collect the actual cost. */
for (int pass = 0; pass < 2; pass++) {
- TileIndex *ti = ts.tile_table;
-
- for (int count = ts.tile_table_count; count != 0; count--, ti++) {
- TileIndex tile = *ti;
+ for (TileIndexSet::const_iterator it = ts.dirty_tiles.begin(); it != ts.dirty_tiles.end(); it++) {
+ TileIndex tile = *it;
assert(tile < MapSize());
/* MP_VOID tiles can be terraformed but as tunnels and bridges
@@ -351,34 +294,26 @@ CommandCost CmdTerraformLand(TileIndex tile, DoCommandFlag flags, uint32 p1, uin
}
Company *c = Company::GetIfValid(_current_company);
- if (c != NULL && (int)GB(c->terraform_limit, 16, 16) < ts.modheight_count) {
+ if (c != NULL && GB(c->terraform_limit, 16, 16) < ts.tile_to_new_height.size()) {
return_cmd_error(STR_ERROR_TERRAFORM_LIMIT_REACHED);
}
if (flags & DC_EXEC) {
/* change the height */
- {
- int count;
- TerraformerHeightMod *mod;
+ for (TileIndexToHeightMap::const_iterator it = ts.tile_to_new_height.begin();
+ it != ts.tile_to_new_height.end(); it++) {
+ TileIndex tile = it->first;
+ int height = it->second;
- mod = ts.modheight;
- for (count = ts.modheight_count; count != 0; count--, mod++) {
- TileIndex til = mod->tile;
-
- SetTileHeight(til, mod->height);
- }
+ SetTileHeight(tile, (uint)height);
}
- /* finally mark the dirty tiles dirty */
- {
- int count;
- TileIndex *ti = ts.tile_table;
- for (count = ts.tile_table_count; count != 0; count--, ti++) {
- MarkTileDirtyByTile(*ti);
- }
+ /* Finally mark the dirty tiles dirty */
+ for (TileIndexSet::const_iterator it = ts.dirty_tiles.begin(); it != ts.dirty_tiles.end(); it++) {
+ MarkTileDirtyByTile(*it);
}
- if (c != NULL) c->terraform_limit -= ts.modheight_count << 16;
+ if (c != NULL) c->terraform_limit -= ts.tile_to_new_height.size() << 16;
}
return total_cost;
}