Hi,

ich bastel im moment an einem kleinen Rennspiel bei dem die Strecke komplett zufällig generiert werden soll.
Mir fällt nur im moment grade keine tolle möglichkeit ein dies zu tun..

Meine strecke wird durch eine Spline-curve.

Wenn ich also meine Curve so aufbaue:



würde eine strecke entstehen die erst geradeaus geht, dann eine linkskurve macht und dann wieder geradeaus.
Durch die Spline ist es eine schön sanfte linkskurve und nicht einfach eine 90° abknickende

Soo... das problem ist jetzt, ich möchte:

a) Einen rundkurs haben - also die zufällig erzeugte strecke muß eine geschlossene kurve bilden.
Ich kann also nicht immer einfach random mäßig werte drauf addieren sondern muß eben zusehen das ich irgendwann wieder richtung start komme um die strecke zu schließen.

b) Die strecke kann sich beliebig im raum rum schlängeln.. also es ist nicht auf X/Z limitiert, sondern die punkte können komplett wild im raum verstreut sein. Also auch loopings etc sind problemlos möglich.

Ein looping sähe z.B. so aus:




c) Die strecke darf nicht mit sich selbst intersecten. Also grob gesagt kann man der spline einfach einen radius geben, und diese röhre darf dann nicht mit sich selbst kollidieren.


Tja... und mir fällt jetzt nichts ein wie ich unter den 3 aspekten schöne zufällig generierte strecken machen kann.

Wenn man z.B. von nem kreis ausgeht am anfang und nur die einzelnen punkte des kreises verschiebt, würde zwar eine geschlossene strecke entstehen wo die punkte auch gescheit liegen (also alle etwa gleichen abstand haben), aber die streckenführung wäre wohl ziemlich langweilig...

Hat jemand ne idee? :/

Aya~

Nur kurzes Brainstorming von mir zu später Stunde...

Mir fällt spontan etwa sowas ein: Starte mit drei Punkten und verbinde sie zu nem Dreieck (mit deinem Spline hast du dann nen langweiligen Rundkurs mit drei Kurven).
Verschiebe diese drei Punkte um zufällige, aber einigermaßen gleichlange Vektoren (etwa gleichlang, damit im Laufe des Prozesses nicht endlos lange, langweilige Geraden entstehen).
Füge zwischen jeweils zwei Punkten wieder einen neuen ein und beginne von vorn.

Alternative:
Erzeuge eine zufällige Punktmenge.
Wähle einen Punkt daraus aus und verbinde ihn mit einem zufälligen nächsten Punkt, der noch nicht mit einem anderen verbunden ist.
Fahre solange fort, bis alle Punkte verbunden sind.

Wenn du zwischendurch vllt. prüfst, ob die Punkte sich nicht zu Nahe kommen, und danach mal nachschaust, ob dabei nicht zufällig Strecken entstanden sind, die übermäßig lange geradeaus gehen (die kannst du ja dann unterbrechen, in dem du einfach noch nen Punkt einschiebst), müsste das auch ein nettes Gewirr geben.

Wenn du willst, kannst du ja so Dinge wie Loopings während des Prozesses bei Schritt zwei einfügen, gib irgendwo vor, wie die Koordinaten relativ zueinander liegen müssen, damit ein Looping entsteht und füg die dann entsprechend ein. Kannst ja noch ne Zufallsvariable für die Größe einfügen, damit nich jeder Looping gleich ist.

Das kannst du so lange wiederholen, bis den Kurs beliebig kompliziert ist.

Das schwierigste sollte die Überprüfung der Intersection werden denke ich, da fällt mir auch nichts Gescheites zu ein...

Ich würde auf anhieb folgende methode nehmen.
-erstelle ein Kreis aus 2 kubischen Bezierkurven mit durchmesser D
-iter=0
-steps=5
loop:
-R=D/((iter+1)*2)
-zerlege die Kubischen bezierkurven in jeweils 2 Teile
-die neuen Mittelpunkt werden mit einem zufälligen 3D Vector(x,y,z) addiert( vec(rnd(R*2)-R),rnd(R*2)-R),rnd(R*2)-R) )
-iter=iter+1;
-wenn iter<steps springe zu ersten Schritt

Sollte eigentlich gute strecken raus werfen, da man durch den Durchmesser am anfang das ganze super regulieren kann und mit jeder Iteration sich der zufalls verschiebung halbiert(r wird halbiert). Man hat also 2 Stützpunkte und mit jeder iteration gibt es neue und die neuen Punkte dazwischen bringen eine art rauschen in den den streckenverlauf. Kubische berzierkurven eigenen sich sehr gut, da man diese problemlos in 2 teile zerlegen kann , im gegensatz zu quadratischen.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Hallo,

ich würde so vorgehen :

1. Konstruiere einen zufälligen ebenen Graph

2. Suche in diesem Graph einen zufälligen geschlossenen Kreis ( z.B. zwei zufällige Punkte generieren und zwei Pfade konstruieren, die sich nicht schneiden dürfen )

3. Die Knoten des Kreises dann als Kontrollpunkte für die Splines nehmen


Viele Grüße
dj3hut1

P.S. : Als Alternative kannst du für den Kreis ( in der Graphentheorie einfach eine Bezeichnung für einen geschlossenen Pfad ) auch 3 oder 4 zufällige Startpunkte nehmen, bei mehr als 3 wird es allerdings schwerer herauszufinden, welche Punkte nebeneinander liegen.
Enthält der Kreis zu viele Kurven, entweder ein paar Punkte entfernen oder am Anfang einen größeren Knotenabstand wählen.

_________________
Wenn Gauß heute lebte, wäre er ein Hacker.
Peter Sarnak, Professor an der Princeton University

Hab vor einiger Zeit schonmal probiert einen zufälligen Graphen zu erzeugen.
Das sieht dann ungefähr so aus : http://algoria.de/files/planar.jnlp ( Quellcode : http://algoria.de/files/planar.zip )

Für die Pfad- oder Kreissuche müsste man Breitensuche ( ausgehend jeweils von Anfangs- und Endpunkt ) oder Djikstra ( falls man den kürzesten Pfad sucht ) probieren.

_________________
Wenn Gauß heute lebte, wäre er ein Hacker.
Peter Sarnak, Professor an der Princeton University