# 2D Map Optimization via Beam Search in Python

This is a problem based on the game "NGU Industries" in which the objective is to build a factory. Each tile can hold either a production building or a "beacon" which increases the production of buildings near to it in a given offset pattern. In other words, adding a beacon increases the productivity of nearby tiles at the cost of the tile it is placed on. Some tiles on each map are blocked and unusable.

The variable map1 contains the layout of the game's first map, where a . indicates a usable square and a   an unusable square.

The available beacons are represented in the program by the symbols *, k, >, <, ^, v, and the bonuses they give and the layouts they give them in are as follows:

• * gives a +30% bonus to every cardinally or diagonally adjacent square.
+30% +30% +30%
+30%   *  +30%
+30% +30% +30%

• k gives a +35% bonus to every square a knight's move away from it.
---- +35% ---- +35% ----
+35% ---- ---- ---- +35%
---- ----  k   ---- ----
+35% ---- ---- ---- +35%
---- +35% ---- +35% ----

• v gives a +22% bonus to tiles in an arrow shape below it. >, < and ^ apply the same shape in different directions.
---- ----   v  ---- ----
---- ---- +22% ---- ----
---- ---- +22% ---- ----
+22% +22% +22% +22% +22%
---- +22% +22% +22% ----
---- ---- +22% ---- ----


A square can be affected by any number of beacons of any type or combination of types. If a square is affected by multiple beacons the bonuses are added together; so a square affected by two *s and a v has a bonus of +88% for a total of 188%.

This program attempts to find the best possible layout for beacons on a given map using a beam search. However even with a high beam width, 10000, it does not find the best solutions - it tops out at a score 17445 (where the score is the sum of production percentages on all empty, usable tiles), whereas the community have found a layout (shown in the variable exi1) yielding 17934.

Is there a fundamental problem with my approach here or is it just a question of needing an even wider search? In a previous version I allowed removing or changing a beacon as a potential change made by beamGrid and this slightly improved results but at the cost of filling the beam with old states and much lower performance since removing a beacon is computationally expensive.

Edit: added beacon removal back in using cached values to save recalculating everything, but still doesn't seem to reach optimal values.

Edit 2: removed a really dumb bug where added beacons would be immediately culled. I don't think this improves optimality but it speeds things up.

map1 = ["        ..          ",
"        ...    .    ",
"       . ..   ..... ",
"       ..... ...... ",
"        ..  ....... ",
"   .... ..   . . .. ",
"   ........ ........",
"   ........ .  .    ",
"   ..........  .    ",
"   ..........  .    ",
"      .. .......... ",
"             ...  . ",
"             ...... ",
"  .    ...   ...... ",
"  ..   ...          ",
"       ...          ",
"                    "]

exi1 = ["        ..          ",
"        .*.    .    ",
"       v v.   .v.k. ",
"       vvv>. .k.k.< ",
"        vv  .k.k.k. ",
"   >>.. ..   . . .< ",
"   >>>..... <k...k.<",
"   >>>..... <  .    ",
"   >>>....<<<  ^    ",
"   >>.....<<<  v    ",
"      ^. ^>>.....<< ",
"             ...  < ",
"             ....<< ",
"  .    ...   ....<< ",
"  ..   .*.          ",
"       ...          ",
"                    "]

mycl = ["....     ... ..  ...",
".....           ....",
"....  ...   ........",
"..     .  .  .....  ",
"..  .   .   ...... .",
"..  ...... ......   ",
"...  ..... ...... ..",
"....  .... .........",
". ...  ... ...   ...",
".  ...   . ... .   .",
"..  ....         . .",
"...  ..  ..... ... .",
".... ....  ..      .",
"......  . ... ......",
" .....  ..... .  ...",
"  ........... .. ...",
"   ..........    ..."]

beacons = [
# Box
(2,30,[(-1,-1),(0,-1),(1,-1),(-1,0),(1,0),(-1,1),(0,1),(1,1)]),
# Knight
(3,35,[(-1,-2),(-2,-1),(-2,1),(-1,2),(1,-2),(2,-1),(2,1),(1,2)]),
# Arrows
(4,22,[(0,-1),(0,-2),(0,-3),(0,-4),(0,-5),(-1,-3),(-2,-3),(1,-3),
(2,-3),(-1,-4),(1,-4)]),
(5,22,[(0,1),(0,2),(0,3),(0,4),(0,5),(-1,3),(-2,3),(1,3),
(2,3),(-1,4),(1,4)]),
(6,22,[(1,0),(2,0),(3,0),(4,0),(5,0),(3,-1),(3,-2),(3,1),(3,2),
(4,1),(4,-1)]),
(7,22,[(-1,0),(-2,0),(-3,0),(-4,0),(-5,0),(-3,-1),(-3,-2),(-3,1),
(-3,2),(-4,1),(-4,-1)]),
# Not unlocked until later in the game
#  (8,27,[(-1,0),(-2,0),(-3,0),(-4,0),(-5,0),(-6,0),(1,0),(2,0),(3,0),(4,0),
#          (5,0),(6,0)]),
#  (9,27,[(0,-1),(0,-2),(0,-3),(0,-4),(0,-5),(0,-6),(0,1),(0,2),(0,3),(0,4),
#          (0,5),(0,6)]),
#  (10,26,[(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2),(-2,-1),(2,-1),(-2,0),(2,0),
#          (-2,1),(2,1),(-2,2),(-1,2),(0,2),(1,2),(2,2)])
]

chars = ['',' ','*','k','^','v','>','<',"-","|","o"]

def initFromMap(mapp):
"""Creates an initial grid from a string representation of a map only."""
grid = [[(100,0) if x == '.' else (100,1) for x in s] for s in mapp]
return grid

def initFromPre(pre):
"""Creates a grid from a string representation of a map with beacons."""
grid = [[(100,0) if x == '.' else (100,1) for x in s] for s in pre]
for y in range(17):
for x in range(20):
ch = pre[y][x]
if ch != ' ':
if ch in chars:
ind = chars.index(ch)
grid = applyBeacon(grid, x, y, beacons[ind-2])
return grid

def applyBeacon(pair,x,y,beacon):
"""Add the given beacon to the grid at the given coordinates and return
an updated grid."""
(grid, score) = pair
(bid,bonus,offsets) = beacon
newGrid = [l.copy() for l in grid]
assert newGrid[y][x][1] == 0   # Can't replace beacons by this method
score -= newGrid[y][x][0]
newGrid[y][x] = (newGrid[y][x][0],bid)      # Set beacon id on cell
for (ox,oy) in offsets:
nx = x+ox
ny = y+oy
if (nx < 0) or (nx > 19) or (ny < 0) or (ny > 16):
continue
newGrid[ny][nx] = (newGrid[ny][nx][0] + bonus, newGrid[ny][nx][1])
if newGrid[ny][nx][1] == 0:
score += bonus           # Score only if no beacon on square
return (newGrid, score)

def removeBeacon(pair,x,y):
(grid, score) = pair
newGrid = [l.copy() for l in grid]
assert newGrid[y][x][1] > 1
(oldId, oldBonus, oldOffsets) = beacons[newGrid[y][x][1]-2]
newGrid[y][x] = (newGrid[y][x][0],0)
score += newGrid[y][x][0]
for (ox,oy) in oldOffsets:
nx = x+ox
ny = y+oy
if (nx < 0) or (nx > 19) or (ny < 0) or (ny > 16):
continue
newGrid[ny][nx] = (newGrid[ny][nx][0] - oldBonus, newGrid[ny][nx][1])
if newGrid[ny][nx][1] == 0:
score -= oldBonus
return (newGrid, score)

def buildBenefitMap(mapp):
benefitMap = []
baseScore = gridScore(mapp)
for beacon in beacons:
page = []
for y in range(17):
line = []
for x in range(20):
if mapp[y][x][1] == 1:
line.append(0)
else:
(newGrid,newScore) = applyBeacon((mapp, baseScore), x, y, beacon)
line.append(newScore-baseScore)
page.append(line)
benefitMap.append(page)
return benefitMap

def cullBeacons(pair,benefitMap):
(grid, score) = pair
for y in range(17):
for x in range(20):
if grid[y][x][1] > 1:

if (grid[y][x][0]-100) >= benefitMap[grid[y][x][1]-2][y][x]:
(grid, score) = removeBeacon((grid,score),x, y)

return (grid,score)

def stringifyGrid(grid):
"""Converts a grid into an array of output strings."""
out = []
for row in grid:
ostr = ""
for (value,beacon) in row:
if beacon>0:
ostr += chars[beacon]
else:
ostr += '.'
out.append(ostr)
return out

def drawGrid(grid):
"""Outputs a grid representation."""
for row in stringifyGrid(grid):
print(row)

def gridScore(grid):
"""Returns a grid's total production."""
return sum([sum([x if y == 0 else 0 for (x,y) in row]) for row in grid])

def fullDrawGrid(grid):
"""Draws a grid with production values for each square."""
strs = stringifyGrid(grid)
for y in range(17):
for x in range(20):
if strs[y][x] == " ":
print("   ",end="")
elif strs[y][x] == ".":
print(f'{grid[y][x][0]:3}',end="")
else:
print(strs[y][x]+"  ",end="")
print(" ",end="")
print()

def addToBeam(beam,pair,width):
"""Adds a grid to a sorted list of scored grid candidates."""
(grid, score) = pair
if score <= beam[-1][1]:
return
for x in range(len(beam)):
(eg, es) = beam[x]
if es == score:
if eg == grid:
return
if es < score:
index = x
break
else:
return
beam[index+1:] = beam[index:-1]
beam[index] = pair

def beamGrid(grids,width,benefitMap):
beam = grids[:width]

for (grid, score) in grids:

for y in range(17):
for x in range(20):
if grid[y][x][1] == 0:
for beacon in beacons:
if benefitMap[beacon[0]-2][y][x] > (grid[y][x][0]-100):
newPair = applyBeacon((grid,score),x,y,beacon)
newPair = cullBeacons(newPair,benefitMap)
addToBeam(beam, newPair, width)
elif grid[y][x][1] > 1:
newPair = removeBeacon((grid,score), x, y)
addToBeam(beam, newPair, width)

return beam

def beamSearch(grid,width):
initScore = gridScore(grid)
initBeam = [(grid.copy(),initScore) for x in range(width)]
benefitMap = buildBenefitMap(grid)

beam = beamGrid(initBeam,width,benefitMap)
oldBeam = None
gen = 0

while beam != oldBeam:
oldBeam = beam.copy()
beam = beamGrid(oldBeam, width, benefitMap)
if (len(beam) != width):
print("WIDTH ERROR")

print(gen, beam[0][1],"-",beam[-1][1])
gen += 1

return oldBeam[0]

• A beam search is not guaranteed to return an optimal solution unless the beam width is infinite. Commented May 19, 2021 at 5:48
• Is there a better approach, then? There are too many options for exhaustive search to be reasonable. Commented May 19, 2021 at 8:22
• How does one invoke this code? Which method is the entry point? Commented May 19, 2021 at 10:51
• I start with x = beamSearch(initFromMap(map1),4000) (replacing 4000 with the width to try) Commented May 19, 2021 at 13:51
• I think the underlying problem with your code Mark isn't that it's bad, just that you're using a heuristic to try and find a solution to a problem. In the present case, the community has a better heuristic than you do, which "makes sense" because there are certainly many ways to deal with this problem as an optimization problem. From what I understand, it looks like a discrete optimization problem and there are many ways to do discrete optimization Commented May 21, 2021 at 13:47