Skip to content

Instantly share code, notes, and snippets.

@zapakh

zapakh/do_maze.py

Created May 22, 2024 06:01
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save zapakh/9a9b39a07964bbd27ab8cbd05ca35501 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save zapakh/9a9b39a07964bbd27ab8cbd05ca35501 to your computer and use it in GitHub Desktop.
Download ZIP
In-situ DFS maze solver for The Farmer Was Replaced
Raw
do_maze.py
# Make sure you have enough Fertilizer before starting.
def do_maze(iterations=1):
# Define some geometry help for later
opp = {North: South, East: West,
South: North, West: East}
dx = {North: 0, East: 1, South: 0, West: -1}
dy = {North: 1, East: 0, South: -1, West: 0}
# Start a Maze.
harvest()
plant(Entities.Bush)
while get_entity_type() == Entities.Bush:
use_item(Items.Fertilizer)
x, y = get_pos_x(), get_pos_y()
goalx, goaly = None, None
while iterations > 0:
while get_entity_type() == Entities.Treasure:
if measure() == None:
# We've hit the recycling limit.
iterations = 0
break
goalx, goaly = measure()
# Recycle the maze
iterations -= 1
if iterations <= 0:
break
while not use_item(Items.Fertilizer):
pass
# Use depth-first search, but avoid cycles by keeping
# track of where we've been, and not revisiting those.
#
# https://en.wikipedia.org/wiki/Depth-first_search
#
# Our search is "in situ", meaning the literal position
# of the drone tracks our position in the search.
stack = [([North, East, South, West], None)]
visited = {(get_pos_x(), get_pos_y())}
# Each item in the stack is a 2-tuple containing
# * A list of directions to try from this position
# * The direction back to the previous position
#
# Pushing (appending) an item onto the stack means
# that we will eventually try all the directions in
# the list, and then go back to the previous one.
#
# Unless we find the Treasure first, of course.
while get_entity_type() != Entities.Treasure:
dirs, back = stack[-1] # stack peek
oldx = x
oldy = y
dir = None
# Which way do we try next?
while len(dirs) > 0:
dir = dirs.pop()
x = oldx + dx[dir]
y = oldy + dy[dir]
if (x, y) in visited or not move(dir):
# Can't go there. Try another one.
dir = None
continue
else:
# Can go there. Let's go there.
break
if dir == None:
# Time to backtrack.
stack.pop() # Get rid of the node we peeked
if back == None:
print("I give up!")
while True:
do_a_flip()
move(back)
x = oldx + dx[back]
y = oldy + dy[back]
else:
# We've made a forward step. (x, y) have
# already been updated to our new position.
visited.add((x, y))
# Push a stack item to guide the search from here.
stack.append(
(get_ranked_dirs(x, y, goalx, goaly, opp[dir]),
opp[dir]))
harvest()
# Helper function, broken out for readability.
def get_ranked_dirs(pos_x, pos_y, goal_x, goal_y, exclude=None):
if goal_x == None:
# Fake the priorities since we have no guidance.
all_dirs = [(1, North), (2, East), (3, South), (4, West)]
else:
# The small added amounts break ties, so that min()
# will not attempt to compare the directions directly,
# which would cause a crash.
all_dirs = [
(goal_y - pos_y + 0.1, North),
(goal_x - pos_x + 0.2, East),
(pos_y - goal_y + 0.3, South),
(pos_x - goal_x + 0.4, West)]
# The returned list puts our favorite directions at the end
# so they are the first returned by pop().
ranked_dirs = []
for i in range(len(all_dirs)):
worst_dir = min(all_dirs)
all_dirs.remove(worst_dir)
if worst_dir[1] != exclude:
ranked_dirs.append(worst_dir[1])
return ranked_dirs
# Example usage
do_maze(10)
@CalfordMath
Copy link

CalfordMath commented Sep 12, 2024 •
edited
Loading

I love both these solutions! Just a note for @zapakh to move "iterations -=1" outside of the inner while loop, otherwise it decreases with each fertilizing attempt to recycle the maze. I love the clean way you break the movement into x and y components, and the optimization of the order it tries the directions. I see why it works append the min(all_dirs) when deciding between North vs. South and East vs. West, since one will be negative and the other positive (or both zero), depending on the location of the treasure. min() will give the negative (moving away from treasure) which is certainly worse. It's insignificant, but I think this way of ordering would incorrectly rank two positive distances (the winner of E/W vs winner of N/S), but the code certainly works like a charm, so meh!
I had toyed with a recursive method as well, but I found the stack limit was quickly hit after a few treasure relocations, which I'm guessing is why @cyearsley calls the function in an external while true loop so the stack resets. The computer keeps a copy of all variables with each recursion call, so it adds up quickly. I love the minimalism of the recursive method above, but without implementing measure() to inform the priority of direction choice, I think it would become very inefficient as walls are removed. I wanted to keep it in one function call.

Here is my maze solution! I'm using some hints from the above solutions, but with my own over complicated math loving flare. I'm using the Euclidean distance between a potential move and the treasure to optimize direction selection (choose minimum distance option). I'm a math geek, so I made heavy use of modulo calculations to navigate the maze, referring to my directions = [North, East, South, West] by index 0, 1, 2, 3. This way, "opposite" is simply (direction + 2) % 4, etc. This function will continue until hitting the recycle limit, and then harvest the gold.

def run_maze():
	#so we can call directions by number: 0,1,2,3 and use math to move around!
	directions=[North, East, South, West]
    
	#If not already in a maze, start one.
	if get_entity_type() != Entities.Hedge and get_entity_type() != Entities.Treasure:
		harvest()
		plant(Entities.Bush)
		while get_entity_type() != Entities.Hedge:
			if num_items(Items.Fertilizer)<1:
				trade(Items.Fertilizer)
			use_item(Items.Fertilizer)

	#initially we don't know where the treasure spawned    
	goalx, goaly = None, None	
	
	while True:
		#A tuple, where the first value is itself a list of tuples: (distance to treasure, direction), 
		#and the second value in the outer tuple is the opposite direction for backtracking purposes
		tree = [([(random(),0),(random(),1),(random(),2),(random(),3)],None)] #filler values prior to first treasure find
		x, y = get_pos_x(), get_pos_y()
		visited = {(x, y)}
		
		while get_entity_type() != Entities.Treasure:
			back = tree[-1][1]
			direction = None
			while len(tree[-1][0]) > 0:
				bestdir = min(tree[-1][0]) #grabs direction giving closest Euclidean distance to treasure
				tree[-1][0].remove(bestdir)                
				direction = bestdir[1] #just grab the direction
				
				if not move(directions[direction]):
					direction=None #move to next option
				else: #moved successfully, get out of loop
					break
			if direction == None: #exhausted direction options, remove this branch from the tree and backtrack
				tree.pop()				       
				move(directions[back]) 
				x = x + (-back + 2)*(back % 2) #If back is 1 or 3 (i.e. East or West) this will add 1 or subtract 1
				y = y + (-back + 1)*((back+1) % 2) #If back is 0 or 2 (i.e. North or South) this will add 1 or subtract 1              
			else:
				#already moved, update x and y to new location
				x = x + (-direction + 2)*(direction % 2) 
				y = y + (-direction + 1)*((direction+1)%2) 
				visited.add((x, y))
				
				#make new tree branch including the distance to treasure from each valid direction option
				new_directions = [0, 1, 2, 3]
				new_directions.remove((direction + 2) % 4) #remove opposite
				new_tree_item = []
								
				for i in range(len(new_directions)):
					potential_direction = new_directions[i]
					tempnewx = x + (-potential_direction + 2)*(potential_direction % 2)
					tempnewy = y + (-potential_direction + 1)*((potential_direction + 1) % 2)                     
					if not (tempnewx, tempnewy) in visited:
						if goalx == None:
							new_tree_item.append((random(), potential_direction))
						else:
							#include the Euclidean distance between potential new point and the treasure for optimizing choice later
							new_tree_item.append((((tempnewx - goalx)**2 + (tempnewy - goaly)**2)**(1/2), potential_direction))
				tree.append((new_tree_item, (direction + 2) % 4)) # direction + 2 is the opposite direction, mod 4 to wrap.
		
		if measure() == None: #hit recycle limit
			harvest()
			break
		else:
			goalx, goaly = measure()
			while get_entity_type() == Entities.Treasure:
				if num_items(Items.Fertilizer)<1:
					trade(Items.Fertilizer)
				use_item(Items.Fertilizer)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment