(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

• Make sure your program can be compiled using the following command: javac aixxx.java

• Your program will be tested on osprey as follows: java aixxx input_map_file.txt input_map_file: a text file similar to map1.txt

• Output: a sequence of coordinates showing the shortest path from the start point to the goal point.

Explanation / Answer

import java.util.*;

public class aixxx {
public static final int DIAGONAL_COST = 14;
public static final int V_H_COST = 10;
  
static class Cell{
int heuristicCost = 0; //Heuristic cost
int finalCost = 0; //G+H
int i, j;
Cell parent;
  
Cell(int i, int j){
this.i = i;
this.j = j;
}
  
@Override
public String toString(){
return "["+this.i+", "+this.j+"]";
}
}
  
//Blocked cells are just null Cell values in grid
static Cell [][] grid = new Cell[5][5];
  
static PriorityQueue<Cell> open;

static boolean closed[][];
static int startI, startJ;
static int endI, endJ;
  
public static void setBlocked(int i, int j){
grid[i][j] = null;
}
  
public static void setStartCell(int i, int j){
startI = i;
startJ = j;
}
  
public static void setEndCell(int i, int j){
endI = i;
endJ = j;
}
  
static void checkAndUpdateCost(Cell current, Cell t, int cost){
if(t == null || closed[t.i][t.j])return;
int t_final_cost = t.heuristicCost+cost;
  
boolean inOpen = open.contains(t);
if(!inOpen || t_final_cost<t.finalCost){
t.finalCost = t_final_cost;
t.parent = current;
if(!inOpen)open.add(t);
}
}
  
public static void AStar(){
  
//add the start location to open list.
open.add(grid[startI][startJ]);
  
Cell current;
  
while(true){
current = open.poll();
if(current==null)break;
closed[current.i][current.j]=true;

if(current.equals(grid[endI][endJ])){
return;
}

Cell t;
if(current.i-1>=0){
t = grid[current.i-1][current.j];
checkAndUpdateCost(current, t, current.finalCost+V_H_COST);

if(current.j-1>=0){
t = grid[current.i-1][current.j-1];
checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST);
}

if(current.j+1<grid[0].length){
t = grid[current.i-1][current.j+1];
checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST);
}
}

if(current.j-1>=0){
t = grid[current.i][current.j-1];
checkAndUpdateCost(current, t, current.finalCost+V_H_COST);
}

if(current.j+1<grid[0].length){
t = grid[current.i][current.j+1];
checkAndUpdateCost(current, t, current.finalCost+V_H_COST);
}

if(current.i+1<grid.length){
t = grid[current.i+1][current.j];
checkAndUpdateCost(current, t, current.finalCost+V_H_COST);

if(current.j-1>=0){
t = grid[current.i+1][current.j-1];
checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST);
}
  
if(current.j+1<grid[0].length){
t = grid[current.i+1][current.j+1];
checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST);
}
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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