spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hey,
Ich möchte in meinem Spiel automatisch erstellte Graphen in meinen Levels haben. Wer das Buch Programming Game AI by Example kennt, kennt vielleicht auch dessen Ansatz. Mit Floodfill wird dort der Graph bestimmt. Mein Problem dabei ist aber das ich mir nicht sicher bin wie ich doppelte Knoten verhindern kann und dabei performant bleibe.
Als Veranschaulichung für das Problem:
Stell dir vor du willst Türme von Hanoi mit einem Graphen lösen. Der Graph wird Schritt für Schritt expandiert. Man möchte keine Knoten doppelt haben. Mein wirklich naiver Ansatz wäre bei jedem Neuerzeugen von einem Knoten zu gucken ob dieser Knoten schon irgendwo im Graph vorhanden ist. Ich vermute aber das geht auch mit schönerer Laufzeit
Hoffe ihr könnt mein Problem nachvollziehen.
Lieben Gruß und schonmal guten Rutsch.
Sören

Die Knoten des Graphen sollen Koordinaten darstellen. Und beim erzeugen werden nun Knoten doppelt erstellt. Neue Knoten die aber an den gleichen Koordinaten stehen. Aber für den Graph ist es erstmal der selbe Knoten. Man könnte jetzt vor jedem einfügen überprüfen ob schon ein Knoten mit genau diesen Koordinaten vorhanden ist. Wobei ich halt vermute das das einfacher geht. Ich glaub auch weniger durch die Wahl der Container. Hoffe das hat dir weitergeholfen

Nein es soll ein ungerichteter Graph für Wegfindung etc über die Spielwelt gelegt werden. Und dieser Graph soll automatisch berechnet werden.

Ich möchte die Karte ungern Tilebasiert regeln. Die Idee ist, dass man eine Karte mit Objekten hat. Man setzt irgendwo in der Karte einen Knoten für den Graph fest. Und mit Floodfill vervollständigt man den Graphen. Man geht halt von diesem Knoten ein Netz von allen möglichen Nachfolgerknoten durch, bis die Map komplett gefüllt ist. Wenn ein Knoten einen mindestabstand zu Kollidierbaren objekten nicht einhalten kann, so wird dieser natürlich nicht gesetzt. Dadurch wird automatisch ein Bewegungsgraph erzeugt, auf dem alle möglichen Punkte der Karte erreichbar sind. Mir gehts jetzt um den Graphen und die erzeugung der Knoten. Die Knoten werden zwar durch indizes auseinandergehalten, die Indizes haben aber nichts mit den Koordinaten zutun.

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

Ich hätte vielleicht dazu sagen sollen das die Vektoren aus float Werten bestehen. Hatte auch erst über ein mapping mit Koordinaten als Indizes nachgedacht, wird aber mit float Werten relativ schwer. Würde sich da dann nicht vielleicht eine Hashtable anbieten?
Hmm naja bleibt dann nur die Frage wie man das Problem in anderen Fällen lösen sollte. Beispiel ein State Graph mit dem ein Rubiks Cube gelöst werden soll. Aus den Zuständen kann ich ja schlecht Indizes machen bzw nur unter großen Aufwand.