We find paths using the geometric world model. Consider the problem of
going from [4,4] to [5,6]. We start at [4,4] and
enumerate all the clear neighbours. We then calculate the distance from
each of them to [5,6], using the standard formula. We pick the
neighbour for which this distance is least, and then repeat, finding its
neighbours, calculating distance, and so on. This is called guided
search. Instead of picking a neighbour blindly, we pick one which seems
most likely to lead to our goal. Our measure of success - our evaluation function - is distance.
In this particular problem, this gives us a nice short path. However, it wouldn't do so if there had been an obstacle a bit later on: our use of distance as a guide would not tell us about this. Picking the neighbour with the least distance from the goal is a good rule-of-thumb - a good heuristic - but one that sometimes fails.
After the search had finished, it generated this path:
[ [4, 4], [4, 5], [5, 5], [5, 6] ]
The final stage was to convert it into moves. This needed to know PopBeast's initial heading, and to keep track of how it changed. The result was this set of moves:
[left, forward, right, forward, left, forward]
The other path was generated in the same way, giving a complete plan of
[left, forward, right, forward, left, forward, grab, right, forward, forward, right, forward, forward, left, forward, use ]