My first step into Artificial Intelligence. The A* algorithm finds the shortest path from a point to another using a heuristic (you could say a "guess"), which estimates the distance from a node to the goal using a particular path in order to prioritize the nodes that are most likely to be on the shortest path, therefore reducing memory cost and complexity. The heuristic used here is a diagonal heuristic, which simply estimates the distance to the goal by the number of nodes separating it from the goal in a straight line through walls, also allowing diagonal moving. This heuristic is a very common one because it is simple to program and works well enough if you don't have so many nodes.
The blue tile shows the starting point, the red tiles are the path, the grey tiles are the area which has been searched and the black ones are the tiles through which we don't allow the path to go through also called "walls".
Just start by placing your starting point, then add the walls and press start when you want to place the goal. Enjoy the beautiful optimal path you get, push Clear and start all over again.
Interesting project, I would recommend it to any practicing Java programmer.
Written in : March 2007
Link for the application : Here
Skills used : GUI making, Structure handling, A* algorithm implementation.
Note : All my programs are applications, not applets. Post a comment or contact me if you're interested in a source code.
No comments:
Post a Comment