Steam Community :: Guide :: A different approach to solving the maze

Store Page

The Farmer Was Replaced

All Discussions Screenshots Artwork Broadcasts Videos News Guides Reviews

The Farmer Was Replaced > Guides > Koenich's Guides

Not enough ratings

A different approach to solving the maze

By Koenich

With the October 2023 update a new maze functionality was introduced: fertilizing the treasure chest to spawn it at another location (with increased value). This opens up a new strategy to farm gold, which might require a different maze solving algorithm then the left-hand (or right-hand) method.
As a side effect, the maze despawns walls if the chest is fertilized, creating loops, which is another reason to think about a different strategy.

Award

Created by

Koenich
Offline

Category: Gameplay Basics, Walkthroughs

Languages: English

Posted

1 Nov, 2023 @ 1:53pm

3,898	Unique Visitors
9	Current Favorites

Guide Index

Overview

Choosing a maze solving algorithm

Navigating the maze

Implementation - pseude code

A new definition - where the dfs tree grows

Maze solving 2.0 - pseude code

What if - Some further thoughts

Comments

Choosing a maze solving algorithm

I have decided to use the Trémaux algorithm[en.wikipedia.org], because it works while moving inside the maze. As we are only getting information from the drone (we do not have access to other fields on the farm than the one the drone is on) other pathfinding solutions didn't seem appropriate to me.

Navigating the maze

Trémaux gives these instructions to solve a real life maze:
Whenever you enter a passage or junction (a field on our farm), do the following:

mark your entrance
pick an unmarked entrance (or exit if you wish)
if all entrances are marked use the one you just came in (unless it has 2 marks)
if your entrance has 2 marks, pick a random exit with only 1 mark
mark the exit

This will guide you through any maze in real life, but to translate it into TFWR we need to take care of some speciallities:

marking is not possible, so we need some kind of memory
(list or dictionary - I'd prefer the latter)
we should not choose randomly in step 2 and 4
(instead take directions from a list)
the drone has no sensors to "see" the exits, we can only detect them by trying to move in a direction
unfortunately we do not have a can_move() function

Implementation - pseude code

Here is one possibility to implement the algorithm in pseudo code. It might not be the prettiest or smartest one, but it gets you on the right track to make it work.

until drone is over treasure chest: if not already done before: put current location into memory if we moved here: increase counter for direction we came from loop through the 4 possible directions: if current direction counter is 0 in memory: try to move there if move was successful: increase counter (mark) for current direction in memory exit loop else set counter to 2 (wall) if we didn't move: if we moved here: if the counter for the direction we came from < 2: move there if we still didn't move: loop through the 4 possible directions: if current direction counter is < 2 in memory: try to move there if move was successful: increase counter for current direction in memory exit loop else set counter to 2 if again we still didn't move: print("Someone stole the treasure chest, we've been everywhere!")

This is quite a big buzzer. Can't we improve it, make a bit smaller?
I am glad you asked.

A new definition - where the dfs tree grows

Now that we have understood how this algorithm was originally intended to be used, let's look at it from a different, more programming related angle. If you think of the maze as rooms connected through ways, like branches on a tree...
You eventually see the parallels to a modern data structure called Data-Tree, in this case actually a Trémaux Tree[en.wikipedia.org].
And when you think of the walk through the maze more like traversing the rooms (tree nodes) you will end up with something that is known as depth-first search[en.wikipedia.org].
To easier understand what this means, think of the maze solving in reverse. Instead of looking at what we already did (remembering already visited ways), let's instead create a To-Do List of ways we have not yet explored, and then work that list in a specific order.

Maze solving 2.0 - pseude code

Some rules we need to understand before we start:

We will use a list of the 4 directions (North, East, South, West), this needs to be ordered in some way, i.e. clockwise or counterclockwise (or whatever rule you can come up with)
Our To-Do list needs to be LIFO (last in first out) so we can easily backtrack the way we came from.
We will stop when finding the chest, as there will always be a chest. So no need to remember where we started and end our search if we start to loop.

make an ordered list with all possible directions make a to-do list and add all 4 directions # we have nothing explored yet until drone is over treasure chest: try the last direction from to-do list if it is a wall -> try next # so we found a way move in this direction add all 4 directions to our to-do list, the one we came from first # That's it if get_entity_type() == Entities.Treasure: Yay!

It looks so small compared to the other one, right? Let's look at it:
We take the last direction from our To-Do-List and test if we can move there.
If so, we do and add the 4 directions to the end of the list (the direction we came from first)
Then we start over, until we found the treasure chest.
Because we are adding to the end of the list, and also taking from the end, we essentially always move forward (down one way of the tree (maze)) until we hit a dead-end (3 directions are walls) We then return to where we came, hence the order of adding, and take a new direction from the to-do-list (branching onto another way). Normally this end when you reach the same position as you started and no neighbouring nodes are left. In TFWR we can assume there will always be a treasure chest, so we can simply stop when we found it.

What if - Some further thoughts

We can now fertilize the chest (just like the bush), and it eventually will move to another location, increasing its worth. We could just use this to then run the maze algorithm again and so on. Essentially this would just save us the time to wait for another bush to grow ... but ... before fertilizing the chest we can measure() it to get the new location of the chest.
What if
Instead of searching for the chest, we use the algorithm to map the entire maze. Then (with this knowledge) find the shortest way to the chest, fertilize it and measure() the new location. With the map of the maze, we can now find the shortest way to the new chest. Measure it, fertilize it, find the shortest way to the new spawn point, measure(), fertilize, ...

https://gtm.steamproxy.vip/sharedfiles/filedetails/?id=3063256073

hm?

6 Comments

< >

Padicus 14 Jan @ 2:39am

Very simple implementation of hand-on-wall:

dir = [North, East, South, West] #We'll use this to find which direction to go next
d = 0

clear()
while(True): #Infinite loop. Will run as long as you have WS
----plant(Entities.Bush)
----use_item(Items.Weird_Substance, 100) #change 100 for the desired amount of WS
----|---while get_entity_type() != Entities.Treasure: #Run until you run into the treasure
----|---|---if not move(dir[d]): #Try to move in the chosen direction
----|---|---|---d = (d + 1) % 4 #If you moved, turn right
----|---|---else:
----|---|---|---d = (d - 1) % 4 #If you didn't move, turn left
----|---harvest() #Profit. Rinse and repeat

VrIgHtEr 22 Jun, 2024 @ 11:45am

Also, since you're implementing the hand-on-wall algorithm, you don't even need a stack. In each cell note the direction you last moved in (or tried to move in), turn 90 degrees (always clockwise or anticlockwise, do not mix) and try moving.

VrIgHtEr 22 Jun, 2024 @ 11:41am

I don't know why you bothered mentioning tremaux at the beginning. The final code is quite literally implementing the hand-on-wall algorithm not the tremaux algorithm. It won't work on a non-perfect maze, ex. if you stop a harvesting cycle early, and restart the program in the middle of a maze that has some walls removed.

cry about it 1 Jun, 2024 @ 8:27pm

A simple dfs approach is to just do it recursively, propagating all the way back if it finds the target (which you of course could do with coordinates instead of checking the type)

Steam is not great for formatting code... So I added some "-"s and "|" to mark indentation.

def dfs(visited):
----if get_entity_type() == Entities.Treasure:
----|---return True
----for dir in [North, East, South, West]:
----|---if move(dir):
----|---|---if get_pos() not in visited:
----|---|---|---visited.add(get_pos())
----|---|---|---if dfs(visited):
----|---|---|---|---return True
----|---|---move(opposite(dir))
----return False

Moving and then checking if we have already visited is not really efficient, it would be better to write a function to tell you where you would have ended up if you moved, and check if that position is already visited before trying to move. But I'll leave it as this for simplicity.

AmidstDarkness 1 Jun, 2024 @ 4:16pm

i have been making an attempt at doing the second one, and for some reason, it always fails at three way intersections. Here is the working parts of what I have.

def harvest_treasure_new(req):
#start_maze() #creates a maze
while num_items(Items.Gold) < req:
#list of all directions, and a todo list of directions yet to be gone
directions = [North, East, South, West]
todo = list(directions)
while get_entity_type() != Entities.Treasure:
#write something that checks if there is a wall at the last location in todo,
#if there is a wall, remove the item, and go to the next one.
#if there is no wall, go that direction.
#issue being, it doesnt know when it should be backtracking
#instead of forging a new path

AmidstDarkness 1 Jun, 2024 @ 4:16pm

#add all 4 directions to our to-do list, the one we came from first
#figures out which item is at todo[-1], and sets previousDirection to its opposite
for dex in range(4):
if directions[dex] == todo[-1]:
previousDirection = directions[(dex+2)%4]
#append previousDirection to todo
todo.append(previousDirection)
#append the other directions to todo
for dir in directions:
if dir != previousDirection:
todo.append(dir)

#found treasure
print('Success!')
if measure() == None:
start_maze() #creates a maze
while get_entity_type() == Entities.Treasure:
use_fertilizer() #if there isnt enough fertilizer, trades for some, then uses it

< >