Hallo allerseits,

Nachdem meine Programmiererei in den letzten Wochen eigentlich recht sauber ging, stehe ich nun vor einer interessanten Fragestellung. Da ich ja einen Zufallsgenerator für das Füllen von Sektoren implementiere, gehts auch darum, die Objekte im Raum zu platzieren.
Das soll ziemlich zufällig ablaufen. Allerdings muss ich auch aufpassen, dass es nicht zu Kollisionen zwischen den Objekten kommt. Dazu vereinfache ich die Objekte zu Kugeln mit festem Radius. Die einfachste Variante, die mir für das zufällige Platzieren von Objekten dann einfällt, ist Try'n'Error. D.h. Zufallswert generieren und schauen, ob er kollidiert. Wenn ja, dann neuen Wert generieren und so weiter. Das kann je nach Füllung der Sektoren und Zufallswerten natürlich eine ganze Zeit dauern. Außerdem müsste man irgendwie eine Überfüllung, also den Fall, wenn keine Objekte mehr in den Sektor passebn, erkennen und darauf reagieren.

Gibt es da eine bessere Lösung? So eine Möglichkeit, einen Zufallsgenerator zu implementieren, der bestimmte Wertebereiche einfach auslässt? Diese lägen ja nicht am Anfang oder Ende der Werteskala sondern auch mal mitten drin.
Am allerbesten wäre noch, wenn man auch noch Gebiete festlegen könnte, wo Treffer wahrscheinlicher sind als in anderen.

Irgendwelche Vorschläge?
~Horazont

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

Naja, so oder so hast du ja am Ende ein Raster, bei random(100) z.B. ein Raster mit 100 Stufen (Das sei mal der Wert, den ich für das Beispiel festsetze)
Du könntest alle Punkte des Rasters durchgehen (bei dir wahrscheinlich dann 100x100x100) und wenn der Punkt frei für ein Objekt des Radius r ist, das eingefügt werden soll, wird er in eine dynamische Liste gehauen (Wobei ein vorbeidefiniertes Array mit 100³ Elementen hier natürlich schneller ist)
Wenn die erstellt ist mit maximal 100³ Elemente oder aber z.B. auch 0 (=> Ausschluss), dann kannst du einfach mit random(Listengröße) einen Punkt auswählen. Total zufällig.

Hier muss man natürlich schauen, wie man optimieren kann. Aber was anderes fällt mir spontan nicht ein und ich glaube, da ist try'n'Error schneller. Im Zweifel kann man "Kein Objekt kann mehr reingesetzt werden" ja auch so sehen, wenn z.B. 1.000 mal kein Platz frei war. Oder wenn der "1.000 Plätze voll"-Fall eintritt, benutzt du meine Methode um auf Nummer Sicher zu gehen.

_________________
Denn wer nur schweigt, weil er Konflikte scheut, der macht Sachen, die er hinterher bereut.
Und das ist verkehrt, denn es ist nicht so schwer, jeden Tag zu tun als ob's der letzte wär’.
Und du schaust mich an und fragst ob ich das kann.
Und ich denk, ich werd' mich ändern irgendwann.
_________________Farin Urlaub - Bewegungslos

Ich weiß nicht wirklich ob eine Idee effektiv ist:

Ich würde den Raum in einzelne Würfel aufteilen, so dass je Würfel genug Platz ist, dass ein Objekt trotzdem noch in diesem kleinen Raum zufällig platztiert wird, danach wird dann der Abstand zu den Objekten in den Nachbarwürfeln getestet (wobei da nun irrelevant ist ob es dynamisch erzeugte oder statische Objekte sind) udn wenn dieser zu klein ist, wird das Objekt verworfen...

Das macht natürlich nicht viel Sinn wenn das andauernd berechnet wird...

Das beste wäre du würdest uns sagen, ob es nur einmal generiert werden soll und ob eine bestimmte Anzahl von Objekten hinzugefügt werden muss.

cuz
bubble

_________________
Wenn Worte nichts als Worte sind,
dann müssen's Steine sein!
Solange - bis sie pleite sind - schmeißt Fensterscheiben ein!
- Fidl Kunterbunt -

Machs doch so wie ich in meinem Zufallsdungeongenerator. Ich nutz da ja für die Raumplatzierung (was ja letztendlich genau dein Problem ist, bei mir halt nur in 2D) einen Qaudtree. Du müsstest dann nur nen Octree wählen, und bei der Zerteilung leicht zufällig die Größe variieren, und am Ende hast du einen zufällig unterteilt wirkenden Octree in dem du dann deine Objekte schön und effizient platzieren kannst. Da sich im Octree ja Würfel nie überschneiden und du eine Baumstruktur hast lassen sich die Objekte dann kinderleicht und performant platzieren, ohne dass du prüfen musst ob an der gewollten Position schon ein anderes Objekt liegt.

_________________
www.SaschaWillems.de | GitHub | Twitter | GPU Datenbanken (Vulkan, GL, GLES)

Hm... Danke für die Anregungen. Es geht auf jeden Fall um einmalige Generierung, allerdings durchaus auch mit "vielen" Objekten (so > 500 pro Sektor könnens schon mal werden).
Mit den Baumunterteilungen hab ich jetzt noch keine Erfahrung. Was ich mich da Frage ist, ob es da zu einem (sichtbaren) Rasterungseffekt kommt. Denn das ist etwas, was ich auf jeden Fall vermeiden will. In den Originalsektoren hat man teilweise Asteroidenfelder, wo diese recht dicht liegen, aber sie sehen trotzdem nicht aus wie in einer Reihe gesät. Wenn ich mich jetzt richtig an deinen Dungeon erinnere, Sascha, lagen die Räume doch in einem Raster, selbst wenn dieses unterteilt war.

Was ich vielleicht nicht ganz klar gemacht habe ist halt, dass es sich um einen theoretisch unendlich großen Raum handelt, der aber einen Erstellungsschwerpunkt in einem Quader mit einer einstellbaren Seitenlänge hat. Dort wird sich das meiste Abspielen. Allerdings werden auch Objekte außerhalb dieses Quaders platziert, hauptsächlich wohl in einem Quader dessen Kantenlänge doppelt so groß ist.

Bei den Raumunterteilungsbäumen könnte ich mir das noch vorstellen, wenn ich das mit einem Array mache, wirds wohl eng, zumal ich ja Rasterung vermeiden will und diese Daten für bis zu 336 Sektoren gleichzeitig parat haben muss (Das Wirtschafts-Generierungs-Modul muss darauf zurückgreifen können).

Ich denke aber, dass eine Liste mit möglichen Werten vielleicht sogar machbar ist. Geschwindigkeit ist ja nicht das Hauptziel bei dieser Sache, da man wohl nicht allzu oft sein Universum neu aufbauen lässt. Vielleicht macht man mal zehn, zwanzig Durchgänge hintereinander, weils einem noch nicht 100%ig gefällt, aber ich denke, danach ist auch Schluss.
Mit so einer Liste könnte man dann auch die Gewichtungen realisieren (selbst wenn nur in diskreten Spektren), indem solche Einträge mit höherer Wahrscheinlichkeit doppelt oder dreifach eingefügt werden.

Noch weitere Ideen?

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

Wenn eine Sache nicht zeitkritisch ist, würde ich deine Try'n'Error Methode wählen. ^^ Ich meine, du redest von einem (Sonnen)system. Wenn nach vielleicht 1000 Versuchen immernoch keine Stelle frei ist, sieht dein System eh "komisch" aus...

_________________
Denn wer nur schweigt, weil er Konflikte scheut, der macht Sachen, die er hinterher bereut.
Und das ist verkehrt, denn es ist nicht so schwer, jeden Tag zu tun als ob's der letzte wär’.
Und du schaust mich an und fragst ob ich das kann.
Und ich denk, ich werd' mich ändern irgendwann.
_________________Farin Urlaub - Bewegungslos

Du kannst ja einfach mal berechnen wie groß die Wahrscheinlichkeit ist das du nach 10 Iterationen der Try'n'Error-Methode immer noch keine freie Position gefunden hast:

Der Einfachheit nehmen wir mal an du hast ein 100x100x100 Raster und du willst 500001 Objekte platzieren.
Wenn 500000 Objekte bereits platziert sind ist die Chance einen bereits belegten Platz zu treffen
500000 / 1000000 = 0.5, also 50%. Und das dann 10 mal hintereinander....wäre 0.5^10 = 0.000976, also die Chance dafür ist unter 0.1%. Gut, da du 500000 Objekte platzierst wird die 0.1% Chance natürlich einige Male auftreten. Aber mit steigender Anzahl Versuche geht die Chance recht schnell gegen 0. Kritisch wird es nur wenn du den Platz fast vollständig füllen willst. (*)

=> Try'n'Error ist die einfachste und schnellste Methode.

(*) In dem Fall kann es sinnvoll sein umgekehrt vorzugehen und die Orte zu wählen an denen sich kein Objekt befinden soll.

_________________
Yeah!

Also wenn die Anzahl der Vorhandenen freien Plätze bekannt ist, oder sich der gesamte Platz gleichmäßig unterteilen lässt, kann man doch diese Plätze alle in einer Schleife durchgehen und jedes mal Würfeln (ich nehme mal an dass man da ne prozentuale Wahrscheinlichkeit ganz gut einarbeiten kann). Ist der Wurf über der Wahrscheinlichkeit, gibts kein Objekt an dieser stelle, andernfalls wird das Objekt erzeugt. So kannst du über die Wahrscheinlichkeit die ungefähre Anzahl der Objekte festlegen (oder den Algo solange laufen lassen, bis die gewünschte Zahl erreicht wurde).

Edit: Über einen Quad/Octtree könnte man dann theoretisch eine Verteilungsdichte ermitteln und feststellen, ob es Ballungsgebiete gibt, die evtl. weiter verteilt werden müssten. Nachteil ist, dass die Schleife extrem lang werden kann, wenn viel Platz vorhanden ist. Da wäre die try'n'error Methode sehr viel effizienter.

_________________
Klar Soweit?