|
|
|
Programm schreiben, das den Weg aus einem Labyrinth findet. |
|
| pip |
Forum-Newbie
|
 |
Beiträge: 9
|
|
|
|
Anmeldedatum: 06.04.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
 |
|
Verfasst am: 06.04.2008, 07:42
Titel: Programm schreiben, das den Weg aus einem Labyrinth findet.
|
 |
Hallo allerseits!
Ich habe folgendes Problem. Wir sollen für eine Hausaufgabe ein Programm in Matlab schreiben, dass ein Bild von einem Labyrinth einlesen soll. Daraufhin soll der Benutzer einen beliebigen Punkt in diesem Labyrinth angeben und unser Programm soll einen Weg zum Ausgang finden.
Ich habe eigentlich so viele Frage, dass ich gar nicht weiß, wo ich anfangen soll.
Das Bild einzulesen und als Matrix darzustellen haben wir soweit schon hinbekommen, aber wie soll es dann weiter gehen?
Ich wäre jedem dankbar, der mir helfen würde einen Lösungsansatz zu finden.
schönen gruß pip
|
|
|
|
|
|
| Michaela |
Forum-Century
|
|
Beiträge: 239
|
|
|
|
Anmeldedatum: 12.07.07
|
|
|
|
Wohnort: ---
|
|
|
|
Version: bis 2007b
|
|
|
|
|
|
|
Verfasst am: 06.04.2008, 09:26
Titel:
|
|
Also, ich habe mal gelernt. Wenn man immer an derselben Wand entlanggeht (also immer rechts oder immer links abbiegen) dann kommt man irgendwann auch raus (durchläuft aber auch alle Sackgassen entlang des Weges). Vielleicht könnt ihr damit was anfangen?
_________________
---------------------------------------------------------------
Leider habe ich daheim zwar Internet aber kein Matlab - daher sind alle Syntaxbeispiele circa Angaben.....
|
|
|
|
| nschlange |
Ehrenmitglied
|
|
Beiträge: 1.320
|
|
|
|
Anmeldedatum: 06.09.07
|
|
|
|
Wohnort: NRW
|
|
|
|
Version: R2007b
|
|
|
|
|
|
|
Verfasst am: 06.04.2008, 11:33
Titel:
|
|
| Michaela hat Folgendes geschrieben: |
| Also, ich habe mal gelernt. Wenn man immer an derselben Wand entlanggeht (also immer rechts oder immer links abbiegen) dann kommt man irgendwann auch raus (durchläuft aber auch alle Sackgassen entlang des Weges). Vielleicht könnt ihr damit was anfangen? |
Genau, ich glaube, ich habe das als 'Hand-an-der-Wand'-Verfahren oder so kennengelernt.
Vielleicht guck Ihr auch mal nach 'Backtracking', aber auch hier wird nicht zwangsläufig der kürzeste Weg gefunden, sondern ein beliebiger.
_________________
Viele Grüße
nschlange
"Chuck Norris ejakuliert fluessigen Stahl!"
|
|
|
|
| outsider |
Forum-Meister
|
|
Beiträge: 806
|
|
|
|
Anmeldedatum: 03.09.07
|
|
|
|
Wohnort: München
|
|
|
|
Version: R2012b
|
|
|
|
|
|
|
Verfasst am: 06.04.2008, 13:01
Titel:
|
|
Das lässt sich relativ einfach rekursiv lösen. Du fängst mit einem Punkt an und von dem ausgehend, kannst Du in 4 Richtugnen sich bewegen (oben, unten, links, rechts). Sobald Du einen Schritt machst hast Du wieder 4 Möglichkeiten für eine Bewegung, d.h. Du rufst die Funktion erneut (rekursiv) auf. Falls man auf eine Wand stößt springt man sofort zurück (Abbruchkriterium).
Es verhält sich genau so wie die graphishe Funktion zum Füllen einer Fläche mit Farbe. Hier ist zB. ein Link der die Funktion zum Füllen von Objekten beschreib:
http://www.hdm-stuttgart.de/~rk020/.....ng/printable_version.html
Somit findest Du immer einen Weg nach Aussen. Eng kann es werden, wenn der Rekursionslimit erreicht wird (in MATLAB standardmässig 500) bei sehr großen Labirynten.
Vielleicht kannst Du sogar die Funktion FILL dafür benutzen.
MfG
|
|
|
|
| pip |
Themenstarter
Forum-Newbie
|
|
Beiträge: 9
|
|
|
|
Anmeldedatum: 06.04.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 06.04.2008, 13:01
Titel:
|
|
Hey, vielen Dank für die Antworten.
Das Problem liegt aber leider woanders. Die Möglichkeiten ein Labyrinth zu lösen sind momentan noch zweitranging. Bei Wikipedia stehen dazu ein paar Lösungsansätze.
Das Problem ist eher die Implementierung in Matlab.
Wir lesen unser Bild in Matlab ein und bekommen eine Matrix, die aus 1 und 0 aufgebaut ist. Die 1 entsprechen dem Gang. Und da fängt das Problem an. Wie sollen wir zum Beispiel in so einer Matrix sagen, dass immer rechts abgebogen werden soll. Oder wie sagen wir dem Computer, dass die 1 der Gang ist und dass er sich nur darauf bewegen soll.
Sorry, dass ich vorhin nicht genau darauf eingegangen bin. Man muss das ganze halt über die Matrix machen, nur wie ist die Frage. Oder hat jemand von euch einen anderen Lösungsweg?
sg philipp
|
|
|
|
| Michaela |
Forum-Century
|
|
Beiträge: 239
|
|
|
|
Anmeldedatum: 12.07.07
|
|
|
|
Wohnort: ---
|
|
|
|
Version: bis 2007b
|
|
|
|
|
|
|
Verfasst am: 06.04.2008, 13:45
Titel:
|
|
Naja, ihr habt ja einen Startpunkt (i,j), der hoffentlich eine 1 ist (ansonsten steckt ihr ja in der Wand fest.) Dann muss man eben schaun ob oben (i-1,j) unten(i+1,j) links(i,j-1) rechts(i,j+1) 1 oder 0 steht oder die Matrix zuende ist, um dann zu entscheiden in welche Richtung man laut Algorithmus weitergehen soll.
_________________
---------------------------------------------------------------
Leider habe ich daheim zwar Internet aber kein Matlab - daher sind alle Syntaxbeispiele circa Angaben.....
|
|
|
|
| pip |
Themenstarter
Forum-Newbie
|
|
Beiträge: 9
|
|
|
|
Anmeldedatum: 06.04.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 06.04.2008, 16:09
Titel:
|
|
Hi, hab mir das auch so ungefähr überlegt. Einfach mit der Kombination while und if den Weg zu suchen, aber ist leider nicht so einfach:(
Ich denke mal es ist auch großes Problem für uns, dass wir gar nicht wissen wie das Labyrinth aussehen wird, mit dem unser Programm später getestet wird. Je nachdem wie groß das Bild sein wird, könnte es dadurch sehr lange dauern, bis der Computer eine Lösung berechnet hat. Aber ich denke mal, wir werden einfach anfangen mal auszuprobieren.
Eine konkrete Frage habe ich aber noch. Wie soll ich den Benutzer am besten einen Punkt in dem Labyrinth auswählen lassen? Über die Funtion imshow() kann ich das Bild anzeigen lassen, aber leider nicht bearbeiten.
sg pip
|
|
|
|
| makl314 |
Forum-Anfänger
|
|
Beiträge: 34
|
|
|
|
Anmeldedatum: 23.01.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 07.04.2008, 11:11
Titel:
|
|
| |
 |
 |
Das angeben eines Startpunktes ist kein Problem: Schreib eine Funktion, die die Startkoordinaten und die Labyrinth-Matrix übergeben bekommt. Die Funktion soll dann am besten mit der "Hand-an-der-Wand"-Methode das Labyrinth abgehen. Wenn die Wände nur ein Pixel dick sind, kannst du auch dikekt auf der Wand gehen, du musst dann nur aufpassen, dass du nicht die Seite wechselst.
Alternativ kannst du auch eine Art Region-Growing-Algorithmus verwenden, soll heißen, du gehst von deinem Startpunkt in iregeneine Richtung und überprüfst, ob das nächste Pixel in der Richtung keine Wand ist. Wenn doch speicherst du die Koordinaten und gehst nach links oder rechts weiter. Wenn du dann wieder zu einer Wand kommst, machst du dasselbe nochmals, usw. Wenn du in einer Sackgasse bist, gehst du einfach vom letzten gespeicherten Koordinatenpaar in die übrig bleibende Richtung weiter, geht dort auch nichts, nimmst du das Kooridinatenpaar davor, und gehst von dort aus in die übrig bleibende Richtung weiter. Ob du einen Ausgang gefunden hast, kannst du überprüfen, indem du prüfst, ob die Koordinaten am Rand der Grafik liegen.
|
|
|
|
| pip |
Themenstarter
Forum-Newbie
|
|
Beiträge: 9
|
|
|
|
Anmeldedatum: 06.04.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 01.05.2008, 03:12
Titel:
|
|
Hi, such eine Funktion mit dem ich folgendes realisieren kann.
Der Benutzer wird bei der Ausführung der M-datei aufgefordert einen Dateipfad einzugeben und wenn der Pfad ungültig ist, soll das Skript beendet werden, aber nicht Matlab selber.
Weiß nicht, wie ich das mit dem beenden hinbekommen soll.
Danke für eure Hilfe.
sg philipp
|
|
|
|
| makl314 |
Forum-Anfänger
|
|
Beiträge: 34
|
|
|
|
Anmeldedatum: 23.01.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 01.05.2008, 10:25
Titel:
|
|
|
Mit der input() Funktion kannst du den Benutzer auffordern eine Eingabe zu machen. In der M-Datei prüfst du die Eingabe auf ihre Richtigkeit, ist sie falsch, kannst du z.B. in einer if-Anweisung eine Fehlermeldung ausgeben und sonst nichts tun (womit die Funktion auch beendet wird).
|
|
|
|
| pip |
Themenstarter
Forum-Newbie
|
|
Beiträge: 9
|
|
|
|
Anmeldedatum: 06.04.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 01.05.2008, 11:33
Titel:
|
|
Es muss doch möglich sein in die if-Anweisung eine Funktion zu schreiben, die das Matlab Skript vorzeitig beendet. Es geht mir nur darum.
sg pip
|
|
|
|
| steve |
Ehrenmitglied
|
|
Beiträge: 2.028
|
|
|
|
Anmeldedatum: 03.09.07
|
|
|
|
Wohnort: Wien
|
|
|
|
Version: R2024a
|
|
|
|
|
|
|
Verfasst am: 02.05.2008, 12:05
Titel:
|
|
|
|
|
| pip |
Themenstarter
Forum-Newbie
|
|
Beiträge: 9
|
|
|
|
Anmeldedatum: 06.04.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 08.05.2008, 02:45
Titel:
|
|
| steve hat Folgendes geschrieben: |
Meinst du so etwas wie
?
Gruß
Alex |
danke, genau das hab ich gesucht:D
sg philipp
|
|
|
|
|
|
|
Einstellungen und Berechtigungen
|
|
Du kannst Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum posten
Du kannst Dateien in diesem Forum herunterladen
|
|
Impressum
| Nutzungsbedingungen
| Datenschutz
| FAQ
|  RSS
Hosted by:
Copyright © 2007 - 2024
goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
|
|
