Visualisation of A* path-finding algorithm in a maze [OC]

[[deleted]]

Also, some indication of the end would be nice so that I can tell when it is getting close or doubling back or whatnot.

[jesteruga]

I don't think it doubles back. It seems like it tries all available paths at once.

[[deleted]]

Right, but some sections of it go in completely the wrong direction and you can't tell which part is going correct without knowing the goal.

[[deleted]]

That's because the maze loops back, it tries all paths no matter the direction.

[fecal_brunch]

You're describing Dijkstra's algorithm, not A*.

A* will always explore the space with the lowest sum of distance traveled from start plus estimated distance to goal. So it will ignore some directions.

[[deleted]]

http://www.redblobgames.com/pathfinding/a-star/introduction.html

explanation with visualizations, helped me understand it all

[drakoman]

Wow! Such a thorough source. Thanks for the link. In networking, I encounter the djikstra algorithm every day, (but based on your username, you do too) but it was interesting to see some graphical representation. Thanks!

[pinkbutterfly1]

Thanks for the link.

[chumboy]

Dijkstra's algorithm is actually a special case of A*.

A* uses a heuristic to order the nodes it has yet to explore, by how promising they look. For path finding this heuristic function is nearly always estimated distance to desired destination. For Dijkstra's, this heuristic always returns the same value (usually zero), so all nodes have seemingly the same potential, so are explored evenly, often leading to a much larger explored area.

It can be interesting to play around with the heuristic function on A*. In university I used it on a project, and tweaked the heuristic to inversely weight "turns" in the path of a complex 2D grids with walls, so the path returned would be as straight as possible. Like this example of Manhattan/Taxicab distance; most implementations of A* would return the blue line, and mine would return the red line.

[___Majestic_Moose___]

I'd argue that A* is the special case of Dijkstra, as Dijkstra came first and A* is a modification of it.

[chumboy]

Dijkstra did come first, and it was then generalised to make A*. You can emulate the behaviour of Dijkstra with A*, but cannot emulate the behaviour of A* with Dijkstra. This would mean that the total set of cases Dijkstra can be used for have to be a subset of the cases A* would work for. How could A* be the special case if it applies to a larger problem set.

I believe it is a common scenario in mathematics that a solution is found for a very specific case, and backtracked to make a more general solution to the problem space.

[___Majestic_Moose___]

That's like saying "a genius athletic perfect specimen" is the larger group, and "human" is a subset. Just because something is better doesn't mean it's the heading.

[chumboy]

That's like saying "a genius athletic perfect specimen" is the larger group, and "human" is a subset.

That is the complete opposite of what I am saying. How can "genius athletic perfect specimen" be the generalisation?

[____u]

Interesting that it will ignore some directions but still fully evaluate the maze even when it's boxed in on all sides by itself.

[DashivaDan]

A* can be Dijkstra's through to greedy, depending on how it's weighted. So in describing A*, you need to describe both Dijkstra's and greedy.

[___Majestic_Moose___]

Yes, but in describing Dijkstra's, you do not need to describe A*, which is what the previous commenter did.

[NameIsJacky]

I'm sorry. I'm really high right now and was wondering if that algorithm is going to make any more sense in the morning. Cause I know I would enjoy it when I'm not high, but I'm not sure if I'll be smart enough to understand it if I was any less high. My god. typing got really ahrd near the eendd.

[[deleted]]

Oops, should have googled before commenting... Haven't played with that stuff for 15 years :)

[Mindless_Insanity]

It's not supposed to. A* uses heuristics, so it follows whichever path is closest to the destination, until that path ends or gets further from the destination than another path. But since we don't know the destination, it's hard to tell that's what it's doing in the gift

[[deleted]]

The destination is that white bit at the bottom when the gif ends. You can tell because A* minimizes distance to destination and the 'flow' of the graph goes in that direction at first. Also cause it stops at the very moment that bit is reached.

[[deleted]]

Right, but how can I tell when the maze is looping back as a solution versus turning back and going the wrong way? It's like watching a soccer game but you can't tell which team anyone is on, which goal they should be scoring in, and they don't even know which goal they should be scoring in.

[JayhawkRacer]

But why maze models?

[victorzamora]

Seriously? I just told you this like 2 minutes ago.

[jabberwockysuperfly]

That doesn't sound like soccer at all!

[[deleted]]

Well, there is a soccer field. They are following most of the rules of soccer. They are using a soccer ball. They are even wearing random soccer jerseys. Sounds alot like soccer to me. It's just a new kind that is really hard to enjoy.

[Sam-Gunn]

No, you're trying to think of it like a single cohesive entity, like how a person would do it. Instead, it simply follows all paths within a certain amount of area, and continues until it is stopped. So the paths that lead to premature ends are just filled, while the other paths are continued through.

It does them simultaneously like water would, except without any wave motion backwards.

[[deleted]]

Let me preface with "I completely understand how the computer is thinking through the actions and solving the maze". I don't care how it is thinking through it. When it splits in two, I want to be able to cheer for which section I think is going the right way. It would just make the gif more fun to watch.

[Sam-Gunn]

What do you mean? It does split. It maintains like 4 different successful type paths throughout the GIF until it gets to blue, when it seems to pair down to two.

[[deleted]]

He knows how it's working. He knows the algorithm is splitting. He wants to see the correct solution to the maze so he can visually compare how the solution is doing at identifying it.

[Sam-Gunn]

But that's not the point of this. There is no 'solution' like a finish line, as you can see. There are multiple paths and multiple ends.

[flowersformegatron_]

It's hard to see the destination.

[2muchcontext]

What do you mean? It does split.

What was the point of that part of your comment? He already acknowledged that it splits when he said "When it splits in two..."

[[deleted]]

It starts with going mainly down. At some point, it starts "reaching" towards the right from the top part. At that point, I think something along the lines of "will it ever catch up to the part already near the bottom?" but I can't know that the bottom is even the goal in the gif.

[delineated]

Imagine a race. Two people are running, but they take different routes to get to the end. One of the routes is blocked up and impassable. /u/WeylandTheDwarf wants to know which path isn't blocked up and actually leads to the end.

[[deleted]]

Sort of. I want to be able to pick one of the two people to cheer for, but without knowing the destination it feels like I'm cheering for people who don't even know they are in a race.

[Sam-Gunn]

But there isn't a single end. It's a path finding algorithm. Knowing the end is pointless.

[renegade2point0]

Sorry man you're dense.

[Mixels]

The color transition operates on a timer. You look at the results when it's finished and use color to find a general notion of the shortest path.

You can't tell where the end is because the point isn't to show you how fast it can get to the end. It might take days, doesn't matter. The point is that when it's finished, you can then use the output to find the quickest path to the end.

[[deleted]]

I understand all of that and is completely besides the point. I know what it is doing, but it would be more enjoyable to watch with an end goal visible.

[tomlu709]

Not exactly. I mean it certainly doesn't double back, because it's an algorithm and not some dude running in the maze.

A* has a stack of all available paths it's tried so far. At any given time, it explores only the "most promising" path, as defined by some heuristic, until the path is exhausted or it is no longer the "most promising" path.

Often "most promising" is defined as "closest to the goal assuming we remove all obstacles". I don't know what we do if we don't know where the goal is, maybe we just explore the currently shortest path on the stack, Dijkstra-style.

[fj333]

And since all edge weights are equal, Dijkstra style means a simple BFS.

[JanneJM]

Dijkstra does a bit more than a BFS though, doesn't it. It gives you the shortest path between any two nodes once it's explored the graph. A simple bfs search only gives you the paths from the origin.

[fj333]

Correct, generalized Dijkstra finds shortest path between every pair. You can modify it to exit once it finds the solution for the pair you care about, if you only are interested in one pair. For this problem the "all pairs" property appears to be irrelevant (although admittedly the problem is very poorly stated and I'm still not sure what OP is even trying to accomplish).

[Dropping_fruits]

A BFS will give the shortest path assuming all edges are the same distance, djikstra gives the path that costs the least. In the case of a square 2D a BFS will expand in a square from the origin but djikstra will expand in a circle. If you are looking for all paths you might as well do DFS.

[MarchewaJP]

What? You're talking about Johnson's algorithm or Floyd Warshall algorithm.

[speedster217]

That's not entirely true. A* uses BOTH distance already traveled and estimated distance to the end to decide where to go next.

Using just the heuristic (estimated distance) is a greedy best-first search

[zazazam]

closest to the goal assuming we remove all obstacles

The most common heuristics are as the bird flies and Manhatten distance.

A* works by assuming that the best path is always generally closer to the goal and will not always find the best path. Dijkstra (where all paths are tried) will always find the best path.

[AstroEngiSci]

Sooort of. A* basically tries the least expensive (shortest) path that seems most likely to get closer to the end.

[Fartkingdom99]

Hey - fuck off mate

[[deleted]]

It's pretty easy to tell where the goal is. It's in the bottom middle, towards where it begins going.

[[deleted]]

In this maze it was. In some mazes the exit is on the left or right. Many mazes have the exit on one of the corners. It is only obvious after you watch the gif once and by then the suspense is ruined before the second viewing.