Write Java program that implements the A* algorithm to find a path from any two

Question

Write Java program that implements the A* algorithm to find a path from any two given nodes. Problem Overview & Algorithm Description The 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. Your environment should be a 15x15 tile-based world that randomly generates nodes that are unpathable (blocks) in This should be done each time the program compiles ensuring that there are different environment makeups each run. 10% of the nodes The program should display the generated environment when the program runs The Program should allow the user to select a starting node and goal node Once the start and goal nodes have been defined, the program should run the A* algorithm to find a path In a fully-observable environment where there are both pathable and blocked nodes, 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.

Explanation / Answer

The pseudocode for the A* Algorithm to find the path from any two given nodes:

// Java program to check if there is exist a path between two vertices
// of a graph.
import java.io.*;
import java.util.*;
import java.util.LinkedList;

// This class represents a directed graph using adjacency list
// representation
class Graph
{
private int V; // No. of vertices
private LinkedList<Integer> adj[]; //Adjacency List

//Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}

//Function to add an edge into the graph
void addEdge(int v,int w) { adj[v].add(w); }

//prints BFS traversal from a given source s
Boolean isReachable(int s, int d)
{
LinkedList<Integer>temp;

// Mark all the vertices as not visited(By default set
// as false)
boolean visited[] = new boolean[V];

// Create a queue for BFS
LinkedList<Integer> queue = new LinkedList<Integer>();

// Mark the current node as visited and enqueue it
visited[s]=true;
queue.add(s);

// 'i' will be used to get all adjacent vertices of a vertex
Iterator<Integer> i;
while (queue.size()!=0)
{
// Dequeue a vertex from queue and print it
s = queue.poll();

int n;
i = adj[s].listIterator();

// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it
// visited and enqueue it
while (i.hasNext())
{
n = i.next();

// If this adjacent node is the destination node,
// then return true
if (n==d)
return true;

// Else, continue to do BFS
if (!visited[n])
{
visited[n] = true;
queue.add(n);
}
}
}

// If BFS is complete without visited d
return false;
}

// Driver method
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

int u = 1;
int v = 3;
if (g.isReachable(u, v))
System.out.println("There is a path from " + u +" to " + v);
else
System.out.println("There is no path from " + u +" to " + v);;

u = 3;
v = 1;
if (g.isReachable(u, v))
System.out.println("There is a path from " + u +" to " + v);
else
System.out.println("There is no path from " + u +" to " + v);;
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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