HW3: Path Finding Algorithm

Elements Implemented:

A* search algorithm
Two implementation options for connecting start node and goal node to the existing graph
- Include start node and goal node in the node network before drawing graph (in this particular assignment, no graph re-draw is required)
  - This enables a global optimal path search from start to goal
  - In a general path finding simulation when existing graph is large and adding start and goal requires graph redraw, this approach may be time costly
- Find connections between start/goal nodes and existing graph
  - Connections are ranked based on path length + distance to goal
Modify HW3_Test code with following functionalities:
- Handle empty path set and plot direct path between start and goal
- Real time switch between A* algorithm and BFS algorithm
- Real time switch between the two implementation options
- Show algorithm and option and path length on window title

key == '1': AStar

key == '2': BFS

key == '3': op1

key == '4': op2

key == 'r': reset system with different obstacles

left mouse click: set goal position where mouse is (red)

right mouse click: set start position where mouse is (blue)

I compared the new A* search method to the given BFS method. I also compared the two aforementioned planPath implementations.

A* search method with option 1 gives the best performance
For A* search method, option 1 performs better than option 2 with all my test cases.
With the same option, A* finds better path in all my test cases than BFS
BFS can fail to find path in some cases, when a valid path exists
- Due to limited time and it is out of the scope of this assignment (BFS is a provided base algorithm), I will not investigate failure mode at this time.
BFS with option 1 fails to find path more often than BFS with option 2. This is likely due to having more edges in the search graph (causing BFS to fail).
Option 1 costs less time in this particular assignment than Option 2.