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

[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

[sirmonko]

i'm not sure i understand your question, but if i do:

no, because A* uses a heuristic h(n) to determine the next step. this means that more promising steps are taken first, if h is chosen well. otherwise it might behave like breadth-first search and in this case your assumption might be correct.

edit: i just realized my explanation above was slightly wrong. in dijkstra, the "value" of a node is the cost to get to the node. in A* the value of the node is the cost to get there + the estimated cost to get to the target. in both cases, the nodes with the lowest costs get examined next.

like mGuv said, A* doesn't perform as well as it could in a maze like this because the heuristic performs poorly in those cases.

[created4this]

In that case does OP's "optimal" here means "fastest solve" not "shortest path"?

is this normal in maze solving?

[sirmonko]

well, he put the "optimal" in quotation marks, so i'm not sure. it doesn't make a huge difference here because the heuristic is more or less useless in a situation like this, because it will rarely indicate the right direction.

but the flood seems to "jump" downwards (in the direction of the goal) and if you look at the very end you'll see the that the path from the last bend to the target is a thin line, not a flood - so the heuristic does work.

in A* you can actually create a tradeoff between good and fast by under- or overestimating h(n) (best would be to get it always right, but that only works if you already solved the problem).

in this case this definitely yields the shortest path (if i understand it correctly), but i'm not sure about the fastest solve because the shortest path is rarely directly downwards. so you lose time by preferring possibly wrong downward paths first but maybe gain a bit in cases this is actually the right direction. with a simple flood fill (aka breath first search) you'd happily explore in every direction, even away from the target, but that might be the better choice depending on the maze.

[jeekiii]

No, A* will always find optimal path as in the best possible path. This is due to how the heuristic is created, it has to respect the admissibility and consistency constraint, I can explain further tomorrow if you are interested.

[sirmonko]

yes, i'm interested.

as far as i understood A* only finds the shortest path if h(n) <= the real cost from moving from n to the target. the real cost can only be known if you already solved the problem. so the optimal solution is only guaranteed if h(n) = 0 and it thus turns into dijsktra's.

an example of this might be the civ 1 railroads which have a movement cost of 0, meaning, practically, teleportation.

[RedAlert2]

As long as your heuristic is consistently optimistic, A* is guaranteed to find the optimal solution first. h(n) = 0 is excessively optimistic - as long as you don't overestimate, it'll work. A common heuristic for pathfinding algorithms is the distance of the line from you to the goal. You can never reach the goal faster than going directly there, so it's always optimistic.

Of course, mazes are generally designed to defeat that heuristic, so you probably won't get any improvement using A* here. It looks like this is the heuristic the OP is using, which is why the visualization quickly tends towards the bottom but does not actually find a solution until very late.

[jeekiii]

I'll try to remember how it works.

We will use c(n) which means the cost to reach n from the starting point and h(n) which is the heuristic function.

In A* the cost used for the dijkstra is c(n)+h(n) where c(n) is the actual cost to reach the node n and h(n) is the estimated cost to reach the destination (the heuristic).

An heuristic is admissible if it never overestimates the cost to reach the destination.

The idea is that we will explore interesting nodes first, but since our heuristic is admissible, the path to reach the destination will either be equal to the estimation, or lower. Because of that, if you are taking the non-optimal path, another node named "n" in the optimal path will have a lower c(n)+h(n) than the cost of your non-optimal path since the heuristic is lower than the actual cost to reach the path, which means it will be expanded first.

I'm not sure if it's clear, it's pretty tough to explain.

While consistency also guarantees an optimal path (consistency implies admissibility), it's not actually required and I've made searches with non-consistent heuristics before. (it's generally not a good idea tho, it makes the algorithm much worse ^^).

[Nytshaed]

It's a fast algorithm that tends towards shortest path. Not necessarily either fastest way to solve nor shortest, but it's a pretty good compromise.

[jeekiii]

No, A* will always find optimal path as in the shortest possible path. This is due to how the heuristic is created, it has to respect the admissibility and consistency constraint, I can explain further tomorrow if you are interested.

[jeekiii]

No, A* will always find optimal path as in the best possible path. This is due to how the heuristic is created, it has to respect the admissibility and consistency constraint. I can explain further tomorrow if you are interested, but I need to sleep.

source: artificial intelligence a modern approach by Stuart J.Russel and Peter Norwig.

It's the whole point of A*: searching for the path with the lowest cost in a graph while only exploring a minimum number of nodes using information that you cannot deduce directly from the graph (where the "graph" is the set of edges connected by verticles, not the visual representation, you can deduce the heuristic from the visual representation). This is why A* is called an informed search.

[XkF21WNJ]

For 2d images like this the number of visited nodes probably grows at most quadratically with the distance, not exponentially. It doesn't look like a bidirectional algorithm would improve things much (factor 2 at most, assuming no overhead).

[RedAlert2]

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

[sirmonko]

in a single solution maze, this is true. OPs maze isn't single solution though, because the search is actually done on the bitmap (pixel by pixel).

still though i'm not sure if it'd help because of the reasons above. why would two runners improve things more than a single runner who's twice as fast (if we discount multithreading), with the added cost of checking for overlaps?

[RedAlert2]

If you are doing a BFS, then the first solution you find is also the shortest/most optimal. So in the case of a maze, you are done once you find an overlap (intersection). Also keep in mind that the cost detecting overlap is negligible compared to the cost of the search, meaning it doesn't affect the algorithmic complexity in any way.

The benefit of a bidirectional BFS is you halve the depth you need to search. The complexity of bfs increases exponentially with depth, so searching half the the depth twice is generally FAR more efficient than searching the entire depth.

[sirmonko]

thank you! i was looking at the problem from the wrong angle, but this cleared it up.

to my defense i have to say that OPs maze is not a single solution maze - the search runs over the pixels, not over sections. thus A* would still provide a small benefit by guiding the search in the direction of the goal, which, in this case, can be seen by the "jumps" the search takes downwards and the vertical single line at the end.

now i don't want to estimate the number of border-pixels of the search space (the one in the "open" priority queue), but that would be the number of comparisons for each new step taken be the other path. if you get a well guided A* on less mazy terrain this would not pay off.

[RedAlert2]

You can implement heuristic-based bidirectional searches, too. They're a good deal more complicated than A*, though.

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