3
\$\begingroup\$

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]
\$\endgroup\$
7
  • \$\begingroup\$ A beam search is not guaranteed to return an optimal solution unless the beam width is infinite. \$\endgroup\$
    – RootTwo
    May 19 '21 at 5:48
  • \$\begingroup\$ Is there a better approach, then? There are too many options for exhaustive search to be reasonable. \$\endgroup\$
    – Mark Green
    May 19 '21 at 8:22
  • \$\begingroup\$ How does one invoke this code? Which method is the entry point? \$\endgroup\$
    – Reinderien
    May 19 '21 at 10:51
  • \$\begingroup\$ I start with x = beamSearch(initFromMap(map1),4000) (replacing 4000 with the width to try) \$\endgroup\$
    – Mark Green
    May 19 '21 at 13:51
  • \$\begingroup\$ 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 \$\endgroup\$
    – IEatBagels
    May 21 '21 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.