(The program should be written in Java) Consider the problem of finding the shor

Question

(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

Explanation / Answer

import java.util.ArrayList;

import java.util.Stack;

import java.awt.Point;

import java.util.Vector;

import java.util.PriorityQueue;

class EmptyQueueException extends RuntimeException

{

public EmptyQueueException(){ } } class Queue extends Vector { public Object enqueue (Object element) { addElement (element); return element; } public Object dequeue () { int len = size(); if (len == 0) throw new EmptyQueueException(); Object obj = elementAt(0); removeElementAt (0); return obj; } public boolean empty() { return isEmpty(); } public Object peek() { int len = size(); if (len == 0) throw new EmptyQueueException(); return lastElement(); } public int search(Object o) { return indexOf(o); } } class Coordinate implements Comparable { private Point position; private Point goal = new Point(164,79); private Coordinate predecessor; public Coordinate(int x, int y) { position = new Point(x,y); predecessor = null; } public Coordinate getPredecessor() { return predecessor; } public void setPredecessor(Coordinate pre) { predecessor = pre; } public boolean equals(Object obj) { Coordinate cord = (Coordinate) obj; return position.equals(cord.position); } public String toString() { String string = ""; string = String.format("[%d, %d]", position.x, position.y); return string; } public boolean isGoal() { return (position.equals(goal)); } public int distFromGoal() { int distance = 0; distance += Math.sqrt(Math.pow(goal.x - position.x, 2)+Math.pow(goal.y - position.y,2)); return distance; } public int compareTo(Object o) { double dist1 = distFromGoal(); Coordinate compCoordinate = (Coordinate)o; double dist2 = compCoordinate.distFromGoal(); if (dist1 > dist2) return 1; else if (dist1 < dist2) return -1; return 0; } }

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.