Final

Question 1

A tagging system was implemented as part of the obstacle avoidance system. What is the purpose of tagging an obstacle.

Answer 1

1) makes the code more understandable
2) checks to see how close the objects are to an agent, if an agent is within a certain range, it then tags the object. Only the objects tagged will be converted to local space.
3) this ensures only objects that are in danger of colliding with the agent have the more costly trig operations performed on them

Question 2

True or False

Local coordinates allow the agent to measure the distance to an obstacle.

Answer 2

False

Local coordinates allow you to see if the object is within the agent’s path.

Question 3

True or False

Untagging an obstacle early in the avoidance system can save valuable clock cycles.

Answer 3

True

Question 4

How dies the agent know if an obstacle is in front of him or behind him?

Answer 4

If the local X is negative, the obstacle is behind the agent.

Question 5

What are the local coordinates of the object if its global coordinates are (3,4) and the agents global coordinates are (3,5), with an angle of PI squared?

Answer 5

rotate the graph so that the agent is facing positive x.

place the agent at (0,0). The objects position will be the location relative to the player’s new rotation.

Question 6

Why should the player’s hit box extend with increased velocity?

Answer 6

So that there is more time for the agent should slow down should an object happen to be in it’s path.

Question 7

The hit box is rectangular, but our obstacles were circular. How was the collision detection achieved?

Answer 7

When compared in local space: The x axis splits the agent in half, if the radius of the object plus the half width of the agent = less than the local y of the object then there will be a collision

Question 8

True or False

The DFS algorithm will always find the target node on a connected graph.

Answer 8

True

Question 9

True or False

The DFS will always find the shortest path to the target node.

Answer 9

False

Question 10

True or False

The DFS may find the target faster than A*.

Answer 10

True

Question 11

True or False

The DFS may find the target faster than BFS.

Answer 11

True

Question 12

True or False

The DFS marks visited nodes with the current node as it searches.

Answer 12

False

Question 13

Why does the DFS need to keep track of the path it has taken as it searches for the target?

Answer 13

so that it can backtrack if it reaches a dead end.

Question 14

The DFS requires fewer clock cycles than the other two algorithms. Why is it a poor choice for path finding?

Answer 14

It is VERY rarely the shortest path.

Question 15

True or False

The BFS always finds the shortest path to the target.

Answer 15

True

Question 16

True or False

The BFS may find the target before DFS.

Answer 16

True

Question 17

True or False

The BFS can find the target even if there are some walls on the map in between the root and the target.

Answer 17

True

Question 18

True or False

The BFS is always faster than A*.

Answer 18

False

Question 19

True or False

The BFS uses a queue to keep track of the nodes as it searches.

Answer 19

True

DFS uses a stack

Question 20

Describe the pattern formed by the BFS as it searches for the target on a grid like map.

Answer 20

like a spider web

Question 21

Why does the BFS mark the nodes with a visitor?

Answer 21

(visitor == predecessor == parent)

to keep track of the path to the start node.

Question 22

Explain why A* is superior to the BFS for path finding on a large map.

Answer 22

The A* algorithm does not search the entire map, as BFS is prone to do.

Question 23

Explain the purpose of an open list.

Answer 23

List of candidates for the next current node.

Question 24

Explain the purpose of the closed list.

Answer 24

List of nodes you are done with.

Question 25

Explain what g represents in the A* algorithm.

Answer 25

G is the distance from a particular node to the starting node along the current path.

Question 26

What is the formula for calculating f?

Answer 26

h+g

Question 27

What do the parents in A* have in common with the visitors in the BFS?

Answer 27

Keeps track of the path.

Question 28

Why is the Manhattan method preferred over the Pythagorean Theorem to calculate h?

Answer 28

easier, cost effective

Question 29

When A* chooses the next node from the open list, what is it looking for?

Answer 29

lowest f

Question 30

BFS Pseudo-code

Answer 30

Breadth-First-Search(Graph, root): for each node n in Graph: n. distance = INFINITY n. parent = NIL create empty queue Q root.distance = 0 Q.enqueue(root) while Q is not empty: current = Q.dequeue() for each node n that is adjacent to current: if n.distance == INFINITY: n.distance = current.distance + 1 n.parent = current Q.enqueue(n)

Question 31

DFS Pseudo-code

Answer 31

``` 1 procedure DFS-iterative(G,v): 2 let S be a stack 3 S.push(v) 4 while S is not empty 5 v = S.pop() 6 if v is not labeled as discovered: 7 label v as discovered 8 for all edges from v to w in G.adjacentEdges(v) do 9 S.push(w) ```

Question 32

A* Pseudo-code

Answer 32

``` function A*(start, goal) // The set of nodes already evaluated. closedSet := {} // The set of currently discovered nodes still to be evaluated. // Initially, only the start node is known. openSet := {start} // For each node, which node it can most efficiently be reached from. // If a node can be reached from many nodes, cameFrom will eventually contain the // most efficient previous step. cameFrom := the empty map ``` ``` // For each node, the cost of getting from the start node to that node. gScore := map with default value of Infinity // The cost of going from start to start is zero. gScore[start] := 0 // For each node, the total cost of getting from the start node to the goal // by passing by that node. That value is partly known, partly heuristic. fScore := map with default value of Infinity // For the first node, that value is completely heuristic. fScore[start] := heuristic_cost_estimate(start, goal) ``` ``` while openSet is not empty current := the node in openSet having the lowest fScore[] value if current = goal return reconstruct_path(cameFrom, current) ``` openSet.Remove(current) closedSet.Add(current) for each neighbor of current if neighbor in closedSet continue // Ignore the neighbor which is already evaluated. // The distance from start to a neighbor tentative_gScore := gScore[current] + dist_between(current, neighbor) if neighbor not in openSet // Discover a new node openSet.Add(neighbor) else if tentative_gScore >= gScore[neighbor] continue // This is not a better path. ``` // This path is the best until now. Record it! cameFrom[neighbor] := current gScore[neighbor] := tentative_gScore fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal) ``` return failure ``` function reconstruct_path(cameFrom, current) total_path := [current] while current in cameFrom.Keys: current := cameFrom[current] total_path.append(current) return total_path ```