Write a java program that implements the A* algorithm to find a path from any tw

Question

Write a java program that implements the A* algorithm to find a path from any two given nodes.

Must meet this criteria:

Program is free of syntax and runtime errors

Program uses A* and successfully finds a solution

Program displays “no path could be found” if one does not exist

Program generates and displays a 15x15 tile-based environment

Blocks (unpathable tiles) are randomly placed in 10% of the node (not hard coded)

User is able to specify and start and goal node

The solution (path) is properly displayed

Program utilizes an appropriate heuristic (Manhattan method)

Program shows the agent moving along the path from start to goal

Program is free of syntax and runtime errors

Program uses A* and successfully finds a solution

Program displays “no path could be found” if one does not exist

Program generates and displays a 15x15 tile-based environment

Blocks (unpathable tiles) are randomly placed in 10% of the node (not hard coded)

User is able to specify and start and goal node

The solution (path) is properly displayed

Program utilizes an appropriate heuristic (Manhattan method)

Program shows the agent moving along the path from start to goal

Explanation / Answer

Answer: here is the code for A* algorithm to find he shortest path.

output :

Test Case #1
Grid:
SO 0 0 0 BL
0 0 0 0 0   
0 0 BL 0 0   
0 BL DE BL 0   
0 0 0 0 0   


Scores for cells:
0 14 27 41 BL
14 17 29 42 56
27 29 BL 45 59
39 BL 43 BL 0   
52 55 0 0 0   

Path:
[3, 2] -> [2, 1] -> [1, 1] -> [0, 0]


Test Case #2
Grid:
SO 0 0 0 BL
0 0 0 0 0   
0 0 BL 0 0   
0 BL 0 BL 0   
0 0 0 0 DE


Scores for cells:
0 17 33 48 BL
17 20 35 49 62
33 35 BL 52 64
48 BL 52 BL 67
62 65 64 67 77

Path:
[4, 4] -> [3, 4] -> [2, 3] -> [1, 2] -> [1, 1] -> [0, 0]


Test Case #3
Grid:
0 0 0 0 0 0 0   
0 0 0 0 0 0 0   
0 SO 0 BL 0 0 0   
0 0 0 0 0 0 0   
0 BL 0 BL 0 0 0   
0 0 0 BL DE 0 0   
0 0 0 0 0 0 0   


Scores for cells:
40 35 37 40 53 68 0   
22 17 20 34 48 63 0   
17 0 15 BL 48 61 75
20 15 18 31 43 56 70
34 BL 31 BL 46 58 73
48 48 43 BL 56 61 0   
63 61 56 59 0 0 0   

Path:
[5, 4] -> [4, 4] -> [3, 3] -> [3, 2] -> [2, 1]


Test Case #1
Grid:
SO 0 0 0 0   
0 0 0 0 0   
0 0 0 0 0   
0 0 0 BL BL
0 0 0 BL DE


Scores for cells:
0 17 33 48 62
17 20 35 49 62
33 35 38 51 63
48 49 51 BL BL
62 62 63 BL 0   

No possible path

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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