Strategy for solving constraint optimization problems on spatial maps. Use when you need to place items on a grid/map to maximize some objective while satisfying constraints.
name
map-optimization-strategy
description
Strategy for solving constraint optimization problems on spatial maps. Use when you need to place items on a grid/map to maximize some objective while satisfying constraints.
Map-Based Constraint Optimization Strategy
A systematic approach to solving placement optimization problems on spatial maps. This applies to any problem where you must place items on a grid to maximize an objective while respecting placement constraints.
Why Exhaustive Search Fails
Exhaustive search (brute-force enumeration of all possible placements) is the
worst approach
:
Combinatorial explosion: Placing N items on M valid tiles = O(M^N) combinations
Even small maps become intractable (e.g., 50 tiles, 5 items = 312 million combinations)
Most combinations are clearly suboptimal or invalid
The Three-Phase Strategy
Phase 1: Prune the Search Space
Goal:
Eliminate tiles that cannot contribute to a good solution.
Remove tiles that are:
Invalid for any placement
Violate hard constraints (wrong terrain, out of range, blocked)
Dominated
Another tile is strictly better in all respects
Isolated
Too far from other valid tiles to form useful clusters
Before: 100 tiles in consideration
After pruning: 20-30 candidate tiles
This alone can reduce search space by 70-90%.
Phase 2: Identify High-Value Spots
Goal:
Find tiles that offer exceptional value for your objective.
Score each remaining tile by:
Intrinsic value
Skills relacionados
What does this tile contribute on its own?
Adjacency potential
What bonuses from neighboring tiles?
Cluster potential
Can this tile anchor a high-value group?
Rank tiles and identify the top candidates. These are your
priority tiles
any good solution likely includes several of them.
Example scoring:
Tile B: +1 base, +1 adjacency potential = 2 points (LOW)
Phase 3: Anchor Point Search
Goal:
Find placements that capture as many high-value spots as possible.
Select anchor candidates
Tiles that enable access to multiple high-value spots
Expand from anchors
Greedily add placements that maximize marginal value
Validate constraints
Ensure all placements satisfy requirements
Local search
Try swapping/moving placements to improve the solution
For problems with a "center" constraint (e.g., all placements within range of a central point):
The anchor IS the center - try different center positions
For each center, the reachable high-value tiles are fixed
Optimize placement within each center's reach
Algorithm Skeleton
def
optimize_placements
(
map_tiles, constraints, num_placements
):
Phase 1: Prune
candidates = [t
for
t
in
map_tiles
if
is_valid_tile(t, constraints)]
Phase 2: Score and rank
scored = [(tile, score_tile(tile, candidates))
for
tile
in
candidates]
scored.sort(key=
lambda
x: -x[
1
])