03-19

Pathfinding yayayay

idea: (we are NOT finding the most efficient path; just “a” path) )

• Recursion
  • base cases: If we are at the destination OR there are no other neighbours to go to.
• Recursive step/case
  • Keep track of a list of nodes you’ve already been to (otherwise you might search things you’ve already searched and cycle infinitely!)
  • If the node is not null (i.e. not base case) we try to find a path from the node’s unvisited neighbors
  • Note that every time the recursive step is run, it reduces the size of the graph (by adding new nodes in our “already searched” list)

Depth-first search: going as far from the start as possible, and branching from the end. That is what we implement

#define GRAPH_SIZE 64
 
int find_path(int adj_mat[GRAPH_SIZE][GRAPH_SIZE], int at, int goal, int visited[GRAPH_SIZE])
{
	if (at == goal) return 1;
	
	visited[i] = 1; // We have visited it!
	
	for (int i = 0; i < GRAPH_SIZE; i++)
	{
		if (adj_mat[at][i] != 0 && visited[i] == 0)
		{
			if (find_path(adj_mat, i, goal, visited) == 1)
			{
				printf("<-%i", i);
				return 1;
			}
		}
	}
	
	return 0;
}

The adj matrix is for 16 nodes, so the size is 16x16 where each row represents the connections to other nodes

• O(N) for the # of nodes we’re entering
• O(N) for the # of checks for each node we’ve entered So the complexity is O(N^2) (?) Because of edge-querying, adjacency linked lists will be faster cuz you dont need to look for the nodes that a node is attached to.

Breath-first-search (BFS)

• U basically start at the point, queue each neighboring node. The queue is ordered by closest to furthest nodes!
• U track the predecessors in order to actually store the path.

The DFS_FindPath code we wrote has 6 total boxes (4 for the args; 1 local var; 1 return box)

• When calling recursively, in memory, we create new “frames” or big boxes with all the same 6 boxes as in any other call.
• Reserving space for function calls takes time! Stack management takes time. So loops are usually faster.
• Creating too many frames will cause you to run out of memory and the program will be kill.

Recursion optimization!

• Problem with recursion: it uses a lot of memory! And it does a lot of work managing the call stack!
• Instead of waiting for a function to wait for another function’s result, instead we utilize “Tail Recursion Optimization”.
  • Old compilers may not recognize this optimization though.
  • For instance if u have two fncs

return func(x) + 1;

vs

return func(x)

• Then the first one doesn’t qualify for the optimization; the bottom one does!
• Can we do this optimization for all recursive functions ?
• todo He didnt say

Tutorial Time

Graphs

for adding a node, it’s nlog(N). U gotta copy the n entries of the array. So it’s log(N)