Hi, habe ein Problem und weis nicht wie ich ran gehen soll.

Man stelle sich ein Feld aus einzelnen Kästchen vor, von denen jedes entweder rot oder gelb ist. Wie kann man jetzt herausfinden, ob es z.B. von einem gelben Kästchen zu einem anderen gelben Kästchen eine Verbindung gibt oder nicht? Die Verbindung kann auch diagonal sein!
Ich bräuchte nur einen Ansatz wie ich das machen könnte, programmieren will ich natürlich selbst versuchen

Bsp.:

RRRRRRR
RRXRRRR
RRRGRRR
RRGGRRR
RRXRRRR

R=Rotes Feld
X und G = gelbes Feld

Hier sind die beiden Felder X miteinander verbunden, auch oben (Diagonal)

Servus!

So was Ähnliches habe ich folgendermaßen gelöst:
Das Feld ist ein 2-dimensionales Array. Ich nehme den x- und y-Wert des Ausgangspunkts und ermittle den Zustand der umliegenden 8 Felder indem ich zu dem x und y jeweils eins addiere bzw. subtrahiere. Ist zwar nicht besonders elegant, funktioniert aber (ballistische Programmierung: Man ziele aufs Ende und programmiere drauf los...).

Gruß,

Adrian

Ja, so hatte ich mir das auch schon geadcht, wie dat mit den 2D-Arrays geht hab ich mir schon rausgesucht, das Problem ist nur wie finde ich jetzt bei einer Größeren Entfernung heraus ob eine Verbindung existiert, weil wenn man in einem Feld von 100 mal 100 Kästchen eine Art Labyrinth hat und manche Wege auch Sackgassen sind, da kann man ja schlecht jede einzelne Wegmöglichkeit Feld für Feld testen oder?

da muss man sich ein hilfsfelder zulegen: Zuerst ist dieses Hilfsfeld das originale. z.b. mit integer-werten, d.h. 0="da nicht lang", 1="da kann man lang gehen".
man startet bei einem Feld und ändert den Feldwert in 2="schon mal da gwesen". Man sucht dann von diesem Feld aus weiter, ob in der umgebung ein Feld mit 1 ist. Ist das so, dann da weiter gehen, und dieses auf 2 setzen usw.
Wenn man damit ans ziel kommt, alles klar.
Wenn nicht, d.h. man kommt in ne sackgasse, dann gibt es kein Feld mit 1 in der Umgebung, sehr wohl aber mit 2 (man ist ja in die Sackgasse reingelaufen). Laufe dann zurück, und setze dabei den wert der zurückgelaufenen Felder auf 0 (oder auf 3="sackgasse"). Beim zurücklaufen jeweils überprüfen, ob es eine weitere Abzweigung mit 1 gibt und dann dalang laufen.
Damit ist auf einfache Art und Weise gesichert, dass man in jede Sackgasse nur einmal reinläuft, da man die Sackgassen Stück für Stück sperrt.
Ist nicht ganz sauber formuliert, aber ich hoffe, dass die Idee klar ist.

also ich würd das anders machen. viel kürzer. und zwar würd ich ne rekursive funktion coden, die jeweils "sich selbst" mit einem der nächsten felder aufruft. dann wär nur noch zu klären, dass man nicht wieder "zurückgeht"... oder geht das gar net und ich bin im moment nur irgendwie blockiert



MrSaint

Bitte nicht Rekursiv! Das gibt ab einer bestimmten Feldgröße einen Stacküberlauf.
Machs besser mit einer repeat-until (oder auch while) schleife und einer Liste, in die du Alle in der nächsten iteration zu prüfende felder schreibst. und dann noch ein array in dem überprüfte felder gespeichert werdeb.

also das dauert da aber seeeeeeeehhhhhhhhhrrrrrrr lange, bis da n stack-überlauf kommt, wenn mann der funktion vielleicht gerade mal 2 "word"s oder sogar nur 2 "byte"s übergibt und die sonst keine lokalen variablen hat (was sie ja auch nich braucht)...


MrSaint

MrSaint hat folgendes geschrieben:

also ich würd das anders machen. viel kürzer. und zwar würd ich ne rekursive funktion coden, die jeweils "sich selbst" mit einem der nächsten felder aufruft. dann wär nur noch zu klären, dass man nicht wieder "zurückgeht"...

Ob man meinen Vorschlag nun rekursiv oder iterativ proggt, ist mir relativ egal. Ich hab nur die Idee vorgestellt, wie man einen Weg findet, wenn einer existiert. Das Problem beim Wegesuchen ist ja, dass das Programm nicht ständig vor dieselbe Wand rennt. Du sagst ja selbst, dass du dies nicht gelöst hast.
Aber das kann man mit dem von mir vorgestellten Verfahren recht effizient machen. Ich glaube auch nicht, dass es ein schnelleres und leichter zu verstehendes gibt.

Hier habe ich mal so ein Pathfinding-Programm gebastelt:

www.delphi-forum.de/viewtopic.php?t=4802

Die Quellen sind auch dabei, du musst also nur ein Knotennetz mit den Feldern und ihren Verbindungen aufbauen, dann kann die Routine so benutzt werden.

Cu,
Udontknow