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

Originally posted by 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.

[Yawrf]

It's also worth noting that this program doesn't take into account if you can afford the fertilize to continue doing this. I've had my farming program running long enough that I have literally millions of pumpkins and thus it's not something that even occurred to me as I would have to purchase literally hundreds of thousands of fertilizer before it would be an issue. That being said, were it to become an issue, it would be relatively trivial to implement a checker against your num_items(Items.Pumpkins) and instead farm from when they drop below 1,000 to when you're over 10,000 or whatever arbitrary numbers you choose. Would simply want to break the for-loop running the repeats after it paths to the treasure when under the min-pumpkin threshold.

[Bluy]

Quite interesting. I tested it out, and it does what's labeled on the tin.
I would recommend breaking those comments up. The width is too large, and covers the entire screen.
I'd recommend breaking it up at any column length longer then the following.

                    nNode = {"X":nX,"Y":nY,"Parent":node,"Step":dirs[(iDir+2)%4],"G":node["G"]+1,"H":calcH([nX,nY],target)}

[TactileTaco]

I made a binary heap implementation in anticipation of eventually building some type of variation on A* or Dijkstra's algorithm that takes into account unknown features such as walls that haven't been checked for or the accumulating probability of a better path existing after an unknown wall is removed. I thought about potentially researching minesweeper algorithms to get an idea because they have a similar pattern of providing map knowledge as you grow your solution, but I had other ideas as well for the scenario such as accounting for the difference between the solved path(s) & the potential for faster paths when x walls are removed. Anyways, here is a binary heap implementation which may be used to optimize your A* search slightly (though the map is small so I'm not sure it is a significant degree of optimization).

def priorityQueue(comparator = defaultComparator):
	queue = []
	def swap(ia, ib):
		temp = queue[ia]
		queue[ia] = queue[ib]
		queue[ib] = temp
		
	def parent(i):
		i = (i-1) / 2
		return i - (i%1)
		
	def heapify(i=0):
		cmp = i
		l = i*2+1
		r = l+1
		if(l < len(queue)):
			if (comparator(queue[l], queue[cmp])):
				cmp = l
			if (r < len(queue) and comparator(queue[r], queue[cmp])):
				cmp = r
			if (cmp != i):
				swap(i, cmp)
				heapify(cmp)
			
	def yoink():
		if (len(queue) == 0):
			return None
		ret = queue[0]
		swap(0, len(queue) - 1)
		queue.pop()
		heapify()
		return ret
		
	def insert(elm):
		i = len(queue)
		queue.append(elm)
		while(i != 0):
			p = parent(i)
			if (comparator(queue, queue
)):
				swap(i, p)
				i = p
			else:
				break
	return {"yoink":yoink,"insert":insert}

def defaultComparator(a, b):
	return a < b[/code]
Also here is an example usage (though the example doesn't provide a custom comparator, which you may need to integrate into A*)
test = priorityQueue()
test["insert"](5)
test["insert"](7)
test["insert"](4)
print(test["yoink"]())
print(test["yoink"]())
print(test["yoink"]())
print(test["yoink"]())

[TactileTaco]

I am doubtful about Trémaux navigation after a quick glance at it. the maze can be reused 299 times which means mapping it out the first time isn't going to be more expensive than the solves from Trémaux navigation which don't provide the fastest route. There is likely a more optimal way to handle *1* wall being removed at a time, especially considering no paths from original mapping will ever be invalid, and we only need to consider paths which have some significant degree of being sub-optimal compared to the chances of x portals improving the path.

[Yawrf]

Originally posted by Bluy:

I would recommend breaking those comments up. The width is too large, and covers the entire screen.

Fair point, I actually added those in my text editor, so I didn't even think about that. Should be better now. Steam's formatting is a little jank now but it's still readable and will be much better in game

[Yawrf]

Originally posted by TactileTaco:

There is likely a more optimal way to handle *1* wall being removed at a time

I tackled that in my most recent edits. I decided that the compromise I liked the most was to simply recheck the previously-blocked directions of each tile on the way to the treasure chest. In that way, I waste no time checking areas which may not actually have opened up yet, and with enough time the farmer will eventually discover all relevant opened paths

[TactileTaco]

Originally posted by Yawrf:

I tackled that in my most recent edits. I decided that the compromise I liked the most was to simply recheck the previously-blocked directions of each tile on the way to the treasure chest. In that way, I waste no time checking areas which may not actually have opened up yet, and with enough time the farmer will eventually discover all relevant opened paths

That is a good improvement but it still makes the path up to 3x longer. I think there is a way to be greedier.

[Xeridanus]

I tried your code and had the idea of just remapping the entire maze every now and then. It seems to remove a random wall but doesn't check if it's already removed that particular wall. So it starts removing them quickly but towards 300 it removes very few. So if we remap more often at the start it should be somewhat optimal. The values I chose were 10, 25, 50, 100, 150 and 250. Unfortunately your mapmaze function assumes no loops and it got stuck when it couldn't reach every point.

Could you post your updated version with the checking along the path?

[VrIgHtEr]

This is my implementation of the same thing.

https://www.youtube.com/watch?v=o6sYQd6jWjg

It first maps the maze using either the hand-on-wall algorithm, if it knows that it has just grown the maze and that algorithm will work.

If it finds that a maze already exists when it starts, it will use the Tremaux algorithm instead.

Then it uses A* for navigation while rechecking walls while it moves, same approach that you chose.

[VrIgHtEr]

also, your pathfinding could be sped up a bit by simply using a better heuristic. You currently use euclidean distance, which is not ideal in this case.

Since the farmer can only move in 4 directions, we can use the manhattan distance:

abs(x-targetX) + abs(y - targetY)

This is a better estimate for the minimum cost. Choosing a heuristic for a* is a bit like blackjack. You want the heuristic to be as large as possible, without ever overestimating.

In this case it also allows for one more slight optimization. Usually we select the next cell that has the highest cost+heuristic. Now if we use manhattan distance, then the heuristic will only ever increase or decrease by 1. While the cost will always increase by 1. So that means that whenever we move towards the target, the heuristic will decrease by 1, while the cost will increase by one, making the total remain the same. So when ordering the heap, we can use the heuristic by itself as the tiebreaker when the totals are equal. The effect of this is that whenever the selected node has a path leading towards the goal, the algorithm will keep following that path immediately, before exploring other (still) equally costly nodes.

[acters]

Originally posted by TactileTaco:

I am doubtful about Trémaux navigation after a quick glance at it. the maze can be reused 299 times which means mapping it out the first time isn't going to be more expensive than the solves from Trémaux navigation which don't provide the fastest route. There is likely a more optimal way to handle *1* wall being removed at a time, especially considering no paths from original mapping will ever be invalid, and we only need to consider paths which have some significant degree of being sub-optimal compared to the chances of x portals improving the path.

true, however, I made a custom tremaux implementation either way. It can start in the middle of the maze, and can start in the middle of a full 300 iteration run. Will search for missing walls along the way(will only check walls as it memorizes all open paths), does not care about paths as much. it will just run around and search out for a way to get to the treasure chest.
very capable, and quick.
https://github.com/Acters/TheFarmerWasreplacedScripts/blob/main/Mazes.py

I could technically implement a* on top or other solvers to run instead of the tremaux if I segment out the tremaux stuff from the map logic.

[acters]

Originally posted by VrIgHtEr:

This is my implementation of the same thing.

https://www.youtube.com/watch?v=o6sYQd6jWjg

It first maps the maze using either the hand-on-wall algorithm, if it knows that it has just grown the maze and that algorithm will work.

If it finds that a maze already exists when it starts, it will use the Tremaux algorithm instead.

Then it uses A* for navigation while rechecking walls while it moves, same approach that you chose.

This is exactly all the ideas I had in mind to implement, and happy to see it implemented!
very cool, I think tremaux is a hyrbrid search and mapping algorithm. I am happy to see it used for when it is started in the middle of a generated map, as it is extremely robust algorithm on loss of map memory and will be able to handle lower connectivity walls.

I like you using the hand on wall algorithm too for the first iteration to map it and use a* with wall checking. This likely is one of the best scripts possibly made for maze.

[acters]

Originally posted by VrIgHtEr:

This is my implementation of the same thing.

https://www.youtube.com/watch?v=o6sYQd6jWjg

It first maps the maze using either the hand-on-wall algorithm, if it knows that it has just grown the maze and that algorithm will work.

If it finds that a maze already exists when it starts, it will use the Tremaux algorithm instead.

Then it uses A* for navigation while rechecking walls while it moves, same approach that you chose.

My only suggestion is to rely less on A* as connectivity decreases as the tremaux is miles faster at a less connected maze than A* or other path finding algorithms that virtualize the logic. This is because it sits and waits to find the path to the treasure instead of just guessing moves that will bring it closer to the treasure. Mostly because the confidence of there being no walls to short walls gets higher with each iteration.

This is the best possible script for maze solving this efficiently in the beginning but it falls of after 30+ walls are removed.

again check my modified Tremaux algorithm
it took inspiration from this https://openriver.winona.edu/cgi/viewcontent.cgi?article=1131&context=wsurrc

EDIT:
I made a video on my Maze solver that uses Trémaux's algorithm:
https://youtu.be/nDMHi2h9ORI

as you may notice, the time you saved with higher wall connectivity (first 30-50 iterations) is lost in the later portions. While my algorithm loses time in the more connected maze(in the first 30 iterations) and saves most of the time after 50+ walls are removed.

Because of this we both got about the same amount of time in solving the maze.
Do note that Luck does play a big factor in saving time. There are moments where removed walls create a lot of concentrated areas with loops with some areas one only having one opening. this scripts relies on being confident that there are multiple ways to reach a spot.
I was thinking of finding an algorithmic way for the drone to understand areas with one opening and to stay in that area vs trying to find a way around when there isn't.
really depends on the luck of the removed walls opening areas than creating pockets of openings.

[VrIgHtEr]

I wrote a python (real python) script first implementing the game's api so I could have my own visualization of the pathing in progress as well as use an actual debugger. Then I ported it to the game (replacing stuff like "X is not None" with "X != None" and stuff like that. So the code isn't really written with optimization for the game in mind. I want to optimize the code for ops (according to the game's logic), which I haven't gotten to yet. The goal is just one huge (VERY UGLY) function, with absolutely *everything* inlined to save ops on function calls. Also I should modify the binary heap to use 0 based instead of 1 based indexing, to avoid those "-1" in indexing, in the tightest of loops. Storing all the walls in a set for each node, instead of looping on all 4 directions and checking for connectivity, etc. Should squeeze out a bit of performance. I haven't tried optimizing it at all yet.

Also in your video it took 5:44 (344 seconds) to complete. I haven't yet timed mine higher than 320 seconds, and a run I just timed completed in 4:49 (289 seconds), averaging less than 1 second per treasure. As I said, the code can be sped up a bit, but I do believe the A* is actually helping me not hurting in this case. Further testing is needed.

[acters]

Originally posted by VrIgHtEr:

I wrote a python (real python) script first implementing the game's api so I could have my own visualization of the pathing in progress as well as use an actual debugger. Then I ported it to the game (replacing stuff like "X is not None" with "X != None" and stuff like that. So the code isn't really written with optimization for the game in mind. I want to optimize the code for ops (according to the game's logic), which I haven't gotten to yet. The goal is just one huge (VERY UGLY) function, with absolutely *everything* inlined to save ops on function calls. Also I should modify the binary heap to use 0 based instead of 1 based indexing, to avoid those "-1" in indexing, in the tightest of loops. Storing all the walls in a set for each node, instead of looping on all 4 directions and checking for connectivity, etc. Should squeeze out a bit of performance. I haven't tried optimizing it at all yet.

Also in your video it took 5:44 (344 seconds) to complete. I haven't yet timed mine higher than 320 seconds, and a run I just timed completed in 4:49 (289 seconds), averaging less than 1 second per treasure. As I said, the code can be sped up a bit, but I do believe the A* is actually helping me not hurting in this case. Further testing is needed.

I made some changes to my maze solver script that you can view in Github. ( https://github.com/Acters/TheFarmerWasreplacedScripts/blob/main/Mazes.py )
It really depends on the luck of good wall removal, and the treasure being easy to find.

Maybe I should have recorded a best case run but I got lazy and did not want to wait to get good RNG.

On the best runs, my new script now only takes 260 seconds with 15,800 operations per iteration, which is 4,740,000 operations for 300 iterations before it decides to harvest.
This means it uses 158,000 power for the increased speed.
On the worst runs, the new script took 360 seconds with about 18,875 operations per iteration, or 5,662,500 operations before harvesting at the 300th iteration. This consumes 188,750 power. This is almost 20% increase in power usage between bad scenarios and best cases.

I was thinking of implementing a simple lazy depth first search that only searching for paths the drone is thinking of taking that end in dead ends without reaching the treasure. thereby saving operations on moving in that direction.
Alongside the DFS, I want to see if I could mark "entrances" to these dead ends. This would make is so the depth first search is only done on areas that are have only one way to enter/exit from, and the drone can path find its way out of these areas that don't have the treasure.

Alternatively I was thinking of appending to the list of locations with memory of whether or not it searched for the treasure, and therefore can decide to search elsewhere for a path to the treasure. however, I don't see this as a proper solution as it technically already does this by marking each intersection with how many times it went that way.

both of these ideas will only help in the early iterations as the more walls are not connected. As it currently stands, as walls are less connected(removing walls connected with other walls is favorable) the much more faster the drone is. however, I have optimized the early iterations so well, that it is becoming straight RNG to have favorable paths that are easy to find and not too long of a path to traverse.

There is one major limitation that I do want to address and that is when there are 4 or more squares that are connected in a square pattern that don't have walls separating them, the drone will make small circle movements. like a bee or something haha.

I just realized that Tremaux's algorithm is basically a version of a depth first search haha

New idea, make use of dead-end filling on the first iteration to memorize all the dead ends. this way I can prevent the drone from rechecking dead ends, and decide to go a direction with high confidence will lead to the treasure!