From 5324adfe51f1348fc97fe2ee0ca4e4bbd2a6ad64 Mon Sep 17 00:00:00 2001 From: Star Rauchenberger 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/game.cpp | 195 ++++++++++++++++++++++++++++++------------------------- src/game.h | 4 +- src/map.h | 94 +++++++++++++++++++++++++-- src/renderer.cpp | 4 +- 4 files changed, 200 insertions(+), 97 deletions(-) (limited to 'src') diff --git a/src/game.cpp b/src/game.cpp index 088ab4d..9d557e3 100644 --- a/src/game.cpp +++ b/src/game.cpp @@ -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& 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 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(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 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 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 mapDoubleBuffer; + std::vector mapDoubleBuffer; int player_x = 0; int player_y = 0; @@ -111,6 +111,8 @@ public: private: + void tickDirty(bool onlyDark); + void tick( int x1, int y1, 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 tiles; std::array 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(static_cast(*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(static_cast(*this).at(x, y)); } + inline const std::vector& tiles() const + { + return loadedTiles_; + } + + inline std::vector& tiles() + { + return loadedTiles_; + } + inline const std::vector& data() const { return loaded_; @@ -139,6 +159,11 @@ public: int startX = chunkX * CHUNK_WIDTH; int startY = chunkY * CHUNK_HEIGHT; for (int y=0; y(width_ * height_); + loadedTiles_ = std::vector(width_ * height_, Tile::Floor); + dirtyTiles_.clear(); + dirtySet_ = std::vector(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 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 loadedTiles_; std::vector loaded_; std::vector chunks_; @@ -235,6 +318,9 @@ private: std::map> chunkByPos_; // chunkByPos_[X][Y] int unloadedLitTiles_ = 0; + + std::vector dirtyTiles_; + std::vector dirtySet_; }; #endif /* end of include guard: MAP_H_3AB00D12 */ diff --git a/src/renderer.cpp b/src/renderer.cpp index c8c1746..9744e70 100644 --- a/src/renderer.cpp +++ b/src/renderer.cpp @@ -173,7 +173,7 @@ void Renderer::renderGame( if (draw) { - if (game.map.at(x,y).tile != Tile::Wall) { + if (game.map.tile(x,y) != Tile::Wall) { SDL_Rect tileRect {17 * 16, 15 * 16, 16, 16}; SDL_RenderCopy(ren_.get(), tileset_.get(), &tileRect, &rect); @@ -192,7 +192,7 @@ void Renderer::renderGame( SDL_RenderCopy(ren_.get(), tileset_.get(), &tileRect, &rect); } - if (game.map.at(x,y).tile == Tile::Lamp) { + if (game.map.tile(x,y) == Tile::Lamp) { SDL_RenderCopy(ren_.get(), lamp_.get(), nullptr, &rect); } -- cgit 1.4.1