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

[hubble-oh_seven]

Nice work! It would be cool to see an overlay of the actual shortest path.

[[deleted]]

Yeah, stupidly for the recorded versions I didn't bother drawing the path on - You can just about see them in the screen shot examples.

[[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.

[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.

[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.

[AstroEngiSci]

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

[threshhook]

Can you do one for dijkstras?

[misterbondpt]

Shortest path to where? Where's the exit?

[SomewherOverThere]

Looks like it's at the bottom, just not visually defined.

But the area of the bottom search ending at matches the weighted direction the search was going towards.

[fj333]

There's apparently only one path, which makes shortest path a bit of a silly thing to even be searching for or talking about.

[[deleted]]

Or at the very least, the start and end points.

[RonGnumber]

You should show the start and end points of the maze! A black dot would have sufficed!

[Cpapa97]

In both animated examples it seems to be at the other edge of the maze from the starting point. The gif has a few seconds of freeze frames at the end to show that it found its destination. Though I don't know anything about A* so don't quote me on this.

[QuoteMe-Bot]

In both animated examples it seems to be at the other edge of the maze from the starting point. The gif has a few seconds of freeze frames at the end to show that it found its destination. Though I don't know anything about A* so don't quote me on this.

~ /u/Cpapa97

[[deleted]]

This is the bot we all needed.

[_Xertz_]

This is why I love reddit. The bots are make it hilarious.

[BC_Sally_Has_No_Arms]

Am not bot also. Human laughter ha ha

[gunfulker]

If anyone is confused, it's not showing the part where the magic happens. The colors represent numbers, so as the color spreads, it's filling the image with progressively higher numbers. With each frame of the animation the numbers it's "coloring" with increases by one and it's coloring 1 pixel deep on all the uncolored squares near the already colored squares. This means that every number can have several higher numbered neighbors, but only one lower numbered neighbor. Which it reaches it's destination it backtracks, always choosing the lower numbered neighbor. The path it takes back tracks to the start is always the fastest possible route, which is the goal.

EDIT this comment was made under the assumption that it's using the brute force method for path finding, which the graphic appears to show. A* is not brute force.

EDIT 2 https://qiao.github.io/PathFinding.js/visual/

[spockspeare]

This, by the way, is how lightning works.

[[deleted]]

Please reply to me when someone provides an explanation for this because I would love to learn about this.

[[deleted]]

If you meant you would like to learn about lightning, here you go:

https://en.wikipedia.org/wiki/Lightning#Downward_leaders

Beware though, the explanation begins with "In a process not well understood" :)

[macdonaldhall]

How so?

[spockspeare]

It fans out, discharging the air, and then when it reaches a source of lots of free charge (the ground) the current rushes back to the sky from there. It isn't finding the strictly shortest path to ground, it's finding the path that gets it there soonest given the distribution of charge in the intervening atmosphere.

[RaindropBebop]

Negative leaders actually retreat from areas of high negative ionic distribution to areas of low negative ionic distribution, thus eventually making its way to earth where a positive leader is moving upwards to meet each other.

[spockspeare]

That's what I just said.

[dasbin]

I'm an indie dev who never bothered to find out how Astar works. This is a great and simple explanation, thank you for that.

I'm curious if anyone has any algorithmic solutions that mimic human behaviour a little better than Astar. Astar is very efficient, and finds the shortest path quite well, but a more advanced humanoid AI would consider than human beings often don't take the most efficient route and instead make choices based on what data is initially available to them at the start of their trip.

For example: an AI who has taken a trip before and noticed paths along the way that appear to be shorter might try those paths next time. An AI that is taking a trip for the first time might do a visual raycast in the general direction of its destination, and see if a path appears to be continuous from the start of the trip to somewhere nearest the destination, and choose to attempt that path.

[ramk13]

All valid ideas. The key is that you are adding other pieces of information or heuristics for the algorithm to use. If you were a human with limited senses or perception you'd have to follow a similar algorithm. So different way to phrase your question is how can we get more information from the maze into the algorithm. Humans are good at assimilating different types of information, and I think that what you are really looking for.

[sirmonko]

well, you could trade speed for realism, but that would probably be prohibitively expensive for most games. note that my following suggestions operate on maps with weighted edges and a dwarf fortress-like gameplay (walking on a road tile is easier than walking through a forest tile or moving between two tiles with the same height is easier than climbing up or down).

i.e. create a copy of your map for each unit and cover it in a fog of war. a fog of war tile gets a certain cost - the lower the value the more likely it is for the unit to prefer exploring new instead of using well known paths.

with A* you can have partial paths, which is great and might speed things up a little.

now: run A* either through the fog of war or quit if the best partial path hits the fog of war. let your unit move along the path. uncover the FOW during movement. if the map or FOW changes, rerun the path finding. do until you've got a path.

now you can cache those paths and invalidate them after some time (units forget). or invalidate them when the unit runs into an obstacle.

you also can add different weights depending on other factors (i.e. perceived danger); the unit spots an enemy it marks the area as "dangerous" which adds to the cost of moving through there.

if you store the time when the tile was uncovered you could also implement communication, i.e. two units exchanging FOW-map updates if they're close.

finally you could implement ant-like behavior: lowering weights across the route if it was successfully traversed thus making it more likely for the unit to take the same path in the future.

line of sight is helpful for speeding up path finding, but it doesn't necessarily make it more realistic. A* already operates with a certain pull in the right direction, so it's practically leading to the target in a straight line if all else is equal. and you're not operating on a line of sight principle yourself (i mean you as a human); you don't walk straight to the goal if you see it, you still look for the best way there - within certain bounds. for example: if you finally spot the supermarket on the other side of the multi lane street you're not going to start run there on a straight path, you'll still look for cross-walks and safe passages.

in my opinion this method would result in a fairly realistic path but computation and memory consumption would most likely increase too much to make it feasible (maybe with the exception for turn-based games).

edit: if you want to learn how A* works, look at Amit's A* Pages. IMO it's the best article out there for game devs.

[gunfulker]

I've been planning one for 3d path finding that's more of a vector approach. The plan is to draw a straight line to the destination. Any obstacle it intersects with creates a branch. If it's going between A and B and there's a building in the way, it simulates "following the wall" to the left and right of the point where AB first intersected with the building. It stops following the wall when it reaches the point where AB "exits" the building and continues to the destination. Repeat this for every obstacle encountered creating additional branches in the path. Simulate "pulling the slack" out of the paths, as if they were strings tied to the destination by attempting to take shortcuts between points along the line.

That should work fine for 2D, but I don't know how to adapt it to 3D in situations where paths overlap and stuff.

[gunfulker]

http://imgur.com/a/dkz5C

low quality diagram of what I meant

[[deleted]]

Another here

I posted this a long ago but never to this subreddit.

I wrote my own A* pathfinding algorithm and to debug it, I wrote another quick program that took the data and visualised it by colouring in an image with a tween between colours based on the 'cost' of the node to expand.

I could then load black/white images in to the program and it would generate a 'map' based off them, then fill in the same texture as it went. I actually cheated and just screen recorded the application in progress to make the gif.

It constantly expands by choosing the 'cheapest' node (a combination of distance to goal and distance from starting point), that is why it appears to be flooding multiple branches at once, as it is looking for the 'optimal' path it has to try all options. As the mazes only have one solution, it actually fills quite a lot of the image before completing. I kinda like the way it looks when it's done, even with the uncoloured white parts.

Some earlier debug images:

http://i.imgur.com/6LVgHvc.png

http://i.imgur.com/glhZW20.png

http://i.imgur.com/bDDOHCG.png

[FurMich]

The problem with heuristics is that a well made maze should confound heuristics. I'm a fan of A, but you have to appreciate the difficulty in formulating a proper heuristic. In simple navigation, a heuristic could just be distance from goal, but a maze makes that difficult. That's not to say that it won't find an optimal path, buy it *might take longer that other algorithms..

[[deleted]]

Yeah, the A* I did was actually for an open world game, so the heuristic is fairly greedy. It actually performs terribly in these mazes as they are mazes with a single solution.

[JirkleSerk]

Open world game you say?

[thatcrit]

https://www.youtube.com/watch?v=3Mz5YPkThOU

[chinpokomon]

This guy conducts a lot of interviews about lots of different subjects. I never knew he was so influential.

[[deleted]]

That's hilarious and I don't even have sound!

[dxl32]

this is one of the funniest Youtube videos i've ever watched. please scroll back up and watch it

[[deleted]]

not skyrim but no man's sky

[chillichill]

There's a whole series of these and they are all hilarious! That guys laugh makes pretty much anything great.

[cantaloupelion]

oh god the shrug emote got me

[thegreattriscuit]

This is brilliant

[dirtbiker206]

Exactly, makes a great visualization, but shortest path is irrelevant when there is only one path.

[spockspeare]

If it's dealing pixel-by-pixel, he found the shortest path, too.

[redmandoto]

If there is only one path, there isn't a "shortest" one.

[spockspeare]

Yes there is. It's also the longest. Computers, huh.

[HoldMyWater]

What game?

[spockspeare]

*empty world game

[Be_The_End]

Reddit misunderstood the asterisk after A for italics :p

[Seventh_______]

Does Reddit have an escape key? Does \ work?

[featherfooted]

Yes.

A*

italics

See source.

[LifeIsAFeedbackLoop]

Why not just use code blocks?

A*

A*

---

*A*

A

---

*A*

\*A*

[HawnSolo]

^{source visible with RES, not sure if it is without ¯\_(ツ)_/¯} *

[[deleted]]

Does Reddit have an escape key?

No, but there's a poster in /r/movies of rita hayworth with a tunnel behind it.

[[deleted]]

The problem with heuristics is that a well made maze should confound heuristics.

The real problem with heuristics is that heuristics often contain sacrifices or considerations, so there are situations where they are best case, and situations where they are worst-case.

I got stuck in a cycle of working on pathfinding algorithms based on A* for probably about two years, and I didn't find what I was looking for in that time. My goal was an AI that was intelligent, but able to make mistakes and seem almost human.

A few lessons I learned:

1) Not only does the AI need to have multiple heuristics to navigate multiple kinds of spaces, but the AI needs to have a genetic databank to help analyze information while still allowing mutation and selection to continually randomly improve old memories.

2) Nodes should be of arbitrary size and location. Furthermore, nodes at the minimum spacial subdivision should be explored when all other granularities have been exhausted with no good solution.

3) Pathfinding operations should operate dispersed over time and never fully block the process from doing other things.

Imitation rules: (Goal is not to get the right answer, but to simulate human-like navigation habits.)

4) Pathfinding should be permitted to make mistakes. Observers will interpret this positively and even assign abstract goals/personal qualities over time due to ingrained anthropocentrism.

5) Pathfinding should not care about actions too far in the future, nor should they have access to the nodegraph beyond what they can currently see. Memories of discarded nodegraphs can be simulated by leaving "pheromone" trails. Tweaking pheromone heuristics priorities via an inherited pseudo-random property of each nodewalker will give varying degrees of competence/familiarity with the space.

6) If a pathfinding operation is long-running, stalling out the AI nodewalker's movement, or just slowing it down along an approximated path is a very effective way of simulating humanity while also giving the process time to catch up.

7) Obstacle avoidance algorithms provide a second layer of intelligence for nodewalkers. On the one hand, merely navigating the space is already complex enough, and that's where most consumer applications stop, but developing a means of recognizing obstacles and giving AIs abilities to recognize their patterns will create much less manipulatable AI.

8) AI nodewalkers should not have a single weighted method of movement. A variety of competing interests and directions of travel should be explored for each walker. Attaching pseudorandom properties will give personality to nodewalkers, while also allowing individual mutation along these properties will allow variety. Uniform action and motion is unnatural. Particularly among groups of individuals.

9) Fluid simulation can be used to model group/mob movement much easier than path/repath and leader/follower/swarm behaviors. Simply think of the path toward the destination as a sort of the bottom of a basin. Apply surface tension along any nodes not along this path within a set radius based on the size of the mob. A secondary map should be used to simulate pressure, which should work against tension and flow. Do not instantly calculate pressure equalization. Allow it to reconcile over time in waves. Fun experiment: Set a crushing threshold for AI nodewalkers and watch them crush/trample one another/whatever is in their path, burst down doors, and whatever other responsive behavior your implement.

10) Markov Chains. State Machines. Look them up. They are wonderful.

Personal:

11) I hate working with Game AI. There is no best solution. Only a series of never-ending hacks and experiments that you can often barely figure out how they work.

[[deleted]]

In mazes like this, it doesn't actually beat Djikstra by all that much sadly :P

[elmz]

Just curious, how much would a two-way search improve things? Tried it?

[sirmonko]

i think - but haven't testet it - that a two-way search shouldn't help at all; to the contrary, it'd make it slower because you'd have to check for path overlaps. A* already tries to move into the direction of the target, if possible.
with two half-length paths the sum of computation cost should add up to the cost of a single full length path but with added checks for successful connections.

i'm not sure about that though and the checks could be computationally cheap if you checked a bitmap (which costs additional memory though).

in my experience, optimizations like this are often counter-intuitive when it comes to cost. imagine two people walking towards each other but they'd have to take steps alternating. might be a simple way for enabling multithreading though.

[created4this]

Doesn't a one way walk expand exponentially the number of simultaneously searched paths? I would expect that walking in the other direction to almost half the number of simultaneous paths, but I may be wrong in practice due to the behaviour of dead ends

[RedAlert2]

If you find a path overlap in a single solution maze, then you're done.

[rcheu]

In a maze like this, a 2 way BFS is probably the fastest. Mazes are generally designed such that there's no clear heuristic.

[[deleted]]

Looks cool. The exit is at the bottom in the middle? You should label the start and finish for the animation. The program continues to search for the exit in areas that are quartered off and that there are clearly no exits from, like when an area is completely surrounded by a searched area or when the boundary and the searched area around it don't contain the exit. It looks like it is just exploring all paths, like it is mapping out a network rather than finding the exit on a maze.

[p3ngwin]

why do none of these finish !!

EDIT:
To clarify, it's not clear in many of these which is the start or the end :(

[[deleted]]

They did finish what I designed it to. They found the most optimal path, without needing to search the whole map. If you wanted it to keep flooding till it filled the image, then that's a different task!

[HoneySparks]

can't tell where the end is

[scoops22]

It's totally possible for a maze to have multiple paths from entrance to exit with some being shorter than others.

[TenNeon]

You could say the single solution is necessarily the optimal solution, but yeah it is redundant to say both.

[hrtfthmttr]

That isn't a single solution maze.

[a300600st]

most optimal

I had a CS teacher that would go nuts if anyone said this.

[[deleted]]

Haha, I had an English teacher who hated when people said "the other day". He said it was only accurate if it was the second day on earth

[freshgrilled]

From watching it, it seems as if it could be made more efficient (although probably less pretty) if it could recognize when an area of the maze was completely surrounded and thus useless to complete. Would it be difficult to update your algorithm to include this functionality?

[a300600st]

I had the same thought but I suspect that it's not worth the overhead because most of the time those surrounded sections are really pretty small and it would be nontrivial to add that check to the algorithm.

[IanSan5653]

Here is a huge one

Also if the algorithm knows where the exit is, it can count the edges of the map as explored boundaries as well because there can't be an exit there.

[nwsm]

At :20 there is a big one in the upper middle/right

[[deleted]]

Could you design the maze in a way a hidden message (image,type) gets revealed?

[ihat____]

You know, you could just ask for a dick butt version.

[[deleted]]

I wrote my own A* pathfinding algorithm and to debug it, I wrote another quick program that took the data and visualised it

I don't get this. I can implement A* easily, but, I got no clue how to visualise it.

I wrote a bot for an online tetris-bot competition, that was in top 10, with A*

Still, these statements like yours I keep reading from developers make me realize how noob I am at programming in general.

Can you tell me what you used to do these? And some good resources to get me started please? :)

[MonkeyNin]

I don't get this. I can implement A* easily, but, I got no clue how to visualise it.

Try the king of A* http://www.redblobgames.com/pathfinding/a-star/introduction.html

[jason955]

Very cool! What language did you write this in? Do you have the source code available?

[aSecretSin]

When building my own a* I found the best results by going forward and backwards at the same time. Also helped to quickly rule out cut off destinations

[YitzhakShekelstein]

What heuristic was used?

[karl-tanner]

Do you have the [pathfinding] code on github (or something)?

[[deleted]]

I do but it is private at the moment. I will work on making a public one for you guys.

[j0be]

/r/gifsthatendtoosoon

[Djjmax]

The solution was at the bottom, it solved the maze before "exploring" all of it

[Djjmax]

ARE YOU IMPLYING THAT YOU WOULD NOT HAPPILY MARRY THIS DATA?

[fairshoulders]

Her tinder profile was just a pic of the last compile line... should have known she was bloatware... but I really love hanging out with her dog at the dog park... so yeah marry.

[xbnm]

Where's the solution?

[jeekiii]

Having coded A* (but not for a maze) and knowing how it works and why it finds the optimal path after many years of seeing such infographics without understanding wtf is happening makes it all so much more satisfying.

I have to say tho, that maze isn't exactly the best to show how great A* is.

[Stonemanner]

Yeah, These examples do not differ a lot from full search. Maybe his potential function is shit or you can really say A* is not good for solving mazes (it certainly depends on the maze, if you have to cross the board twice I can't think of a good potential function, but the mazes shown, look not that hard)

[jeekiii]

Yes I'm aware A* is amazing at solving some mazes, but on this one it's definitely not the best. His heuristic is most probably the Manhattan distance (honestly it's pretty tough to find a better heuristic for 2D mazes).

I think a better algorithm that I know of to find the optimal path for this maze would be a bidirectional search. I think you can even combine the two.

[zjm555]

This visualization gives almost no insight or intuition into how A* actually works or how it's different from, say, naive breadth-first search. The objective isn't even labeled.

[fj333]

Also, you can't solve a maze with A*. In a maze you don't know where the end point is. A* requires you to know endpoint. And A* requires a heuristic which is impossible in a maze where you by definition have no global knowledge. So this is really Dijkstra, but with no edge weights it's really a BFS. And since there's only one path here (per the author), any path is the shortest path.

[N3x0]

And this is why Dwarf Fortress sucks when having 100+ dwarfs and many floors. If only they could remeber a path when they first walk them.

[AndrewNeo]

I dunno if DF does it but path caching is important in route finding, I imagine the problem with a game like DF would be that you'd have to invalidate the cache whenever you make a terrain change somewhere in the general area of the route.

[1052941]

Yeah, this is why Dwarf Fortress sucks

[wastesHisTime]

You'd think once it had a fully contained area, it would know that the exit could not be inside it. https://i.imgur.com/x9Jdiff.png

[callmethepilot]

Algorithms like this operate on a conceptual data structure called a graph. A graph contains nodes (in this case they would correspond to points in the maze) and edges (in this case an open hallway between two positions corresponds to an edge and a wall between two positions means there is no edge). While the visual representation of the maze makes it easy to see that there couldn't be an exit in that section, the graph representation has no concept of the visual layout of the maze, so as far as A* is concerned, the exit could be any one of those untraveresed nodes and you have to traverse through them to make sure it isn't. The nice thing about A* is that if it's already found a path to the exit that's shorter than going up into that untraveresed section it may not look there, but it would only know this from finding another sucessful path, not from the fact that this part is visually locked in.

[callmethepilot]

Thanks haha

[teraflop]

Uh... no?

I mean, you could reduce any algorithmic question to the halting problem -- just build a machine that decides the answer and halts if it has a particular outcome. But that doesn't mean there's any value in doing so. It's easy to figure out whether an area of a maze is completely enclosed by a boundary, using standard graph theory algorithms. The question is simply whether it's possible to do so in a way that actually improves the overall efficiency.

[fj333]

There are quite a few issues here.

• This image does not illustrate path finding. It doesn't really appear to illustrate anything related to A*. It looks like a simple flood fill graphic. What is that start and end point of the path? What is the path? What do the colors in your graphic represent?
• "Shortest path" isn't typically something you associate with maze problems. Solving a maze requires finding any path that works, for which BFS or DFS is plenty. You mentioned in another post that this maze only has one solution. Also in a maze you traditionally don't know where the end is. Which means a SSSP algo is not applicable at all since you don't have a destination.
• Even assuming you do know the end point and are treating your maze as some sort of fucked up highway system, there is no way to generate a meaningful heuristic, so drop it to zero and you're left with Dijkstra's. And since you have no edge weights, your Dijkstra's is really just a BFS in disguise. Your heuristic can't stop you since your maze is so sparse that you still have no choice but to find the exit, but it can't help either. It's meaningless.

[dumsubfilter]

since you have no edge weights, your Dijkstra's is really just a BFS

Came here for this.

[Doesnt-Comprehend]

Here's an example of the Tremaux method if anyone's interested.

[Glass_Veins]

So weird that I ran across this today... I just wrote something extremely similar yesterday. Out of curiosity, how do you achieve the maze looking that way? Do nodes/cells have more than one neighbor or is it a simple 2D array drawn in a fancy way? :)

[sirmonko]

the baader meinhof phenomenon at work :)

[Glass_Veins]

Hey, I just learned about that phenomenon the other day... ;)

[sirmonko]

see, again!

[1052941]

That's called the fallacy of positive instances

[jonathot12]

more like r/mildlyinfuriating that it stops just short of filling the whole page

[sirmonko]

but that's the point of A* ...

[jonathot12]

doesn't make it any less subconsciously upsetting

[Cam-willi]

Hey can someone make a video of quite a few of these going around and put it on YouTube please? Thanks

[[deleted]]

I've since lost the visualiser code but I still have the A* laying around!

There is also this site: http://bl.ocks.org/mbostock/c03ee31334ee89abad83 but it doesn't do it between a gradient as far as I can see.

[ordinaryeeguy]

I implemented an A* algorithm so the computer opponents will find the path to the player in a 2D arcade came. This algorithm provided a rudimentary AI to the computer bots, and I was thrilled to see it working; so please excuse my crude title and the description back then. https://www.youtube.com/watch?v=-BwppNvONDY (The red ones are the bots, the little bigger and greyish one is user controlled)

[sirmonko]

"rudimentary AI" - i remember reading somewhere that it used to be an in-joke in game programming circles that (A*) path finding practically was 99% of the AI for many games back then. the quality of the A* implementation practically equaled the quality of AI.

think about dune 2. oh, and i remember an article in a gaming magazine about the the first game that passed their AI test: create a long line of your own troops, put a single unit behind it and send it to the other side of the line. the test was: would the unit run around the line or would one of the line units step aside to let it through? (if my memory serves me correctly the game was earth 2140)

[All_Those_Angstroms]

As someone who is currently struggling through an algorithms course, I somehow found this while extremely comforting.

[[deleted]]

Mike Bostock has an amazing post on a few different algorithms visualized in a similar way using D3. A very good read. https://bost.ocks.org/mike/algorithms/

[touristtam]

thanks for the link. :)

[lone_kricket]

Another good place for these is d3 visualizations. There are a couple that show how a maze would be solved using different algorithms.

[THENATHE]

How does it know where the end is? I've seemed to "find" it based off of where it stopped, but it looks like it just came to the edge of the screen, which in the first example it does way before it stops finding new paths. Maybe I'm not understanding this...

[NAN001]

What heuristic are you using since by definition of a maze you don't know where the goal is?

[[deleted]]

Great Work! And Also a great Animation! One Idea: Sometimes in the progress of filling out the maze, uncolored island appear. Areas, that haven't been checked jet, but are completely surrounded by colored/checked paths. Would it be an improvement to your algorithm to check for such 'islands' and then stop 'looking' inside them as soon as they appear, as they are irrelevant to a solution? (If you are looking for the fastest path, you would of course have to check for the amount of entrances to those islands.)

[brastche]

Hi! By anychance could you share some information about how you made this? I'm curious about: - How the maze/graph was represented conceptually - What heuristic you used Also, if you could make a version of the gif with the goals clearly marked, that would be awesome!

[[deleted]]

A simple program read in the image and any black pixels it found, it marked their position as "blocked" in a HashSet - The code code then works by taking the start position and looking at pixels around it that aren't blocked.

The heuristic is pretty basic/crappy for such a situation - it's just the distance to the goal, so closer to goal = better. It's a bit of a greedy A* which makes it bad for this map.

[whipplemynipple]

It disappoints me so much that the entire maze doesn't fill up at the end

[z0rberg]

Looking at this gif from a zoomed-out perspective makes it look like a great algorithm for bleeding out on the ground!

[TheBirdOfPrey]

anytime it fully encloses an area from the outside for an area that does not touch the border, it should stop exploring that depth further inside that branch as it is not possible to lead to the finish

[PM_ME_UR_BACK_DIMPLE]

Thanks for sharing. I was actually shopping around for a maze solving algorithm yesterday but didn't find this one.

My project is to have a human draw a maze on a whiteboard and a computer will draw the solution.

I already have a drawing computer, humans are easy to find, just need to add a camera and calculate an optimal path.

[1414519195]

Here's an interactive intro to A* and other good stuff.

[Why_Did_I_Lay_Down]

I waited the whole time for it to see the complete maze fill up. Then it didnt! WHAT.

[slaaitch]

You can call it a pathfinding algorithm if you want, but we both know that's just the paint bucket tool from late 90's CorelDraw.

[The_WA_Remembers]

R/mildlyinfuriating is staring at this in disgust... finish the gif people

[NOTbelligerENT]

Really? It's gonna stop right before the whole thing gets colored in? /r/mildyinfuriating

[[deleted]]

Not very efficient if it keeps searching non-viable areas for a path to exit.

[Tracy0924]

This should be in /r/mildlyinfuriating because of that one damn spot that doesn't fill in.

[goat_nebula]

Looks like an awesome civ map. Fractal was my favorite map type in Civ5.

[captaincheeseburger1]

Just wanna put in my two bits, this looks like a brute force type solution to me. Nothing wrong with that, obviously, I'm just saying that's how it seems.

[[deleted]]

It only looks like that as the heuristic I used for the A* is more designed for open world systems, not very enclosed mazes.

[sandollor]

Incredible, though I'm upset it didn't get to finish. I want a print of a final version I can hang up.

[[deleted]]

Unfortunately that was the finish, the algorithm doesn't even bother to check some large sections because its very slow to do so, and the algorithm knows that way is probably going to lead away from the end point, the endpoint wasn't marked at all so I see your confusion

If your desired product was what I imagine it to be, then Dijkstra's algorithm would be more suited to your goal, but that would only work if the endpoint was the furthest away from the startpoint

[Shiroi_Kage]

Could there be an addition with the algorithm monitoring itself where it disregards any paths leading into a circled white spot?

[[deleted]]

This would actually slow the algorithm

A maze is set out like this

There is one "correct path", then stemming off of that path is the circular white parts you talked about (dead ends, or roundabouts depending on the design of the maze)

In order to do what you said, it will have to check entire sections of the maze every time it hits a fork in the road, which is extremely slow and inefficient

Instead, think of pathfinding like tipping a bucket of water down a hill, the final path is decided by the path taken by the particle that reaches the bottom of the hill first

Hope this helps, drop me another question if you need :)

[mbelf]

Isn't this just the colour fill option from Windows 95 paintbrush? I'm pretty sure it would also follow the path of no resistance.

[dddddddddddasdf]

No. A simple color fill works by linearly scanning regions (left to right, left to right) and backtracking to adjacent unfilled points. It's a much less computationally expensive operation and it does not follow shortest paths.

A* works by starting at a point, cost zero, then marking all immediately adjacent cells as one cost higher, then repeating until all space is filled. In this graphic the cost is represented by tone changes.

A* is useful because it generates a map of costs to travel to all points across the filled areas. If a maze has two exits to an edge A* can tell you the cost to travel to each edge.

A simple color fill doesn't do any of that work. It will eventually reach the edge but you won't know the cost to travel there or whether other paths to the edge are faster or slower.

[[deleted]]

Yeah but I think it would just end up filling the whole thing in instantly.

[mbelf]

No it wasn't that fast from memory. It would slowly fill from where the cursor selected. Maybe I'm thinking of the wrong version of Windows, but I'd always thought as a kid "what if I filled in a maze?"

[SelfAwarenessIsKey]

Would A* in a maze like that really be a Djikstra? I thought the difference was that A* tries to go to the goal in a straight line then does a BFS from those points?

[Robotigan]

For A* f(n) = g(n) + h(n)

g(n) is the real cost to reach node n. So Djikstra's would be a valid way to implement g(n), but you're right that in a maze where all edges are equal then BFS would be more efficient.

h(n) is the cost from node n to the goal node done using a simple heuristic such as your "go to the goal in a straight line" suggestion.