Breitensuche oder doch lieber ein anderer Algo

[Flogo]

Hi
Ich habe ein zweidimensionales Array mit Pointern, in dem einige Werte nil sind und andere auf Objekte zeigen. Dieses Array stellt ein Koordinatensystem dar. Jetzt will ich zu einer beliebigen Koordinate das nächstliegenste Feld finden, in dem ein Objekt liegt (also Array[x,y] <> nil).

Ist die Breitensuche da der richtige Weg, oder gibt es eine bessere Möglichkeit?

[dizzy]

Für den allgemeinen Fall dürfte das die beste Möglichkeit sein. Soll heissen: Wenn du keine Randbedingungen sicher hast (z.B. einen maximalen Radius in dem sich, und auch nur DAS nächste Element befinden MUSS), dann wirst du kaum eine andere Chance haben.
Auch so Spielchen wie: Erst jeden 2. testen, bei Misserfolg dann doch mit voller Auflösung scannen sind dann leider nicht mehr drin, da du ja das tatsächlich nächste im 1. Lauf verpassen könntest.

Aber wie wäre es, wenn du im Vorfeld das gesamte Array elementweise durchgehst, und dir eine Art "Karte" baust? Also eine Sammlung aller Koordinaten die nicht nil sind. Dann kannst du via Vektorlängenberechnung von einer Koordinate auf den nächsten Treffer schließen ohne groß zu suchen (zumindest vermeidest zu leere Elemente, ist die Frage wie viel schneller das ist als ein paar sqr(t)s. Hängt davon ab welche Feldart häufiger ist!).
Allerdings ist das für dynamische Systeme wieder nicht so irre gut, da du deine "Karte" ständig up to date halten musst. Wenn du allerdings zum Zeitpunkt der Zuweisung eines Elementes seine Koordinaten kennst, dann lässt sich so eine Karte sehr leicht erstellen! Dann fällt das gesamte Scanning weg.

Und wenn du dann noch massig Speicher "verschwenden" willst, so könntest du gleich zu jedem Element a) seinen nächsten Nachbarn speichern (achtung: die verweisen natürlich immer gegenseitig auf sich!), oder gar b) zu jedem Element alle Entfernungen zu allen anderen Elementen. Dann ließe sich (bei b) auch A* bzw. Bestensuche gut einsetzen.

Gruss,
Fabian

[Flogo]

Danke für die ausführliche Antwort.
ALSO:
Das ganze Array ist schon so ein Art Karte
Das Problem, bei den Alternativen ist folgendes:
Ich will von einem "nil-Element" auf das nächste "nicht-nil-Element" kommen (Bei einem "nicht-nil-Element" ist das gesuchte Feld das Feld selber. Sorry war da oben mies erklärt). d.h. Ich kann nichts vorrausberechnen oder extraspeichern
Außerdem würde mir das wirklich zu viel Speicher und Rechenleistung beim Starten kosten. Und wie du schon gesagt hast wird es wahrscheinlich zu aufwändig die Karte zu aktualisieren.

Ich werde also die Breitensuche nehmen.

[OT]
PS: wie kann man den A* dazu benutzen die Entfernungen zu allen Punkten festzustellen? Ich dachte damit findet man (fast) immer den schnellsten Weg?
[/OT]

[dizzy]

Zitat von Flogo:

Ich will von einem "nil-Element" auf das nächste "nicht-nil-Element" kommen

Schlingel. Hätt's ja mal sagen können

Zitat von Flogo:

Ich werde also die Breitensuche nehmen.

Da bleibt dann wirklich nichts anderes mehr. Es sei denn, du musst nur ein Mal von einem nil-Feld ein nicht-nil-Feld finden, und alle weiteren gehen von da aus. Die ließen sich o.g. Verfahren wieder einsetzen.

Zitat von Flogo:

PS: wie kann man den A* dazu benutzen die Entfernungen zu allen Punkten festzustellen? Ich dachte damit findet man (fast) immer den schnellsten Weg?

Mit A* traversiert man einen Graphen dessen Kanten gewichtet sind. So einen Graphen würdest du mit der Speicherung aller Entfernungen + Koordinaten quasi erstellen, und die Entfernungen sind dann die Kantenwichtungen. Allerdings hatte ich einen kleinen Denkfehler drin: Um nur zum nächsten zu kommen ist A* viel zu viel - da reicht ja nen einfacher Vergleich. Allerdings könntest du mit A* auf kürzestem Wege zwischen nicht-nil-Feldern hüpfen. Aber auch hier ein Denk-"Lag" bei mir: Du kommst ja eh an sich von jedem Feld auf jedes andere... Also vergiss das mit A* . Dein Graph wäre komplett genug um ohne Suchalgo auszukommen...
Und: A* an sich findet immer den schnellsten/kürzesten (das muss nicht das selbe sein!) Weg. Der Knackpunkt dabei sind die Bewertungsroutinen, die die Kanten- und Knotenbewertungen machen. Das sind idR nur Schätzwerte, und je schlechter geschätzt, desto schlechter kann A* damit arbeiten.
Aber das ist ja eh hinfällig .

Mir kommt da grad noch eine (doofe) Idee. Mal sehen wie praktikabel das wird :
Stell dir jedes nicht-nil-Feld als schwarzen Pixel vor, und alle anderen als weisse Pixel. Nun lässt du die schwarzen Pixel "ausbluten", so wie mit einem Unschärfefilter. Ergebnis wäre also eine "Bitmap" (ein weiteres 2D-Array mit Zahlenwerten reicht ja), die einem "Gebirge" ähnelt: weiss=hoch; schwarz=tief. Nun, wenn du eine Koordinate hast, suchst du in Richtung des dunkelsten Nachbarwertes weiter. Damit "fällst" du quasi automatisch in die richtige Richtung, und landest zwangsläufig auf dem nächsten gültigen Feld, da das durch keine dunkleren Werte umgeben sein wird.
Allerdings wäre diese "Höhenkarte" auch immer wieder neu zu erstellen, wenn sich an der Struktur der Ausgangsdaten etwas ändert.

Aber die Idee ist doch innovativ, gell!? Vllt. lässt sich da ja echt was draus bauen - war grad ein Spontaneinfall der nicht bis in alle Details durchdacht ist. Ich bin ja fast drauf und dran das mal auszuprobieren... morgen .

Gruss, und danke für eine interessante Frage ,
Fabian

\\edit: kleinen Logikfehler ermordet... --- edit2: einen ähnlichen Kameraden entfernt...

[Flogo]

[quote="dizzy"]So einen Graphen würdest du mit der Speicherung aller Entfernungen + Koordinaten quasi erstellen, und die Entfernungen sind dann die Kantenwichtungen.
[...]
Dein Graph wäre komplett genug um ohne Suchalgo auszukommen...
[/qoute]
Du nimmst mir die Worte aus dem Mund. Also von der Tastatur, oder wie auch immer.

Vielleicht sollte ich mal ausführlicher erklären wozu das Raster eigentlich da ist:
in einem Spiel kann man an bestimmten Stellen laufen, an anderen nicht.
Das Raster ist eine Grobe Karte (die feine Karte speichert für jeden Punkt den Z-Wert). Kann man in den 5x5 Pixeln, die ein Rasterfeld symbolisieren laufen, dann wird dort ein Knoten erstellt. Dieser Knoten enthält ein Array mit max. 8 Kanten, die auf die 8 Nachbarn zeigen - wenn es sie gibt - und die Gewichtung enthalten.
Wenn ich jetzt im Bild irgendwo auf den Weg klicke, wird der Weg (mit A*) gesucht, gefunden und gelaufen
Wenn ich aber nicht auf den Weg klicke sondern daneben (soll ja vorkommen), dann muss der Punkt auf dem Weg gefunden werden, der dem Punkt, auf den ich geklickt habe, am nächsten ist.

Deine Idee klingt zwar echt gut (oder wenigstens "innovativ") aber ich glaube ich werde mich doch an die Breitensuche halten. Das aktualisieren ist mir so einfach zu aufwändig

trotzdem vielen Dank für die Anregungen

[dizzy]

Tjo, bei sich ständig verändernder Grundlage denke ich auch, dass das das schnellste/einfachste wird.
[ot]
Interessantes Projekt was ihr da habt! Euer Grafik-Guru ist wohl auch nicht wenig begnadet, was!? Besonders das Logo ist äusserst kunstvoll, da es alle Buchstaben, ausgenommen das "t", vom Namen enthält. Echt klasse!
[/ot]

Viel Erfolg dabei weiterhin!
Fabian

[Flogo]

Danke, danke! Nach Silvester gibts vielleicht wieder Neuigkeiten.


und das 't' denken wir uns einfach mal mit viel Phantasie in das 's' mit rein