In the February 2023 issue, we made a gardening script for the Farmtronics mod for Stardew Valley. It included a simple goTo function to make the bot try to go to a location, chopping its way through any obstacles that it could. But if it ran into anything it couldn’t chop, it was stuck.

To do better, we need to find paths around any obstacles to a goal position. Humans can see a path easily. However, computers must check one square at a time. This is known as a path-finding problem, and the best solution is called A* (pronounced “A star”). Here’s how to apply the A* algorithm to your Farmtronics bot.

Launch Stardew Valley, and right-click a bot to open its console. Enter reset to be sure memory is clear, then edit to open the code editor. Carefully type in Listing 1. Press the Escape key to exit the editor, then type save “pathfinding” to save the file. Also, try the run command. If there are any errors, edit again to fix them; if nothing appears to happen, that’s a good sign.

Listing 1

import "mathUtil"

// Node class: used internally to represent one step
// in the search process.
Node = {}
Node.neighbors = function
  return [
    {"x":self.position.x + 1, "y":self.position.y},
    {"x":self.position.x - 1, "y":self.position.y},
    {"x":self.position.x, "y":self.position.y + 1},
    {"x":self.position.x, "y":self.position.y - 1}]
end function
Node.make = function(position, endPos, parentNode=null)
  n = new Node
  n.position = {"x":position.x, "y":position.y}
  n.parent = parentNode
  n.estCostToEnd = mathUtil.distance(n.position, endPos)
  n.estTotalCost = n.estCostToEnd
  n.costFromStart = 0
  if parentNode != null then
    n.costFromStart = parentNode.costFromStart + 1
  end if
  n.estTotalCost = n.costFromStart + n.estCostToEnd
  return n
end function
Node.path = function
  result = []
  n = self
  while n
    result.insert 0, n.position
    n = n.parent
  end while
  return result
end function

// Main entry point: Find a path between two positions,
// each specified as a map with "x" and "y" values.
find = function(startPos, endPos)
  toDoList = [Node.make(startPos, endPos)]
  doneSet = {}
  globals.hack = []
  while toDoList
    n = toDoList.pull
    if n.position.x == endPos.x and 
      n.position.y == endPos.y then return n.path
    for pos in n.neighbors
      if doneSet.hasIndex(pos) then continue
      doneSet.push pos
      t = here.tile(pos.x, pos.y)
      if t != null and not t.passable then continue
      noob = Node.make(pos, endPos, n)
      if noob.costFromStart < 50 then toDoList.push noob
    end for
    toDoList.sort "estTotalCost"
  end while
end function

Let’s consider how this works. It first defines a custom class called Node, to represent a location on the map, along with information about how many steps it took to get there (costFromStart), and the estimated number of steps to reach the goal (estCostToEnd). The sum of these is the estimated total cost (number of steps) to get to the goal if the bot goes through that map location. It is stored in estTotalCost. Every Node also knows its “parent” node, the point on the map that the bot would have come from to get there. The path method (lines 26-34) loops over that chain of parent links to build a list of the nodes the path must walk, once we find one that reaches the goal.

With this handy Node class ready, the A* algorithm itself is the find method on lines 38-58. This keeps a toDoList of nodes to consider, starting with the start position. This list is always kept sorted (by line 54) so the most promising nodes — the ones with the lowest estimated total cost — always come first. The find method keeps pulling the best node off this list, checks whether it is the goal position, and otherwise adds all neighbors (that are passable but not already checked) into the toDoList.

Figure 1 shows the first sixteen nodes checked by this program while searching for a path from the bot position to the yellow star. Notice how the cost (“C”) increases by one for every step away from the start position, while the estimated total cost (“E”) also depends on the distance to the yellow star. Always checking nodes in order of the lowest estimated total produces the guaranteed best possible path.

To hook this into your gardening script, type the load “startup.ms” command then type the edit command. Replace the goTo function with the one shown in Listing 2. This imports the pathfinding module you just made and plots a course to the goal.

Listing 2

import "pathfinding"
goTo = function(x,y)
  dest = {"x":x, "y":y}
  path = pathfinding.find(me.position, dest)
  if path == null then
  	print "Can't find a path to " + dest
  else
    print "Going to " + dest
    for pos in path
      faceLoc pos.x, pos.y
      me.forward
    end for
  end if
end function

With this new code, your bots will no longer be stuck behind some big rock or tree; now they can find their way around any obstacles. Your bots got a major upgrade.