Code Share: Reusing the Maze

[Yawrf]

Consider this a follow up to Koenich's wonderful guide on the topic of the initial maze challenge: A different approach to solving the maze.
At the end, they mention

Opprinnelig skrevet av Koenich:

What if
Instead of searching for the chest, we use the algorithm to map the entire maze. Then (with this knowledge) find the shortest way to the chest, fertilize it and measure() the new location. With the map of the maze, we can now find the shortest way to the new chest. Measure it, fertilize it, find the shortest way to the new spawn point, measure(), fertilize, ...

I like it, so I decided to tackle it. This code is far from perfect, I only decided to actually bother unlocking dictionaries halfway through it so I wasn't just working with arbitrarily indexed arrays for everything. For the basic mapping of the maze, I opted for a basic left wall approach and just continuing until I've mapped every square rather than a more complicated (if likely more efficient) method like the Trémaux navigation approach they recommend. I have added on some basic commenting to header each method that I use, but no commenting step-by-step.

I used an external text-editor to convert all the tabs to four spaces instead so that it will look better in steam's formatting here.

dirs = [North, East, South, West]

repeatMaze()

# Essentially the Main() method for this process. I just separate them out so I can maintain 
# multiple separate Main()s while also using the "actual" main window as my Main(). 
# Creates the Maze, Maps it, then navigates to the treasure. It will then fertilize the 
# treasure until it moves and renavigate to it. It will fertilize and renavigate the 299 
# allowed times before harvesting the 300th chest. (If you wish to try this out with less 
# repeats, simply pass in a lower number. Don't remove the limit, if you allow a higher 
# number it will spend all the fertilizer you can afford trying to move the treasure chest again.)
def repeatMaze(repeats = 300):
    dirs = [North, East, South, West]
    repeats = min(repeats, 300)
    
    while True:
        makeMaze()
        maze, treasure = mapMaze()
        for i in range(repeats):
            while get_entity_type() == Entities.Treasure:
                bulkTrade(Items.Fertilizer)
                use_item(Items.Fertilizer)
            map = pathMaze(maze, treasure)
            while map["Step"]:
                move(map["Step"])
                map = map["Parent"]
            #quick_print("Finished: ",i)
            treasure = measure()
        pre = num_items(Items.Gold)
        harvest()
        post = num_items(Items.Gold)
        quick_print(pre,"->",post,"| Gained: ",post-pre)

# Creates the Maze 
def makeMaze():
    clear()
    bush()
    while get_entity_type() == Entities.Bush:
        bulkTrade(Items.Fertilizer)
        use_item(Items.Fertilizer)

# Plants a Bush
def bush():
    makeUnTilled()
    if can_harvest() or get_entity_type() != Entities.Bush:
        harvest()
        plant(Entities.Bush)

# Ensures the ground isn't tilled soil
def makeUnTilled():
    if get_ground_type() == Grounds.Soil:
        till()

# Trades World-Size-squared of an item if under that same amount - used to save operations, as trade() is expensive
def bulkTrade(item):
    size = get_world_size() ** 2
    if num_items(item) < size:
        trade(item, size)

# Paths through the entire maze (all World-Size-squared tiles) and builds a 2D array 
# representing each tile as an array indicating what directions can be travelled from. IE: A 
# tile represented as [True, True, False, False] you could go North or East from, but South 
# and West are blocked by walls. This function returns the map of the maze, as well as a 
# tuple representing the location of the treasure
def mapMaze(maze = []):
    size = get_world_size()
    emptyBlock(size, maze)
    heading = 0
    mapped = 0
    treasure = None
    while mapped < size**2:
        x = get_pos_x()
        y = get_pos_y()
        if not maze[x][y]:
            maze[x][y] = mapTile()
            mapped += 1
            if not treasure:
                if get_entity_type() == Entities.Treasure:
                    treasure = [x,y]
        heading = pathLeft(heading)
    return [maze, treasure]

# Creates an empty 2D array of lengths equal to World Size unless otherwise specified
def emptyBlock(size = get_world_size(), block = []):
    for x in range(size):
        block.append([])
        for y in range(size):
            block[x].append(None)
    return block

# Starting from its provided heading, will first attempt to move left but if unable will 
# cycle clockwise through remaining options
def pathLeft(heading):
    heading -= 1
    while not move(dirs[heading]):
        heading += 1
        heading %= 4
    return heading

# Tests each direction from the current tile to build an array representing which 
# directions are traversable
def mapTile():
    tile = [False,False,False,False]
    for i in range(4):
        d = dirs[i]
        if move(d):
            move(dirs[(i+2)%4])
            tile[i] = True
    return tile

# Sets up groundwork for A* algorithm below. Probably could have been built into one 
# function, but that's not how my brain works. Opted to find the path from the treasure 
# to the farmer as I could set the Step required to go back up the tree as a part of each 
# node's data.
def pathMaze(maze, target):
    posX = get_pos_x()
    posY = get_pos_y()
    tarX = target[0]
    tarY = target[1]
    
    closed = emptyBlock()
    open = emptyBlock()
    open[tarX][tarY] = {"X":tarX,"Y":tarY,"Parent":None,"Step":None,"G":0,"H":calcH([tarX,tarY],[posX,posY]),"F":calcH([tarX,tarY],[posX,posY])} 
    return aStar(open, closed, maze, [posX,posY])
    
# Performs the A* (A-Star) navigation algorithm; finding the lowest-F current node in the 
# Open map and targeting the provided Target. Due to my setting this up as a recursive 
# algorithm, it's worth noting that should the max farm size be increased from 10x10 in 
# the future, this will run into issues with the max stack size. I believe, however, that it 
# would be relatively trivial to make it non-recursive, but again - that's not how my brain works.
def aStar(open, closed, maze, target): 
    lowF = [get_world_size()**3,[-1,-1]]
    for x in range(len(open)):
        for y in range(len(open[x])):
            if open[x][y]:
                if open[x][y]["F"] < lowF[0]:
                    lowF[0] = open[x][y]["F"]
                    lowF[1] = [x,y]    
    x, y = lowF[1]
    node = open[x][y]
    closed[x][y] = node
    open[x][y] = None
    tile = maze[x][y]
    step = [[0,1],[1,0],[0,-1],[-1,0]]
    for iDir in range(len(dirs)):
        if tile[iDir]:
            nX = x + step[iDir][0]
            nY = y + step[iDir][1]
            if not closed[nX][nY]:
                if not open[nX][nY]:
                    nNode = {"X":nX,"Y":nY,"Parent":node,"Step":dirs[(iDir+2)%4],"G":node["G"]+1,"H":calcH([nX,nY],target)}
                    nNode["F"] = nNode["G"] + nNode["H"]
                    open[nX][nY] = nNode
                    if nNode["H"] == 0:
                        return nNode
                else:
                    nNode = open[nX][nY]
                    if nNode["G"] > (node["G"] + 1):
                        nNode["Parent"] = node
                        nNode["Step"] = dirs[(iDir+2)%4]
                        nNode["G"] = node["G"] + 1
                        nNode["F"] = nNode["G"] + nNode["H"]
    
    return aStar(open, closed, maze, target)
        
# Separated off as its own function simply because it's a lot of text that comes up multiple times
def calcH(pos,target):
    return ((target[0]-pos[0])**2) + ((target[1]-pos[1])**2)

I hope at some point we can also get a way to tell where the maze will delete a wall when it deletes one (such as the measure() of a chest returning a tuple containing the new location tuple and then another tuple of the location tuples of the two cells bordering the deleted wall (or None if it won't delete a wall this time). IE [ [1,2] , [ [3,4] , [4,4] ] ]. Were that to happen, it would be fairly trivial to modify this code to automatically update its map to reflect the deleted wall, and the implemented A* pathfinding algorithm would automatically take advantage of it.

---
EDIT: Updating the Map as we go
It occurred to me that with a couple simple tweaks I could just have the farmer check the walls along the way to the treasure each time to see if they have changed and update the map accordingly. I doubt it's the perfect solution, but it seems to me to be the least costly in the short-term.
EDIT 2: One more quick edit to the mapTile function and the corresponding call allows it also update the corresponding cell on the other side of the walls it discovers have been deleted, something I'd overlooked before.

# Updated mapTile() function. It now takes the tile as an input, defaulting to a blank tile.
# This allows for an already-checked tile to be passed in and it will only check the directions
# that were previously blocked. Additionally, passing in an existing map of a maze will set the 
# function in revision mode, automatically updating the corresponding cell as well as passing
# back the updated tile as usual
def mapTile(tile = [False,False,False,False], maze = None, loc = [-1, -1]):
    for i in range(4):
        if not tile[i]:
            d = dirs[i]
            if move(d):
                move(dirs[(i+2)%4])
                tile[i] = True
                # This block will only activate if a Maze was passed in
                # This will assume it is functioning in revision mode instead of construction
                if maze:
                    # Get the cell of the maze in the direction found to be open
                    # and then set the opposite direction to be True
                    # For example, finding the tile North to be unblocked will
                    # change its South direction to be true
                    maze[loc[0] + step[i][0]][loc[1] + step[i][1]][(i+2)%4] = True
    return tile

# Updated Main() function, only one section changed as marked below
def repeatMaze():
dirs = [North, East, South, West]

while True:
    clear()
    makeMaze()
    maze, treasure = mapMaze()
    repeats = 300
    for i in range(repeats):
        while get_entity_type() == Entities.Treasure:
            bulkTrade(Items.Fertilizer)
            use_item(Items.Fertilizer)
        map = pathMaze(maze, treasure)
        while map["Step"]:
            # The below section is the only change, having it remap every tile that it 
            # passes through on the way to the treasure each time, as well as passing the
            # maze and current location to use the updated mapTile functionality
            x = map["X"]
            y = map["Y"]
            maze[x][y] = mapTile(maze[x][y], maze, [x,y])
            move(map["Step"])
            map = map["Parent"]
        #quick_print("Finished: ",i)
        treasure = measure()
    pre = num_items(Items.Gold)
    harvest()
    post = num_items(Items.Gold)
    quick_print(pre,"->",post,"| Gained: ",post-pre)

These changes should result in its internal map playing a slow game of catchup as it goes through each cycle.

[VrIgHtEr]

I did implement one dead-end-filling iteration right after mapping, as well as efficiently keeping the information up to date with newly discovered walls. The drone always gets out of a corridor, navigates to the nearest junction to the treasure, and then enters the corridor to pick it up. This does not help much, mainly because there just simply aren't enough dead ends for the information to stay useful for much long. If the maze were larger then it would save a significant amount of work in the early stages, but the problem here is too small for it to be worth it. I've left it in my code, but I doubt it's doing much.

I have also updated my benchmarking code to keep track of ops spent fertilizing the initial bush, and refertilizing the treasure. Due to the RNG involved in those steps, I thought it would make sense to take them out of the equation to measure the navigation itself. Surprisingly, about 20% of the total time is spent just trying to use_item(Items.Fertilizer) in a loop, until the treasure relocates.

[acters]

Opprinnelig skrevet av VrIgHtEr:

I did implement one dead-end-filling iteration right after mapping, as well as efficiently keeping the information up to date with newly discovered walls. The drone always gets out of a corridor, navigates to the nearest junction to the treasure, and then enters the corridor to pick it up. This does not help much, mainly because there just simply aren't enough dead ends for the information to stay useful for much long. If the maze were larger then it would save a significant amount of work in the early stages, but the problem here is too small for it to be worth it. I've left it in my code, but I doubt it's doing much.

I have also updated my benchmarking code to keep track of ops spent fertilizing the initial bush, and refertilizing the treasure. Due to the RNG involved in those steps, I thought it would make sense to take them out of the equation to measure the navigation itself. Surprisingly, about 20% of the total time is spent just trying to use_item(Items.Fertilizer) in a loop, until the treasure relocates.

Yeah, that is why I include the time from start to after harvesting the final iteration 300 treasure with all the fertilizing and bush.
So I guess the benchmark numbers for my script was slightly different to yours.

[VrIgHtEr]

That was how I measured the benchmarks in total as well, This is just to compare one version of my algorithm to another version and see whether it has improved or regressed. The posted times always include all the ops from planting to harvesting.

[VrIgHtEr]

I have improved my algorithm and code further. I now average less than 150s per run. Here's the stats for 20 consecutive runs:

144.65 s, 2429729 o, 24.59 r, 109.08 a, 404.92 p, 150000 g
134.29 s, 2254435 o, 28.3 r, 96.29 a, 375.74 p, 150000 g
147.49 s, 2476571 o, 25.25 r, 110.24 a, 412.76 p, 150000 g
142.43 s, 2393335 o, 26.83 r, 104.22 a, 398.89 p, 150000 g
141.05 s, 2369441 o, 24.77 r, 106.11 a, 394.91 p, 150000 g
149.54 s, 2514153 o, 25.69 r, 111.12 a, 418.99 p, 150000 g
142.52 s, 2395086 o, 25.34 r, 106.41 a, 399.18 p, 150000 g
150.44 s, 2527110 o, 23.49 r, 115.11 a, 421.18 p, 150000 g
145.52 s, 2444691 o, 25.75 r, 108.05 a, 407.45 p, 150000 g
154.46 s, 2596083 o, 24.51 r, 116.6 a, 432.68 p, 150000 g
147.93 s, 2484708 o, 26.83 r, 108.25 a, 414.08 p, 150000 g
143.57 s, 2412736 o, 25.34 r, 107.19 a, 402.08 p, 150000 g
142.16 s, 2389472 o, 26.12 r, 105.02 a, 398.21 p, 150000 g
155.59 s, 2613223 o, 23.91 r, 118.39 a, 435.54 p, 150000 g
155.86 s, 2619908 o, 23.95 r, 118.53 a, 436.65 p, 150000 g
146.4 s, 2459171 o, 27.95 r, 105.48 a, 409.86 p, 150000 g
145.38 s, 2443328 o, 23.57 r, 111.11 a, 407.22 p, 150000 g
134.56 s, 2258809 o, 26.81 r, 98.48 a, 376.43 p, 150000 g
138.67 s, 2329680 o, 27.74 r, 100.2 a, 388.28 p, 150000 g
137.79 s, 2315837 o, 25.26 r, 102.99 a, 385.93 p, 150000 g

legend:
s = total run time in seconds (s = r + a)
o = total number of ops
r = time spent re-fertilizing the treasure
a = time spent doing anything else
p = power
g = gold