TFWR. Labyrinth

TFWR. Labyrinth

Let’s think about the labyrinth problem in The Farmer Was Replaced game.

First of all, let’s state it. We have an
𝑛×𝑛 labyrinth, where n = get_world_size(). In position measure() there is a treasure. Our current position is (get_pos_x(), get_pos_y()). We can move our drone by issuing commands move(East|North|West|South). Our task is to find the treasure, which we can detect by the condition get_entity() == Entities.Treasure(). Information on the maze map we can obtain through the boolean can_move(East|North|West|South) function.

To be honest, I have no clue why the approach of “right hand” or “left hand” is so popular. I started with DFS (Depth First Search), and I want to explain this approach in the post.

It seems that it’s quite popular to start with these “hand” approaches. But they fail when you are trying to gain more money from your treasure hunt. According to the rules, the prize doubles when, instead of harvesting, you use weird substance on the treasure. In this case, you reuse the labyrinth, and the treasure jumps into some other place. You can do it 30 times (and should, if you want to have an efficient farm). Also, when the treasure jumps, some walls in the labyrinth disappear. There are two consequences of this disappearance. First of all, the “hand” approaches don’t work anymore. On the other hand, the maze simplifies and, if you use an appropriate algorithm, your drone finds the treasure faster and faster.

In this topic I want to show the simplest possible DFS code which doesn’t rely on a “strict tree structure” of the maze.

Let’s do it. DIRECTIONS – array with arguments for the move() function. visited – the set of positions we have visited so far. OPPOSITE – the dictionary with opposite directions.

def go_best(d1, d2, l1, l2):
  d, l = d1, l1
  if l2 < l1:
    d, l = d2, l2
  for _ in range(l):
    move(d)


def nav(x2, y2):
  n = get_world_size()
  x1, y1 = get_pos_x(), get_pos_y()
  go_best(East, West, (x2 - x1)%n, (x1 - x2)%n)
  go_best(North, South, (y2 - y1)%n, (y1 - y2)%n)

def apply_proper_substance():
  substance = get_world_size() * 2**(num_unlocked(Unlocks.Mazes) - 1)
  use_item(Items.Weird_Substance, substance)


set_world_size(8)
nav(3, 3)
plant(Entities.Bush)
apply_proper_substance()

DIRECTIONS=[East, North, South, West]
OPPOSITE={East:West, West:East, North:South, South:North}

def dfs(visited):
    if (get_pos_x(), get_pos_y()) in visited:
        return

    visited.add((get_pos_x(), get_pos_y()))
    if get_entity_type() == Entities.Treasure:
        harvest()

    for dir_to_move in DIRECTIONS:
        if can_move(dir_to_move):
            move(dir_to_move)

            dfs(visited)

            move(OPPOSITE[dir_to_move])

visited = set()
dfs(visited)

while True:
  pass

The code is as simple as possible and because of this it contains a few obvious issues:

issue: in this algorithm the drone “jitters” forward and backward all the time
reason: it checks its current position in visited, so it really needs to move into a cell to check it
how to fix: write a “projection” function which can calculate the drone’s position after it makes a step and check it in visited

issue: this code collects the treasure immediately
reason: I wanted this code to be as simple as possible
how to fix: add logic to break the recursion when the drone is over the treasure, and create an outer loop for the labyrinth upgrade