From 5324adfe51f1348fc97fe2ee0ca4e4bbd2a6ad64 Mon Sep 17 00:00:00 2001
From: Star Rauchenberger <fefferburbia@gmail.com>
Date: Thu, 17 Mar 2022 15:28:22 -0400
Subject: lotta performance improvements

the two main things:

1) When ticking three times after a lighting change, we no longer iterate over the entire map. Instead, we keep a list of the tiles that have changed and the ones adjacent to them, and we iterate over that list.
2) The map tile type is now stored in a separate array from the rest of the tile data. This is because the tile type is the only thing needed for the cellular automata tick, and thus the only thing that we need to actually copy.
---
 src/map.h | 94 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 90 insertions(+), 4 deletions(-)

(limited to 'src/map.h')

diff --git a/src/map.h b/src/map.h
index de74b14..fe3270c 100644
--- a/src/map.h
+++ b/src/map.h
@@ -25,7 +25,6 @@ enum class Source {
 };
 
 struct MapData {
-  Tile tile = Tile::Floor;
   bool lit = false;
   bool wasLit = false;
   size_t dustLife = 0;
@@ -39,6 +38,7 @@ struct MapData {
 };
 
 struct Chunk {
+  std::array<Tile, CHUNK_WIDTH*CHUNK_HEIGHT> tiles;
   std::array<MapData, CHUNK_WIDTH*CHUNK_HEIGHT> data;
   int litTiles = 0;
   int x;
@@ -101,6 +101,16 @@ public:
            (y < top_ + height_);
   }
 
+  inline const Tile& tile(int x, int y) const
+  {
+    return loadedTiles_[(x - left_) + width_ * (y - top_)];
+  }
+
+  inline Tile& tile(int x, int y)
+  {
+    return const_cast<Tile&>(static_cast<const Map&>(*this).tile(x, y));
+  }
+
   inline const MapData& at(int x, int y) const
   {
     return loaded_[(x - left_) + width_ * (y - top_)];
@@ -111,6 +121,16 @@ public:
     return const_cast<MapData&>(static_cast<const Map&>(*this).at(x, y));
   }
 
+  inline const std::vector<Tile>& tiles() const
+  {
+    return loadedTiles_;
+  }
+
+  inline std::vector<Tile>& tiles()
+  {
+    return loadedTiles_;
+  }
+
   inline const std::vector<MapData>& data() const
   {
     return loaded_;
@@ -139,6 +159,11 @@ public:
           int startX = chunkX * CHUNK_WIDTH;
           int startY = chunkY * CHUNK_HEIGHT;
           for (int y=0; y<CHUNK_HEIGHT; y++) {
+            std::copy(
+              std::next(std::begin(loadedTiles_), (chunkY*CHUNK_HEIGHT + y)*width_ + chunkX*CHUNK_WIDTH),
+              std::next(std::begin(loadedTiles_), (chunkY*CHUNK_HEIGHT + y)*width_ + (chunkX+1)*CHUNK_WIDTH),
+              std::next(std::begin(chunk.tiles), y*CHUNK_WIDTH));
+
             for (int x=0; x<CHUNK_WIDTH; x++) {
               chunk.data[x+y*CHUNK_WIDTH] = loaded_[startX+x+(startY+y)*width_];
               if (chunk.data[x+y*CHUNK_WIDTH].lit) {
@@ -169,6 +194,9 @@ public:
     width_ = chunksHoriz_ * CHUNK_WIDTH;
     height_ = chunksVert_ * CHUNK_HEIGHT;
     loaded_ = std::vector<MapData>(width_ * height_);
+    loadedTiles_ = std::vector<Tile>(width_ * height_, Tile::Floor);
+    dirtyTiles_.clear();
+    dirtySet_ = std::vector<bool>(width_ * height_, false);
 
     // Load in the requested chunks.
     for (int chunkY = 0; chunkY < chunksVert_; chunkY++) {
@@ -190,14 +218,16 @@ public:
           chunk.y = topmostChunk_ + chunkY;
           chunk.litTiles = 0;
 
-          for (MapData& md : chunk.data)
+          for (Tile& tile : chunk.tiles)
           {
             if (std::bernoulli_distribution(0.5)(rng))
             {
-              md.tile = Tile::Wall;
+              tile = Tile::Wall;
             } else {
-              md.tile = Tile::Floor;
+              tile = Tile::Floor;
             }
+          }
+          for (MapData& md : chunk.data) {
             md.dirtyRender = true;
           }
         }
@@ -206,6 +236,10 @@ public:
         Chunk& chunk = chunks_[chunkIndex];
 
         for (int y = 0; y < CHUNK_HEIGHT; y++) {
+          std::copy(
+            std::next(std::begin(chunk.tiles), y*CHUNK_WIDTH),
+            std::next(std::begin(chunk.tiles), (y+1)*CHUNK_WIDTH),
+            std::next(std::begin(loadedTiles_), (chunkY*CHUNK_HEIGHT + y)*width_ + chunkX*CHUNK_WIDTH));
           std::copy(
             std::next(std::begin(chunk.data), y*CHUNK_WIDTH),
             std::next(std::begin(chunk.data), (y+1)*CHUNK_WIDTH),
@@ -215,7 +249,55 @@ public:
         unloadedLitTiles_ -= chunk.litTiles;
       }
     }
+  }
 
+  void markDirtyAround(int x, int y) {
+    if (x > left_) {
+      if (y > top_) {
+        markDirty(x-1, y-1);
+      }
+      markDirty(x-1, y  );
+      if (y < top_+height_-1) {
+        markDirty(x-1, y+1);
+      }
+    }
+
+    if (y > top_) {
+      markDirty(x  , y-1);
+    }
+    markDirty(x  , y  );
+    if (y < top_+height_-1) {
+      markDirty(x  , y+1);
+    }
+
+    if (x < left_+width_-1) {
+      if (y > top_) {
+        markDirty(x+1, y-1);
+      }
+      markDirty(x+1, y  );
+      if (y < top_+height_-1) {
+        markDirty(x+1, y+1);
+      }
+    }
+  }
+
+  void markDirty(int x, int y) {
+    size_t index = (x-left_)+(y-top_)*width_;
+    if (!dirtySet_[index]) {
+      dirtySet_[index] = true;
+      dirtyTiles_.emplace_back(x,y);
+    }
+  }
+
+  const std::vector<coord> getDirty() const {
+    return dirtyTiles_;
+  }
+
+  void resetDirty() {
+    for (auto [x,y] : dirtyTiles_) {
+      dirtySet_[(x-left_)+(y-top_)*width_] = false;
+    }
+    dirtyTiles_.clear();
   }
 
 private:
@@ -228,6 +310,7 @@ private:
   int topmostChunk_;
   int chunksHoriz_;
   int chunksVert_;
+  std::vector<Tile> loadedTiles_;
   std::vector<MapData> loaded_;
 
   std::vector<Chunk> chunks_;
@@ -235,6 +318,9 @@ private:
   std::map<int, std::map<int, size_t>> chunkByPos_; // chunkByPos_[X][Y]
 
   int unloadedLitTiles_ = 0;
+
+  std::vector<coord> dirtyTiles_;
+  std::vector<bool> dirtySet_;
 };
 
 #endif /* end of include guard: MAP_H_3AB00D12 */
-- 
cgit 1.4.1