diff options
Diffstat (limited to 'game-engine/src/main/kotlin')
10 files changed, 417 insertions, 3 deletions
diff --git a/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/cards/Requirements.kt b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/cards/Requirements.kt index e04fa7a0..4417620f 100644 --- a/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/cards/Requirements.kt +++ b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/cards/Requirements.kt @@ -2,9 +2,9 @@ package org.luxons.sevenwonders.game.cards import org.luxons.sevenwonders.game.api.Table import org.luxons.sevenwonders.game.boards.Board -import org.luxons.sevenwonders.game.resources.BestPriceCalculator import org.luxons.sevenwonders.game.resources.ResourceTransactions import org.luxons.sevenwonders.game.resources.Resources +import org.luxons.sevenwonders.game.resources.bestPrice data class Requirements @JvmOverloads constructor( val gold: Int = 0, @@ -55,7 +55,8 @@ data class Requirements @JvmOverloads constructor( if (producesRequiredResources(board)) { return true } - return BestPriceCalculator.bestPrice(resources, table, playerIndex) <= board.gold - gold + val bestPrice = bestPrice(resources, table, playerIndex) + return bestPrice != null && bestPrice <= board.gold - gold } private fun hasRequiredGold(board: Board): Boolean { diff --git a/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/data/serializers/ProductionSerializer.kt b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/data/serializers/ProductionSerializer.kt index 538fdbb4..781ee3af 100644 --- a/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/data/serializers/ProductionSerializer.kt +++ b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/data/serializers/ProductionSerializer.kt @@ -16,7 +16,7 @@ class ProductionSerializer : JsonSerializer<Production>, JsonDeserializer<Produc override fun serialize(production: Production, typeOfSrc: Type, context: JsonSerializationContext): JsonElement { val fixedResources = production.fixedResources - val choices = production.alternativeResources + val choices = production.getAlternativeResources() return when { fixedResources.isEmpty -> serializeAsChoice(choices, context) choices.isEmpty() -> serializeAsResources(fixedResources, context) diff --git a/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/BestPriceCalculator.kt b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/BestPriceCalculator.kt new file mode 100644 index 00000000..6e7d76f6 --- /dev/null +++ b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/BestPriceCalculator.kt @@ -0,0 +1,122 @@ +package org.luxons.sevenwonders.game.resources + +import org.luxons.sevenwonders.game.api.Table +import java.util.ArrayList +import java.util.EnumSet + +fun bestPrice(resources: Resources, table: Table, playerIndex: Int): Int? { + return bestSolution(resources, table, playerIndex)?.price +} + +fun bestTransaction(resources: Resources, table: Table, playerIndex: Int): ResourceTransactions? { + return bestSolution(resources, table, playerIndex)?.transactions +} + +fun bestSolution(resources: Resources, table: Table, playerIndex: Int): TransactionPlan? { + val calculator = BestPriceCalculator(resources, table, playerIndex) + return calculator.computeBestSolution() +} + +data class TransactionPlan(val price: Int, val transactions: ResourceTransactions) + +private class ResourcePool( + val provider: Provider?, + private val rules: TradingRules, + val choices: Set<MutableSet<ResourceType>> +) { + fun getCost(type: ResourceType): Int = if (provider == null) 0 else rules.getCost(type, provider) +} + +private class BestPriceCalculator(resourcesToPay: Resources, table: Table, playerIndex: Int) { + + private val pools: List<ResourcePool> + private val resourcesLeftToPay: Resources + private val boughtResources: ResourceTransactions = ResourceTransactions() + private var pricePaid: Int = 0 + + var bestSolution: ResourceTransactions? = null + var bestPrice: Int = Integer.MAX_VALUE + + init { + val board = table.getBoard(playerIndex) + this.resourcesLeftToPay = resourcesToPay.minus(board.production.fixedResources) + this.pools = createResourcePools(table, playerIndex) + } + + private fun createResourcePools(table: Table, playerIndex: Int): List<ResourcePool> { + val providers = Provider.values() + + val board = table.getBoard(playerIndex) + val rules = board.tradingRules + + val pools = ArrayList<ResourcePool>(providers.size + 1) + // we only take alternative resources here, because fixed resources were already removed for optimization + val ownBoardChoices = board.production.getAlternativeResources() + pools.add(ResourcePool(null, rules, ownBoardChoices.map { it.toMutableSet() }.toSet())) + + for (provider in providers) { + val providerBoard = table.getBoard(playerIndex, provider.boardPosition) + val pool = ResourcePool(provider, rules, providerBoard.publicProduction.asChoices().map { it.toMutableSet() }.toSet()) + pools.add(pool) + } + return pools + } + + fun computeBestSolution(): TransactionPlan? { + computePossibilities() + return if (bestSolution == null) null else TransactionPlan(bestPrice, bestSolution!!) + } + + private fun computePossibilities() { + if (resourcesLeftToPay.isEmpty) { + updateBestSolutionIfNeeded() + return + } + for (type in ResourceType.values()) { + if (resourcesLeftToPay.getQuantity(type) > 0) { + for (pool in pools) { + if (pool.provider == null) { + computeSelfPossibilities(type, pool) + } else { + computeNeighbourPossibilities(pool, type, pool.provider) + } + } + } + } + } + + private fun computeSelfPossibilities(type: ResourceType, pool: ResourcePool) { + resourcesLeftToPay.remove(type, 1) + computePossibilitiesWhenUsing(type, pool) + resourcesLeftToPay.add(type, 1) + } + + private fun computeNeighbourPossibilities(pool: ResourcePool, type: ResourceType, provider: Provider) { + val cost = pool.getCost(type) + resourcesLeftToPay.remove(type, 1) + boughtResources.add(provider, Resources(type)) + pricePaid += cost + computePossibilitiesWhenUsing(type, pool) + pricePaid -= cost + boughtResources.remove(provider, Resources(type)) + resourcesLeftToPay.add(type, 1) + } + + private fun computePossibilitiesWhenUsing(type: ResourceType, pool: ResourcePool) { + for (choice in pool.choices) { + if (choice.contains(type)) { + val temp = EnumSet.copyOf(choice) + choice.clear() + computePossibilities() + choice.addAll(temp) + } + } + } + + private fun updateBestSolutionIfNeeded() { + if (pricePaid < bestPrice) { + bestPrice = pricePaid + bestSolution = ResourceTransactions(boughtResources.asList()) + } + } +} diff --git a/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/Production.kt b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/Production.kt new file mode 100644 index 00000000..1a3240c2 --- /dev/null +++ b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/Production.kt @@ -0,0 +1,95 @@ +package org.luxons.sevenwonders.game.resources + +import java.util.Arrays +import java.util.EnumSet + +class Production { + + val fixedResources = Resources() + private val alternativeResources: MutableSet<Set<ResourceType>> = mutableSetOf() + + fun getAlternativeResources(): Set<Set<ResourceType>> { + return alternativeResources + } + + fun addFixedResource(type: ResourceType, quantity: Int) { + fixedResources.add(type, quantity) + } + + fun addChoice(vararg options: ResourceType) { + val optionSet = EnumSet.copyOf(Arrays.asList(*options)) + alternativeResources.add(optionSet) + } + + fun addAll(resources: Resources) { + fixedResources.addAll(resources) + } + + fun addAll(production: Production) { + fixedResources.addAll(production.fixedResources) + alternativeResources.addAll(production.getAlternativeResources()) + } + + internal fun asChoices(): Set<Set<ResourceType>> { + val fixedAsChoices = fixedResources.asList().map{ EnumSet.of(it) }.toSet() + return fixedAsChoices + alternativeResources + } + + operator fun contains(resources: Resources): Boolean { + if (fixedResources.containsAll(resources)) { + return true + } + return containedInAlternatives(resources - fixedResources) + } + + private fun containedInAlternatives(resources: Resources): Boolean { + return containedInAlternatives(resources, alternativeResources) + } + + private fun containedInAlternatives(resources: Resources, alternatives: MutableSet<Set<ResourceType>>): Boolean { + if (resources.isEmpty) { + return true + } + for (type in ResourceType.values()) { + if (resources.getQuantity(type) <= 0) { + continue + } + val candidate = findFirstAlternativeContaining(alternatives, type) + ?: return false // no alternative produces the resource of this entry + resources.remove(type, 1) + alternatives.remove(candidate) + val remainingAreContainedToo = containedInAlternatives(resources, alternatives) + resources.add(type, 1) + alternatives.add(candidate) + if (remainingAreContainedToo) { + return true + } + } + return false + } + + private fun findFirstAlternativeContaining( + alternatives: Set<Set<ResourceType>>, + type: ResourceType + ): Set<ResourceType>? { + return alternatives.stream().filter { a -> a.contains(type) }.findAny().orElse(null) + } + + override fun equals(other: Any?): Boolean { + if (this === other) return true + if (javaClass != other?.javaClass) return false + + other as Production + + if (fixedResources != other.fixedResources) return false + if (alternativeResources != other.alternativeResources) return false + + return true + } + + override fun hashCode(): Int { + var result = fixedResources.hashCode() + result = 31 * result + alternativeResources.hashCode() + return result + } +} diff --git a/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/Provider.kt b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/Provider.kt new file mode 100644 index 00000000..5d0f3159 --- /dev/null +++ b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/Provider.kt @@ -0,0 +1,8 @@ +package org.luxons.sevenwonders.game.resources + +import org.luxons.sevenwonders.game.boards.RelativeBoardPosition + +enum class Provider(val boardPosition: RelativeBoardPosition) { + LEFT_PLAYER(RelativeBoardPosition.LEFT), + RIGHT_PLAYER(RelativeBoardPosition.RIGHT) +} diff --git a/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/ResourceTransaction.kt b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/ResourceTransaction.kt new file mode 100644 index 00000000..c500f0d0 --- /dev/null +++ b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/ResourceTransaction.kt @@ -0,0 +1,15 @@ +package org.luxons.sevenwonders.game.resources + +import org.luxons.sevenwonders.game.api.Table + +data class ResourceTransaction(val provider: Provider, val resources: Resources) { + + internal fun execute(table: Table, playerIndex: Int) { + val board = table.getBoard(playerIndex) + val price = board.tradingRules.computeCost(this) + board.removeGold(price) + val providerPosition = provider.boardPosition + val providerBoard = table.getBoard(playerIndex, providerPosition) + providerBoard.addGold(price) + } +} diff --git a/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/ResourceTransactions.kt b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/ResourceTransactions.kt new file mode 100644 index 00000000..24556d19 --- /dev/null +++ b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/ResourceTransactions.kt @@ -0,0 +1,37 @@ +package org.luxons.sevenwonders.game.resources + +import org.luxons.sevenwonders.game.api.Table + +data class ResourceTransactions(private val resourcesByProvider: MutableMap<Provider, Resources> = mutableMapOf()) { + + constructor(transactions: Collection<ResourceTransaction>) : this() { + transactions.forEach { t -> add(t.provider, t.resources) } + } + + fun add(provider: Provider, resources: Resources) { + resourcesByProvider.merge(provider, resources) { old, new -> old + new } + } + + fun remove(provider: Provider, resources: Resources) { + resourcesByProvider.compute(provider) { p, prevResources -> + if (prevResources == null) { + throw IllegalStateException("Cannot remove resources from resource transactions") + } + prevResources.minus(resources) + } + } + + fun execute(table: Table, playerIndex: Int) { + asList().forEach { t -> t.execute(table, playerIndex) } + } + + fun asList(): List<ResourceTransaction> { + return resourcesByProvider + .filter { (_, resources) -> !resources.isEmpty } + .map { (provider, resources) -> ResourceTransaction(provider, resources) } + } + + fun asResources(): Resources { + return resourcesByProvider.values.fold(Resources(), Resources::plus) + } +} diff --git a/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/ResourceType.kt b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/ResourceType.kt new file mode 100644 index 00000000..67b176df --- /dev/null +++ b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/ResourceType.kt @@ -0,0 +1,28 @@ +package org.luxons.sevenwonders.game.resources + +enum class ResourceType(val symbol: Char?) { + WOOD('W'), + STONE('S'), + ORE('O'), + CLAY('C'), + GLASS('G'), + PAPYRUS('P'), + LOOM('L'); + + companion object { + + private val typesPerSymbol = values().map { it.symbol to it }.toMap() + + fun fromSymbol(symbol: String): ResourceType { + if (symbol.length != 1) { + throw IllegalArgumentException("The given symbol must be a valid single-char resource type, got $symbol") + } + return fromSymbol(symbol[0]) + } + + fun fromSymbol(symbol: Char?): ResourceType { + return typesPerSymbol[symbol] + ?: throw IllegalArgumentException(String.format("Unknown resource type symbol '%s'", symbol)) + } + } +} diff --git a/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/Resources.kt b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/Resources.kt new file mode 100644 index 00000000..96ad0b20 --- /dev/null +++ b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/Resources.kt @@ -0,0 +1,72 @@ +package org.luxons.sevenwonders.game.resources + +import java.util.NoSuchElementException + +class Resources(quantities: Map<ResourceType, Int> = emptyMap()) { + + private val quantities: MutableMap<ResourceType, Int> = quantities.toMutableMap() + + constructor(singleResource: ResourceType): this(mapOf(singleResource to 1)) + + val isEmpty: Boolean + get() = size() == 0 + + fun add(type: ResourceType, quantity: Int) { + quantities.merge(type, quantity) { x, y -> x + y } + } + + fun remove(type: ResourceType, quantity: Int) { + if (getQuantity(type) < quantity) { + throw NoSuchElementException("Can't remove $quantity resources of type $type") + } + quantities.computeIfPresent(type) { _, oldQty -> oldQty - quantity } + } + + fun addAll(resources: Resources) { + resources.quantities.forEach { type, quantity -> this.add(type, quantity) } + } + + fun getQuantity(type: ResourceType): Int = quantities[type] ?: 0 + + fun asList(): List<ResourceType> = quantities.flatMap { e -> List(e.value) { e.key } } + + fun containsAll(resources: Resources): Boolean = resources.quantities.all { it.value <= this.getQuantity(it.key) } + + operator fun plus(resources: Resources): Resources { + val new = Resources(this.quantities) + new.addAll(resources) + return new + } + + /** + * Creates a new [Resources] object containing these resources minus the given resources. + * + * @param resources + * the resources to subtract from these resources + * + * @return a new [Resources] object containing these resources minus the given resources. + */ + operator fun minus(resources: Resources): Resources { + val diff = Resources() + quantities.forEach { type, count -> + val remainder = count - resources.getQuantity(type) + diff.quantities[type] = Math.max(0, remainder) + } + return diff + } + + fun size(): Int = quantities.values.sum() + + override fun equals(other: Any?): Boolean { + if (this === other) return true + if (javaClass != other?.javaClass) return false + + other as Resources + + if (quantities != other.quantities) return false + + return true + } + + override fun hashCode(): Int = quantities.hashCode() +} diff --git a/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/TradingRules.kt b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/TradingRules.kt new file mode 100644 index 00000000..b6dc09e6 --- /dev/null +++ b/game-engine/src/main/kotlin/org/luxons/sevenwonders/game/resources/TradingRules.kt @@ -0,0 +1,36 @@ +package org.luxons.sevenwonders.game.resources + +class TradingRules(private val defaultCost: Int) { + + private val costs: MutableMap<ResourceType, MutableMap<Provider, Int>> = mutableMapOf() + + fun getCosts(): Map<ResourceType, Map<Provider, Int>> { + return costs + } + + internal fun getCost(type: ResourceType, provider: Provider): Int = + costs.computeIfAbsent(type) { mutableMapOf() }.getOrDefault(provider, defaultCost) + + fun setCost(type: ResourceType, provider: Provider, cost: Int) { + costs.computeIfAbsent(type) { mutableMapOf() }[provider] = cost + } + + fun computeCost(transactions: ResourceTransactions): Int { + return transactions.asList().map { this.computeCost(it) }.sum() + } + + internal fun computeCost(transaction: ResourceTransaction): Int { + val resources = transaction.resources + val provider = transaction.provider + return computeCost(resources, provider) + } + + private fun computeCost(resources: Resources, provider: Provider): Int { + var total = 0 + for (type in ResourceType.values()) { + val count = resources.getQuantity(type) + total += getCost(type, provider) * count + } + return total + } +} |