Talk:Maze-solving algorithm: Difference between revisions

Revision as of 18:10, 10 February 2022

Latest revision as of 17:21, 2 July 2024

(4 intermediate revisions by 4 users not shown)

Line 1:

{{WikiProject banner shell|

{{WikiProject Computer science}}

}}

== Random mouse algorithm ==

It is incorrect that random mouse algorithm "will always eventually find the solution". In most cases such algorithm would trap the mouse indefinitely in a section the only exit from which is in the middle of the wall. I would suggest changing the wording to smth along the lines of "may eventually find the solution".

Line 66 ⟶ 67:

The pledge algorithm starts out by saying wall-following fails sometimes, which is why pledge is needed. But then it goes on to give an example of a simple maze that fails because of a left-turn algorithm, not a wall-following algorithm. If the wall were followed an exit would be found. And no distinction is made by the example between a wall-following and a pledge algorithm.

[[Special:Contributions/50.35.103.217|50.35.103.217]] ([[User talk:50.35.103.217|talk]]) 18:55, 27 June 2017 (UTC)

:I realize this is an old post, but I agree the example needs clarification. It took me an embarrassingly long time to understand what was going on, as my wall follower algorithm in my game would not get stuck in a loop with the example maze. It wasn't until I saw a video of robot using a left-turn algorithm before I understood it was the example here that was misleading me. [[User:Rdsarson|Rdsarson]] ([[User talk:Rdsarson|talk]]) 13:13, 27 October 2023 (UTC)

I had another question: what does the Pledge Algorithm do when it needs to do a 180 degree turn? Does this count as +0.5 rotations or -0.5 rotations on the angle-counter? [[User:Charmoniumq|Charmoniumq]] ([[User talk:Charmoniumq|talk]]) 20:30, 7 May 2018 (UTC)

Line 84 ⟶ 87:

: I got a version working. The termination test for wall-following in the paper is sightly off, rendering the proof unsound. But it would be [[WP:OR]] to fix it. Here's my working version in Python.[https://github.com/John-Nagle/lslutils/blob/master/npc/obsolete/mazesolver.py]. But, again, [[WP:OR]]. It's really a variant of Pledge's fix to wall-following, which is already in the article. [[User:Nagle|John Nagle]] ([[User talk:Nagle|talk]]) 23:54, 28 June 2019 (UTC)

== Origin Shift algorithm ==

What about the Origin Shift algorithm, as described in [https://www.youtube.com/watch?v=zbXKcDVV4G0] by CaptainLuma?

Is this a new maze creation algorithm? <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/193.191.180.235|193.191.180.235]] ([[User talk:193.191.180.235#top|talk]]) 09:39, 2 July 2024 (UTC)</small> <!--Autosigned by SineBot-->

:We cannot include material without published reliable sources. A YouTube video does not meet that standard. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 17:21, 2 July 2024 (UTC)