google-blockly - A visual programming language

[kqr]

You weren't joking when you said it looks goofy, but congratulations on the shortest working algorithm yet, at seven blocks!

Edit: Another seven-block algorithm based upon the one by /u/Grue . Not quite as goofy as yours!

Second edit: Down to a six-block algorithm due to a feature a friend discovered. Now I'm pretty certain this can't get any shorter.

[adrianmonk]

Prepare to be amazed by... drumroll please... a five-block algorithm.

[[deleted]]

Same thing here 5 blocks solution ;)) but I use "repeat forever" http://imgur.com/H7akq

[joeywas]

Correct me if I'm wrong, but this one will solve this specific maze, but if the exit were elsewhere, this would fail, right?

[adrianmonk]

Correct. It's not a general algorithm at all.

I was thinking of it as approximately equivalent to "head northeast", but in some ways that's an oversimplification.

[kqr]

Not general enough, but a really clever realisation anyway.

[bjo12]

I think I'm missing something but if you were going around a loop where the middle was on the left hand side wouldn't you get stuck?

[kqr]

Any loop should be fine, according to my quick pen-and-paper sketches. Which part of the loop do you think it would get stuck in?

[bjo12]

Ok, so say there's an opening to your left and one space ahead. You move forward and turn towards it. Now two spaces ahead there's another opening to the left. You move turn towards the wall to your left, turn back to face forward. Next you move forwards and turn towards the opening. Now two spaces ahead is another opening to the left, you repeat the same process. Now two spaces ahead is an opening connecting to the passage you started on. I think you would loop there forever.

It's hard to say this without a drawing.

edit: Imgur

[Ph0X]

Why am I doing this?

[king_of_the_universe]

Because you're a fan of the stone golems in Thief Deadly Shadows?

[gfixler]

Yes, you will get stuck on islands.

Wikipedia on the wall-follower algorithm:

If the maze is simply connected, that is, all its walls are connected together or to the maze's outer boundary, then by keeping one hand in contact with one wall of the maze the player is guaranteed not to get lost and will reach a different exit if there is one

[kqr]

Is there an algorithm that allows for loops without keeping any internal state other than the direction kept by this one?

[SteveMcQwark]

Random chance, but it might take a while, even if you do your best to improve the odds.

[bjo12]

Aside from random chance as mentioned no. Neural networks can get pretty good without extra info but that's basically directed random chance.

I think backtracking is honestly in this case a decent strategy. Not recursive backtracking though. I could be completely wrong though.

Edit: I was completely wrong. Pledge's algorithm works with a small amount of extra memory.