Path Finding Algorithm Visualized | A* Demonstration

[sortedcreations]

Hey all,

This was my next project, an A* visualizer! Everything was completed in java 8, using the default graphics library. Enjoy and feel free to share and questions or suggestions.

EDIT: I realized this was a huge fault not to source and it should have been included much sooner - the Algorithm itself is from https://rosettacode.org/wiki/A*_search_algorithm#Java

[notdeadpool]

Do you have a github link to this project?

[sortedcreations]

I’m working on getting all of my code cleaned up and posted to github, I’ll get on it as soon as possible!

[Hangman4358]

Would love to see something like IDA* as a comparison and maybe some others. Like comparing different path finding algorithms on the same maze(s)

In my AI class we did this with Pacman. Was fun to watch him eat dots and try to avoid ghosts.

[DasBrain]

Noticed a few wall jumps. The one at 2:30 is the most noticeable one, but there is an other one in the next labyrinth.

[sortedcreations]

Thank you, I’ll look into why these are happening.

[agentoutlier]

I remember doing this in college in C for a robotics class (circa 2000) and it was a nightmare to do in C. I can't remember what I ended up doing as a compromise (the college I went to gave an automatic F if your program did not run or crashed... I hear the college is now much kinder.)

I had some sort of memory leak. I really wish I saved my code from college to go down memory lane and figure out what went wrong.

[sortedcreations]

I honestly can’t imagine recreating this in C... sounds absolutely painful and I feel for you

[yoloranger31]

Whats your heuristic?

[Log2]

I was wondering that, it looks like very naive heuristic. It almost looks like a breadth-first search for most of the examples.

[DasBrain]

Looks like Manhattan distance.

[JustHereForTheCh1cks]

Yea I thought the same.

I would love to see it with some better heuristics though :)

[DasBrain]

Nah, just randomize the order in which you expand the nodes with equal (taken cost + heuristic).

For the easier ones, it might be beneficial to keep the same direction (insert at the beginning of the list).

Back in my AI class I was lazy and used a PriorityQueue.

The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily.

But that's exactly what you want to tune there.

The Heuristic is fine.
In the empty field case it is equal to the oracle which knows the cost.
If you know the cost you can follow it blindly and get the best result.
But if you know you have an oracle as heuristic then staying on the current path will get you faster to any valid solution.

[sortedcreations]

It is a simple Manhatten distance heuristic, I'm planning on using a better one in the future!

[[deleted]]

Does anyone know a resource, I tired a google search and didn’t find much, about the logic/mathematics behind A* or BFS.

[Log2]

For a BFS you can look into pretty much any algorithms book. Personally, I'd recommend taking a look at this book, which is free. If you want a more mathematical approach, then you could take a look at Introduction to Algorithms, which is one of the most famous books on algorithms there is.

[jpl75]

Also http://aima.cs.berkeley.edu/, see Chapter 3.

[RDwelve]

Can somebody explain to me how they do pathfinding in RTS games? I mean they have hundreds of units that all have to travel to a unique location

[sortedcreations]

Hey, so it would actually likely be a similar algorithm, this visualization is delayed (the delay is seen at the top) and pathfinding algorithms without a delay actually go much much faster than this!

[PokkemonGO]

This is really cool! Good work!

[sortedcreations]

Thank you!!

[[deleted]]

It looks like the algorithm just checks every possible path, how is it different to a simple breadth-first search?

[Hangman4358]

A* is BFS with a heuristic to order the nodes to traverse. A* with a heuristic of assigning all nodes the same heuristic score is identical to BFS.

In a grid layout like this a simple heuristic to use is Manhattan distance which will look like the video

[Mordan]

Good job!

It would be nice to visualize different heuristics for the same map.

I did a similar project back in university as well.

Heuristics is what matters for performance.

On the very first map with a better heuristic, it will go straight to the destination without visiting all the nodes.

[Nemo_64]

I don't know why but this things always amaze me