spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Habe jetzt heute im Gespräch mit nem Arbeitskollegen eine einigermaßen zufriedenstellende Lösung gefunden. Vielleicht ist es ja für den ein oder anderen interessant.
Die beste Lösung wäre es eine Indizierung für die Knoten zu finden. Bei dem Problem mit den Koordinaten können natürlich die Koordinaten als Index in einer Hashmap oä benutzt werden. Beim Rubiks-Cube könnte man den Index aus den Feldern und Farben zusammensetzen. Die Idee(Die ohne mathematischen Beweis sinnvoll erscheint) setzt sich folgendermaßen zusammen:
Jedes Feld des Würfels stellt eine Stelle der Zahl dar. Jede Farbe bekommt einen Zahlenwert. Sagen wir mal Rot ist 1, Blau ist 2 und so weiter. Ist stelle 1 rot, ist die erste Zahl vom Index also 1. Ist die zweite Stelle blau kommt an die zweite Stelle eine Zwei. Ist die dritte wieder rot würde an Stelle 3 eine 1 kommen. Das macht man nun für jedes Feld des Würfels und hat hinterher einen Index mit 54 Stellen. Ist natürlich nicht besonders schön, liefert aber eindeutige Indizes. Die Werte müssen natürlich nicht direkt als eine Zahl gespeichert werden(Integer wäre dort ja eh nicht geeignet ), könnten jedoch auf mehrere kleinere Integer aufgesplittet werden. Wie auch immer man das jetzt genau umsetzen möchte. Ein bisschen Kreativität soll ja bleiben
So hätte man für eine Überprüfung eine Laufzeit von O(1).
Ansonsten könnte man die Liste aller Knoten durchlaufen und überprüfen ob der Knoten schon vorhanden ist. Habe da nochmal drüber nachgedacht und die Laufzeit hierfür wäre O(n) bei n Knoten, was auch ok wäre
Naja vielleicht hilfts ja irgendjemandem weiter.

Die Idee für die Indizes im Cube hatten wir, da dort durch ein bisschen denken zu erkennen ist, dass wirklich kein Index doppelt vergeben wird. Klar lässt sich hierfür sicherlich eine bessere Lösung finden, was aber ohne mathematischen Beweis nicht ohne weiteres funktionieren würde. Wenn ich nur mögliche Stellungen des Würfels als Index zulassen würde, müsste ich vorher überlegen bzw. vorberechnen welche Stellungen möglich sind. Genau das soll ja verhindert werden.
Und zum Floodfill. Klar, normalerweise wird er auf Arrays angewand. An sich sagt Floodfill jedoch nicht mehr aus als das ich in alle Richtungen gucke und dann mache was auch immer ich tun will. Da die Vektoren in meinem Fall float Werte haben, eignen sie sich nicht als Index in einem Array. ein Vektor A(5.3f, 7.8f) könnte zum Beispiel nicht ohne weiteres hierfür genutzt werden. Dann akzeptiere ich lieber die lineare Laufzeit beim durchsuchen der Knoten.

Würde sich auch eignen. Stimme ich dir zu.