Frohes Neues erstmal
Also ich versuchs nochmal zu erklären.
Es geht um Graphentheorie wenn ich von Graph spreche. Es geht nicht um irgendwelche bestimmten Containerimplementationen, sondern allein um die Logik dahinter. Die Graphenklasse wird von mir selbst geschrieben. Ich möchte einen Graphen über meine Spielwelt spannen. Dies bringt halt Vorteile wie zb Wegfindung etc. Sollte klar sein
Der Graph wird über Floodfill bestimmt. Floodfill ist ja ein Algorithmus, der nicht nur zum füllen von Farbflächen gedacht ist, auch wenn er meist dort eingesetzt wird
Stellt euch eine Zweidimensionale Welt vor. An der Stelle (5,5) wird nun fest der erste Knoten des Graphen gesetzt. Jetzt guckt der Algorithmus in einem bestimmten Abstand um diesen Knoten ob er neue Knoten erzeugen kann, oder ob Objekte im Weg sind.
Sagen wir Abstand ist 1. Also würden jetzt die Punkte (4,5),(5,4),(6,5),(5,6) überprüft und gegebenfalls als Knoten dem Graph hinzugefügt. Das geht dann rekursiv(oder von mir aus auch iterativ, je nach Umsetzung) für jeden weiteren Knoten so. Am Ende hat man einen Zusammenhängenden Graph in der Welt.
Soviel zum Hintergrund. Mein Problem ist einfach nur wenn ich Beispielsweise die Knoten (4,5) und (5,4) expandieren würde, würden beide Knoten zu einer neuen Koordinate (4,4) führen. Sagen wir (4,4) ist frei von Kollision und soll so als neuer Knoten dem Graph hinzugefügt werden. So würden zwei bzw. mehrere Versionen des Knotens hinzugefügt. einmal wenn (4,5) expandiert wird und einmal wenn (5,4) expandiert wird. Jetzt könnte man vor jedem einfügen in den Graphen checken, ob bereits ein Knoten mit genau den Koordinaten vorhanden ist, was ich aber für relativ umständlich halte. Vielleicht gibt es ja auch keine andere Lösung
Das Problem hiermit trifft eigentlich fast jedes mal auf wenn ein Graph erst zur Laufzeit bestimmt wird. Gleiches Problem wäre bei der Graphenlösung vom Rubiks-Cube oder der Türme von Hanoi, da dort auch durch verschiedene Wege der gleiche Knoten erreicht werden kann. Ich denke für das Problem sollte es eine Lösung geben.
Hoffe das war diesmal verständlicher