Stap 4: Oplossen van de Maze - de regel van de linkerhand
Zoals besproken bij introductie de meerderheid van de doolhoven, echter complex hun ontwerp lijken, werden hoofdzakelijk gevormd uit een continue muur met vele kruispunten en takken. Als de muur rond het doel van een doolhof is aangesloten op de omtrek van het labyrint bij de ingang, de doolhof altijd kan worden opgelost door te houden enerzijds bij aanraking met de muur, maar veel omwegen die verbonden zijn eventueel. Deze 'eenvoudige' doolhoven worden correct genoemd "Enkelvoudig samenhangende."
Zoeken op Wikipedia, leren we dat "de volgeling van de muur de bekendste regel is voor het doorlopen van de doolhoven. Het is ook bekend als de linker regel of de rechter regel. Als het doolhof enkelvoudig samenhangend is, dat wil zeggen, worden alle de muren verbonden samen of aan de buitenrand van de doolhof, dan houden enerzijds in contact met een muur van de maze de Oplosser is gegarandeerd niet verdwalen en zal een andere uitgang bereiken als er een; anders, hij of zij zal terugkeren naar de ingang naast elke gang hebben doorkruist die sectie van muren ten minste eenmaal verbonden."
Kortom, kan de regel van de linkerhand omschreven worden als:
- Plaats je linkerhand op de muur.
- Beginnen lopen vooruit
- Op elk snijpunt van, en in het doolhof, houd uw linkerhand raken van de muur aan uw linkerkant.
- Uiteindelijk, bereik je het eind van het doolhof. Zal je waarschijnlijk niet naar de kortste en meest directe manier, maar je zal er komen.
Dus, de sleutel is hier is het identificeren van de snijpunten, definiëren welke cursus te nemen op basis van de bovenstaande regels. Specifiek in onze soort 2D doolhof vinden we 8 verschillende soorten kruispunten (zie afbeelding 1):
Op zoek naar de afbeelding, kunnen we ons realiseren dat de mogelijke acties op kruispunten zijn:
- Aan een "kruis"
- Ga naar links
- Ga naar rechts
- Rechtdoor
- Op een "T":
- Ga naar links
- Ga naar rechts
- Op een recht alleen:
- Ga naar rechts
- Alleen een links:
- Ga naar links
- Op rechte of links:
- Ga naar links
- Rechtdoor
- Op rechte of recht:
- Ga naar rechts
- Rechtdoor
- Op een dood spoor:
- Ga terug ("U-bocht")
- Aan het eind van het doolhof:
- Stop
Maar, de "regel van de linkerhand" toe te passen, de acties zal worden verlaagd tot één optie elke:
- Aan een "kruis": Ga naar links
- Op een "T": Ga naar links
- Op een recht alleen: Ga naar rechts
- Een links alleen: Ga naar links
- Op rechte of links: Ga naar links
- Op rechte of recht: Go Straight
- Op een dood spoor: Ga terug ("U-bocht")
- Aan einde van doolhof: stoppen
We zijn er bijna. Wanneer de robot een doodlopende weg of het einde van een doolhof bereikt, is het gemakkelijk te identificeren, omdat bestaan niet dubbelzinnige situaties (wij hebben al deze acties op de lijn volgeling Robot uitgevoerd). Het probleem is wanneer de robot vinden een 'regel' bijvoorbeeld, omdat een regel kan een "Cross" (1) of een "T" (2). Wanneer het bereikt een "links of rechts draai", die kunnen ook de opties voor rechtdoor of een simpele draai (opties 3 of 4) (5 of 6). Om te ontdekken precies op wat voor soort doorsnede de robot is, een extra stap moet worden genomen: de robot moet uitvoeren van een "extra duim" en zien wat er volgende (Zie de figuur 2 als voorbeeld).
Dus, in termen van stroom die de mogelijke acties nu kunnen beschrijven als:
- Op een dood spoor: Ga terug ("U-bocht")
- Bij een regel:
- Uitvoeren van een extra duim
- Als er een lijn: het is een "kruising" == > Ga naar links
- Als er geen lijn is: het is een "T" == > Ga naar links
- Als er een andere lijn: het is het eind van het doolhof == > stoppen
- Bij een bocht naar rechts:
- Uitvoeren van een extra duim
- Als er een lijn: het is een Straight of rechts == > Ga rechtstreeks
- Als er geen lijn is: het is een recht alleen == > Ga naar rechts
- Bij een linker bocht:
- Uitvoeren van een extra duim
- Als er een lijn: het is een Straight of links == > Ga links
- Als er geen lijn is: het is een links alleen == > Ga naar links
Merk op dat in feite, in het geval van een "LINKSAF", kunt u de test, overslaan omdat je links toch zal nemen. Ik verliet de uitleg meer generieke alleen voor de duidelijkheid. De echte code zal ik deze test overslaan.
(de afbeelding 3, toont een zeer eenvoudige doolhof op mijn lab vloer, die ik gebruik voor testdoeleinden):
