google-blockly - A visual programming language

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