## Swarm Robotics in the Classroom

dark mode light mode Search Menu
Search

steamXO on Flickr

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.