Steams gemenskap :: Guide :: Solving the maze

Butikssida

The Farmer Was Replaced

Alla Diskussioner Skärmbilder Konst Sändningar Filmer Nyheter Guider Recensioner

The Farmer Was Replaced > Guider > BtBs guider

28 betyg

Solving the maze

Av BtB

The maze levels are very different than the remainder of the game. It's possible that, while enjoying the rest of the game, someone may get stuck on a maze and end up just finding a solution. The goal of this guide is to walk someone through the process of solving the maze without simply providing a solution (although a working implementation is included).

Utmärkelse

Skapat av

BtB
Offline

Kategori: Gameplay Basics, Walkthroughs

Languages: English

Lades upp

Uppdaterades

13 mar, 2023 @ 20:27

15 apr, 2023 @ 23:24

6,990	Unika besökare
19	Nuvarande favoriter

Guideindex

Överblick

General maze-solving technique

Creating the maze

Navigating the maze

Detecting/collecting the treasure

Implementation

Kommentarer

General maze-solving technique

The mazes in The Farmer Was Replaced contain no loops, meaning the easiest method of solving the maze is to follow the left wall. It is not the most efficient solution given full knowledge of the maze, it is a classic technique used in both corn fields and firefighting. It will always lead to the exit (or in this case a certain square) eventually and requires no knowledge other than the wall state of the left.

This guide implements this by taking every left turn whenever possible and testing if the floor beneath the drone contains the treasure.

Since the drone harvesting on any square other than the treasure ends the maze, the treasure must be detected prior to attempting to collect it.

The components of the program are as follows:

Create Maze
Navigate Maze
Find Treasure
Collect Treasure

Collecting the treasure is trivial, but there remaining sections have multiple parts.

Creating the maze

The maze is created by using fertilizer on a bush, but currently has a low percentage of success. This means the drone needs to check if the maze has been created prior to beginning navigation. Since the maze replaces the bush, the drone can check to see if the bush exists to determine if the fertilization was successful. Using a while loop ensures that the drone will keep trying until the maze is spawned.

Automating this system has a few issues, the largest of which is fertilizer isn't free. You can purchase fertilizer in the while loop, but this also means that you are continuously spending pumpkins. Without error checking, the drone could be stuck in an endless loop, hovering over a bush.

As an example:

#We require a bush to generate the maze. Code assumes clear() has been called plant(Entities.Bush) #This will continuously loop until the bush goes away (indicating the maze has spawned) while get_entity_type() == Entities.Bush: trade(Items.Fertilizer) use_item(Items.Fertilizer) if num_items(Items.Pumpkin) < 10: #If we can't afford more fertilizer return #Leave this function entirely

Navigating the maze

Navigation seems difficult, but can be broken down into a very simple procedure:

If there's no wall to your left, turn and go left.
If you can't go left, go straight.
If you can't go straight, turn and go right.
If you can't go right, turn around and back up.

Since there's no way to sense a wall, the drone can only sense if it's moved. Therefore we need to *attempt* to move in a direction then detect if our position changed.

The movement can be simplified by using a heading and realizing that testing for a left-hand wall is identical to trying to turn left and move forward. Therefore we can redefine the movement as:

Turn left
Try to move forward
If drone has not moved, turn right and try to move forward until drone moves

I implemented this as follows:

# Directions based on the right hand rule # This is required because movement requires a cardinal direction as an object, # and switch statements made of if/elif take much more space. dirs = [North,West,South,East] dir = 0 #Starting direction -- North #... oldx = get_pos_x() oldy = get_pos_y() move(dirs[dir]) # Finds direction object from list and moves that way while checkmove(oldx,oldy) == False: # While the drone hasn't moved... dir += 1 #...turn left... if dir > 3: #...and if we just turned North... dir = 0 #...reset to zero... move(dirs[dir]) #...then move forward. dir -= 1 # Now that we've moved, turn right... if dir < 0: #...and if we turned East... dir = 3 #...reset to 3

with this as a support function:

#Returns true if drone has moved from position X,Y. Else returns false def checkmove(X,Y): if X != get_pos_x(): return True if Y != get_pos_y(): return True return False

Detecting/collecting the treasure

A fairly simple section, there are two major ways to implement this. Finding the treasure is a matter of checking the ground, similarly to a plant.

if get_entity_type() == Entities.Treasure:

The above conditional statement can act as a trigger, or it can be modified in a while loop to navigate while the treasure isn't present, then break the loop once it's found.

Once found, a simple harvest() will collect the treasure and end the maze.

Implementation

I highly encourage you to work out the problem on your own; it's incredibly satisfying and there are many alternate solutions and implementations. The joy is in the creation, not the having.

But if you want a working implementation for reference or simply want to not do it yourself, I'm not here to tell you how to have fun.

def Maze(): clear() # Setting board to known state dirs = [North,West,South,East] # See above dir = 0 oldx = 1 # Begin homing to 1,1 (not necessary) oldy = 1 while get_pos_x() != 1: move(West) while get_pos_y() != 1: move(South) # End homing plant(Entities.Bush) # Begin maze spawning, see above while get_entity_type() == Entities.Bush: trade(Items.Fertilizer) use_item(Items.Fertilizer) if num_items(Items.Pumpkin) < 10: harvest() return while get_entity_type() != Entities.Treasure: # Navigate the maze until drone sees the treasure oldx = get_pos_x() # See above for notes oldy = get_pos_y() move(dirs[dir]) while checkmove(oldx,oldy) == False: dir += 1 if dir > 3: dir = 0 move(dirs[dir]) dir -= 1 if dir < 0: dir = 3 harvest() # We spawned the maze and navigated until we see treasure beneath us. Collect it. def checkmove(X,Y): if X != get_pos_x(): return True if Y != get_pos_y(): return True return False

The code is self contained, just enter the two functions and call "maze". You should have all required unlocks by the time you're trying to implement maze runs.

I had a blast making this and writing it up. Hope you have as much fun implementing it!

10 kommentarer

< >

TenuousBloom48 20 okt @ 21:35

Good news! They have since updated with a "can_move()," so you don't have to do the actual move!

1mpulse 16 okt @ 2:14

what is the performance of this script?
I need a script that can receive more than 2,000,000 gold per minute.

unfortunately, my script can only output 1,110,000 per minute.

Grey 28 jul, 2024 @ 0:26

You can also use a recursive backtracking algorithm.

def opposite_direction(dir):
return {
North: South,
East: West,
West: East,
South: North
}[dir]

def rec(dir):
if get_entity_type() == Entities.Treasure:
harvest()
return True
for d in [North, East, West, South]:
if d != opposite_direction(dir) and move(d):
if rec(d):
return True
move(opposite_direction(dir))
return False

def one_maze():
i = 0
if get_entity_type() != Entities.Bush and get_entity_type() != Entities.Hedge:
harvest()
plant(Entities.Bush)
while get_entity_type() == Entities.Bush:
if num_items(Items.Fertilizer) == 0:
trade(Items.Fertilizer)
use_item(Items.Fertilizer)
if get_entity_type() == Entities.Treasure:
harvest()
return
for d in [North, East, West, South]:
if move(d):
if rec(d):
break
return True

franzen.raphael 16 maj, 2024 @ 12:29

I made my own Version of the Maze Program:

It starts with some support functions, followed by the actual program

def Maze():
def expecting(ground):
if get_ground_type()!=ground:
till()
def fertilize():
if num_items(Items.Fertilizer)<=1 and num_items(Items.Pumpkin)>=10:
if not trade(Items.Fertilizer):
return False
elif num_items(Items.Pumpkin)<=10:
return False
if num_items(Items.Fertilizer)>1:
return use_item(Items.Fertilizer)
def plant_bush():
expecting(Grounds.Turf)
plant(Entities.Bush)
def plant_maze():
harvest()
plant_bush()
while get_entity_type() != Entities.Hedge:
fertilize()
return None

dirs = [North,West,South,East]
dir = 0
plant_maze()
while get_entity_type() != Entities.Treasure:
while not move(dirs[dir]):
dir = (dir + 1) % 4
dir = (dir - 1) % 4
harvest()
return True

killmetohell 2 jan, 2024 @ 12:06

nvm fixed it got my dir order wrong :P

killmetohell 2 jan, 2024 @ 11:34

some reason my nav version of my script broke but the test case works fine :(.

Tanner07 25 dec, 2023 @ 20:27

Wait nevermind

Tanner07 25 dec, 2023 @ 20:16

There is a way to sense in a specific direction, meaning no testing moves is needed

BtB [skapare] 28 sep, 2023 @ 10:40

Nice! Returning a bool is a game changer.

And the modulo is a brilliant change. Well done!

Koenich 28 sep, 2023 @ 4:57

since move() now returns a bool whether the move was succesfull or not, you can forget the part with position testing. Just check the return value of move().
Also (advanced) you can simnplify the calculation of the direction using modulo.

[code]
dirs = [North, East, South, West]
dir = 0

while get_entity_type() != Entities.Treasure:
while not move(dirs[dir]):
dir = (dir + 1) % 4
dir = (dir - 1) % 4

harvest()[/code]

< >