spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Eine sehr simple Variante die ich gern in diversen projekten nutze, funktioniert folgendermaßen:

bezogen auf Tilemaps, Pixel, isomaps, Voxelartige maps, jedoch nenne ich es nun weiterhin einfach nurnoch "tiles"

Zuerst zufällig auf der karte die "biome zentren" verteilen.
Die details hier kann man varrieren wie man möchte, welche biomes häufiger vorkommen sollen, ob manche am kartenrand sind oder manche nur im zentrum etc.
Da man nur einzelne tiles verteilen muss, kann man hier sehr flexibel sein.

Der zweite und spannendere schritt ist:
Zuerst Zählst du alle noch nicht gesetzten tiles, also alle felder auf der karte die noch zu setzen sind.

Dann eine while schleife:
Solange "Gesetzte felder" < "zu setzen"
Eine zufällige position auf der karte auswählen
wenn das tile an dieser position noch nicht gesetzt:
einen zufälligen nachbar auswählen.
wenn der zufällig gewählte nachbar ein gesetztes tile ist (z.B. tile <> null)
tileart vom nachbarn auf das aktuelle tile übertragen.


klingt erstmal sehr simple, und geht auch vom berechnen her schneller als man denkt.
In einer html5 variante habe ich damit eine map in der größe 512x512 in weniger als 0.5 sekunden erzeugt.
Kein perlin noise, oder fraktale dinge sind für diese Variante nötig.

Die durchschnittliche größe der biome richtet sich danach wieviele "Biome Zentren" verteilt werden,
zudem sind natürlich weitere varianten möglich, z.B. indem man die gesetzten Tilearten zählt, und dafür sorgt das eine spezifische tileart nur gesetzt wird wenn <beliebige bedingung> (z.B. nur wüste nur plazieren wenn es nich bereits mehr als n wüstentiles gibt, oder das verhältniss wüste/grasland gleich bleibt)

So sehen die Resultate aus zwei von meinen Projekten aus:

Für ein Strategispiel mit Landschaftlichen gebieten (Biomes)
(Die linien sind lädnergrenzen und haben nichts mit der biomerstellung zu tun)

Für ein Mininggame mit einer sidescroller map, bei der ich die gesetzen biometypen von der höhe+zufall abhänig gemacht habe.



Vielleicht hilft dir diese idee ja weiter,
wenn du weitere fragen zu dieser Variante hast oder ein codesnipsel möchtest sag gern bescheid

Zitat von »Salmakis«

Eine zufällige position auf der karte auswählen

Ich hoffe Du führst dabei eine Liste der Positionen, die noch nicht gesetzt wurden, damit Du nicht abertausende Misses in einer total leeren Region landest oder bereits bevölkerte Felder untersuchst. Wenn ich mir die 0.5 Sekunden und die Bedingung Deines Algos aber so anschaue (was ARG lange ist), wohl eher nicht. Das sollte dringend nachgeholt werden.

Nein, so eine liste führe ich nicht.
Vermutlich gibt es abtertausende Misses in einer total Leeren Region, und später wenn die karte voller ist gibt es auch abertausende misses in bereits gefüllten gebieten.
Natürlich kann man das optimieren, aber eine liste mit gesetzten positionen an sich wird nicht viel helfen
da ich ja direkt schauen kann ob das tile an der position gesetzt ist.
Was soll man da mit einer Liste mit leeren positionen?

wenn überhaupt müsste man eine Liste führen, welche die "randgebiete" hält, also tiles die nicht besetzt sind, aber an besetzte grenzen und aus dieser dann einen zufälligen eintrag wählen und seine position nehmen, darüber könnte man nachdenken, die frage ist nur ob sich der aufwand lohnt.
Man müsste:
->Beim setzen eines tiles, die nachbarn checken, und unbesetzte in die liste eintragen.
-> zum eintragen ggf neue objekte erzeugen,welche die position repräsentieren.
->Das eben gesetzte aus der liste entfernen.
wer weis ob das, jeh nach verwenderter listen art wirklich schneller ist.
Linked list ist nicht so toll, wenn man ein zufälliges aus der liste auswählen möchte, da man da ggf hunderte / tausende von objekten durchlaufen muss mit getnext.
Ein array wäre wohl eine bessere idee, da müste man aber einträge aufrücken lassen wenn welche entfernt werden.

In c++ dauerte das ganze bei einer 512x512 map nichtmal 30ms, ist also aufjedenfall verträglich.

Nunja die damit generierte map, muss ja nicht zwangsläufig direkt deine spielwelt sein.
Sie kann ja auch als grobe übermap dienen, zum definieren der biomes und regionen, die du dann für dein projekt weiter auflöst, und bei bedarf generierst.

Aber dies ist ja auch nur eine möglichkeit, es gibt sicher auch viele andere möglichkeiten, ich bin gespannt auf neue ideen, da mich dieses thema auch interresiert.
Und die variante die ich nutze, habe ich vor vielen jahren erdacht als ich nicht wirklich viel ahnung hatte.
allein die Listensache stelle die BlueCobold angesprochen hat, hat mich angeregt mein system um eine deratige zu erweitern, das mach ich wohl heute abend

Zitat von »Salmakis«

Natürlich kann man das optimieren, aber eine liste mit gesetzten positionen an sich wird nicht viel helfen
da ich ja direkt schauen kann ob das tile an der position gesetzt ist.
Was soll man da mit einer Liste mit leeren positionen?

Was man mit so einer Liste soll? Na nur die auswählen, die überhaupt in Frage kommen können!? Sodass jedes Feld genau einmal bearbeitet. Nicht mehr und nicht weniger. Dann hätte der Algo eine Komplexität von O(n), wobei die Anzahl Fehler ist. Deiner bisher hat irgendwas total verrücktes als Laufzeit. Vermutlich irgendwas in O(n²) oder schlimmer.

nun, hättest du nicht direkt den erstbesten absatz zitiert, sondern erst den (ganzen) beitrag gelesen, (erst lesen dann schreiben) hättest du erkannt das ich eine liste durchaus für sinnvoll halte, jedoch eben nicht eine liste die einfach nur die "unbesetzten" felder führt.
Meine aussage bezog sich auf deine aussage:

Zitat

Ich hoffe Du führst dabei eine Liste der Positionen, die noch nicht
gesetzt wurden, damit Du nicht abertausende Misses in einer total leeren
Region landest oder bereits bevölkerte Felder untersuchst.

Einfach eine Liste mit unbesetzten positionen würde nicht viel bringen.

Wie bereits ausgeführt müste man sicherstellen das sich in der liste nur Positionen befinden die auch ganz sicher gesetzt werden können.
Dazu müste man eben beim setzen einer position die unbesetzten nachbarn eintragen.

Dies werd ich heute abend einmal umsetzen

Zitat

Deiner bisher hat irgendwas total verrücktes als Laufzeit. Vermutlich irgendwas in O(n²) oder schlimmer.

Ja das kann sein, wie ich bereits in einem späteren beitrag, den du scheinbar auch nicht gelesen hast (stichwort: erstbesten absatz zitieren)
ausführte ist dies eine sehr alte angehensweise, die ich, da sie sehr tolle ergebnisse liefert und die laufzeiten nie abartig groß waren, nicht weiter überarbeitet habe.
In diesem beitrag schrieb ich übrigens auch das ich mich daran mache dies einzubauen, ich bin also im grunde deiner kritik nachgekommen

Zitat von »Salmakis«

Linked list ist nicht so toll

Klar, wenn man die falsche Datenstruktur wählt, hat man wohl kaum was gewonnen. Niemand hier sprach aber von einer Linked List. Ich sprach von einer Liste. Das ist ein generischer Datentyp, der verschieden viele Elemente halten, welche hinzufügen und welche entfernen kann. In C++ Sprache wäre das passende offensichtlicherweise ein Vector, aber hier wurde nicht von C++ gesprochen, sondern allgemein.

Zitat von »Salmakis«

Einfach eine Liste mit unbesetzten positionen würde nicht viel bringen.

Sie würde deutlich mehr bringen als Dein bisheriger Bruteforce-Ansatz. Dass da noch mehr dran hängt um sie optimal zu halten, das ist offensichtlich, war für mich aber nicht Kern der notwendigen Aussage. Daher bin ich darauf auch nicht weiter eingegangen.