Goals

The goals of this assignment are to learn the following:

Computer Science Principles Curriculum

Common Core Standards

Vocabulary

Overview

In this lesson we will learn about a computer science programming technique called recursion and then use it in a pathfinding algorithm called A* (A star). A* is very common in programming, one application being self-driving cars!

Goal 1: Recursion

Before we can work on a pathfinding algorithm we need to understand a technique called recursion. Recursion basically involves an action calling itself repeatedly until a stopping condition is hit. Typically you call a recursive function from a main procedure once and then the recursive procedure executes until it returns a final value. For a simple example of recursion we will look at a factorial operation from mathematics. As a reminder, factorial is denoted by an exclamation point following the number and represents the product of all positive integers less than or equal to the number.

For example, the factorial of 5 is: 5! = 5 * 4 * 3 * 2 * 1 = 120

Example: Create a template for a factorial calculator

We can write a factorial calculator program in a few lines of code. Lets setup up a class Main with two actions, Main and Factorial. The Factorial(integer n) action will take an integer parameter and will return an integer. In action Main, place a single statement output Factorial(5)

class Main
    action Main
      output Factorial(5)
    end

    action Factorial(integer n) returns integer

    end
end

Try Your Code Here

Inside the Factorial action, we will call Factorial recursively (meaning that the function will call itself repeatedly). In math, we know that n! = n * (n-1)!. So in our computer program we can say, assuming that Factorial(n-1) returns the correct value, that n * Factorial(n-1) is equivalent to Factorial(n). In the Factorial action , lets insert the statement: return n * Factorial(n-1). Let's run the program now and see what happens.

Incomplete Factorial program:

class Main
    action Main
      output Factorial(5)
    end

    action Factorial(integer n) returns integer
      return n * Factorial(n-1)
    end
end

If we run the program now, we will get an error like this:

Error: class java.lang.StackOverflowError, null
file: main.quorum,  class: Main,  action: Factorial,  line: 10 
file: main.quorum,  class: Main,  action: Factorial,  line: 10 
...
file: main.quorum,  class: Main,  action: Factorial,  line: 10

This is called a stack overflow error. The problem with our program is that the recursive function kept calling itself repeatedly until the computer ran out of memory (on its "stack"). In order to fix this, we need to tell the Factorial action when to stop. Typically this is done in the first lines of the recursive function with an if statement to check for the stopping condition, and then the if statement will return a base value instead of calling the function recursively again.

Activity

In our factorial calculation program, the base stopping condition is when n = 1 since we multiply the value passed to the action by n-1 for all positive integers and 1 is the lowest positive integer. When we reach 1 in the base case through the recursive calls, we should return the value 1 since 1! = 1, so in our program Factorial(1) should return the value 1. To fix the program, we insert an if statement code block to check if n = 1 and if so, simply return the value 1 and the action will no longer call itself. After the base case is returned, all of the other nested recursive calls can then return one by one, until the top level call is returned.

For this activity, add the stopping condition so that the program correctly outputs 120, the correct value of 5!.

Pathfinding Overview

Now that we understand how recursion works, we will use it in an algorithm to navigate automatically through a graph or a map. In order to perform this navigation your program needs to be able to choose the best path among several possibilities at each step. For example, when you need to go from point A to point B you may have the choice between several paths but we will use this algorithm to find the shortest.

In this assignment, you will write a program that uses a well known computer science algorithm called A* (A Star), which will find the best (shortest) path between 2 points in a grid with obstacles. This is commonly called pathfinding. To perform this operation you will use recursion in your algorithm. In our case, we will call the action to take the best next step in the path until we find the end point (which is our stopping condition).

The action AlgorithmAStar(integer iteration) in our code (the template is below) is the recursive action which will call itself repeatedly until we have achieved our goal and further calls are no long necessary. You will notice that the action AlgorithmAStar(integer iteration) has one parameter (integer iteration) which uses an integer variable called iteration which will be incremented by 1 each time we call the recursive action. The action also has a return value integer pathSize which returns the length of the final path (or -1 if there is no solution). The different positions/points are represented in the grid by Nodes which have several attributes like the position, the different values of G, H and F, a reference to the parent Node and a field indicating if the node is a starting or ending point.

In this algorithm we basically "visit" each Node iteratively (one at a time) and analyze the best path from that Node forward. The program we will write uses two lists : List openList and List closedList. The first list, openList, will contain the list of Nodes which have not yet been visited and the second list, closedList, will contain the Nodes which have already been visited. We will start by placing all of the Nodes in openList and move them one by one to closedList as we visit them.

When we visit a Node in the A* algorithm we analyze it by calculating values for each of the following fields of each Node :

Now we will program the actual algorithm with the instructions below. Download this Challenge 5.2 Template.zip file for a template to get started.

Challenge 5.2 Template

Goal 2: Choose the Node to visit next

The first thing we have to do in this algorithm is to declare an integer which will contain the size of the path (starting at 0 in the first point). Next we will choose the Node to visit, which we take from openList. We determine which Node to take from openList by selecting the Node which has the best chance to be on the optimal path. As we described before, the Node with the lowest stepsTotal value will be the Node to analyze next since that value will represent the lowest overall estimation of the final total cost if the path crosses the current Node.

Example:

This code calls an action GetNodeWithLowestEstimate(List nodeList) which finds the Node in the openList with the lowest score for stepsTotal, the estimate of the total number of steps from the start to the end point. The action is already written for you in the template project you downloaded earlier, so you will only need to call the action in your code.

// Select the Node from openList with the lowest estimate of total steps
Node currentNode = GetNodeWithLowestEstimate(openList)

Activity:

In the action AlgorithmAStar(...) in the template code, follow these steps:

We will use currentNode as the startingNode for our example.

Goal 3: Visit the Node

After choosing the node with the lowest steps estimate, we have to visit it and perform our analysis by recalculating the values. We do this using recursion, but like in the Factorial example above, we must first determine the stopping condition. In the recursive procedure, the stopping condition is checked first to determine if we should proceed with the recursion or stop and return a value for the base case. In this example, the stopping condition is when our currentNode is the end Node. So the first thing we check when we visit a Node is whether or not it is the end Node. If so, the algorithm has encountered the stopping condition and we have completed our path. If not, we must continue the algorithm to take another step. In this step, we consider the case where we have arrived at the end Node and we take the correct actions.

Example:

If we are at the end Node, we must do three things for our example:

Activity:

In the template project for Step 2, first create a code block that executes if currentNode is the end Node. You can check this condition by calling the IsEndingNode() action of currentNode. If this condition is not true then you will proceed to Step 3 so you will not need an else condition.

Inside the conditional code block you perform three tasks:

Goal 4: Identify adjacent Nodes

In this step, the stopping condition has not been met, which means we are that currentNode is not the end Node. So we have two things we must do:

Example:

Following is an example of how you can check adjacent Nodes to the currentNode by calling the AdjacentNode action. The AdjacentNode action is already written for you and will first verify that the Node you are checking is not already in either the openList or closeList and that it is not an obstacle. If none of these are true, the action adds the Node to the openList and sets the Parent to the currentNode for the back tracing step from Goal 2.

// Note that each Node as four adjacent Nodes at positions (x+1, y+0), (x-1, y+0), (x+0, y+1), (x+0, y-1) relative to the currentNode.
// Call the AdjacentNode action to each node to verify: (i)that the Node is not an obstacle or in either 
// the openList or closedList and set the Parent of the Node to currentNode.
if currentNode:GetPositionX() + 1 < nodeGrid:GetMaxNumberOfRows()
    AdjacentNode(currentNode, currentNode:GetPositionX() + 1, currentNode:GetPositionY())
end

Activity:

In the next line of the AlgorithmAStar() action after the stopping condition block's, do the following:

Goal 5 : Implement recursion

After we have completed our maintenance activities on the currentNode and our Node lists, we call AlgorithmAStar() recursively to find the next best Node from the current Node.

Example:

This is an example of how to call AlgorithmAStar(integer iteration) recursively:

pathSize = AlgorithmAStar(iteration + 1)

Activity:

Sample Output

Now that you have written the complete AlgorithmAStar() with the 4 previous parts, you can run the program. The instruction will be put at the top of the game window. Choose a starting and an ending point and press "ENTER" to execute the algorithm, it will find the best path.

If you want to change the obstacles you can do it in the main.quorum class, in the CreateGame() action, you will find 2 loops which browse all the grid and a condition with the positions of obstacles (i and j), change the value in this condition will change the positions of obstacles. Congratulations! You now understand a pathfinding algorithm and recursion and have an idea on how to use A* Algorithm.