Write a program in Java or C# that implements the A* algorithm to find a path fr
ID: 3860790 • Letter: W
Question
Write a program in Java or C# that implements the A* algorithm 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 but using them will help you with debugging and problem solving. 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.
The rubric below will be used in the grading of your program. Partial points may be awarded for each category.
Category
Value
Program is free of syntax and runtime errors
/ 10
Program uses A* and successfully finds a solution
/ 40
Program displays “no path could be found” if one does not exist
/ 10
Program generates and displays a 15x15 tile-based environment
/ 10
Blocks (unpathable tiles) are randomly placed in 10% of the node (not hard coded)
/ 5
User is able to specify and start and goal node
/ 10
The solution (path) is properly displayed
/ 10
Program utilizes an appropriate heuristic (Manhattan method)
/ 5
Program shows the agent moving along the path from start to goal
/5 (bonus)
Total Points
/ 100
Category
Value
Program is free of syntax and runtime errors
/ 10
Program uses A* and successfully finds a solution
/ 40
Program displays “no path could be found” if one does not exist
/ 10
Program generates and displays a 15x15 tile-based environment
/ 10
Blocks (unpathable tiles) are randomly placed in 10% of the node (not hard coded)
/ 5
User is able to specify and start and goal node
/ 10
The solution (path) is properly displayed
/ 10
Program utilizes an appropriate heuristic (Manhattan method)
/ 5
Program shows the agent moving along the path from start to goal
/5 (bonus)
Total Points
/ 100
Explanation / Answer
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class Path_Between_Nodes
{
private Map<String, LinkedHashSet<String>> map = new HashMap();
public void addEdge(String node1, String node2)
{
LinkedHashSet<String> adjacent = map.get(node1);
if (adjacent == null)
{
adjacent = new LinkedHashSet();
map.put(node1, adjacent);
}
adjacent.add(node2);
}
public void addTwoWayVertex(String node1, String node2)
{
addEdge(node1, node2);
addEdge(node2, node1);
}
public boolean isConnected(String node1, String node2)
{
Set adjacent = map.get(node1);
if (adjacent == null)
{
return false;
}
return adjacent.contains(node2);
}
public LinkedList<String> adjacentNodes(String last)
{
LinkedHashSet<String> adjacent = map.get(last);
if (adjacent == null)
{
return new LinkedList();
}
return new LinkedList<String>(adjacent);
}
private static String START;
private static String END;
private static boolean flag;
public static void main(String[] args)
{
Path_Between_Nodes graph = new Path_Between_Nodes();
graph.addEdge("A", "C");
graph.addEdge("B", "A");
graph.addEdge("B", "D");
graph.addEdge("B", "E");
graph.addEdge("B", "F");
graph.addEdge("C", "A");
graph.addEdge("C", "E");
graph.addEdge("C", "F");
graph.addEdge("D", "B");
graph.addEdge("E", "C");
graph.addEdge("E", "F");
graph.addEdge("F", "C");
graph.addEdge("F", "E");
LinkedList<String> visited = new LinkedList();
System.out.println("Enter the source node:");
Scanner sc = new Scanner(System.in);
START = sc.next();
System.out.println("Enter the destination node:");
END = sc.next();
visited.add(START);
new Path_Between_Nodes().breadthFirst(graph, visited);
sc.close();
}
private void breadthFirst(Path_Between_Nodes graph,
LinkedList<String> visited)
{
LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
for (String node : nodes)
{
if (visited.contains(node))
{
continue;
}
if (node.equals(END))
{
visited.add(node);
printPath(visited);
flag = true;
visited.removeLast();
break;
}
}
for (String node : nodes)
{
if (visited.contains(node) || node.equals(END))
{
continue;
}
visited.addLast(node);
breadthFirst(graph, visited);
visited.removeLast();
}
if (flag == false)
{
System.out.println("No path Exists between " + START + " and "
+ END);
flag = true;
}
}
private void printPath(LinkedList<String> visited)
{
if (flag == false)
System.out.println("Yes there exists a path between " + START
+ " and " + END);
for (String node : visited)
{
System.out.print(node);
System.out.print(" ");
}
System.out.println();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.