Path Finding Algorithm (A* and Dijkstra's)

This Blog is about a project which I did in JANUARY 2021. I created a path finding algorithm simulator using JavaFX. It helps to get a visual representation of two path finding algorithms which are A* and Dijkstra's Path finding Algorithm. I used JavaFX because it is one of the fastest growing technologies in java and it is replacing java swing .JavaFX is much more powerful then java swing and  it has some amazing features like we can apply CSS in JavaFX.

The reason why I choose  to A* and Dijkstra's Path Finding Algorithm from a Pool of Algorithm because they help us to  get a basic knowledge of Path finding in Graph. These two are also really great for comparison  with each other and they are also quite famous.

Working

so let me tell you how this application works. You can download the project by clicking here and then  configure it  in your favorite java IDE .  Now if you have configured the project which I don't think so, then press the run button in your IDE. when the application starts this is what you will get to see.

Now to create the maze  press the "Create Maze". This will create a maze for you.This is what it looks after you press the button.

I know it does not looks like a actual maze but the fact is we can draw a Actual maze by using certain Algorithms and making slight changes in the project. One of the Algorithm which can help you to draw an actual maze is Backtracking  Algorithm and the reason why I didn't  Implemented it is because I am lazy 😅.

Now if you are not satisfied with the maze you got then you can make changes in it by selecting "Wall" from Tile type and put your own walls in the grid by clicking a cell or you can delete a wall by selecting "clear " from Tile Type and click on the wall which you want to remove and if you are free enough then you can also draw your own maze from scratch with this two options.

Now if you are satisfied with your maze then you can select the start and end of the path. Remember there can be only one start and one end for a path. once you select the start and end of your path then your maze may look like this.

Now we have got the maze ,start point and end point and now it's time to select an algorithm. You have got two options i.e. A* and Dijkstra's. I know you will try both of the Algorithms but my suggestion is to go with Dijkstra's first. Once you select your Algorithm then press the "RUN" button. Once you press the run button the application will execute and find a path from starting point to the end point.

Now for my case I ran Dijkstra's first and I got this path.

and for A*  I got this.

after the algorithm executes you can see the statistics where you can see Total Tiles, Tiles Visited, Path Found, Path Cost, Time of execution, etc.

The Brown tiles are the tiles considered while finding the path. The Dark Cyan represents the path and the Red and Green tile represents the Start and End.

In the A* algorithm to find HCost and GCost I have used "Manhattan Distance".

HCost: The Estimated movement Cost to move  from that given square on the grid to the final destination

GCost: The movement cost to move from the starting point to a given square on the grid ,following the path generated to get there.

Now here I am not going to explain you about A* and Dijkstra's algorithm because there are already many good articles present but I will just give you a basic idea of both of them.

Dijkstra's Algorithm:-

It finds the distance of every reachable node from the start node irrespective of the fact that if it is the designation node or not.

to study this in detail click here

A* Algorithm:-

It knows from Beginning of the execution  that where the destination node lies and hence tries to find the shortest path to reach the designation node.

 to study this in detail click here.

Now this is not a YouTube channel so I can't ask to like and subscribe but if you have any doubt about the project then feel free to drop a comment and if possible mail me the query. If you like this Blog then feel free to share it .

Thank You for Reading😀.