So now you have a maze and are wondering how do I get this drone to that gold.


Now there are at least 2 other guides already,

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

Both of which offer a good amount of information and guidance on solving this problem.

Both lack a complete solution that sat well with me. So as a result I have explored this problem space a little more and offer it out to the world so that it can be built upon and made into something more.


As I have already mentioned two other guides I will not get into the basics but talk about how we can build up from where they left off and implement a strategy that allows us to propagate forward the information about the maze in a away that does not soft lock us.

Not soft locking the maze solution is a hard problem, but we have the tools!

I will be mainly exploring the least walked direction to this problem and correcting anything that will not work with my solution during it as well.

The first thing we need to do is make it so that the maze can be recreated dynamically. This will allow us to call simple functions to just get it done and not worry about how it is implemented.

It would be a really cool thing to see if any space on the board gives us a higher reward over time but that is beyond the scope of this guide so we will just randomize the starting (x, y) of the maze/drone. For that we will need a function to give us back a random int.


Using the above function we can now get the random numbers we need to go to a random (x, y).

Let us create and call a function that generates the maze now.


Now, you may be wondering how the heck'n we can start randomly if we are not taking in a (x, y) into the plant function. We just move there first then plant at that location. The code code would look like



Now that we mentioned it, the plant function is the first thing we can change to get this maze created faster.

A few things of note

• All plants can be planted on tilled soil
  
• Only tilled soil can be watered
  
• Fertilizer can be used basically instantly after the bush is grown till the maze is created

With these things in mind let's construct our plant_maze function.


So all the thing that needed to happen are happening, but why am I return True/False you ask. By returning the truthiness of our success we can use it to determine if we need to switch from mazes back to a different phase so we can continue or not as we do need pumpkins for fertilizer.

Now we have a working maze creator and it does a very good job, there are still some things we could try to speed it up but that is left to the reader.


Next we need to get to the treasure, but the drone is a blind boi and cannot see the map from the same perspective that we can. So we have to tell it to go on an arduous journey which has never ending instructions to finally get its so coveted prize, that gold!

The method I will implement here is to calculate the least traveled direction. This will allow the little drone to circumnavigate the maze in a somewhat timely manner.


So here is the function signature that we will be using. We will be taking in a argument called mv which will be the propagated maze values, starting with an empty list.

Now going with that though let set up some basic abilities of the function


Ok, we are making the mv variable local to the scope of the function, faster access and no scoping blunders, and defining a variable that lets us have all the possible directions we can move locally.

Next, we need to populate the maze_values if it is not already done by the propagated values.


So, wow that is a lot of loops! (DON'T really need them but again that is left to the viewer)
The data structure that we are creating looks something like

Where each of the int stored in the multi dimensional list is the value we will use to determine the least traveled direction.

Now it's time to get to the nitty gritty of this function and start moving around and mapping the least traveled as we go.


Oh boy! There is a ton going on here. So starting off we need a "wall" value, or a value which will limit that direction for travel, so that the drone will not choose it. Most algorithms that use this approach will select much higher values for the lwq than 12, but for this implementation we need a lower value that can be overridden as the maze does change through it's permutations.

Next is the whole of the while True loop, first inside we have to check we hit the jackpot and exit from the loop if we did as that is our loops exit condition.

Following that we initialize several variables that will decide which direction the drone is moving. lwd is least walked direction and is set to 3, 3 is max index of directions, at the start just so we can access it outside the following for loop. lwq is the wall value we will use. pbw is just our current (x, y)


Inside the the for loop we are doing a bunch of work. The first thing is that the for loop is going over the directions we have possible in movements variable that we declared before. Then it attempts to move in that direction, if it failed we set that direction to lwq so that it is hard to select it later on.

Looking at this line

We are getting the value for selected direction

Then

Which is getting the least direction traveled, and as a side effect if this never results to True we will have a bug where lwd never changes so we can potentially get stuck on multiple solves, that's for later though.

Then the final chunk

This whole bit can be improved and shortened, basically what is happening is that if the movement is successful then we will add a point for this direction as we have traveled it before.

Then using the b_ variable we decide the opposite direction and add a point to the current cell we have moved too. Else a wall.

Phase 1 is where we can solve the maze in a basic manner. There is no reuse of any part of the previous maze nor could we use the bonus system to replant the maze to get more gold.

Alright, by this point we have all the bits and bobs needed to create and solve a maze. At max unlocks and map size it takes <10 secs to solve which is worth 500 Gold!

Now, how do we make this WAY better, like way, way better? How about using the regrow option for the treasure before harvesting it.

Let me give you some metrics to start, without showing you anything else to see if it's worth.
All these tests are done with only propagation no use of something like A* to quickly get to the destination.

Also as we have to normalize the data structure each propagation it takes a long time as the data-structure is terrible, again another thing the viewer can work on.


As we can see, there are time savings and we get a sizable bonus for each retry for the extra time we spent. If strategies that involved building a node tree and then looking to see if the next location, given by measure on the treasure before harvest, is given then moving towards that using the tree was employed it would be many times faster.

Even with this basic, and junk, go at it we can directly see a gain over time of doing it. We can also see though that it will take a monstrous amount of time to get through all 300 possible growths if we wanted to attempt it.

Following the pattern set currently it would be about ~3 secs per attempt which is 299 * 3 or 897 secs to complete a whole maximized set.

As we have shown redoing the maze even with a trash strategy is worth it. So lets continue using the previous code we have created with a few tweaks to get it going.

One we need to start passing the value forward to the next call. We will do that in the mazes function that contains all the logic for doing the mazes, shown in code section for phase 1.


Everything is this code block is doing the things that I mentioned before. It is taking the previous maze and passing it forward to the next maze solve. This comes with some inherent problems as you go forward with the maze solves it get's "easier" to get to the treasure as there are less walls as seen here.

Though we will not worry about it in this phase as we are where we need to be with forward propagated maze data. The next challenge is to move to a move efficient data-structure and strategy to solve the maze in a faster time.

Phase 2 is where we can start reusing the previous map state and use that to solve the maze faster as we are not longer in the discovery phase.

Here are all the helper functions mentioned as code, there will not be any help provided here for these functions. This is just a reference to these functions that will be used throughout this guide.

It will be left to the viewer for these following suggestions.

One thing is to reduce the size complexity of the data-structure used to store the values for the discover map. This can be done multiple ways such as using (key: value) with a dict as this would make the normalization of the data faster.

Another thing would be to just have a shifting maximum value to use as the limit and then change the amount you add per loop in proportion to that so that you will always be able to check for new paths that have opened up. Or other hacks that basically negate the need to normalize the data.

A big change that can save some time is implementing a better and faster solver so that you can minimize the time between each growth of the treasure.

One that would not be too complicated to implement is the A* but you still have to discover the map or do in place discovery. There are many ways to implement something like but I will leave it up to the viewer to do some research on this to implement their own solution. As A* is an already solved map solver just google it for python and bang your head against the keyboard till it works.


Update 6/19/24

I implemented a breadth-first search (BFS) and was able to get an average of ~1.7 seconds per set until it hit the maximum of 300 for max gold generation. So even without going full A* or Dijkstra the times can still get decent.

The below code will not have any helper functions or what not, it is just for reference as I do not want to ruin any gains someone could get from figuring how to implement it out themselves. The code bit here is like a procedure code block as most of it is missing. The logic used for this particular implementation of a BFS can be found on the wiki or many other locations but gearing it up for your own use is a fun challenge if you are not used to doing so.

Feel free to ask any questions.

So an easy fix for the code I am using was to simply ensure that I was not building the graph each iteration. Do this saved a heap of time as it was not needed to build the graph each time.

After changing the graph building the code is now able to do all 300 iterations in a amazingly fast 192.19. The new function to do so looks like

Here is a video of the maze being solved.

https://www.youtube.com/watch?v=zc-rftetn_8

Was browsing the discussion and the following was there

https://gtm.steamproxy.vip/app/2060160/discussions/0/4521136185566148104/

This person's solution is really clever, check it out!