Visualization of A* Algorithm - Final Version

Actually, I finished this project nearly a month ago but since I'm so lazy lately, I can write a post and put the program here at this moment. You can find more information about this project here my previous blog post.

Since then, all of the improvements were about GUI, adding load maze property and fixing bugs. As a GUI, I added radio button set which is used to replace starting and destination nodes and put obstacles.

After making some tests on the map, I encountered a problem. Since the algorithm can spread on every direction, the scenarios like in the image can create unwanted situations. Technically speaking, this is caused by diagonal search of neighbor nodes.

To avoid that, I added a radio button which enables and disables diagonal movement. Here is the new result of the same scenario. In this case, neighbor search is done only horizontal and vertical directions.

Other than these, I wanted to add an extra property which is loading maze to the map. With it, users can choose predefined mazes according to their difficulties. These are easy maze, medium maze, hard maze and dead-end maze. To do this, I used the idea of tile maps. I created txt files which includes numbers which are 0, 1, 2 and 3. Each of the numbers has its own node type. 0's are the normal nodes, 1 is the starting node, 2 is the destination node and 3's are the obstacle nodes.

0 0 0 0 0 0 0 0 0 0 0 0

 1 0 0 0 0 3 0 0 0 0 0 0 

0 0 0 0 0 3 0 0 0 0 0 0

0 0 0 0 0 3 0 0 0 0 2 0

0 0 0 0 0 3 0 0 0 0 0 0

This is an example of a txt file that includes nodes' information.

On the Java side, I'm going through all numbers in the file with two for loops and prepare the new state of the nodes according to the number that is read from the file.

In the class that I made this project for, as a difference, our professor wanted us to write software design document before starting project. Also at the end of the project, we wrote unit tests and user manual. I have to admit that I really didn't like writing these documents. Also, writing tests for the code that I wrote didn't sound meaningful to me. Maybe the idea for writing tests for others' code would be more meaningful. But, in a very limited time that couldn't be possible.

And of course images of the program:

You can download the executable jar here. Loading maze is not working in this version. Because it is using another folder which has maze files.

Before finishing the post I would like to share the links that gave me idea about how I should set up the GUI and choose colors.
http://www.ccg.leeds.ac.uk/people/j.macgill/xaStar/
http://www.youtube.com/watch?v=FNRfSQDF7TA

Visualization of A* Algorithm - A Java Project

As I mentioned in the last post this semester I'm doing a Java project which is Visualization of A* Algorithm. Because of the exams, I couldn't spare time to improve it. I did some in this weekend. I redesigned the class structure because a class was doing things that it shouldn't do. I added one more class and it is more object-oriented right now.

When I did the first version - before the improvements above - I showed it to my professor. He wanted me to add the spreading of the algorithm in every step. In this way, we are able to see how the algorithm works. To do this, I had to sleep the algorithm for awhile in every step. And I added sleep into the function which finds the path. But it didn't work as I expected. Because GUI slept, too. After a little search, I found that I had to make thread programming to fix that problem. My program was executing in a single thread, when I sleep a function, GUI was sleeping, too. The thing that I have to do was dividing the program into two pieces, first is the piece that shows the GUI elements and the second is the piece that does calculations for algorithm.

I know a little bit of thread programming from my Operating Systems course. We also did a lab to learn better. We were using C, you can find the code for that here. In Java, thread programming was easier than I thought. After doing that, program was working correctly.

Now, I have to study to understand algorithm better. I am little bit confused because of heuristic part of algorithm. The heuristic is directly affecting the algorithm, choosing the right heuristic is the main issue of A*.

Here is some images from the project;

Initial position of starting and destination nodes. Later, users will be able to change their positions.

Spreading of algorithm. Light gray nodes are in closedList. Dark blue nodes are in openList. Calculating g value of neighbors is like this:

currentNode.g + 10 for horizontal and vertical neighbors

currentNode.g + 14 for diagonal neighbors
And Manhattan heuristic is used.

When I finish this project, I'm planning to open the source code. I will probably share the codes on Github.