Python Labyrinth?
Eure Aufgabe ist es einen "Roboter" zu programmieren, der sich selbstständig durch ein Labyrinth bis zu einem Ausgang den Weg findet.
Hierzu muss der Roboter einen Algorithmus nutzen, d.h. er darf nicht um Zufallsverfahren Schritte machen und "hoffen", dass er irgendwann am Ziel ankommt.
Ihr dürft annehmen, dass es sich um ein echtes Labyrinth OHNE Kreise handelt, d.h. es gibt garantiert immer (mindestens) 1 Pfad vom Start bis zum Ziel, man kann aber nicht "im Kreis" laufen. Sackgassen hingegen gibt es natürlich schon.
4 Antworten
Sorry fürs Vorsagen, aber ich konnte nicht widerstehen:
Eine Labyrinth-Datei sieht bei mir so aus (R=Roboter, E=Ausgang, Space=Pfad):
XXXXXXXXXXXXXXXXXXXX
X X X
X X XX X XXXXXXXXXXX
XXX X X X
E X XXXX XXX XXXXX
XXXXX XXXX X X X
X X XXX XX X
X X XXXXXX X XX X
R X X X XX
XXXXXXXXXXXXXXXXXXXX
Und so spaziert der Roboter durch, immer schön die rechte Hand an der Wand:
#! /usr/bin/env python3
"""
Let a robot find its way out of a maze.
Copyright: public domain
"""
from sys import argv
class Maze:
"""
A Maze is a list of strings.
Space = walkable path
R = start position
E = exit positions
X (or any other character) = wall
"""
def __init__( self, filename ):
self.maze = tuple(self._load(filename))
self.robot = self._locate('R')
self.dir = 1, 0
def __str__( self ):
return ''.join( ('*' if (l,c)==self.robot else char)
for l,line in enumerate(self.maze)
for c,char in enumerate(line)
)
@staticmethod
def _load( filename ):
"""Helper: iterate the lines of a text file"""
with open(filename) as stream:
for line in stream:
yield line
def _locate( self, entry ):
"""Helper: find the position of a symbol in the maze"""
for l, line in enumerate(self.maze):
for c, char in enumerate(line):
if char==entry:
return l, c
return None
def peek( self, pos ):
"""
Read the maze symbol at a position.
The maze starts at pos=(0, 0).
If pos is out of range, '\n' is returned.
"""
if 0 <= pos[0] < len(self.maze):
line = self.maze[pos[0]]
if 0 <= pos[1] < len(line):
return line[pos[1]]
return '\n'
def _next( self ):
"""Helper: compute the position robot+dir"""
return self.robot[0]+self.dir[0], self.robot[1]+self.dir[1]
def walk( self ):
"""
Make a single step, trying to keep in touch with a wall
on the right hand.
@return True, if an exit is reached.
"""
# first, turn right once:
self.dir = self.dir[1], -self.dir[0]
# now look counterclockwise for a path:
while self.peek(self._next()) not in "E ":
# TODO: stop, if this happens in all 4 directions.
self.dir = -self.dir[1], self.dir[0] # turn left
# Step forward:
self.robot = self._next()
# Check, if the robot is at an exit:
return self.peek(self.robot)=='E'
if __name__ == '__main__':
"""
Usage: ./maze.py <maze-file>
Let the robot find its way out of a maze.
If no file is specified, "maze.txt" is used.
"""
maze = Maze(argv[1] if len(argv)>1 else "maze.txt")
key = 's' # single step mode (see below)
while not maze.walk():
print("\033[H\033[J\n", maze, sep='')
if key in 's\n':
key=input("s or <Enter>=single step, q=quit, r=run \n")
if key=='q':
break
Die Escape-Sequenzen \033[H\033[J (Konsole löschen) werden unter Windows wahrscheinlich nicht funktionieren. Dann lösch sie einfach.
Wie bekomme ich es hin, dass der Roboter am Ende den kürzesten Weg bis zum Ziel anzeigt?
Sollt ihr das Labyrinth auch selbst programmieren?
Spontan würden mir ja Pyhton Kara oder der Java Hamster in den Sinn kommen.
ja in python aber habe bereits probleme das spielfeld aus einer textdatei darzustellen.
In dem Fall, da es nichtmal Zyklen gibt:
Immer der Nase nach, die erstbeste Abbiegemöglichkeit nutzen (immer rechts oder immer links), bei Sackgasse um 180° drehen und weiter im Takt.
Lass den "Roboter" bei einer Kreuzung immer nach links laufen. Wenn er in eine Sackgasse gelangt, fährt er bis zur letzten Kreuzung zurück und nimmt die nächste linke Abbiegung, die er noch nicht genommen hat. Sind bei einer Kreuzung alle Abbiegungen abgearbeitet worden wird diese als Sackgasse markiert und zur letzten Kreuzung zurückgekehrt.
Kann man natürlich auch so implementieren, dass der "Roboter" immer die rechte Abbiegung nimmt.
In Python sollte das nicht allzu schwer zu implementieren sein
Bugfix: Wenn die Gänge breiter sind und der Roboter keine Wand um sich hat, dreht er sich nur im Kreis.
Abhilfe: In der Methode walk() darf er nur dann rechts abbiegen, wenn er zuvor noch an einer Wand entlang lief: