Labyrint Problemlösaren Robot, med artificiell intelligens med Arduino (4 / 10 steg)

Steg 4: Lösa labyrinten - vänster Hand regeln

Som diskuterats på inledning majoriteten av labyrinter, men komplexa deras design kan visas, i huvudsak bildades från en kontinuerlig vägg med många korsningar och grenar. Om muren som omger målet av en labyrint är ansluten till omkretsen av labyrinten vid ingången, labyrinten alltid kan lösas genom att hålla en hand i kontakt med väggen, men många omvägar som kan innebära. Dessa "enkla" labyrinter är korrekt kallas "Helt enkelt-ansluten".

Söka på Wikipedia, vi lär oss att "vägg efterföljare är den mest kända regeln för korsa labyrinter. Det är även känd som regeln om vänstra eller högra regeln. Om labyrinten är enkelt anslutna, det vill säga är alla dess väggar anslutna tillsammans eller till en labyrint yttre gräns, sedan genom att hålla en hand i kontakt med en vägg av labyrinten Problemlösaren garanteras inte att gå vilse och kommer att nå en annan utgång om det finns en; annars kan han eller hon kommer att återvända till ingången efter att ha korsat varje korridor bredvid som ansluten avsnitt av väggar minst en gång."

Kort sagt, kan den vänstra handen regeln beskrivas som:

1. Placera din vänstra hand på väggen.
2. Börja gå framåt
3. Vid varje korsning, och hela labyrinten, håll vänster hand röra väggen på vänster sida.
4. Så småningom kommer du nå slutet av labyrinten. Du kommer förmodligen inte att gå den kortaste och mest direkta sättet, men du kommer dit.

Så, viktigaste här är att identifiera korsningarna, definiera vad kursen ta utifrån ovanstående regler. Särskilt i våra slags 2D labyrint, kan vi hitta 8 olika typer av korsningar (se bild 1):

Titta på bilden, kan vi inse att de möjliga åtgärderna vid korsningar är:

1. På en "korsning"
   • Gå till vänster
   • Gå till höger
   • Rakt fram
2. På ett "T":
   • Gå till vänster
   • Gå till höger
3. På rätt endast:
   • Gå till höger
4. En vänster bara:
   • Gå till vänster
5. På stege eller vänster:
   • Gå till vänster
   • Rakt fram
6. På rak eller höger:
   • Gå till höger
   • Rakt fram
7. På en återvändsgränd:
   • Gå tillbaka ("U-sväng")
8. Slutet av labyrinten:
   • Stanna

Men, tillämpa "Vänster Hand regeln", vilka åtgärder kommer att minskas till ett alternativ:

1. På en "korsning": gå till vänster
2. På ett "T": gå till vänster
3. På rätt bara: gå till höger
4. En vänster bara: gå till vänster
5. På stege eller vänster: gå till vänster
6. På rak eller höger: gå rakt
7. På en återvändsgränd: gå tillbaka ("U-sväng")
8. Slutet av labyrinten: stoppa

Vi är nästan där. När roboten når en återvändsgränd eller slutet av en labyrint, det är lätt att identifiera det eftersom existerar inte tvetydiga situationer (vi har redan genomfört dessa åtgärder på rad efterföljare Robot). Problemet är när roboten hitta en "linje" till exempel, eftersom en linje kan vara ett "kors" (1) eller ett "T" (2). Också när den når en "vänster eller höger sväng", de kan vara i en enkel (alternativ 3 eller 4) eller alternativ att gå rakt (5 eller 6). För att upptäcka exakt på vilken typ av korsning roboten är, måste ett ytterligare steg tas: roboten måste köra en "extra tum" och se vad som händer (se bild 2 som ett exempel).

Så, när det gäller flödet av möjliga åtgärder kan vara nu beskrivs som:

1. På en återvändsgränd: gå tillbaka ("U-sväng")
2. På en linje:
   • Kör en extra tum
   • Om det finns en linje: det är en "korsning" == > gå till vänster
   • Om det finns ingen linje: det är ett "T" == > gå till vänster
   • Om det finns en annan linje: det är i slutet av labyrinten == > stoppa
3. Vid en höger sväng:
   • Kör en extra tum
   • om det finns en linje: det är en rak eller rätt == > gå direkt
   • Om det finns ingen linje: det är en rätt bara == > gå till höger
4. Vid en vänster sväng:
   • Kör en extra tum
   • om det finns en linje: det är en rak eller vänster == > gå vänster
   • Om det finns ingen linje: det är en vänster bara == > gå till vänster

Observera att i själva verket vid en "VÄNSTERSVÄNG", kan du hoppa över test, eftersom du tar vänster ändå. Jag lämnade förklaringen mer generisk bara för tydlighetens skull. På riktiga koden kommer jag hoppa över detta test.

(bild 3, visar en mycket enkel labyrint på min lab våningen, som jag använder på försök):