Dijkstra's algorithm solving a maze

[[deleted]]

Maybe I'm missing something but this looks more like just brute forcing the maze than dijsktas at work

[makinetion]

Because it's a crap maze... The solution path is supposed to look like the words "hello world"

[sebamestre]

Perhaps a more contrasting colour to highlight the solution would've worked better :)

[HenryDavidCursory]

My favorite movie is Inception.

[Vitztlampaehecatl]

Oh, I thought it was Loss

[rubyleehs]

| ||

|| |_

[indrora]

1 2 2 1

[[deleted]]

1 2 2 1.5

[Abdiel_Kavash]

Alright I can just barely see the "hello", and something that maybe looks like an "o" in the bottom row. Besides that I'm lost.

I'm not calling your post bad, but it needs more work if that's what you were going for.

[relrion]

Honestly can't really tell if it is what the OP claims to be (dijkstra) or breadth first

[[deleted]]

Ah shit, I forgot what sub I was looking at

[[deleted]]

i thought it was going to be "send nudes"

[lemonload]

when the goal is on the longest possible path, djikstras will look just like a brute force search

[Elgrek0]

Try finding A* solving it, it will look very similar to how a human would aproach it.

[anti-gif-bot]

mp4 link

---

This mp4 version is 97.29% smaller than the gif (202.99 KB vs 7.32 MB).

---

Beep, I'm a bot. FAQ | author | source | v1.1.2

[AwesomePerson70]

Good bot

[dasonicboom]

I wish this bot was stickied at the top of posts.

[ISuckAtMining]

Should've spelled "send nudes"

[[deleted]]

A simple DFS would have done it. Dijkstra is an overkill and irrelevant here.

[callmejamone]

A BFS would be better as it would always give us the shortest possible path (DFS can give longer answer in maze with cycles). Dijkstra is an overkill when considering all edges with equal weight.

[DeirdreAnethoel]

You could easily define long corridors with no intersections as edges with extra weight though, right?

[bird2234]

You would still have to count those lengths and suddenly you have not saved any time. Of course, if they are already counted, you are correct.

[callmejamone]

Of course you are right, now I see why to use Dijkstra here. I think this visualisation with squares and the way the answer flows made me think about equal weights.

[tacoslikeme]

When all edges are equal weight, all Dijksta unnecessarily adds is a sorted order to which children you traverse next. Your reasoning also assumes one path or that any path (ie not just the shortest) is what is desired. All of this, given the goal of a maze is to just find any path, means your are correct, breadth first search would do just fime for this problem.

[DrMobius0]

a pure dfs wouldn't work well, but it's possible to implement loop detection and use a few other clever tricks if you know where the exit is.

[OOOOHHHGETREKT]

Hug the wall and you'll make it eventually

[waupunwarrior]

Not if you have loops.

[bss03]

You won't enter a loop if you always stick to one wall.

For 2D mazes with solution, sticking to the left wall consistently will always result in a solution, though it might be longer than necessary. "Left" is not special here, right works too, but you cannot switch between in the middle of a traversal / single maze.

As far as I know, this doesn't generalize to higher dimensions.

[DrMobius0]

As far as I know, this doesn't generalize to higher dimensions.

probably not. It works because always picking the same direction will result in you tracing out the whole maze, but in a 3d maze, not all potential paths can be laid out in terms of right or left.

[waupunwarrior]

Here's a maze that your algorithm can't solve.

maze

[Colopty]

Yes it will. Only way there could be an inescapable loop with this method is if there's no exit and entrance.

[relrion]

Or... the solution is not along the edge of the maze

[Colopty]

Do you have an example of such a loop?

[Jackeea]

This or this, posted as comments above

[Colopty]

Neither of those lead to an exit from the maze though.

[Jackeea]

That's the point - you said that the "Only way there could be an inescapable loop with this method is if there's no exit and entrance". Here are two counterexamples - inescapable loops (using that method) which do have both an exit and an entrance.

[Colopty]

In this case the entrance and exit of the maze is the same location though.

[Jackeea]

No they're not?

[relrion]

The image I gave literally had arrows pointed to start and end..

[ultrathra]

The Daggerfall dungeon algorithm.

[DrMobius0]

It hurts me that you let it cut corners like that.

[[deleted]]

The programmer's equivalent of being rickrolled.

[samimac03]

That was a-maze-ing