Ein Ausflug zu den Sternen

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
Antworten
Orioner
Beiträge: 102
Registriert: Mo Dez 10, 2012 10:52 am

Ein Ausflug zu den Sternen

Beitrag von Orioner » Sa Jun 29, 2013 5:00 pm

Ich möchte einen Map-Editor programmieren. Er soll eine Sternenkarten erzeugen, mit bis zu 99 Sternen, die zufällig auf der 601x601-Karte platziert werden. Dabei sollen diese Sterne nicht zu dicht beieinander liegen und auch nicht zu dicht am Rand. Die betreffenden Positionen, die mir zu dicht am Rand währen oder die zu dicht an bereits erzeugten Sternen liegen würden, sollen quasi mit einer weniger großen Wahrscheinlichkeit "gewählt" werden, als normal.

Hierbei gelten noch einige Rahmenbedingungen: Die einzelnen Felder (361.201 an der Zahl) sollen durchnummeriert werden (ich sehe den Vorteil der Verwendung von Koordinaten nicht).

Wenn es zu Demonstrationszwecken einfacher sein sollte, kann das Prinzip auch anhand von weniger Sternen und einer kleineren Karte dargestellt werden.

Wie würdet ihr vorgehen?

Mein Ansatz:

Ich vergrößere die Karte, die programmtechnisch aus einem Array besteht, um 2 Felder pro Position. Will heißen: Ich habe 1.083.603 Felder, wobei jede Position nun aus insgesamt 3 Feldern besteht. Das Array wird nun auf Null gesetzt, was bedeutet, dass alle Felder die gleiche Wahrscheinlichkeit haben, als Position für einen Stern ausgewählt zu werden.

Sobald ich einen Stern per Zufall habe setzen lassen, schnappe ich mir dessen Position und verändere das oben genannte Array so, dass nicht mehr jedes Feld die gleiche Wahrscheinlichkeit hat, "gewählt" zu werden.

Das erreiche ich, indem ich das Feld meines Array, an dem sich der erste Stern befindet "sperre", indem ich alle 3 Felder an der Stelle von 0 auf 1 setze, die 8 Positionen drumherum ebenfalls. Alle Felder rund um die Position meines Sterns, die noch eins weiter außen liegen, bekommen zwei von drei Feldern auf 1 gesetzt, noch weiter außen liegende Positionen bekommen noch ein Feld auf 1 gesetzt und alle übrigen behalten alle drei Felder auf 0, sodass sich für sie nichts ändert (an der Wahrscheinlichkeit).

Kann man diesen Ansatz wählen? Oder fällt euch etwas besseres ein, weil eleganter oder einfacher umzusetzen?

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Ein Ausflug zu den Sternen

Beitrag von Xin » Sa Jun 29, 2013 7:44 pm

Orioner hat geschrieben:Ich möchte einen Map-Editor programmieren. Er soll eine Sternenkarten erzeugen, mit bis zu 99 Sternen, die zufällig auf der 601x601-Karte platziert werden. Dabei sollen diese Sterne nicht zu dicht beieinander liegen und auch nicht zu dicht am Rand.
...
Hierbei gelten noch einige Rahmenbedingungen: Die einzelnen Felder (361.201 an der Zahl) sollen durchnummeriert werden (ich sehe den Vorteil der Verwendung von Koordinaten nicht).
Naja, die Frage ist, wie Du diese 361.201 Felder anordnest. Liegen die Reihen hintereinander, wird das kompliziert. Da Du den Vorteil von Koordinaten nicht siehst, stellt sich mir die Frage, wie Du unterscheidest, dass ein Stern, der 601 Felder weiter liegt, direkt unter dem vorherigen Stern liegt.
Orioner hat geschrieben:Mein Ansatz:
Ich verstehe den Ansatz nicht. Da Du Felder sperrst, kannst Du genauso gut fragen, ob ein Feld in der Nachbarsschaft bereits gesetzt wurde. Diese Anfrage kannst Du kombinieren der Frage, ob Du gerade am Rand liegst.

Du kannst z.B. Dir die Anzahl der Sterne, die am Rand liegen merken und in diese Berechnung eingehen lassen. Bei der Frage, ob Du den Stern hier setzen möchtest, baust Du Dir eine Formel auf, die die Distanz zum Rand mit der Anzahl der Sterne in relevanter Entfernung eingeht - in Abhängigkeit zu der Entfernung der relevanten Sterne.
Da kommt eine Fließkommezahl raus. Liegt sie über einem Grenzwert, suchst Du Dir eine andere Position.

Ich sehe nicht, dass Du die 2. Dimension einfach ignorieren solltest...
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Orioner
Beiträge: 102
Registriert: Mo Dez 10, 2012 10:52 am

Re: Ein Ausflug zu den Sternen

Beitrag von Orioner » Sa Jun 29, 2013 9:04 pm

Xin hat geschrieben:Naja, die Frage ist, wie Du diese 361.201 Felder anordnest. Liegen die Reihen hintereinander, wird das kompliziert. Da Du den Vorteil von Koordinaten nicht siehst, stellt sich mir die Frage, wie Du unterscheidest, dass ein Stern, der 601 Felder weiter liegt, direkt unter dem vorherigen Stern liegt.
Du hast Recht, vielleicht sollte ich wirklich "in die zweite Dimension gehen". Allerdings gibt es einen, wie ich finde recht gewieften Trick, wie man 2 Dimensionen eines Feldes auf eine Dimension abbilden kann:

Nehmen wir an, das Feld ist 10x10 Felder groß. Sein Koordinatenursprung befindet sich links oben. Dann ist das Feld mit den Koordinaten 0,0 Feld 0, das Feld mit den Koordinaten 1,0 Feld 1, 2,0 -> Feld 2, usw.

Jetzt nimm das 11. Feld! Es hat die Nr. 10 (da wir ja bei 0 angefangen haben zu zählen) und liegt genau unter dem Feld mit der Nr. 0. Was haben wir gemacht? Wir haben eigentlich nur 10 zum Wert 0 hinzuaddiert und sind so zum ersten Feld in der 2. Zeile gelangt.

Worauf will ich hinaus:
Wenn ich die Dimensionen des Feldes kenne, kann ich immer aus einer "eindimensionalen" Zahl auf deren Koordinaten schließen und umgekehrt.

Beispiel: x = 2, y = 3 (Ursprung: 0, 10x10 Felder)
Nr. des Feldes: 32 = 3 * 10 + 2

Wir haben soeben die Koordinaten eines Beispielpunkts in seine Position des Zahlenraums von 0-99 verwandelt. Dies lässt sich auch umkehren. Ahnst du, wie? Was meinen die anderen?

Eine Frage zum Schluss: Meintest du wirklich, du verstehst meinen Ansatz nicht, oder meintest du eher, du verstehst nicht, warum ich einen solchen verfolge? (Ich bin gerade etwas am zweifeln, ob ich den Sachverhalt einleuchtend geschildert habe.)

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Ein Ausflug zu den Sternen

Beitrag von Xin » So Jun 30, 2013 11:14 am

Orioner hat geschrieben:Du hast Recht, vielleicht sollte ich wirklich "in die zweite Dimension gehen".
Solange Du zweidimensionale Probleme hast, wirst Du da nur wenig drumrum kommen.
Orioner hat geschrieben:Allerdings gibt es einen, wie ich finde recht gewieften Trick, wie man 2 Dimensionen eines Feldes auf eine Dimension abbilden kann:

Nehmen wir an, das Feld ist 10x10 Felder groß. Sein Koordinatenursprung befindet sich links oben. Dann ist das Feld mit den Koordinaten 0,0 Feld 0, das Feld mit den Koordinaten 1,0 Feld 1, 2,0 -> Feld 2, usw.

Jetzt nimm das 11. Feld! Es hat die Nr. 10 (da wir ja bei 0 angefangen haben zu zählen) und liegt genau unter dem Feld mit der Nr. 0. Was haben wir gemacht? Wir haben eigentlich nur 10 zum Wert 0 hinzuaddiert und sind so zum ersten Feld in der 2. Zeile gelangt.
Das ist ein sehr üblicher Trick, der von C auch direkt unterstützt wird, sofern Du die Größe des Feldes vorher kennst.

In dem Fall arbeitest Du aber trotzdem mit zweidimensionalen Daten und wenn Du ein zweidimensionales Problem lösen willst und eine 1 <-> 1 Zuordnung von eindimensionalen Feld und zweidimensionalen Daten hast, dann geht das auch.
Dein Problem bleibt aber zweidimensional.
Orioner hat geschrieben:Eine Frage zum Schluss: Meintest du wirklich, du verstehst meinen Ansatz nicht, oder meintest du eher, du verstehst nicht, warum ich einen solchen verfolge? (Ich bin gerade etwas am zweifeln, ob ich den Sachverhalt einleuchtend geschildert habe.)
Ich habe nichts dagegen, dass Du Deine Daten in einem eindimensionalen Array speicherst. Aber Du hast halt kein lineares Problem. Also muss Deine Betrachtung nunmal zweidimensional sein. Wie die Daten dabei im Speicher liegen, spielt keine Rolle.
Du musst halt aufwendiger bestimmen, wie sich in einem eindimensionalen Feld "Rand" definiert und wie sich der Abstand berechnet und darauf bist Du bisher nicht eingegangen.
In Deinem Ansatz fehlen also noch Anforderungen, die Du stellst.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten