解开迷宫

0 点赞
编程农场
转载

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). 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!