AI doesn't settle very unfavorable locations

[tuvus]

The AI sometimes settles in the middle of a desert or poles with very little resources around. This PR tries to fix that by adding a minimum value that a location must have in order for the AI to settle it.

Details

This value is currently set to 50. The picture below shows a location with a value of 45 so the settler would not settle here. Note that adding 2.5 more grassland tiles would convince the settlers to settle here. Any sort of resources would also convince them to settle. Note that locations ranked above 100 are usually good locations to settle. The value can go to over 150.

Sometimes the value of a location can go negative (eg. between two cities). Before this PR the AI would still settle there. Now, the AI should leave more space (in some scenarios).

More Pictures with the change

As shown in the picture above, the AI will still settle the tundra created by rivers in the snow area.

While this does seem like a relatively simple idea, it might break a few mods. So maybe the value should be lower a lot more or just set to 0 to filter the negatively valued locations. Or we could make this value modable so some mods can override it.

The alternative would be to search a much greater distance or develop a complex heuristic as to where the settler should go for a better location.

Also, I need to work on something that can check if a city is close to the edge of a map, since that is also bad.

What are your thoughts?

[github-actions[bot]]

This PR is stale because it has been open 45 days with no activity. Remove stale label or comment or this will be closed in 10 days.

[github-actions[bot]]

This PR was closed because it has been stalled for 10 days with no activity.

[yairm210]

This is a good idea, I've been auto ignoring it because it's a draft, but I like 👍🏿 It's also small, and easily reversible if we see it causes problems, so I approve @tuvus is there a reason for this to be draft?

[SomeTroglodyte]

I'd also say let's get this in... But I had to look and will add my dos centavos:

• getBestTilesToFoundCity signature: An optional param followed by a nonoptional, which has the same value in all existing calls. Fine by function, just doesn't taste right.
• Hardcoded 50f - wouldn't mods changing a lot of tile / resource yields need different thresholds?
• I'd make minimumValue a Float? = null and fetch a ModConstant for the null - tightens diff as two files touched could go back to untouched?
• Adds a few points of Kdoc neediness - I mean unit is obvious, distanceToSearch mostly (but effect of omitting could use a hint), now minval - what's the value's unit, scale, relative to what etc? Not obvious...
• That if (distanceToSearch != null) distanceToSearch else - that's an Elvis that seems needlessly converted to Java. I know the compiler gets confused and will see ?: {stuff} as assigning a lambda, but giving the block a local function with a name fixes that and makes for readability? Worth it or not? ^1
• Might affect that // Special case, we want AI to settle in place on turn 1. comment - if the mapgen / gamestarter happens to place the first settler on a 49f value tile it will start to move instead. Which is the point of your PR - but why does the situation even arise then??? Would the necessary extremes not affect everybody to a similar degree? What if the terrain is mod-made so poor all tiles end up below the threshold?
• How about changing "fetch a ModConstant" to "calculate an average over all candidate tiles on the map - no - better - a specific percentile we define - I'd say 0.25 if we just want them to avoid the very worst places late in the game, up to 0.75 if we want them to be picky and only found really juicy places? Maybe even move the percentile as a function of map crowdedness? Count of settleable tiles vs count of players - 100:1->0.75..5:1->0.25? Then cache that on TileMap or even on GameInfo - serialized as it's costly to calc but cheap to save. And cache means could be done very early - at the conclusion of gamestarter. hey, a dynamic done in gamestarter could even do stuff like - take all original starting locations, discard outliers, save minimum, half of that is threshold...
• val baseTileMap- suboptimal name. Isn't that a purely local cache for partial ranking values?

fun distanceToSearchDefault(): Int { val distanceFromHome = if (unit.civ.cities.isEmpty()) 0 else unit.civ.cities.minOf { it.getCenterTile().aerialDistanceTo(unit.getTile()) } return (8 - distanceFromHome).coerceIn(1, 5) // Restrict vision when far from home to avoid death marches }

    val range =  distanceToSearch ?: distanceToSearchDefault()

[SomeTroglodyte]

Played around a bit more and - the range of tile rankings at turn zero is quite interesting. The distribution seems to almost always have extreme outliers - one or two in twenty - that are less than a third of the average, sometimes way into the negative. Must be city-states getting leftovers. So a median is best bet to get something relative to mods and map randomness...

Index: core/src/com/unciv/logic/GameInfo.kt
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/core/src/com/unciv/logic/GameInfo.kt b/core/src/com/unciv/logic/GameInfo.kt
--- a/core/src/com/unciv/logic/GameInfo.kt	(revision 5ee662a744e222ae8bf253f2d8e007b52016a00f)
+++ b/core/src/com/unciv/logic/GameInfo.kt	(date 1715302643287)
@@ -13,6 +13,7 @@
 import com.unciv.logic.GameInfo.Companion.CURRENT_COMPATIBILITY_NUMBER
 import com.unciv.logic.GameInfo.Companion.FIRST_WITHOUT
 import com.unciv.logic.automation.civilization.BarbarianManager
+import com.unciv.logic.automation.unit.CityLocationTileRanker
 import com.unciv.logic.city.City
 import com.unciv.logic.civilization.Civilization
 import com.unciv.logic.civilization.CivilizationInfoPreview
@@ -39,6 +40,7 @@
 import com.unciv.models.translations.tr
 import com.unciv.ui.audio.MusicMood
 import com.unciv.ui.audio.MusicTrackChooserFlags
+import com.unciv.ui.components.extensions.medianOrDefault
 import com.unciv.ui.screens.savescreens.Gzip
 import com.unciv.ui.screens.worldscreen.status.NextTurnProgress
 import com.unciv.utils.DebugUtils
@@ -175,6 +177,20 @@
     @Transient
     var cityDistances: CityDistanceData = CityDistanceData()
 
+    @delegate:Transient
+    val cityLocationTileRankerThreshold by lazy {
+        val uniqueCache = LocalUniqueCache()
+        val tileRankCache = HashMap<Tile, Float>()
+        val ranks = civilizations.asSequence().flatMap { civ ->
+            civ.units.getCivUnits()
+                .filter { it.baseUnit.isCityFounder() }
+                .map { unit ->
+                    CityLocationTileRanker.rankTileToSettle(unit.currentTile, civ, sequenceOf(), tileRankCache, uniqueCache)
+                }
+        }
+        ranks.medianOrDefault(100f) * 0.42f  // ends up close to 50f in vanilla games
+    }
+
     //endregion
     //region Pure functions
 
Index: core/src/com/unciv/ui/components/extensions/CollectionExtensions.kt
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/core/src/com/unciv/ui/components/extensions/CollectionExtensions.kt b/core/src/com/unciv/ui/components/extensions/CollectionExtensions.kt
--- a/core/src/com/unciv/ui/components/extensions/CollectionExtensions.kt	(revision 5ee662a744e222ae8bf253f2d8e007b52016a00f)
+++ b/core/src/com/unciv/ui/components/extensions/CollectionExtensions.kt	(date 1715302643279)
@@ -105,3 +105,17 @@
 /** Simplifies testing whether in a sparse map of sets the [element] exists for [key]. */
 fun <KT, ET> HashMap<KT, HashSet<ET>>.contains(key: KT, element: ET) =
     get(key)?.contains(element) == true
+
+/** Statistical Median for a Sequence of Floats
+ *  - Iterates the Sequence only once
+ *  - Not a generic because `Number` does not cover plus or division
+ */
+fun Sequence<Float>.medianOrDefault(default: Float): Float {
+    val materialized = toCollection(arrayListOf()) // same as toMutableList but retains the knowledge that the RandomAccess interface is supported
+    if (materialized.isEmpty()) return default
+    if (materialized.size > 2) materialized.sort()
+    val index1 = (materialized.size - 1) / 2
+    val index2 = materialized.size / 2
+    if (index1 == index2) return materialized[index1]
+    return (materialized[index1] + materialized[index2]) / 2
+}
Index: core/src/com/unciv/ui/screens/worldscreen/WorldMapHolder.kt
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/core/src/com/unciv/ui/screens/worldscreen/WorldMapHolder.kt b/core/src/com/unciv/ui/screens/worldscreen/WorldMapHolder.kt
--- a/core/src/com/unciv/ui/screens/worldscreen/WorldMapHolder.kt	(revision 5ee662a744e222ae8bf253f2d8e007b52016a00f)
+++ b/core/src/com/unciv/ui/screens/worldscreen/WorldMapHolder.kt	(date 1715253970349)
@@ -855,7 +855,7 @@
         // Highlight best tiles for city founding
         if (unit.hasUnique(UniqueType.FoundCity)
                 && UncivGame.Current.settings.showSettlersSuggestedCityLocations) {
-            CityLocationTileRanker.getBestTilesToFoundCity(unit, minimumValue = 50f).tileRankMap.asSequence()
+            CityLocationTileRanker.getBestTilesToFoundCity(unit).tileRankMap.asSequence()
                 .filter { it.key.isExplored(unit.civ) }.sortedByDescending { it.value }.take(3).forEach {
                 tileGroups[it.key]!!.layerOverlay.showGoodCityLocationIndicator()
             }
Index: core/src/com/unciv/logic/automation/unit/CityLocationTileRanker.kt
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/core/src/com/unciv/logic/automation/unit/CityLocationTileRanker.kt b/core/src/com/unciv/logic/automation/unit/CityLocationTileRanker.kt
--- a/core/src/com/unciv/logic/automation/unit/CityLocationTileRanker.kt	(revision 5ee662a744e222ae8bf253f2d8e007b52016a00f)
+++ b/core/src/com/unciv/logic/automation/unit/CityLocationTileRanker.kt	(date 1715303384412)
@@ -21,12 +21,16 @@
     /**
      * Returns a hashmap of tiles to their ranking plus the a the highest value tile and its value
      */
-    fun getBestTilesToFoundCity(unit: MapUnit, distanceToSearch: Int? = null, minimumValue: Float): BestTilesToFoundCity {
-        val range =  if (distanceToSearch != null) distanceToSearch else {
+    fun getBestTilesToFoundCity(unit: MapUnit, distanceToSearch: Int? = null, minimumValue: Float? = null): BestTilesToFoundCity {
+        fun distanceToSearchDefault(): Int {
             val distanceFromHome = if (unit.civ.cities.isEmpty()) 0
             else unit.civ.cities.minOf { it.getCenterTile().aerialDistanceTo(unit.getTile()) }
-            (8 - distanceFromHome).coerceIn(1, 5) // Restrict vision when far from home to avoid death marches
+            return (8 - distanceFromHome).coerceIn(1, 5) // Restrict vision when far from home to avoid death marches
         }
+
+        val range =  distanceToSearch ?: distanceToSearchDefault()
+        val minRank = minimumValue ?: unit.civ.gameInfo.cityLocationTileRankerThreshold
+
         val nearbyCities = unit.civ.gameInfo.getCities()
             .filter { it.getCenterTile().aerialDistanceTo(unit.getTile()) <= 7 + range }
 
@@ -39,15 +43,14 @@
         val possibleTileLocationsWithRank = possibleCityLocations
             .map {
                 val tileValue = rankTileToSettle(it, unit.civ, nearbyCities, baseTileMap, uniqueCache)
-                if (tileValue >= minimumValue)
+                if (tileValue >= minRank)
                     bestTilesToFoundCity.tileRankMap[it] = tileValue
-
                 Pair(it, tileValue)
-            }.filter { it.second >= minimumValue }
+            }.filter { it.second >= minRank }
             .sortedByDescending { it.second }
 
         val bestReachableTile = possibleTileLocationsWithRank.firstOrNull { unit.movement.canReach(it.first) }
-        if (bestReachableTile != null){
+        if (bestReachableTile != null) {
             bestTilesToFoundCity.bestTile = bestReachableTile.first
             bestTilesToFoundCity.bestTileRank = bestReachableTile.second
         }
@@ -77,7 +80,7 @@
         return true
     }
 
-    private fun rankTileToSettle(newCityTile: Tile, civ: Civilization, nearbyCities: Sequence<City>,
+    fun rankTileToSettle(newCityTile: Tile, civ: Civilization, nearbyCities: Sequence<City>,
                                  baseTileMap: HashMap<Tile, Float>, uniqueCache: LocalUniqueCache): Float {
         var tileValue = 0f
         tileValue += getDistanceToCityModifier(newCityTile, nearbyCities, civ)
Index: core/src/com/unciv/logic/automation/unit/SpecificUnitAutomation.kt
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/core/src/com/unciv/logic/automation/unit/SpecificUnitAutomation.kt b/core/src/com/unciv/logic/automation/unit/SpecificUnitAutomation.kt
--- a/core/src/com/unciv/logic/automation/unit/SpecificUnitAutomation.kt	(revision 5ee662a744e222ae8bf253f2d8e007b52016a00f)
+++ b/core/src/com/unciv/logic/automation/unit/SpecificUnitAutomation.kt	(date 1715253970381)
@@ -107,7 +107,7 @@
 
         // It's possible that we'll see a tile "over the sea" that's better than the tiles close by, but that's not a reason to abandon the close tiles!
         // Also this lead to some routing problems, see https://github.com/yairm210/Unciv/issues/3653
-        val bestTilesInfo = CityLocationTileRanker.getBestTilesToFoundCity(unit, rangeToSearch, 50f)
+        val bestTilesInfo = CityLocationTileRanker.getBestTilesToFoundCity(unit, rangeToSearch)
         var bestCityLocation: Tile? = null
 
         if (unit.civ.gameInfo.turns == 0 && unit.civ.cities.isEmpty() && bestTilesInfo.tileRankMap.containsKey(unit.getTile())) {   // Special case, we want AI to settle in place on turn 1.

...looks good from debugger inspection at several turn 0 starts. All values seen were 50f +/- 5.

That lazy value won't do of course in production as it needs to persist, but I was lazy and only wanted to see first turns. And no. Gdx Json can't read into lazies and un-lazy them while doing so... Could be a var with caching get and a private set, or somesuch. And for backwards compat it would need to detect the compat case then include all tiles with original capitals instead of or in addition to the tiles under all settlers on the map - better instead of after turn two.

[tuvus]

Alrighty, looking at this again it seems like it is more needed than I thought.

I added a few more changes including the original.

• The AI doesn't put cities in the ice zones as much
• It doesn't settle on the borders of the map like before
• It also tries to settle 7 tiles away from nearby cities (the perfect distance with no tiles in between)
• The AI doesn't value building a city on the coast as much (since non resource water tiles can't have improvements)

Pictures

Before

After

I think modding this will probably have to go into a different PR as I would need to look into that more.