Toy maze solver (stateless) for https://store.steampowered.com/app/2060160/The_Farmer_Was_Replaced/
Last active
October 28, 2025 22:08
-
-
Save andrew-raphael-lukasik/ad3b7eb048bb9135734feb76a96f9f9f to your computer and use it in GitHub Desktop.
"The Farmer Was Replaced" maze solver
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def create_maze(): | |
| clear() | |
| for i in range(get_world_size()): | |
| plant(Entities.Bush) | |
| while get_water()<0.9: | |
| use_item(Items.Water) | |
| move(North) | |
| for i in range(get_world_size()): | |
| while can_harvest()==False: | |
| pass | |
| while get_entity_type()==Entities.Bush: | |
| if num_items(Items.Fertilizer)==0: | |
| trade(Items.Fertilizer) | |
| #if num_items(Items.Fertilizer)==0: | |
| #main() | |
| use_item(Items.Fertilizer) | |
| treasure_hunt() |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def treasure_hunt(): | |
| dir = West | |
| x = get_pos_x() | |
| y = get_pos_y() | |
| while True: | |
| move(dir) | |
| x2 = get_pos_x() | |
| y2 = get_pos_y() | |
| if x==x2 and y==y2: | |
| if dir==West: | |
| dir = North | |
| elif dir==North: | |
| dir = East | |
| elif dir==East: | |
| dir = South | |
| elif dir==South: | |
| dir = West | |
| else: | |
| x = get_pos_x() | |
| y = get_pos_y() | |
| if dir==West: | |
| dir = South | |
| elif dir==North: | |
| dir = West | |
| elif dir==East: | |
| dir = North | |
| elif dir==South: | |
| dir = East | |
| if get_entity_type()==Entities.Treasure: | |
| harvest() | |
| create_maze() |
The maze code works well. I think maybe someone could find a more optimized maze solver in python but that doesn't really matter.
Ope. I'll see what I can do to prevent this.
Fixed Code: Run main to start the program.
main
while True:
if create_maze():
if treasure_hunt():
continue
create_maze
# https://gist.github.com/andrew-raphael-lukasik/ad3b7eb048bb9135734feb76a96f9f9f
def create_maze():
clear()
plant(Entities.Bush)
while get_entity_type()==Entities.Bush:
if num_items(Items.Weird_Substance) > get_world_size():
use_item(Items.Weird_Substance, get_world_size())
return 1
if can_harvest():
harvest()
plant(Entities.Bush)
if num_items(Items.Fertilizer)==0:
# I do not have trade unlocked
#trade(Items.Fertilizer)
return 0
use_item(Items.Fertilizer)
return 1
treasure_hunt
# https://gist.github.com/andrew-raphael-lukasik/ad3b7eb048bb9135734feb76a96f9f9f
def treasure_hunt():
dir = West
x = get_pos_x()
y = get_pos_y()
while True:
move(dir)
x2 = get_pos_x()
y2 = get_pos_y()
if x==x2 and y==y2:
if dir==West:
dir = North
elif dir==North:
dir = East
elif dir==East:
dir = South
elif dir==South:
dir = West
else:
x = get_pos_x()
y = get_pos_y()
if dir==West:
dir = South
elif dir==North:
dir = West
elif dir==East:
dir = North
elif dir==South:
dir = East
if get_entity_type()==Entities.Treasure:
harvest()
return 1
in the newer version you need to change just a little bit in the code for it to run. but its only in the main script because of the new import function
its a simple fix:
import create_maze
import treasure_hunt
while True:
if create_maze.create_maze():
if treasure_hunt.treasure_hunt():
continue
Can someone explain why this algorithm works?
@mahdi-mezghani this is straight-forward wall-hugging. Every valid maze can be solved by following a wall and this is exactly what treasure_hunt() does here. It's nothing complicated. Simplicity is an underappreciated code quality.
This approach won't produce an optimal path every time but it doesn't matter that much in this game. At least while mazes are relatively small. For big mazes this method becomes ill-fitted, but it's a problem most players won't even have.
Ope. I'll see what I can do to prevent this.
Stack overflow is caused by recursive function calls.
Any specific reason why you're planting a full row of bushes and watering them before spawning a maze? You should just need to move to (0,0) and plant a single bush (then use substances) in create_maze(). From my testing, water or fertilizers do nothing to mazes, too...
Any specific reason why you're planting a full row of bushes and watering them before spawning a maze? You should just need to move to (0,0) and plant a single bush (then use substances) in create_maze()
This is simply how it worked at the time of me writing this code. Have no idea how it changed since then
I added a summon drone to run in the opposite direction- to speed up maze completion. I also added *2 for the upgraded maze. The weird substance cost and earnings increase for higher level mazes.
With the drone, I also had to add a get entity for grass. If the summoned drone completed the maze it was stuck in a loop, so I had to return 1.
I'm new to Github and coding- sorry if the code and posting isn't quite right.
(https://gist.github.com/1337dondongo/6cb2506bb1847d1b4490260673aa49c4)
Thank you for the maze code! It really helped me!
I added a summon drone to run in the opposite direction- to speed up maze completion. I also added *2 for the upgraded maze. The weird substance cost and earnings increase for higher level mazes.
With the drone, I also had to add a get entity for grass. If the summoned drone completed the maze it was stuck in a loop, so I had to return 1.
I'm new to Github and coding- sorry if the code and posting isn't quite right.
(https://gist.github.com/1337dondongo/6cb2506bb1847d1b4490260673aa49c4)
Maybe you know how to add up to 4 drones?
Maybe you know how to add up to 4 drones?
Andrew wrote great code, but the game forces you to start mazes at 1 location. You can spawn more drones, but unless you code new ways to explore the maze it won't make it faster. His code followed the left hand side so I simply added a drone to follow the right hand side- at the same time. Maybe there's another way to explore the maze I can't think of?
You can spawn more drones, but unless you code new ways to explore the maze it won't make it faster. His code followed the left hand side so I simply added a drone to follow the right hand side- at the same time. Maybe there's another way to explore the maze I can't think of?
If it is really possible to spawn more drones now, then you can "multi-thread" the search process by moving every drone to a different starting position. Start with map corners or spread them evenly across the maze. This will lower the search time slightly with every new drone added.
sidenote:
As number of drones approaches get_world_size() this search technique could potentially start to lose to more "naive" search patterns. For example:
- Every drone picking a row and just scanning it start to finish simultaneously
(imagine a police search party where people search an area by moving in a line formation). - Every drone picking an equally spaced starting position and searching in some kind growing-spiral pattern
(like a coastal guard searching an area) - Every drone calculating its unique rectangular area to scan at the start then each scanning his own quadrant
What I personally do is use this two-drone approach in opposite directions, and make them only return when they reach the end. This is suboptimal but quite easy to implement. Once a different drone picks the treasure, the remaining drones will remain walking in 2x2 circles wherever they were, meaning that my distribution of drones around the field trends upwards, and they are reasonably evenly distributed. That’s probably the fastest you can get without using proper search algorithms.
If it is really possible to spawn more drones now, then you can "multi-thread" the search process by moving every drone to a different starting position. Start with map corners or spread them evenly across the maze. This will lower the search time slightly with every new drone added.
Good idea. I put the 1 spawn drone in def treasure_hunt():, so the clone is spawned after the maze is created. Not sure, but they normally spawn on the original drones location.
In addition to the wall-following strategy, I created code that marks the forks, so it explores a fork until the end. If it doesn't find the treasure, it returns to the fork and explores the next one.
This is useful for larger mazes with a larger number of drones.
def create_maze():
clear()
plant(Entities.Bush)
while get_entity_type()==Entities.Bush:
substance = get_world_size() * 2**(num_unlocked(Unlocks.Mazes) - 1)
if num_items(Items.Weird_Substance) > substance:
use_item(Items.Weird_Substance, substance)
return 1
if can_harvest():
harvest()
plant(Entities.Bush)
if num_items(Items.Fertilizer)==0:
# I do not have trade unlocked
#trade(Items.Fertilizer)
return 0
use_item(Items.Fertilizer)
# === Helper Functions ===
def turn_left(dir):
if dir == North:
return West
if dir == West:
return South
if dir == South:
return East
if dir == East:
return North
def turn_right(dir):
if dir == North:
return East
if dir == East:
return South
if dir == South:
return West
if dir == West:
return North
def try_move(dir):
if can_move(dir):
move(dir)
return True
return False
# === Strategy 1: Follow the left wall ===
def wall_follow_left():
dir = North
while True:
left = turn_left(dir)
if can_move(left):
dir = left
move(dir)
elif can_move(dir):
move(dir)
else:
dir = turn_right(dir)
if get_entity_type() == Entities.Treasure:
harvest()
return 1
# === Strategy 2: Follow the right wall ===
def wall_follow_right():
dir = North
while True:
right = turn_right(dir)
if can_move(right):
dir = right
move(dir)
elif can_move(dir):
move(dir)
else:
dir = turn_left(dir)
if get_entity_type() == Entities.Treasure:
harvest()
return 1
# === Strategy 3 (improved): Move towards the treasure with exploration memory ===
def move_towards_treasure():
tiles = {} # Dictionary: (x, y) -> info about walls and bifurcation
path = [] # List containing the path taken
bifurcations = [] # List containing bifurcations not yet fully explored
while True:
# If another drone already got the treasure, wait until the maze resets
m = measure()
if m == None:
while measure() == None:
return 1
x = get_pos_x()
y = get_pos_y()
pos = (x, y)
# Check if standing on the treasure
if get_entity_type() == Entities.Treasure:
harvest()
return 1
# Detect walls around the current tile
walls = {
North: not can_move(North),
East: not can_move(East),
South: not can_move(South),
West: not can_move(West)
}
# If the tile hasn't been recorded yet
if pos not in tiles:
n_walls = 0
if walls[North]:
n_walls = n_walls + 1
if walls[East]:
n_walls = n_walls + 1
if walls[South]:
n_walls = n_walls + 1
if walls[West]:
n_walls = n_walls + 1
is_bifurcation = n_walls < 3 # Less than 3 walls = bifurcation
tiles[pos] = {
"walls": walls,
"visited": True,
"bifurcation": is_bifurcation
}
if is_bifurcation:
bifurcations.append(pos)
# Mark the tile as visited
tiles[pos]["visited"] = True
if len(path) == 0 or path[-1] != pos:
path.append(pos)
# Find free directions not yet visited
free_dirs = []
for d in [North, East, South, West]:
if not walls[d]:
dx = 0
dy = 0
if d == North:
dy = 1
elif d == South:
dy = -1
elif d == East:
dx = 1
elif d == West:
dx = -1
next_pos = (x + dx, y + dy)
if next_pos not in tiles or not tiles[next_pos]["visited"]:
free_dirs.append(d)
# Randomly choose one of the available directions
if len(free_dirs) > 0:
r = random()
dir = free_dirs[0]
if len(free_dirs) == 2:
if r > 0.5:
dir = free_dirs[1]
elif len(free_dirs) == 3:
if r < 0.33:
dir = free_dirs[0]
elif r < 0.66:
dir = free_dirs[1]
else:
dir = free_dirs[2]
elif len(free_dirs) == 4:
if r < 0.25:
dir = free_dirs[0]
elif r < 0.5:
dir = free_dirs[1]
elif r < 0.75:
dir = free_dirs[2]
else:
dir = free_dirs[3]
move(dir)
continue
# No free paths — backtrack to the previous bifurcation
if len(path) > 1:
path.pop()
prev = path[-1]
px = prev[0]
py = prev[1]
# Physically move backwards
if px > x:
move(East)
elif px < x:
move(West)
elif py > y:
move(North)
elif py < y:
move(South)
x = get_pos_x()
y = get_pos_y()
pos = (x, y)
# If back at a bifurcation, try another unexplored direction
if pos in tiles and tiles[pos]["bifurcation"]:
walls = tiles[pos]["walls"]
free_dirs = []
for d in [North, East, South, West]:
if not walls[d]:
dx = 0
dy = 0
if d == North:
dy = 1
elif d == South:
dy = -1
elif d == East:
dx = 1
elif d == West:
dx = -1
next_pos = (x + dx, y + dy)
if next_pos not in tiles or not tiles[next_pos]["visited"]:
free_dirs.append(d)
if len(free_dirs) > 0:
r = random()
dir = free_dirs[0]
if len(free_dirs) == 2:
if r > 0.5:
dir = free_dirs[1]
elif len(free_dirs) == 3:
if r < 0.33:
dir = free_dirs[0]
elif r < 0.66:
dir = free_dirs[1]
else:
dir = free_dirs[2]
elif len(free_dirs) == 4:
if r < 0.25:
dir = free_dirs[0]
elif r < 0.5:
dir = free_dirs[1]
elif r < 0.75:
dir = free_dirs[2]
else:
dir = free_dirs[3]
move(dir)
def treasure_hunt():
# Uses wall-following strategies
spawn_drone(wall_follow_left)
spawn_drone(wall_follow_right)
# Uses the bifurcation exploration strategy
while num_drones() != max_drones():
spawn_drone(move_towards_treasure)
move_towards_treasure()
to use
from MazeUtil2 import create_maze, treasure_hunt
times = 30
#for i in range(times):
#create_maze()
#treasure_hunt()
while True:
if create_maze():
if treasure_hunt():
continue
I updated my code in the link. I drop the drones before starting the maze, and removed the clear function. This is in response to KanzakiRanko1 who had a great idea on letting spawned drones persist between mazes.
In addition to the wall-following strategy, I created code that marks the forks, so it explores a fork until the end. If it doesn't find the treasure, it returns to the fork and explores the next one.
This is useful for larger mazes with a larger number of drones.
def create_maze(): clear() plant(Entities.Bush) while get_entity_type()==Entities.Bush: substance = get_world_size() * 2**(num_unlocked(Unlocks.Mazes) - 1) if num_items(Items.Weird_Substance) > substance: use_item(Items.Weird_Substance, substance) return 1 if can_harvest(): harvest() plant(Entities.Bush) if num_items(Items.Fertilizer)==0: # I do not have trade unlocked #trade(Items.Fertilizer) return 0 use_item(Items.Fertilizer) # === Helper Functions === def turn_left(dir): if dir == North: return West if dir == West: return South if dir == South: return East if dir == East: return North def turn_right(dir): if dir == North: return East if dir == East: return South if dir == South: return West if dir == West: return North def try_move(dir): if can_move(dir): move(dir) return True return False # === Strategy 1: Follow the left wall === def wall_follow_left(): dir = North while True: left = turn_left(dir) if can_move(left): dir = left move(dir) elif can_move(dir): move(dir) else: dir = turn_right(dir) if get_entity_type() == Entities.Treasure: harvest() return 1 # === Strategy 2: Follow the right wall === def wall_follow_right(): dir = North while True: right = turn_right(dir) if can_move(right): dir = right move(dir) elif can_move(dir): move(dir) else: dir = turn_left(dir) if get_entity_type() == Entities.Treasure: harvest() return 1 # === Strategy 3 (improved): Move towards the treasure with exploration memory === def move_towards_treasure(): tiles = {} # Dictionary: (x, y) -> info about walls and bifurcation path = [] # List containing the path taken bifurcations = [] # List containing bifurcations not yet fully explored while True: # If another drone already got the treasure, wait until the maze resets m = measure() if m == None: while measure() == None: return 1 x = get_pos_x() y = get_pos_y() pos = (x, y) # Check if standing on the treasure if get_entity_type() == Entities.Treasure: harvest() return 1 # Detect walls around the current tile walls = { North: not can_move(North), East: not can_move(East), South: not can_move(South), West: not can_move(West) } # If the tile hasn't been recorded yet if pos not in tiles: n_walls = 0 if walls[North]: n_walls = n_walls + 1 if walls[East]: n_walls = n_walls + 1 if walls[South]: n_walls = n_walls + 1 if walls[West]: n_walls = n_walls + 1 is_bifurcation = n_walls < 3 # Less than 3 walls = bifurcation tiles[pos] = { "walls": walls, "visited": True, "bifurcation": is_bifurcation } if is_bifurcation: bifurcations.append(pos) # Mark the tile as visited tiles[pos]["visited"] = True if len(path) == 0 or path[-1] != pos: path.append(pos) # Find free directions not yet visited free_dirs = [] for d in [North, East, South, West]: if not walls[d]: dx = 0 dy = 0 if d == North: dy = 1 elif d == South: dy = -1 elif d == East: dx = 1 elif d == West: dx = -1 next_pos = (x + dx, y + dy) if next_pos not in tiles or not tiles[next_pos]["visited"]: free_dirs.append(d) # Randomly choose one of the available directions if len(free_dirs) > 0: r = random() dir = free_dirs[0] if len(free_dirs) == 2: if r > 0.5: dir = free_dirs[1] elif len(free_dirs) == 3: if r < 0.33: dir = free_dirs[0] elif r < 0.66: dir = free_dirs[1] else: dir = free_dirs[2] elif len(free_dirs) == 4: if r < 0.25: dir = free_dirs[0] elif r < 0.5: dir = free_dirs[1] elif r < 0.75: dir = free_dirs[2] else: dir = free_dirs[3] move(dir) continue # No free paths — backtrack to the previous bifurcation if len(path) > 1: path.pop() prev = path[-1] px = prev[0] py = prev[1] # Physically move backwards if px > x: move(East) elif px < x: move(West) elif py > y: move(North) elif py < y: move(South) x = get_pos_x() y = get_pos_y() pos = (x, y) # If back at a bifurcation, try another unexplored direction if pos in tiles and tiles[pos]["bifurcation"]: walls = tiles[pos]["walls"] free_dirs = [] for d in [North, East, South, West]: if not walls[d]: dx = 0 dy = 0 if d == North: dy = 1 elif d == South: dy = -1 elif d == East: dx = 1 elif d == West: dx = -1 next_pos = (x + dx, y + dy) if next_pos not in tiles or not tiles[next_pos]["visited"]: free_dirs.append(d) if len(free_dirs) > 0: r = random() dir = free_dirs[0] if len(free_dirs) == 2: if r > 0.5: dir = free_dirs[1] elif len(free_dirs) == 3: if r < 0.33: dir = free_dirs[0] elif r < 0.66: dir = free_dirs[1] else: dir = free_dirs[2] elif len(free_dirs) == 4: if r < 0.25: dir = free_dirs[0] elif r < 0.5: dir = free_dirs[1] elif r < 0.75: dir = free_dirs[2] else: dir = free_dirs[3] move(dir) def treasure_hunt(): # Uses wall-following strategies spawn_drone(wall_follow_left) spawn_drone(wall_follow_right) # Uses the bifurcation exploration strategy while num_drones() != max_drones(): spawn_drone(move_towards_treasure) move_towards_treasure()to use
from MazeUtil2 import create_maze, treasure_hunt times = 30 #for i in range(times): #create_maze() #treasure_hunt() while True: if create_maze(): if treasure_hunt(): continue
I made a few changes to Filipe-Brr's code and it seems to be going much faster. I moved clear() from the beginning of def create_maze to right above the while loop in the trigger code (the one marked as "to use"). At first this made the maze only run a few times then stall, but this was fixed by changing the last paragraph of def treasure_hunt() as follows:
while num_drones() != max_drones():
spawn_drone(move_towards_treasure)
if get_entity_type() != Entities.Hedge:
return 1
It now works indefinitely, and after when it would have normally stalled all the drones stay in their previous positions when the map reloads, making for much faster maze clear times.
One of the things I would add to the code would be with the Strategy 3 stuff.
That is updating the for d checks for this:
for d in [North, East, South, West]:
if not walls[d]:
dx = 0
dy = 0
if d == North:
dy = 1
elif d == South:
dy = -1
elif d == East:
dx = 1
elif d == West:
dx = -1
next_pos = (x + dx, y + dy)
if next_pos == m: #You're right next to the chest, so move there!
move(d)
harvest()
return 1
if next_pos not in tiles or not tiles[next_pos]["visited"]:
free_dirs.append(d)
I also do try to 'priortize' moves that would lead closer to the chest's X/Y coordinates, but that doesn't always work faster.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
use_item(Items.Water_Tank)is no morechange it to
use_item(Items.Water)Also in the Dec 18th updated version the code doesn't work.
I am going to try to update it and post it back here.