(The program should be written in Java)

Consider the problem of finding the shortest path between two points on a place that has convex polygonal obstacles as shown in the following figure. This is an idealization of the problem that a robot has to solve to navigate in a crowded environment.

Write a program to implement A* search to find the shortest path from the start point to the goal. Make sure your program generates the shortest path on any map, not just this particular one.

Details about the program:

Input: a text file containing the coordinates of start point, goal point, and vertices of all polygons. For example, an input text file map1.txt contains:

1, 3 ! (x, y) of the start point

34, 19 ! (x, y) of the goal point

0, 14; 6, 19; 9, 15; 7, 8; 1, 9 ! vertices of the 1st polygon, separating by semicolons

2, 6; 17, 6; 17, 1; 2, 1 ! vertices of the 2nd polygon, separating by semicolons