"The Farmer Was Replaced" maze solver

.The Farmer Was Replaced.md

Toy maze solver (stateless) for https://store.steampowered.com/app/2060160/The_Farmer_Was_Replaced/

create_maze.py

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()

treasure_hunt.py

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()

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.

gist:6cb2506bb1847d1b4490260673aa49c4

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.

Shortest working simple code for me is that.

def createLab(): # taken directly from in game advice
	plant(Entities.Bush)
	substance = get_world_size() * 2**(num_unlocked(Unlocks.Mazes) - 1)
	use_item(Items.Weird_Substance, substance)

def findLeftTreasure(): # This code will work like our drone have left hand on the wall while trying to find treasure
	rightOf={North:East, East:South, South:West, West:North}
	leftOf={North:West, West:South, South:East, East:North}
	dir=North
	while True:
		if can_move(dir):
			move(dir)
			dir=leftOf[dir]
		else:
			dir=rightOf[dir]
		if get_entity_type()==Entities.Treasure:
			harvest()
			return 1
	
def TreasureUp(Target):
	while num_items(Items.Gold)<Target: # Code will continue till target ammount of gold is met
		createLab()
		findLeftTreasure()
	return 1

Target=100000
TreasureUp(Target)

Shortest working simple code for me is that.

def createLab(): # taken directly from in game advice
	plant(Entities.Bush)
	substance = get_world_size() * 2**(num_unlocked(Unlocks.Mazes) - 1)
	use_item(Items.Weird_Substance, substance)

def findLeftTreasure(): # This code will work like our drone have left hand on the wall while trying to find treasure
	rightOf={North:East, East:South, South:West, West:North}
	leftOf={North:West, West:South, South:East, East:North}
	dir=North
	while True:
		if can_move(dir):
			move(dir)
			dir=leftOf[dir]
		else:
			dir=rightOf[dir]
		if get_entity_type()==Entities.Treasure:
			harvest()
			return 1
	
def TreasureUp(Target):
	while num_items(Items.Gold)<Target: # Code will continue till target ammount of gold is met
		createLab()
		findLeftTreasure()
	return 1

Target=100000
TreasureUp(Target)

I modified this to use both a left and right hand path, and then after 100 steps each done will spawn a drone of it's opposing direction. Helps it to feel more efficient.

def createLab(): # taken directly from in game advice
	if get_ground_type() != Grounds.Grassland:
		till()
	plant(Entities.Bush)
	substance = get_world_size() * 2**(num_unlocked(Unlocks.Mazes) - 1)
	use_item(Items.Weird_Substance, substance)

def findLeftTreasure(): # This code will work like our drone have left hand on the wall while trying to find treasure
	rightOf={North:East, East:South, South:West, West:North}
	leftOf={North:West, West:South, South:East, East:North}
	dir=North
	cnt = 0
	while True:
		cnt = cnt+1
		if cnt == 100:
			spawn_drone(findRightTreasure)
		if can_move(dir):
			move(dir)
			dir=leftOf[dir]
		else:
			dir=rightOf[dir]
		if get_entity_type()==Entities.Treasure:
			harvest()
			return 1
		if can_move(East) and can_move(West) and can_move(North) and can_move(South):
			return 1

def findRightTreasure(): # This code will work like our drone have left hand on the wall while trying to find treasure
	rightOf={North:West, West:South, South:East, East:North}
	leftOf={North:East, East:South, South:West, West:North}
	dir=South
	cnt = 0
	while True:
		cnt = cnt+1
		if cnt == 100:
			spawn_drone(findLeftTreasure)
		if can_move(dir):
			move(dir)
			dir=leftOf[dir]
		else:
			dir=rightOf[dir]
		if get_entity_type()==Entities.Treasure:
			harvest()
			return 1
		if can_move(East) and can_move(West) and can_move(North) and can_move(South):
			return 1
	
def TreasureUp(Target):
	while num_items(Items.Gold)<Target: # Code will continue till target ammount of gold is met
		createLab()
		spawn_drone(findRightTreasure)
		findLeftTreasure()

Target=100000
TreasureUp(Target)

I found the above scripts may held the drone and oscillated between two squares.
Instead, I am using DFS to solve the puzzle. It's generally faster than the above implementation, and guaranteed to solve the maze.

Size and location (origin) can be specified. Therefore it is handy for multi-drone farming for higher throughput.
16 * 8x8 mazes / 25 * 6x6 mazes are effective.

def treasure(origin, sz=0):
    def create_maze(origin, sz=0):
        movement.to(origin)  # Move the Drone to the center first
        # Following is taken directly from in game advice
        if sz == 0:
            sz = get_world_size()
        if get_ground_type() != Grounds.Grassland:
            till()
        plant(Entities.Bush)
        substance = sz * 2 ** (num_unlocked(Unlocks.Mazes) - 1)
        use_item(Items.Weird_Substance, substance)

    def dfs(last_dir):   
        # Defining the reverse direction. Used to determine where the drone comes from.
        reverse = {
            North: South, South: North, East: West, West: East, 
            None: None, # None is added to handle the first move
        }
        if get_entity_type() == Entities.Treasure:
            harvest()
            return True # Notify the callers to stop

        # Consider each direction as a branch.
        for dir in (North, East, South, West):
            # Skipping the Reverse of the Last Action, which is the previous space.
            # Also Skipping directions with wall.
            if dir == reverse[last_dir] or not can_move(dir):
                continue
            move(dir)           # Step into the next direction.
            found = dfs(dir)    # See if we can find the treasure from the next direction + the following moves.
            if found:
                return True     # Notify the callers to stop
            move(reverse[dir])  # Not found... Step back and try another direction.
        return False            # All Directions are not found. The caller shall not stop.

    create_maze(origin, sz)
    dfs(None)

# Example: Create a 8x8 maze, centered at (4,4) and solve it.
tresaure((4,4), 8)

If you don't have the implementation of movement.to(origin), which moves the drone to a specific place:

def to(pos):
	x,y = pos
	dx,dy = get_pos_x()-x, get_pos_y()-y
	if dx != 0:
		dir = East
		if dx > 0:
			dir = West
		for _ in range(abs(dx)):
			move(dir)
	if dy != 0:
		dir = North
		if dy > 0:
			dir = South
		for _ in range(abs(dy)):
			move(dir)