Write a program that implements the A Star algorithm using Java to find a path f

Question

Write a program that implements the A Star algorithm using Java to find a path from any two given nodes.

Problem Overview & Algorithm Description
In a fully-observable environment where there are both pathable and blocked nodes, an agent must find a good path from their starting node to the goal node. The agent must use the A* algorithm to determine its path. For this program, you must use the Manhattan method for calculating the heuristic.

Remember: your heuristic function is a representation of how good or close you are to the goal state.
Program Requirements
No graphics are required for this program. Your environment should be a 15x15 tile-based world that randomly generates nodes that are unpathable (blocks) in 10% of the nodes. This should be done each time the program compiles ensuring that there are different environment makeups each run. The program should display the generated environment when the program runs, and should allow the user to select a starting node and goal node. This can be done via text input into the console or with a GUI. Once the start and goal nodes have been defined, the program should run the A* algorithm to find a path. The path should be displayed (series of [x,y] nodes, highlighting nodes, or actually moving the agent) if one exists, or a message indicating that a path could not be found. The user should be able to continue specifying starting and goal nodes after paths have been found.

You are also to use this node class for the program:

public class Node {
  
   private int row, col, f, g, h, type;
   private Node parent;

   public Node(int r, int c, int t){
       row = r;
       col = c;
       type = t;
       parent = null;
       //type 0 is traverseable, 1 is not
   }
  
   //mutator methods to set values
   public void setF(){
       f = g + h;
   }
   public void setG(int value){
       g = value;
   }
   public void setH(int value){
       h = value;
   }
   public void setParent(Node n){
       parent = n;
   }
  
   //accessor methods to get values
   public int getF(){
       return f;
   }
   public int getG(){
       return g;
   }
   public int getH(){
       return h;
   }
   public Node getParent(){
       return parent;
   }
   public int getRow(){
       return row;
   }
   public int getCol(){
       return col;
   }
  
   public boolean equals(Object in){
       //typecast to Node
       Node n = (Node) in;
      
       return row == n.getRow() && col == n.getCol();
   }

   public String toString(){
       return "Node: " + row + "_" + col;
   }
  
}

Explanation / Answer

The code required is as follows:

import java.util.*;

public class AAlgo {
public static final int DIAG_PRICE = 14;
public static final int V_COST = 10;
  
static class PACKS{
int heuristics = 0;
int finalPrice = 0;
int uu, qq;
PACKS par;
  
PACKS(int uu, int qq){
this.uu = uu;
this.qq = qq;
}
  
@Override
public String toString(){
return "["+this.uu+", "+this.qq+"]";
}
}
  
static PACKS [][] grids = new PACKS[5][5];
  
static PriorityQueue<PACKS> op;

static boolean close[][];
static int strt1, strt2;
static int end1, end2;
  
public static void setBlocked(int uu, int qq){
grids[uu][qq] = null;
}
  
public static void setStartCell(int uu, int qq){
strt1 = uu;
strt2 = qq;
}
  
public static void setEndCell(int uu, int qq){
end1 = uu;
end2 = qq;
}
  
static void updates(PACKS curr, PACKS toa, int pric){
if(toa == null || close[toa.uu][toa.qq])return;
int t_final_cost = toa.heuristics+pric;
  
boolean inOp = op.contains(toa);
if(!inOp || t_final_cost<toa.finalPrice){
toa.finalPrice = t_final_cost;
toa.par = curr;
if(!inOp)op.add(toa);
}
}
  
public static void AAlgo(){
  
op.add(grids[strt1][strt2]);
  
PACKS curr;
  
while(true){
curr = op.poll();
if(curr==null)break;
close[curr.uu][curr.qq]=true;

if(curr.equals(grids[end1][end2])){
return;
}

PACKS toa;
if(curr.uu-1>=0){
toa = grids[curr.uu-1][curr.qq];
updates(curr, toa, curr.finalPrice+V_COST);

if(curr.qq-1>=0){
toa = grids[curr.uu-1][curr.qq-1];
updates(curr, toa, curr.finalPrice+DIAG_PRICE);
}

if(curr.qq+1<grids[0].length){
toa = grids[curr.uu-1][curr.qq+1];
updates(curr, toa, curr.finalPrice+DIAG_PRICE);
}
}

if(curr.qq-1>=0){
toa = grids[curr.uu][curr.qq-1];
updates(curr, toa, curr.finalPrice+V_COST);
}

if(curr.qq+1<grids[0].length){
toa = grids[curr.uu][curr.qq+1];
updates(curr, toa, curr.finalPrice+V_COST);
}

if(curr.uu+1<grids.length){
toa = grids[curr.uu+1][curr.qq];
updates(curr, toa, curr.finalPrice+V_COST);

if(curr.qq-1>=0){
toa = grids[curr.uu+1][curr.qq-1];
updates(curr, toa, curr.finalPrice+DIAG_PRICE);
}
  
if(curr.qq+1<grids[0].length){
toa = grids[curr.uu+1][curr.qq+1];
updates(curr, toa, curr.finalPrice+DIAG_PRICE);
}
}
}
}
  
  
public static void dryRun(int cases1, int io, int mn, int te, int lk, int opq, int eba, int[][] blocks){
System.out.println(" Test Case #"+cases1);
grids = new PACKS[io][mn];
close = new boolean[io][mn];
op = new PriorityQueue<>((Object o1, Object o2) -> {
PACKS c1 = (PACKS)o1;
PACKS c2 = (PACKS)o2;

return c1.finalPrice<c2.finalPrice?-1:
c1.finalPrice>c2.finalPrice?1:0;
});
setStartCell(te, lk);

setEndCell(opq, eba);

for(int uu=0;uu<io;++uu){
for(int qq=0;qq<mn;++qq){
grids[uu][qq] = new PACKS(uu, qq);
grids[uu][qq].heuristics = Math.abs(uu-end1)+Math.abs(qq-end2);
System.out.print(grids[uu][qq].heuristics+" ");
}
System.out.println();
}
grids[te][lk].finalPrice = 0;

  
for(int uu=0;uu<blocks.length;++uu){
setBlocked(blocks[uu][0], blocks[uu][1]);
}
  
System.out.println("Grid: ");
for(int uu=0;uu<io;++uu){
for(int qq=0;qq<mn;++qq){
if(uu==te&&qq==lk)System.out.print("SO ");
else if(uu==opq && qq==eba)System.out.print("DE ");
else if(grids[uu][qq]!=null)System.out.printf("%-3d ", 0);
else System.out.print("BL ");
}
System.out.println();
}
System.out.println();

AAlgo();
System.out.println(" Scores for cells: ");
for(int uu=0;uu<io;++uu){
for(int qq=0;qq<io;++qq){
if(grids[uu][qq]!=null)System.out.printf("%-3d ", grids[uu][qq].finalPrice);
else System.out.print("BL ");
}
System.out.println();
}
System.out.println();
  
if(close[end1][end2]){
System.out.println("Path: ");
PACKS curr = grids[end1][end2];
System.out.print(curr);
while(curr.par!=null){
System.out.print(" -> "+curr.par);
curr = curr.par;
}
System.out.println();
}else System.out.println("No possible path");
}

public static void main(String[] args) throws Exception{   
dryRun(1, 5, 5, 0, 0, 3, 2, new int[][]{{0,4},{2,2},{3,1},{3,3}});
dryRun(2, 5, 5, 0, 0, 4, 4, new int[][]{{0,4},{2,2},{3,1},{3,3}});   
dryRun(3, 7, 7, 2, 1, 5, 4, new int[][]{{4,1},{4,3},{5,3},{2,3}});
  
dryRun(1, 5, 5, 0, 0, 4, 4, new int[][]{{3,4},{3,3},{4,3}});
}
}

Please rate the answer if it helped.....Thankyou

Hope it helps....

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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