In deze oefening ga je het spel Rush Hour modelleren als een zoekprobleem en oplossen met behulp van het A* zoek algoritme.

Het spel wordt gespeeld op een 6 x 6 rooster. Op het bord staan meerdere auto’s:

• Elke auto heeft:

  • een unieke ID (string, bv. "A", "B", "X")
  • een startpositie (rij, kolom)
  • een lengte (als oriëntatie "H" dan groeit de auto naar rechts, anders naar beneden)

  • een oriëntatie:

    • "H" = horizontaal
    • "V" = verticaal

De speciale auto "X" (de rode auto) moet naar de uitgang rechts van het bord rijden. De uitgang is altijd rechts van auto "X" op dezelfde rij als deze auto. De auto "X" heeft de uitgang bereikt als deze voor de uitgang staat (. . . . X X | waarbij | de uitgang is).

Schrijf een programma dat de kortste oplossing vindt om de rode auto "X" naar de uitgang te brengen.

Een toestand (state) wordt voorgesteld als een tuple van auto’s: ((id, rij, kolom, lengte, oriëntatie), ...)

Bijvoorbeeld:

1  (
2      ("X", 2, 0, 2, "H"),
3      ("A", 0, 0, 2, "V"),
4      ("B", 0, 3, 3, "V"),
5  )

Betekend:

We lossen deze oefening stap per stap op. De eerste functie dat je moet implementeren is is_uitgang(state). Deze functie controleert of de rode auto "X" de uitgang heeft bereikt.

Schrijf de methode getNeighbours(self, v) die alle mogelijke volgende toestanden teruggeeft vanuit de meegegeven state.

Opmerkingen: - Auto’s kunnen enkel bewegen in hun eigen richting - Auto's mogen niet door andere auto’s rijden - Elke move verschuift één auto met exact 1 stap

Hint: Maak eerst een matrix van de huidige state

Schrijf een functie h(v, t, G). Definieer hierin een heuristiek voor A*.

• v: Vertrex
• t: Doelvertrex

Voorbeelden: Afstand van de rode auto tot de uitgang, Aantal blokkerende auto’s, ...

Opmerkingen:

• Zorg ervoor dat de heuristiek admissible is.
• Aangezien de heuristiek verschillende resultaten geeft per implementatie kan dit niet getest worden. Deze opgave zla dus altijd juist zijn als de functie is geïmplementeerd!

Hint: I.p.v. direct de doelvertex t te gebruiken, maak gebruik van de positie van de rode auto X om de heuristiek tot het doel te berekenen. Dit voorkomt problemen later.

Gegeven bovenstaande functies, gebruik A* om de oplossing te vinden:

• Input: starttoestand
• Output: minimum aantal zetten (of None als geen oplossing bestaat)