How to Optimize your Harvesting Route in Stardew Valley

Introduction

Stardew Valley is a farming sim that includes a plethora of activities, not just limited to farming: from mining rare geodes to fighting sinister monsters, there is plenty to do in the valley. To give a brief explanation of how Stardew Valley works, players start out on their grandfather’s rundown farm, where they may cultivate crops and raise animals. Other activities include fishing, mining, and more. Players can interact with NPCs and build relationships with them, as well as unlock and explore other areas of Stardew Valley. 

However, there are some restrictions in the game; the most prominent one (in my opinion) being that your farmer has to go to bed by 2AM. Thus, for many players such as myself, we’d want to do as much as possible with the amount of time we’re given in order to be efficient as possible. One activity that takes up the most of players’ time is farming. From planting seeds to harvesting crops, it can be a very time-consuming process. Hence why, we will explore how to speed up this process, even for a few seconds.

Analysis

Lily Wu explores how to optimize the harvesting route of crops using graph theory, with a 12×10 patch of crops acting as the graph. She deduced that this graph had a few rules, mainly:

1. The optimal path (i.e. the shortest one) reaches each and every crop such that it takes the minimum amount of time to harvest crops
2. The crop you start at or end at does not matter as long as we obtain the fastest route 
3. It is a weighted multigraph; since harvesting crops walking to the right is faster than harvesting crops walking to the left, each pair of adjacent crops has two edges—one for each direction with the edge representing how much time it takes to walk between crops

   

   

4. The graph is defined to be an undirected one as at any point in the path, the direction of travel can change
5. Edge weights are dynamically populated as they are based on how much travel was done in a specific direction

To help solve this problem, several greedy algorithms were tested to see if they passed these rules. Unfortunately, none of the greedy algorithms used were able to satisfy all conditions. However, Lily was able to extrapolate two important pieces of information from this experiment:

1. Greedily choosing the best path at each crop helps make implementing dynamic edges easier
2. A data structure can be used to help choose the best path in an efficient manner

Thus, an algorithm was created to calculate the quickest path to take when harvesting your crops. The path took a total of 65.39 seconds, which was an improvement from Lily’s 69.87 seconds from just going up right-to-left.   

However, Lily noticed that the route was flawed due to the amount of times the route took a left-turn—the slowest direction to walk toward. Thus, she created a new route focused on going upwards and downwards, both of which are almost as fast as going to the right.

This route took a total of 64.53 seconds, a small improvement from the route the algorithm produced. Furthermore, it was much more straightforward than the path presented by the algorithm.

Conclusion

Aside from the optimal route to harvest your crops in, it was also concluded that human intuition was an important addition to flawed algorithms such as the one created by Lily. I highly agree with this sentiment as computers cannot always grasp the core needs of humans. This can be evidently seen when comparing the routes produced by the algorithm and by Lily, with the algorithm creating a highly complex route and Lily a much simpler and intuitive path.

Sources

https://towardsdatascience.com/solving-a-stardew-valley-routing-problem-with-graph-theory-python-fd4471077b3a