-
-
Save zapakh/9a9b39a07964bbd27ab8cbd05ca35501 to your computer and use it in GitHub Desktop.
| # 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) |
Thanks for sharing! I decided to go with a recursive DFS search. I'm sure there could be some improvements with the caching... but it works haha.
The action here could be whatever function you'd like to pass in (i.e. harvest, or custom function to fertilize).
Using it is pretty simple:
while True:
navigateMaze()
# Or something like:
# navigateMaze(customFunctionToFertilize)def navigateMaze(action = harvest, moveDirection = None, cache = {}):
isFound = False
if get_entity_type() == Entities.Treasure:
action()
return True
while get_entity_type() != Entities.Hedge:
plant(Entities.Bush)
use_item(Items.Fertilizer)
x = get_pos_x()
y = get_pos_y()
directions = {
North: {
"target": (x, y+1),
"opposite": South
},
South: {
"target": (x, y-1),
"opposite": North
},
East: {
"target": (x+1, y),
"opposite": West
},
West: {
"target": (x-1, y),
"opposite": East
},
}
for key in directions:
if moveDirection != directions[key]["opposite"] and not directions[key]["target"] in cache:
if move(key):
cache[directions[key]["target"]] = True
isFound = navigateMaze(action, key, cache)
if not isFound:
move(directions[key]["opposite"])
return isFound
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)
Thank you!