Challenge 5.2: A *

Goals

The goals of this assignment are to learn the following:

• How to use recursion in programming
• Understand a "pathfinding" algorithm and how it works

Computer Science Principles Curriculum

• Big Idea: Algorithms: EK 4.1.1A, EK 4.1.1B, EK 4.1.1C, EK 4.1.1D, EK 4.1.1E, EK 4.1.1F, EK 4.1.1G, EK 4.1.1H, EK 4.2.1A, EK 4.2.1B
• Big Idea: Programming: EK 5.1.2A, EK 5.1.2B, EK 5.2.1A, EK 5.2.1B, EK 5.2.1C, EK 5.2.1D, EK 5.2.1E, EK 5.5.1A, EK 5.5.1D
• Big Idea: CreativityEU 1.3, LO 1.3.1, EK 1.3.1D

Common Core Standards

• English Language Arts Standards » Science & Technical Subjects: CCSS.ELA-Literacy.RST.9-10.3, CCSS.ELA-Literacy.RST.9-10.4, CCSS.ELA-Literacy.RST.9-10.5, CCSS.ELA-Literacy.RST.9-10.7, CCSS.ELA-Literacy.RST.9-10.10, CCSS.ELA-Literacy.RST.11-12.2, CCSS.ELA-Literacy.RST.11-12.3, CCSS.ELA-Literacy.RST.11-12.4, CCSS.ELA-Literacy.RST.11-12.5, CCSS.ELA-Literacy.RST.11-12.10
• Mathematics Content: High School Functions » Building Functions: CCSS.Math.Content.HSF.BF.1A
• Standards For Mathmatical Practice: CCSS.Math.Practice.MP1, CCSS.Math.Practice.MP2, CCSS.Math.Practice.MP4, CCSS.Math.Practice.MP5, CCSS.Math.Practice.MP6, CCSS.Math.Practice.MP7, CCSS.Math.Practice.MP8

Vocabulary

• A* (pronounced A Star)
• Algorithm
• Edge
• Factorial
• Graph
• Node
• Parameter
• Pathfinding
• Recursion

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

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!.

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:

• Find the Node with the lowest stepsTotal value with the openList as a parameter by calling Node GetNodeWithLowestEstimate(openList).
• Assign the result of the previous call to a new Node variable called currentNode as indicated in the example
• Declare a variable called pathSize and initialize it to 0.

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:

• We update and display our grid
• We retrace our optimal path in the reverse direction and mark each Node orange for display purposes
• We count the length of the path

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:

• Redraw the grid by calling the DrawGrid() action, which is already included for you in main.quorum
• Retrace the optimal path by moving the currentNode from the ending Node to the startingNode and marking each Node on that path by changing its color to orange. This may seem out of order at this point, but remember that the base case is the ending condition, so we can assume that the path from each Node to the next best Node has already been set (even though we don't actually write the code for this until later. Set up a repeat loop to execute while currentNode:IsStartingNode() = false.
• Inside the repeat loop block, first change the Node in the nodeGrid array by calling SetColor(color:Orange) on the Node and then set currentNode = currentNode:GetParent() to move it back one Node on the path.
• In order to get the correct Node from the NodeGrid, use the GetPositionX() and GetPositionY() actions from the currentNode. You will use the GetParent() action on the currentNode to find the previous step on the optimal path. Note that this field will be set during the analysis phase of a non-ending node (Goal 4).
• Increment the pathSize variable by 1.
• Return the pathSize variable.

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:

• First, we must remove the currentNode from the openList and add it to the closedList since we are now analyzing it.
• Second, we have to add any new Nodes adjacent to the currentNode which are not obstacles to the openList which we can see now. These new nodes are candidates for analysis in the future. We can adjust the stepsFromStart field of each new Node to be the value of the currentNode's stepsFromStart value + 1 since it will take 1 more step to reach that Node from where we are.

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:

• Add currentNode to the closedList
• Remove currentNode from the openist
• Call AdjacentNode as in the example above on each of the four adjacent Nodes.

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.

• When the openList is empty, it means that we have reached a dead end and the algorithm can not continue because there are no further Nodes to analyze. So there is no path between the starting and the ending point. in this case you should return -1 to indicate no solution is found.
• Otherwise call AlgorithmAStar() again with the parameter set to iteration + 1 and assign the result to pathSize and then return pathSize.

Example:

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

pathSize = AlgorithmAStar(iteration + 1)

Activity:

• Implement a condition to check if openList:IsEmpty() is true. If so, return -1 to indicate that the algorithm failed to find a path, otherwise, set the pathSize variable to the recursive call to AlgorithmAStar(). Be sure to pass iteration + 1 as the parameter.
• Return the pathSize variable

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.

End of Lesson

You have reached the end of the lesson for Classes. To view more tutorials, press the button below or you can go back to the previous lesson pages.