clear the cache

src/main/cpp/net/eagle0/shardok/library/BUILD.bazel

@@ -7,6 +7,7 @@ cc_library(
     copts = COPTS,
     visibility = ["//visibility:public"],
     deps = [
+        ":unit_location_cache",
         ":unit_placement_info",
         "//src/main/cpp/net/eagle0/shardok/library/actions:perform_undead_commands_action",
         "//src/main/cpp/net/eagle0/shardok/library/actions:update_game_status_action",
@@ -163,3 +164,16 @@ cc_library(
         ":shardok_c_types",
     ],
 )
+
+cc_library(
+    name = "unit_location_cache",
+    srcs = ["unit_location_cache/UnitLocationCache.cpp"],
+    hdrs = ["unit_location_cache/UnitLocationCache.hpp"],
+    copts = COPTS,
+    visibility = ["//src/main/cpp/net/eagle0/shardok/library:__subpackages__"],
+    deps = [
+        ":shardok_c_types",
+        "//src/main/flatbuffer/net/eagle0/shardok/storage:game_state_cc_fbs",
+        "//src/main/flatbuffer/net/eagle0/shardok/storage:unit_cc_fbs",
+    ],
+)

src/main/cpp/net/eagle0/shardok/library/ShardokEngine.cpp

@@ -21,6 +21,7 @@
 #include "src/main/cpp/net/eagle0/shardok/library/actions/UpdateOpponentKnowledgeAction.hpp"
 #include "src/main/cpp/net/eagle0/shardok/library/fb_helpers/GameStateHelpers.hpp"
 #include "src/main/cpp/net/eagle0/shardok/library/map/TileModifierWithCoords.hpp"
+#include "src/main/cpp/net/eagle0/shardok/library/unit_location_cache/UnitLocationCache.hpp"
 #include "src/main/cpp/net/eagle0/shardok/library/util/ActionResultFlatbufferHelpers.hpp"
 #include "src/main/cpp/net/eagle0/shardok/library/util/PlayerUtils.hpp"
 #include "src/main/cpp/net/eagle0/shardok/library/util/WeatherHelpers.hpp"
@@ -99,6 +100,9 @@ void ShardokEngine::ApplyAndAddActionResults(const vector<ActionResultProto> &re
 void ShardokEngine::ApplyAndAddActionResult(const ActionResultProto &result) {
     MutatingApplyResult(gameState, result, settingsGetter);
 
+    // Clear the unit location cache since the game state has been modified
+    UnitLocationCache::clearCache();
+
     if (trackHistory) {
         actionHistory.emplace_back();
         *actionHistory.back().mutable_action_result() = result;
@@ -460,7 +464,7 @@ void ShardokEngine::HandleActionResult(
         const Coords modifiedCoords = FromCoordsProto(modifierWithCoords.coords());
         const TileModifierProto &modifier = modifierWithCoords.modifiers();
 
-        const Unit *occupant = Occupant(GetCurrentGameState()->units(), modifiedCoords);
+        const Unit *occupant = OccupantFast(GetCurrentGameState(), modifiedCoords);
         // Check for swept away hero
         if (const Terrain *terrain = GetTerrain(GetCurrentGameState()->hex_map(), modifiedCoords);
             occupant && IsWater(terrain->type()) && !IsTraversible(modifier) &&

src/main/cpp/net/eagle0/shardok/library/action_factories/PlayerSetupCommandFactory.cpp

@@ -28,7 +28,7 @@ auto PlayerSetupCommandFactory::AddAvailablePlaceAndHideUnitCommandsForOneUnit(
 
     CoordsSet unusedStartingPositions(gameState->hex_map());
     for (const Coords *possiblePosition : *thisUnitStartingPositions) {
-        if (!Occupant(gameState->units(), *possiblePosition)) {
+        if (!OccupantFast(gameState, *possiblePosition)) {
             unusedStartingPositions.Add(*possiblePosition);
         }
     }
@@ -37,7 +37,7 @@ auto PlayerSetupCommandFactory::AddAvailablePlaceAndHideUnitCommandsForOneUnit(
     CoordsSet unusedHidingPositions(gameState->hex_map());
 
     for (const Coords &possibleHidingPosition : GetAllCoords(gameState->hex_map())) {
-        if (!Occupant(gameState->units(), possibleHidingPosition)) {
+        if (!OccupantFast(gameState, possibleHidingPosition)) {
             const Terrain *terrain = GetTerrain(gameState->hex_map(), possibleHidingPosition);
             if (AllowsHiding(terrain)) { unusedHidingPositions.Add(possibleHidingPosition); }
         }

src/main/cpp/net/eagle0/shardok/library/actions/FallIntoWaterAction.cpp

@@ -78,7 +78,7 @@ auto FallIntoWaterAction::AdjacentsWithTerrain(
     vector<AdjacentWithTerrain> vec{};
 
     for (const Coords &adjCoords : adjacentCoords) {
-        const auto *possibleOccupant = Occupant(gameState->units(), adjCoords);
+        const auto *possibleOccupant = OccupantFast(gameState, adjCoords);
         if (possibleOccupant &&
             (possibleOccupant->player_id() == playerId || !possibleOccupant->hidden())) {
             continue;
@@ -151,7 +151,7 @@ auto FallIntoWaterAction::InternalExecute(
 
         for (const auto &adjWithTerrain : adjacentCoordsAndTerrain) {
             const auto *possibleOccupant =
-                    Occupant(currentState->units(), adjWithTerrain.adjacentCoords);
+                    OccupantFast(currentState, adjWithTerrain.adjacentCoords);
             if (possibleOccupant && (possibleOccupant->player_id() == fallerAfter.player_id() ||
                                      !possibleOccupant->hidden())) {
                 continue;
@@ -172,7 +172,7 @@ auto FallIntoWaterAction::InternalExecute(
             }
         }
 
-        if (found && !Occupant(currentState->units(), bestCoords)) {
+        if (found && !OccupantFast(currentState, bestCoords)) {
             PercentileRollOdds odds = EscapeChance(
                     baseEscapeOdds,
                     bestTerrain,

src/main/cpp/net/eagle0/shardok/library/actions/MeteorCastAction.cpp

@@ -182,7 +182,7 @@ auto MeteorCastAction::PerformOneActorCast(
     results.push_back(mainResult);
 
     const Coords target = actorBefore->attached_hero().profession_info().cast_target();
-    const Unit *possibleOccupant = Occupant(runningGameState->units(), target);
+    const Unit *possibleOccupant = OccupantFast(runningGameState, target);
     const Terrain *targetTerrain = GetTerrain(startingGameState->hex_map(), target);
     if (possibleOccupant) {
         // Direct damage action
@@ -247,7 +247,7 @@ auto MeteorCastAction::PerformOneActorCast(
     for (const Coords &splashCoords : adjacentCoords) {
         const auto &splashTerrain = GetTerrain(runningGameState->hex_map(), splashCoords);
 
-        const Unit *splashOccupant = Occupant(runningGameState->units(), splashCoords);
+        const Unit *splashOccupant = OccupantFast(runningGameState, splashCoords);
         if (splashOccupant) {
             MeteorUnitDamageAction splashUnitDamageAction(
                     settings,
@@ -300,7 +300,7 @@ auto MeteorCastAction::PerformOneActorCast(
 
     // Check for fallen heroes
     for (const Coords &coords : destroyedBridgeOrIceTiles) {
-        const auto *maybeOccupant = Occupant(runningGameState->units(), coords);
+        const auto *maybeOccupant = OccupantFast(runningGameState, coords);
         if (maybeOccupant) {
             const BattalionTypeSPtr &battalionType =
                     settings.GetBattalionType(maybeOccupant->battalion().type());

src/main/cpp/net/eagle0/shardok/library/actions/UpdateGameStatusAction.cpp

@@ -5,6 +5,7 @@
 #include "UpdateGameStatusAction.hpp"
 
 #include "src/main/cpp/net/eagle0/shardok/library/util/ActionResultFlatbufferHelpers.hpp"
+#include "src/main/cpp/net/eagle0/shardok/library/util/HexMapUtils.hpp"
 #include "src/main/flatbuffer/net/eagle0/shardok/storage/game_status.hpp"
 #include "src/main/flatbuffer/net/eagle0/shardok/storage/player_info.hpp"
 #include "src/main/flatbuffer/net/eagle0/shardok/storage/victory_condition.hpp"
@@ -229,7 +230,7 @@ auto UpdateGameStatusAction::InternalExecute(
                 // Check for attacker occupying castles & towns
                 bool foundUncontrolledCriticalTile = false;
                 for (const auto& criticalTile : criticalTileLocations) {
-                    const auto* possibleOccupant = Occupant(gameState->units(), criticalTile);
+                    const auto* possibleOccupant = OccupantFast(gameState, criticalTile);
 
                     if (!possibleOccupant) {
                         foundUncontrolledCriticalTile = true;

src/main/cpp/net/eagle0/shardok/library/unit_location_cache/UnitLocationCache.cpp

@@ -0,0 +1,75 @@
+//
+// UnitLocationCache.cpp
+// Implementation of O(1) unit location cache
+//
+
+#include "UnitLocationCache.hpp"
+
+#include "src/main/flatbuffer/net/eagle0/shardok/storage/unit.hpp"
+
+namespace shardok {
+
+// Thread-local cache storage
+thread_local std::unordered_map<
+        UnitLocationCacheKey,
+        std::unique_ptr<UnitLocationCacheEntry>,
+        UnitLocationCacheKeyHash>
+        UnitLocationCache::cache;
+
+auto UnitLocationCache::buildCacheEntry(const GameState* gameState)
+        -> std::unique_ptr<UnitLocationCacheEntry> {
+    const auto* hexMap = gameState->hex_map();
+    const int rowCount = hexMap->row_count();
+    const int columnCount = hexMap->column_count();
+
+    auto entry = std::make_unique<UnitLocationCacheEntry>(rowCount, columnCount);
+
+    // Populate the cache by iterating through all units
+    const auto* units = gameState->units();
+    for (int unitIndex = 0; unitIndex < static_cast<int>(units->size()); ++unitIndex) {
+        const auto* unit = units->Get(unitIndex);
+        if (unit && unit->status() == net::eagle0::shardok::storage::fb::UnitStatus_NORMAL_UNIT) {
+            const auto& location = unit->location();
+            const int coordIndex = location.row() * columnCount + location.column();
+
+            // Bounds check to avoid crashes with corrupted data
+            if (coordIndex >= 0 && coordIndex < static_cast<int>(entry->unitsByLocation.size())) {
+                entry->unitsByLocation[coordIndex] = unitIndex;
+            }
+        }
+    }
+
+    return entry;
+}
+
+auto UnitLocationCache::getUnitAt(const GameState* gameState, const Coords& coords) -> const Unit* {
+    const UnitLocationCacheKey key(gameState);
+
+    // Check if we have a cached entry
+    auto it = cache.find(key);
+    if (it == cache.end()) {
+        // Build new cache entry
+        auto entry = buildCacheEntry(gameState);
+        it = cache.emplace(key, std::move(entry)).first;
+    }
+
+    const auto& entry = it->second;
+    const int index = coords.row() * entry->columnCount + coords.column();
+
+    // Bounds check
+    if (index < 0 || index >= static_cast<int>(entry->unitsByLocation.size())) { return nullptr; }
+
+    const int unitIndex = entry->unitsByLocation[index];
+    if (unitIndex == INVALID_UNIT_INDEX) { return nullptr; }
+
+    // Look up the unit by array index (O(1) in FlatBuffer)
+    return gameState->units()->Get(unitIndex);
+}
+
+auto UnitLocationCache::hasUnitAt(const GameState* gameState, const Coords& coords) -> bool {
+    return getUnitAt(gameState, coords) != nullptr;
+}
+
+auto UnitLocationCache::clearCache() -> void { cache.clear(); }
+
+}  // namespace shardok

src/main/cpp/net/eagle0/shardok/library/unit_location_cache/UnitLocationCache.hpp

@@ -0,0 +1,96 @@
+//
+// UnitLocationCache.hpp
+// Cache for O(1) unit lookups by coordinate
+//
+
+#ifndef EAGLE0_UNITLOCATIONCACHE_HPP
+#define EAGLE0_UNITLOCATIONCACHE_HPP
+
+#include <memory>
+#include <unordered_map>
+#include <vector>
+
+#include "src/main/cpp/net/eagle0/shardok/library/ShardokCTypes.h"
+#include "src/main/flatbuffer/net/eagle0/shardok/storage/game_state.hpp"
+#include "src/main/flatbuffer/net/eagle0/shardok/storage/unit.hpp"
+
+namespace shardok {
+
+using Coords = net::eagle0::shardok::storage::fb::Coords;
+using GameState = net::eagle0::shardok::storage::fb::GameState;
+using Unit = net::eagle0::shardok::storage::fb::Unit;
+using Units = flatbuffers::Vector<const Unit*>;
+
+constexpr int INVALID_UNIT_INDEX = -1;
+
+/**
+ * Cache key for the unit location cache based on game state pointer and version
+ */
+struct UnitLocationCacheKey {
+    const GameState* gameState;
+    size_t stateHash;
+
+    UnitLocationCacheKey(const GameState* gs)
+        : gameState(gs),
+          stateHash(std::hash<const void*>{}(gs)) {}
+
+    bool operator==(const UnitLocationCacheKey& other) const {
+        return gameState == other.gameState && stateHash == other.stateHash;
+    }
+};
+
+struct UnitLocationCacheKeyHash {
+    std::size_t operator()(const UnitLocationCacheKey& key) const { return key.stateHash; }
+};
+
+/**
+ * Cache entry containing the unit location array for a specific map
+ */
+struct UnitLocationCacheEntry {
+    std::vector<int> unitsByLocation;
+    int rowCount;
+    int columnCount;
+
+    UnitLocationCacheEntry(int rows, int cols)
+        : unitsByLocation(rows * cols, INVALID_UNIT_INDEX),
+          rowCount(rows),
+          columnCount(cols) {}
+};
+
+/**
+ * Thread-safe cache for O(1) unit location lookups
+ * Replaces the O(n) Occupant() function with array-based indexing
+ */
+class UnitLocationCache {
+private:
+    static thread_local std::unordered_map<
+            UnitLocationCacheKey,
+            std::unique_ptr<UnitLocationCacheEntry>,
+            UnitLocationCacheKeyHash>
+            cache;
+
+    static auto buildCacheEntry(const GameState* gameState)
+            -> std::unique_ptr<UnitLocationCacheEntry>;
+
+public:
+    /**
+     * Get the unit at the specified coordinates, or nullptr if no unit present
+     * O(1) lookup using array indexing
+     */
+    static auto getUnitAt(const GameState* gameState, const Coords& coords) -> const Unit*;
+
+    /**
+     * Check if a unit exists at the specified coordinates
+     * O(1) lookup using array indexing
+     */
+    static auto hasUnitAt(const GameState* gameState, const Coords& coords) -> bool;
+
+    /**
+     * Clear the cache (useful for testing)
+     */
+    static auto clearCache() -> void;
+};
+
+}  // namespace shardok
+
+#endif  // EAGLE0_UNITLOCATIONCACHE_HPP

src/main/cpp/net/eagle0/shardok/library/util/BUILD.bazel

@@ -41,6 +41,7 @@ cc_library(
         ":hex_cube_utils",
         "//src/main/cpp/net/eagle0/common:container_utils",
         "//src/main/cpp/net/eagle0/common:filesystem_utils",
+        "//src/main/cpp/net/eagle0/shardok/library:unit_location_cache",
         "//src/main/cpp/net/eagle0/shardok/library/map:coordinates",
         "//src/main/cpp/net/eagle0/shardok/library/map:coords_set",
         "//src/main/cpp/net/eagle0/shardok/library/map:hex_map_direction",

src/main/cpp/net/eagle0/shardok/library/util/HexMapUtils.cpp

@@ -11,6 +11,7 @@
 #include "HexCubeUtils.hpp"
 #include "src/main/cpp/net/eagle0/common/FilesystemUtils.hpp"
 #include "src/main/cpp/net/eagle0/shardok/library/map/CoordsSet.hpp"
+#include "src/main/cpp/net/eagle0/shardok/library/unit_location_cache/UnitLocationCache.hpp"
 
 namespace shardok {
 
@@ -690,4 +691,20 @@ auto KnownEnemyOccupant(
     return nullptr;
 }
 
+auto KnownEnemyOccupantFast(
+        const PlayerId playerId,
+        const GameState *gameState,
+        const vector<PlayerId> &allyPids,
+        const Coords &coords) -> const Unit * {
+    const auto *occupant = UnitLocationCache::getUnitAt(gameState, coords);
+    if (occupant) {
+        if (!occupant->hidden() && occupant->player_id() != playerId &&
+            !common::Contains(allyPids, occupant->player_id())) {
+            return occupant;
+        }
+    }
+
+    return nullptr;
+}
+
 }  // namespace shardok

src/main/cpp/net/eagle0/shardok/library/util/HexMapUtils.hpp

@@ -16,6 +16,7 @@
 #include "src/main/cpp/net/eagle0/shardok/library/map/CoordsSet.hpp"
 #include "src/main/cpp/net/eagle0/shardok/library/map/HexMapDirection.hpp"
 #include "src/main/cpp/net/eagle0/shardok/library/settings/GameSettings.hpp"
+#include "src/main/cpp/net/eagle0/shardok/library/unit_location_cache/UnitLocationCache.hpp"
 #include "src/main/flatbuffer/net/eagle0/shardok/storage/hex_map.hpp"
 #include "src/main/flatbuffer/net/eagle0/shardok/storage/unit.hpp"
 #include "src/main/protobuf/net/eagle0/shardok/api/unit_view.pb.h"
@@ -97,6 +98,7 @@ auto CoordsAreValid(int rowCount, int columnCount, const Coords &coords) -> bool
 [[nodiscard]] auto TwoAwayTilesUnblockedByMountains(const HexMap *map, const Coords &coords)
         -> CoordsSet;
 
+// DEPRECATED: Use OccupantFast for O(1) performance
 static inline auto Occupant(const Units *units, const Coords &coords) -> const Unit * {
     for (const auto &unit : *units) {
         if (unit->status() == net::eagle0::shardok::storage::fb::UnitStatus_NORMAL_UNIT &&
@@ -108,6 +110,13 @@ static inline auto Occupant(const Units *units, const Coords &coords) -> const U
     return nullptr;
 }
 
+// Optimized O(1) version using UnitLocationCache
+static inline auto OccupantFast(
+        const net::eagle0::shardok::storage::fb::GameState *gameState,
+        const Coords &coords) -> const Unit * {
+    return UnitLocationCache::getUnitAt(gameState, coords);
+}
+
 static inline auto Occupant(const Units &units, const Coords &coords) -> const Unit * {
     for (const auto &unit : units) {
         if (unit->status() == net::eagle0::shardok::storage::fb::UnitStatus_NORMAL_UNIT &&
@@ -239,6 +248,13 @@ auto KnownEnemyOccupant(
         const vector<PlayerId> &allyPids,
         const Coords &coords) -> const Unit *;
 
+// Optimized O(1) version using UnitLocationCache
+auto KnownEnemyOccupantFast(
+        PlayerId playerId,
+        const net::eagle0::shardok::storage::fb::GameState *gameState,
+        const vector<PlayerId> &allyPids,
+        const Coords &coords) -> const Unit *;
+
 template<class UnitContainer>
 auto KnownEnemyOccupant(
         PlayerId playerId,