Find Algorithms to Solve Mazes and Explore Dungeons

Iterated DFS

>program robot to not stop walking until it finds the exit
>profit

this is without a doubt the fastest way out of the maze

Attached: labbypath.jpg (820x580, 264K)

>Walks into a wall forever

>change direction whenever it bumps into something
eventually it will have to get there

True

Bull shit, theres always a chance it just goes in a loops
>hits wall
>Turns 180
>walks straight
>hits wall
>turns 180
>walks straight
>hits wall
>turns 180
repeat forever.

Problem is that sometimes you have to turn without bumping into a wall to get to the exit. Example: T junction where the middle path leads to exit.

Flood fill

Basically the only method that will get you to the exit of any maze in finite time without having any memory of past turns is choosing random direction every time you reach a junction.

That requires memory which we don't have.

Hugging a wall only works in a maze with no loops.

>turn for a random angle between 0 and 180 degrees in intervals of 30 degrees
eventually we'll get there

he could theoretically bump into the top section of the T, right at the intersection, making him change direction into the correct path

and yes, it's inefficient, but one day, you'll have to reach the exit

Most efficient angle change per bump and interval for any given maze?

How would you get stuck in a loop? Shouldn't following one wall be a surefire way?

I don't know if it's the most efficient one, nor am I interested enough in finding the most efficient way because the entire approach is based on the idea that it's sufficient to solve the problem, not necessarily the best solution.

...

>turn in random direction each time at a junction
>don't walk into walls
solved

The only situation in which it doesn't apply is when the exit is within the maze itself, because in that case you can design the maze in a way for that exit's room walls to be disconnected from the rest of the maze. Think of a trapdoor inside the floor, for example.

>pic related
Made a brief mock-up of what that situation could be like.

Attached: mazeexamp.jpg (800x400, 20K)

turn 90 degree to right and he will find the exit in under 1000years.
not efficent but it will bring results.

What if the maze is this. Since the correct turn doesnt happen at a corner, it will never make that turn.

Attached: Untitled.png (1152x648, 11K)

bread crumbs

make the algorithm strong enough to break walls

problem solved

What about we always make right turns, unless we hit a dead end? Then we turn around? Is this a step in the right direction?

It seems to work for every maze I try except this one Maybe it could be modified?

Attached: maze2.jpg (547x427, 89K)

If a perfect maze (no cycles) you take every right turn (or every left) and then repeat for the other side (or just turn around when you get to the end).

How would you know you took every right turn?

0-Start outside entrance
1-Face entrance
2-LABEL: looptop
3-move forward
4-IF passage to my right side, turn right
5-ELSE IF passage to my front, {//do nothing}
6-ELSE IF passage to my left, turn left
7-ELSE Turn left twice ENDIF
8-IF moretoexplore = TRUE, GOTO looptop

Isn't this the same as following one wall (right, in this case)?

>to solve ANY maze
>that doesn't rely on remembering past turns.

Good luck with a Kruskal

Attached: tight lipped.jpg (828x633, 62K)

What if we switched walls after turn?

following one wall always works for solving mazes that have no cycles. If you do it once for each wall you will traverse the entire maze, or you could turn around at the exit and explore the rest of the maze.

If the maze does have cycles you need some kind of memory to avoid looping forever. Now you could technicly solve any maze using brownian motion which has no memory but there is no guarantee that you'll solve the maze before an inordinate amount of time passes.

Put your hand on the right wall and just follow it until you're through. Slow but guaranteed to work

Switching walls after each turn seems to avoid this issue

No it would require remembering past positions

maze w/o loops
>move forward, drawing the path as you go
>only take junctions that have no marks

maze w/ loops
>move forward, drawing your path as you go
>at any junction, randomly select a path from the least-marked options

Attached: 1518848544404.jpg (1000x1000, 55K)

Put hand on one wall and other hand on opposite wall. Walk to exit.

Attached: Yes.png (1290x758, 15K)

Attached: ITS SO BRIGHT.gif (800x430, 564K)

This is impossible if you cannot retain information.

Or to put it better, there is no algorithm that exist that isn't just at a turn, go a random direction, and eventually you will reach the end.

That's a memory requirement though.

this path is so gay

Attached: 1521106399655.png (820x580, 135K)

>The maze could have the 'exit' be the cente
hugging the wall would bring you back to the start

no it isn't.
>IF turn THEN switch wall
no need to remember past turns or walls

Are you allowed to mark the walls in some way?

Fucking retard.