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.

1 files changed, 105 insertions, 90 deletions

@@ -20,7 +20,7 @@ Game::Game(std::mt19937& rng, Muxer& muxer, Renderer& renderer) :
   {
     for (int x = -1; x <= 1; x++)
     {
-      map.at(x,y).tile = Tile::Floor;
+      map.tile(x,y) = Tile::Floor;
     }
   }
 
@@ -35,12 +35,12 @@ Game::Game(std::mt19937& rng, Muxer& muxer, Renderer& renderer) :
 
 inline bool isTileSetOrNotLit(const Map& map, int x, int y)
 {
-  return (map.inBounds(x, y) && (map.at(x,y).tile == Tile::Wall || !map.at(x,y).lit));
+  return (map.inBounds(x, y) && (map.tile(x,y) == Tile::Wall || !map.at(x,y).lit));
 }
 
 inline bool isTileSet(const Map& map, int x, int y, Tile val = Tile::Wall)
 {
-  return (map.inBounds(x, y) && map.at(x,y).tile == val);
+  return (map.inBounds(x, y) && map.tile(x,y) == val);
 }
 
 inline void incrementIfSet(const Game& game, int& count, int x, int y, Tile val = Tile::Wall)
@@ -55,6 +55,56 @@ inline int getZoomLevel(const Game& game) {
   return game.curZoom - INIT_ZOOM;
 }
 
+inline void tickIndividual(Game& game, std::vector<Tile>& mapDoubleBuffer, int x, int y, bool onlyDark) {
+  if (onlyDark && game.map.at(x,y).lit)
+  {
+    return;
+  }
+
+  if (game.map.tile(x,y) == Tile::Lamp)
+  {
+    return;
+  }
+
+  int count = 0;
+
+  incrementIfSet(game, count, x-1, y-1);
+  incrementIfSet(game, count, x-1, y  );
+  incrementIfSet(game, count, x-1, y+1);
+  incrementIfSet(game, count, x  , y-1);
+  incrementIfSet(game, count, x  , y  );
+  incrementIfSet(game, count, x  , y+1);
+  incrementIfSet(game, count, x+1, y-1);
+  incrementIfSet(game, count, x+1, y  );
+  incrementIfSet(game, count, x+1, y+1);
+
+  int tempIndex = game.map.getTrueX(x) + game.map.getTrueY(y) * game.map.getWidth();
+  if (count >= 5)
+  {
+    mapDoubleBuffer[tempIndex] = Tile::Wall;
+  } else {
+    mapDoubleBuffer[tempIndex] = Tile::Floor;
+  }
+
+  if (mapDoubleBuffer[tempIndex] != game.map.tile(x,y)) {
+    game.map.at(x,y).dirtyRender = true;
+    game.dirtyRender = true;
+    game.map.markDirtyAround(x,y);
+  }
+}
+
+void Game::tickDirty(bool onlyDark) {
+  mapDoubleBuffer = map.tiles();
+  std::vector<coord> dirty = map.getDirty();
+  map.resetDirty();
+
+  for (auto [x,y] : dirty) {
+    tickIndividual(*this, mapDoubleBuffer, x, y, onlyDark);
+  }
+
+  std::swap(map.tiles(), mapDoubleBuffer);
+}
+
 void Game::tick(
   int x1,
   int y1,
@@ -63,7 +113,8 @@ void Game::tick(
   bool invert,
   bool onlyDark)
 {
-  mapDoubleBuffer = map.data();
+  mapDoubleBuffer = map.tiles();
+  map.resetDirty();
 
   for (int y = map.getTop(); y < map.getBottom(); y++)
   {
@@ -74,44 +125,11 @@ void Game::tick(
         continue;
       }
 
-      if (onlyDark && map.at(x,y).lit)
-      {
-        continue;
-      }
-
-      if (map.at(x,y).tile == Tile::Lamp)
-      {
-        continue;
-      }
-
-      int count = 0;
-
-      incrementIfSet(*this, count, x-1, y-1);
-      incrementIfSet(*this, count, x-1, y  );
-      incrementIfSet(*this, count, x-1, y+1);
-      incrementIfSet(*this, count, x  , y-1);
-      incrementIfSet(*this, count, x  , y  );
-      incrementIfSet(*this, count, x  , y+1);
-      incrementIfSet(*this, count, x+1, y-1);
-      incrementIfSet(*this, count, x+1, y  );
-      incrementIfSet(*this, count, x+1, y+1);
-
-      int tempIndex = map.getTrueX(x) + map.getTrueY(y) * map.getWidth();
-      if (count >= 5)
-      {
-        mapDoubleBuffer[tempIndex].tile = Tile::Wall;
-      } else {
-        mapDoubleBuffer[tempIndex].tile = Tile::Floor;
-      }
-
-      if (mapDoubleBuffer[tempIndex].tile != map.at(x,y).tile) {
-        mapDoubleBuffer[tempIndex].dirtyRender = true;
-        dirtyRender = true;
-      }
+      tickIndividual(*this, mapDoubleBuffer, x, y, onlyDark);
     }
   }
 
-  std::swap(map.data(), mapDoubleBuffer);
+  std::swap(map.tiles(), mapDoubleBuffer);
 }
 
 void Game::tick(bool onlyDark)
@@ -127,11 +145,11 @@ void Game::tick(bool onlyDark)
 
 bool Game::movePlayer(int x, int y)
 {
-  if (map.at(x,y).tile == Tile::Floor && !map.at(x,y).sign)
+  if (map.tile(x,y) == Tile::Floor && !map.at(x,y).sign)
   {
-    if (map.at(player_x, player_y).tile == Tile::Floor)
+    if (map.tile(player_x, player_y) == Tile::Floor)
     {
-      map.at(player_x, player_y).tile = Tile::Dust;
+      map.tile(player_x, player_y) = Tile::Dust;
       map.at(player_x, player_y).dustLife = 1;
       numDust++;
     }
@@ -169,14 +187,15 @@ void Game::recalculateLighting()
   litSpots = 0;
   dirtyRender = true;
 
-  for (MapData& md : map.data())
-  {
-    md.wasLit = md.lit;
-    md.lit = false;
-    md.litTiles.clear();
+  for (int y=map.getTop(); y<map.getBottom(); y++) {
+    for (int x=map.getLeft(); x<map.getRight(); x++) {
+      map.at(x,y).wasLit = map.at(x,y).lit;
+      map.at(x,y).lit = false;
+      map.at(x,y).litTiles.clear();
 
-    if (md.tile == Tile::Wall) {
-      md.dirtyRender = true;
+      if (map.tile(x,y) == Tile::Wall) {
+        map.at(x,y).dirtyRender = true;
+      }
     }
   }
 
@@ -188,7 +207,7 @@ void Game::recalculateLighting()
     [] (void* data, int x, int y) {
       Game& game = *static_cast<Game*>(data);
 
-      return game.map.inBounds(x,y) && game.map.at(x,y).tile == Tile::Wall;
+      return game.map.inBounds(x,y) && game.map.tile(x,y) == Tile::Wall;
     });
 
   fov_settings_set_apply_lighting_function(
@@ -223,11 +242,11 @@ void Game::recalculateLighting()
       {
         ls = Source::Player;
         lightRadius = RADIUS;
-      } else if (map.at(x,y).tile == Tile::Dust)
+      } else if (map.tile(x,y) == Tile::Dust)
       {
         ls = Source::Dust;
         lightRadius = 2;
-      } else if (map.at(x,y).tile == Tile::Lamp)
+      } else if (map.tile(x,y) == Tile::Lamp)
       {
         ls = Source::Lamp;
         lightRadius = RADIUS;
@@ -265,7 +284,7 @@ void Game::recalculateRender() {
       if (map.at(x,y).dirtyRender) {
         map.at(x,y).dirtyRender = false;
 
-        if (map.at(x,y).tile == Tile::Floor) {
+        if (map.tile(x,y) == Tile::Floor) {
           int renderDesc = 0;
           if (isTileSetOrNotLit(map, x-1, y-1)) renderDesc |= (1 << 7);
           if (isTileSetOrNotLit(map, x  , y-1)) renderDesc |= (1 << 6);
@@ -297,7 +316,7 @@ void Game::recalculateRender() {
             map.at(x,y).renderId = -1;
             map.at(x,y).sign = false;
           }
-        } else if (map.at(x,y).tile == Tile::Wall) {
+        } else if (map.tile(x,y) == Tile::Wall) {
           static bool initWalls = false;
           static std::vector<int> wallRenders(256, TilesetIndex(0, 0));
           if (!initWalls) {
@@ -439,12 +458,12 @@ void Game::popLamp(int x, int y, size_t chain)
 {
   muxer.playSoundAtPosition("pop", x, y);
 
-  if (map.at(x,y).tile == Tile::Lamp)
+  if (map.tile(x,y) == Tile::Lamp)
   {
     numLamps--;
   }
 
-  map.at(x,y).tile = Tile::Dust;
+  map.tile(x,y) = Tile::Dust;
   map.at(x,y).dustLife = 2;
   numDust++;
   dirtyLighting = true;
@@ -465,19 +484,19 @@ void Game::processKickup()
         coord c {x,y};
 
         if (map.inBounds(x,y) &&
-            (map.at(x,y).tile == Tile::Floor || map.at(x,y).tile == Tile::Lamp) &&
+            (map.tile(x,y) == Tile::Floor || map.tile(x,y) == Tile::Lamp) &&
             !kickup.done.count(c))
         {
           newFront.insert(c);
           kickup.done.insert(c);
 
-          if (map.at(x,y).tile == Tile::Floor)
+          if (map.tile(x,y) == Tile::Floor)
           {
-            map.at(x,y).tile = Tile::Dust;
+            map.tile(x,y) = Tile::Dust;
             map.at(x,y).dustLife = 2;
             numDust++;
             dirtyLighting = true;
-          } else if (map.at(x,y).tile == Tile::Lamp)
+          } else if (map.tile(x,y) == Tile::Lamp)
           {
             popLamp(x, y, kickup.chain + 1);
           }
@@ -571,11 +590,11 @@ void Game::setZoom(size_t zoom)
 }
 
 void Game::performDash() {
-  if (map.at(player_x, player_y).tile == Tile::Floor) {
+  if (map.tile(player_x, player_y) == Tile::Floor) {
     std::vector<coord> freeSpaces;
 
     auto addIfFree = [&] (int x, int y) {
-      if (map.inBounds(x,y) && map.at(x,y).tile == Tile::Floor)
+      if (map.inBounds(x,y) && map.tile(x,y) == Tile::Floor)
       {
         freeSpaces.emplace_back(x, y);
       }
@@ -592,7 +611,7 @@ void Game::performDash() {
 
     if (!freeSpaces.empty())
     {
-      map.at(player_x, player_y).tile = Tile::Lamp;
+      map.tile(player_x, player_y) = Tile::Lamp;
       numLamps++;
       dirtyLighting = true;
       kickUpDust(player_x, player_y, 0);
@@ -725,18 +744,19 @@ void Game::updatePlaying(size_t frameTime) {
   {
     numDust = 0;
 
-    for (MapData& md : map.data())
-    {
-      if (md.tile == Tile::Dust)
-      {
-        md.dustLife--;
-
-        if (md.dustLife <= 0)
+    for (int y=map.getTop(); y<map.getBottom(); y++) {
+      for (int x=map.getLeft(); x<map.getRight(); x++) {
+        if (map.tile(x,y) == Tile::Dust)
         {
-          md.tile = Tile::Floor;
-          dirtyLighting = true;
-        } else {
-          numDust++;
+          map.at(x,y).dustLife--;
+
+          if (map.at(x,y).dustLife <= 0)
+          {
+            map.tile(x,y) = Tile::Floor;
+            dirtyLighting = true;
+          } else {
+            numDust++;
+          }
         }
       }
     }
@@ -784,7 +804,7 @@ void Game::updatePlaying(size_t frameTime) {
           {
             for (int x = map.getLeft(); x < map.getRight(); x++)
             {
-              if (map.at(x,y).tile == Tile::Lamp)
+              if (map.tile(x,y) == Tile::Lamp)
               {
                 lamps.emplace_back(x, y);
               }
@@ -874,29 +894,24 @@ void Game::updatePlaying(size_t frameTime) {
       {
         if (!map.at(x,y).lit && map.at(x,y).wasLit)
         {
+          Tile oldTile = map.tile(x,y);
           if (std::bernoulli_distribution(0.5)(rng))
           {
-            map.at(x,y).tile = Tile::Wall;
+            map.tile(x,y) = Tile::Wall;
           } else {
-            map.at(x,y).tile = Tile::Floor;
+            map.tile(x,y) = Tile::Floor;
+          }
+          if (map.tile(x,y) != oldTile) {
+            map.at(x,y).dirtyRender = true;
+            map.markDirtyAround(x,y);
           }
-          map.at(x,y).dirtyRender = true;
         }
       }
     }
 
-    /*int x1 = player_x - curZoom * ZOOM_X_FACTOR / 2 - 1;
-    int y1 = player_y - curZoom * ZOOM_Y_FACTOR / 2 - 1;
-    int x2 = player_x + curZoom * ZOOM_X_FACTOR / 2 + 2;
-    int y2 = player_y + curZoom * ZOOM_Y_FACTOR / 2 + 2;*/
-    int x1 = player_x - CHUNK_WIDTH / 2 - 1;
-    int y1 = player_y - CHUNK_HEIGHT / 2 - 1;
-    int x2 = player_x + CHUNK_WIDTH / 2 + 2;
-    int y2 = player_y + CHUNK_HEIGHT / 2 + 2;
-
-    tick(x1, y1, x2, y2, false, true);
-    tick(x1, y1, x2, y2, false, true);
-    tick(x1, y1, x2, y2, false, true);
+    tickDirty(true);
+    tickDirty(true);
+    tickDirty(true);
 
     // TODO: better zoom algorithm
     setZoom(litSpots / 1500 + INIT_ZOOM);