CSE 101 -- Prog 5

Due Noon, Monday, December 6th, 2021.

Late submissions will not be accepted/graded.

Objectives:

Implement Graph ADT.
Develop graph finding algorithms.

Description:

Path finding is a common issue in multiple domains, including google maps, graph theory and games. You will be exploring path finding in mazes.

You will be using an adjacency list to store edges between nodes. A maze will consist of a grid, where each vertex is adjacent to the vertices directly, above, below, to the left and to the right.

Graph ADT

The graph ADT is defined in Graph.h, and all functions from Graph.h should be implemented in Graph.c. The graph is implemented as an unweighted adjacency list, which uses an array of linked lists to store the neighbouring nodes for each node.

BFS

The search algorithm you will be implementing is breadth first search. You will be provided a start point, and a target end point. You need to find the distance of the shortest path between them. Additionally, you should report the number of left, right, up and down steps taken.

20 bonus points: A*

For bonus points, you can implement A* as a secondary path finding algorithm.
A* is a best-first, heuristic based path searching algorithm that is comonly used in games. It guarantees to find the shortest path between 2 points, given an admissable heuristic.

An admissable heuristic is one that satisfies the equation `Heuristic(node, target) <= Distance(node, target)`, where Distance(node, target) is the true minimal path distance between the node and the target. In simpler terms: the heuristic function must always be less than or equal to the true path length between 2 points to be admissable.
The heuristic you will use for this program is the Manhattan distance.
Manhatan distance is defined as: `d(x1, y1, x2, y2) = abs(x2 - x1) + abs(y2 - y1)`.

Assumptions and simplifications

All input will be valid
There will always be a path between a start node and an end node.
This is an unweighted graph, where the distance between any 2 nodes connected by an edge is 1
The coordinates passed in are in Cairo format: the origin is top left, with x values increasing to the right, and y values increasing down.
The index of the vertices and nodes will start from 0. i.e. first vertex is vertex 0.

Input

You will be provided input via stdin, with the algorithm to use being passed in through a command line argument.

Your program should be able to be executed such that: `./prog5 bfs < maze1.in` will run the program with the BFS algorithm
And: `./prog5 astar < maze1.in` will run the program with the A* algorithm

The input via stdin will consists of 3 sections:
The file will start with the line "======= Nodes ======="
List of nodes, one per line in the form: `x y`.
Line consisting of: "======= Edges ======="
List of undirected edges, one per line in the format: `node_idx_1 node_idx_2`
Line consisting of: "======= Find paths ======="
One path per line in the format: `start_node_idx end_node_idx`

Output

You will output to stdout.
For each line specifying a path to find, print a line of the following format:
`number_explored path_length left_steps right_steps up_steps down_steps`

Where number_explored is the total number of nodes that were explored using the pathfinding algorithm,
path_length is the total length of the path,
left_steps is the number of left neighours followed,
right_steps is the number of right neighbors followed,
up_steps is the number of up neighbors followed,
down_steps is the number of down neighbors followed.

The grid is defined using the same method as Cairo uses, with the origin being in the top left corner, with x increasing to the right and y increasing down. Therefore, up_steps will be the number of times the neighbour node had a smaller y value.

Example input/output

For the following maze, the input and output files are listed below.

                                                              
           ################################                   
           #e.................e...........#                   
           ##############################.#                   
      #####       #.......#     ######  #.##        #####     
      #s..#########.......#######....# ##..#        #...#     
      #...#......##..................###...#####    #...#     
      #...#....................................######...#     
      #...#......######.................................#     
      #.......................s.......e.............#...#     
      #...................s..................#......#...#     
      #################...###########...................#     
                      #...#         ######...#......#####     
                      #####              #...########         
                                         #####

Input: input2.in
Output for BFS: output2.bfs.out
Output for A*: output2.a_star.out

Files for this program:

Makefile: Provided.
List.h: Provided. Header file for List ADT.
List.c: Provided. Implementation of List ADT.
PQueue.h: Provided. Header file for aPriority queue ADT.
PQueue.c: Provided. Implementation of a min heap based Priority Queue ADT.
Dictionary.h: Provided. Header file for Dictionary ADT.
Dictionary.c: Provided. Implementation of Dictionary ADT.
prog5.c: Where you will need to write the code to read input, implement path finding algorithms and write output.
Graph.h: Do not change this file. It has function headers that you need to implement.
Graph.c: This is where you implement the functions for graph operations.

Resources

Here is a blog post going over graph search algorithms: https://www.redblobgames.com/pathfinding/a-star/introduction.html
Here is a good interactive visualisation of A* and BFS https://qiao.github.io/PathFinding.js/visual/
Video explaining A* search: https://www.youtube.com/watch?v=6TsL96NAZCo&ab_channel=JohnLevine
Wikipedia link: https://en.wikipedia.org/wiki/A*_search_algorithm
Sample unit and program tests can be found at the link: exampleTests/

Grading:

Rubric:

You start off with 100 points.

- 40 points for passsing Unit tests on Graph ADT
- 40 points for passing Program tests
- 20 points for code style and commenting
- 20 bonus points for passing A* program tests
You lose credit for missing functionality, incorrect results,
poorly documented or formatted code, or not following instructions.

Below is a partial list:

- up to 10 points off for inadequate comments or hard-to-read code
- up to 10 points off for not following instructions
- up to 10 points off for special handling to grade your homework (usually
  because you did not check that it runs on the computers in the lab first).

Make sure you:
a.  include the Makefile, .c files, and .h files
b.  generate an executable file called prog5 with your Makefile
c.  have confirmed that it compiles and runs properly on unix.ic.ucsc.edu
d.  followed the general instructions described in overview.html
e.  submit early and often with:
    submit cse101-ap.f21 prog5 prog5.zip

Who graded your assignment based on your CRUZID first letter :
```
??: ??
??: ??
```