This program is a simulation that navigates through an NxN grid using straight lines and right angle rotations (i.e., moving up, down, left, or right). The goal of the simulation is to find a path between a starting point (A) and the goal (B), whilst avoiding any obstacles (X).
There are four test files included, namely test1.csv, test2.csv, test3.csv and test4.csv. Each has a different NxN grid, with different start points, goals and obstacles. To run the program, compile it first using “javac Robot.java”. Then, run the program using “java Robot [file.csv]”, where [file.csv] is the test file with a sample NxN grid. There is also a script provided (script.sh) that runs the program with all four sample inputs. To run this script, simply use the command “sh script.sh”.
To find the optimal path between the starting point and the goal, A* search is used. With this approach, the heuristic cost and the exact cost of the path from the starting point to the current point are examined to determine the best solution path.
There are two main data structures maintained with this program. The first is a priority queue with all the paths to be examined, where the priority of each path is based on the heuristic cost plus the exact cost of the path’s terminating point. The second is a HashMap of points and their associated minimum distance to the end goal, which is used to terminate the expansions of suboptimal paths. Initially, the path containing just the starting point is placed into the queue. At each iteration of the loop, the path at the head of the priority queue is removed and expanded. If the cost to reach this path’s terminating point is greater than what was previously known (checked from the HashMap), the neighboring points of the path’s terminating point are not examined since this would not return an optimal path. Otherwise, each neighboring point is converted to a path and is added to the queue to be expanded at a later iteration. If the path dequeued from the priority queue happens to reach the end goal, the solution is complete, and the path can be outlined by tracing the parent references of each point until the starting point is reached. If the queue has no remaining paths, it can be assumed that there is no solution at all.
The Path class holds a reference to the point, and its parent path. It also defines the exact cost associated from the starting point to the current point. Since each point is uniform, the cost of moving from one point to another is just 1. It also contains the heuristic cost for the point. Since the only valid movements are up, down, left, and right, the heuristic distance function is simply the manhattan distance from the current point to the end goal.
The worst case time and space complexity of this approach is O(4^n). This is because 4 points are examined at every extension of the path. Assuming the grid has n points, the worst case would be to examine 4^n points. The space complexity is the same since in the worst case, we add a path for every point we examine to the priority queue.