Content deleted Content added
→Origin Shift algorithm: Reply |
|||
| (10 intermediate revisions by 8 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)
: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)
| |||