Content deleted Content added
→Minimal examples: new section |
→Origin Shift algorithm: Reply |
||
| (19 intermediate revisions by 12 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 14 ⟶ 17:
This is directly contradicted by the gif in this section.
10:04, 24 November 2016 (UTC) <!-- Template:Unsigned IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/124.171.84.237|124.171.84.237]] ([[User talk:124.171.84.237#top|talk]]) </small> <!--Autosigned by SineBot-->
I find the description to be somewhat vague. The "otherwise" instruction subsection is as difficult to follow as the maze Im trying to solve. Furthermore, there seems to be some inconsistencies (perhaps variants exist) with other sources Ive found online. I have found some documents that suggest the importance of marking which path one came down originally each time a new junction is arrived at, and that other path taken, though marked, must be marked uniquely from the path that got you there.
[[Special:Contributions/50.35.103.217|50.35.103.217]] ([[User talk:50.35.103.217|talk]]) 18:47, 27 June 2017 (UTC)
== Maze blog ==
Line 48 ⟶ 54:
#** One where "the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops"
#* Mazes with more than one solution. The current example is humongous, and I am hoping one can find smaller examples. I don't object keeping the pretty picture of the humongous example, but a minimal one should be given as well.
# Also, the picture of the Pledge algorithm shows a "Left-turn solver trapped", but the left-turn rule was never introduced. On the other hand, I would also welcome an example where the Pledge algorithm succeeds and the wall follower fails.▼
▲Also, the picture of the Pledge algorithm shows a "Left-turn solver trapped", but the left-turn rule was never introduced. On the other hand, I would also welcome an example where the Pledge algorithm succeeds and the wall follower fails.
Thanks. [[Special:Contributions/160.83.42.135|160.83.42.135]] ([[User talk:160.83.42.135|talk]]) 17:01, 7 March 2017 (UTC)
== Human or Computer, Distinctions to be made ==
I feel as though some of these algorithms should have their own page. Or perhaps be specifically distinguished with their own major and devoted section. I originally came here looking for techniques for real humans to solve real labyrinths using logic and strategics. Instead what I find are algorithms for computers with an omniscient view of the maze. There is a huge difference and distinction here that is being obfuscated, and it saddens me to see that people cannot think outside of computation and cyberspace. There should be a breakdown on the type of solution processes that are available. Which require omniscient birds-eye views. Which require foreknowledge of an exit ___location. Which require vast memory, or vast calculation skills, etc. What each are optimized for, whether they are meant for humans or computers, etc. And how each can fail. There is a lack of meaningful content in this article as its mostly meant for programming.
[[Special:Contributions/50.35.103.217|50.35.103.217]] ([[User talk:50.35.103.217|talk]]) 18:47, 27 June 2017 (UTC)
== Pledge Algorithm ==
The pledge algorithm needs clarification.
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)
:It depends on whether the implementation of Pledge Algorithm is following the left or right hand walls. Pledge Algorithm doing a 180 degree U-turn only happens when moving in the primary direction, and hitting a corner which turns in the opposite direction of the wall following choice, so that when wall following is started upon the far wall that's hit, it immediately makes one follow the wall back up the passage away from the corner. There's nothing special about the U-turn, and it being +/- 0.5 rotation happens the same as any more gradual turning around. Thanks, - [[User:Cruiser1|Cruiser1]] ([[User talk:Cruiser1|talk]]) 18:03, 9 May 2018 (UTC)
== Question: Picture in section "Shortest Path algorithms" ==
The section and the description of the picture deal with mazes with multiple solutions. A solution should be a path between start and finish of the maze. The maze in the picture doesn't seem to have neither a start nor a finish - what would be a solution in this case? A path between any two places in the maze? A path between any two places on the edge of the maze? Or am I missing something here? [[User:Katzenpfote|Katzenpfote]] ([[User talk:Katzenpfote|talk]]) 01:58, 3 January 2019 (UTC)
:Indeed, this isn't the best example picture, since a Maze should clearly indicate its start and end points. A common practice is to have the start in the upper left corner, and the end in the lower right corner. The viewer should assume that's the case, or else pick their own start and end points. A shortest path algorithm will be able to work regardless of the start and end points chosen (assuming at least one solution exists). Thanks, [[User:Cruiser1|Cruiser1]] ([[User talk:Cruiser1|talk]]) 23:42, 14 March 2019 (UTC)
== "Maze-solving algorithm" ==
The algorithm listed under "Maze-solving algorithm" doesn't seem to work reliably. I was looking for a maze solver with bounded memory requirements, and implemented that one. If you're going from one corner to another in a square grid, and there's an obstacle in the center, you get stuck wall-following round and round the center obstacle.
The source cited at [https://dl.acm.org/citation.cfm?id=2786591] is paywalled, but there is a copy of that paper online at CMU at [https://www.pdl.cmu.edu/PDL-FTP/associated/maze-routing_nocs15.pdf]. The version of the algorithm in the paper ("Algorithm 1", page 4) is somewhat different than the one in the Wikipedia article. I think the problem is, at least, that the paper has a line ''MDbest←MDbest−1'' which isn't in the Wikipedia article. Not sure yet. But I'm not going to debug code in Wikipedia; that would be OR.
This algorithm was put into Wikipedia by an anon at [https://en.wikipedia.org/wiki/Special:Contributions/130.232.103.111]. That's the only edit ever seen from that IP address. So there's no one to ask. --[[User:Nagle|John Nagle]] ([[User talk:Nagle|talk]]) 04:09, 28 June 2019 (UTC)
: 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">— 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)
| |||