Hoppa till huvudinnehåll

Dags att använda DFS i Pac-Man!

Nu när du har förstått hur Depth-First Search fungerar och varför vi ibland behöver spara extra information , så är det dags att testa det i praktiken!

Vi kommer att jobba med ett riktigt Pac-Man-spel och implementera DFS för att styra Pac-Man genom en labyrint.

Följ dessa steg​

1. Öppna GitHub​

2. Hitta och öppna repot:​

  • Sök efter berkeley_pacman

3. Klona repot till din dator:​

Öppna din terminal (CMD, PowerShell eller terminal i VS Code) och skriv:

git clone https://github.com/jeff-hykin/berkeley_pacman.git
cd berkeley_pacman
code .

4. Kör spelet i terminalen:​

cd main
python pacman.py

❗ Obs: Om det inte fungerar, kör:​

pip install future

5. Hitta filen search.py​

  • Hitta funktionen depth_first_search i search.py
  • Det är här vi kommer att skriva vår DFS-algoritm

Nästa steg​

  • Implementera funktionen depth_first_search enligt pseudokoden
  • På nästa sidan finns det en fusklapp på hur jag löste problemet.

DFS Pseudokod​

  • Innan vi skriver riktig kod, låt oss titta på pseudokoden för DFS i detta sammanhang.
DFS(problem):
    Skapa en stack
    Lägg till startpositionen i stacken tillsammans med en tom path

    Skapa en mängd visited_states

    Medan stacken inte är tom:
        Ta ut det översta elementet i stacken (state, path)

        Om state är målet:
            Returnera path

        Om state inte har besökts tidigare:
            Lägg till state i visited_states

            För varje successor (next_state, action, cost) i problem.getSuccessors(state):
                Lägg (next_state, path + [action]) i stacken

När du är klar och vill testa din kod :​

    Python pacman.py --layout tiny_maze -p SearchAgent -a fn=depth_first_search

Mål: Pac-Man ska kunna ta sig till målet med hjälp av just din DFS!