[Projekt] CyberDive (MARPG)

[Artificial Mind]

Genau das war der Plan. Ich _habe_ bereits die meisten Einflüsse für jedes Gebiet berechnet. Ich wollte nur mal eine genauere Reliefkarte erzeugen, aber die muss ich wohl stückeln *g*

[Artificial Mind]

So ein kleines Kurzupdate trotz Erkältung und Besuch bei den Eltern:
Ich habe nun 100km x 100km große Klima-Geozonen, welche sich in 10km x 10km große Mesozonen und 1km x 1km große Mikrozonen aufteilen. Das Klima wird dabei geeignet interpoliert.

Klimazonen (Auflösung: 10km x 10km, Mesozonen)

Das die Ränder zum Wasser momentan seltsam aussehen weiß ich, das liegt daran, dass die Höhen noch nicht geeignet interpoliert werden, sondern über die Klimainterpolation laufen und somit versaut werden.
Die Auflösung ist 4000 x 1333 und soll mir nur erstmal zeigen, dass die Klimadaten richtig interpoliert werden. Außerdem werden die Meso/Mikrozonen bei Bedarf generiert und freigegeben, alle Mesozonen passen beispielsweise schon nicht mehr in den Arbeitsspeicher (bei x86).

Ich habe nun auch tatsächlich ein Bitmap erstellt bekommen, dass 1 Pixel = 1 Mikrozone Auflösung hat. Dies ist tatsächlich ein 40 000 x 13 000 Bitmap mit 2GB Größe. Ich musste es tatsächlich in kleinen Streifen generieren und dann manuell auf byte-Ebene mergen. Nun finde ich kein Programm, dass es mir in png konvertieren kann (Photoshop habe ich grade nicht installiert, Gimp kriegt nen Fehler, weil es 2 080 000 000 Byte nicht allokieren mag, Imagemagick hat einen ähnlichen Fehler, Paint.NET möchte das 3-5fache an Speicher haben bevor es arbeitet und damit kann ich momentan nicht dienen.) Das einzige Programm, dass es vernünftig (und flüssig) anzeigen kann, ist der Windows Photo Viewer, nachdem es 5GB working set bekommen hat.

[Krishty]

Irgendwo gibt es vom Gimp eine experimentelle x64-Version. Die ist genau so lahm wie Windows’ Fotoanzeige; mit der konnte ich aber letztens noch eine 40.000²-8-Bit-BMP konvertieren (in RGB dürfte das wie gespuckt auf deine Größe passen).

[Artificial Mind]

Die letzten beiden Tage hatte ich dann auch mal Lust, an dem Server zu schreiben.
Prinzipiell soll dieser stark multithreaded sein und sich selbst verteilen können, sowohl auf die eigentlichen Server, als auch teilweise auf die Clients. (Lies: Rechenleistung der Clients, die nicht gebraucht wird, aber dem Server dienen könnte, sollte genutzt werden) - so von der Idee her.
Die Architektur ist momentan in Rollen und Worker aufgeteilt, wobei Rollen verschiedene Dienste anbieten und Worker Arbeit verrichten. Die Rollen kapseln also die Daten (um sie bei Bedarf zu verteilen) und die Worker sind quasi aufgabengerichtete Thread-Pools.

Momentan gibt es noch keinen Auslagerungsmechanismus, nur eben schon Rollen und Worker. Da ich glaube, dass ihr eine entsprechende Demo ohne allzu viel Aufwand spielen wollt, habe ich auch zuerst auf den MySQL-Datenbankserver verzichtet und eine dateibasierte Speicherung eingebaut. Idealerweise ist dies später umschaltbar.

Server Window

[Chromanoid]

Sonst nutz doch fürs erste eine eingebettete Datenbank. Was benutzt du eigentlich als Programmiersprache? Für C#, Java und Co. gibt's ja sehr bequeme DB agnostische ORM Bibliotheken.

Ah ich glaube du hattest mal C# erwähnt. Na dann benutzt du ja wahrscheinlich eh schon ADO.net oder so. :)

[Artificial Mind]

Ich benutze C# und den MySQL-Connector für meine lokale xampp-MySQL-DB. Ich bin mir auch nicht sicher, ob ich wirklich eine ORM haben möchte, ich weiß nicht, ob diese den Grad an Flexibilität und die Performance bieten, den ich von (My)SQL gewöhnt bin. Aber ich habe da auch noch nicht so viele Erfahrungen gemacht, als das diese Meinung wirklich fundiert ist.
Eingebettete Datenbanken funktionieren natürlich auch, aber es bleibt mir dann trotzdem irgendwie nicht richtig erspart, viel Code doppelt zu schreiben. Files als Zwischenlösung sind wenigstens gut human-readable/editable.

[Chromanoid]

Naja das wäre ja der Vorteil an ORM. Da brauchst du dann nur ein paar Annotationen und fertig ist der Kram für alle Datenbanken, die ADO.net unterstützt. Ich würde das ADO.NET Entity Framework einfach mal ausprobieren und ein bisschen benchmarken. Gerade für den Anfang sollte erst mal gelten, Produktivität über Performance oder? :) Außerdem: Wenn deine Operationen nicht horizontal skalieren musst du dir eh Gedanken über deine Architektur machen :). Sachen wie MongoDB kannst du dir ja auch mal anschauen...

[Artificial Mind]

Ja klar, Produktivität steht am Anfang an oberster Stelle, sonst hätte ich mir auch nicht C# ausgesucht ;)
Das Entity Framework sieht vielversprechend aus, ich werd mir das nachher mal angucken, danke :)

[Artificial Mind]

So mal ein kurzes Update:

Ich benutzte jetzt SQLite und den entsprechenden Adaptern. Das funktioniert soweit ganz gut und ich muss nicht allzu viel neu/um- schreiben, wenn ich auf ne richtige SQL Datenbank umsteigen will.

Es gibt ein kleines Hauptmenü mit Login und Character Liste, Accountdaten und Characterdaten werden schon in den entsprechenden Tabellen gespeichert.

[Artificial Mind]

Ich bin gerade dabei die Verteilung der Städte zu generieren, habe mir auch einige vielversprechende Konzepte dazu ausgedacht. Dazu kommt noch ein Post, sobald das fertig ist.

Um sich nicht immer Namen ausdenken oder Platzhalter benutzen zu müssen, habe ich eine erste Version eines Namensgenerators geschrieben, der mir Namen generieren soll. Vielleicht kann ich das später mit User Generated Content kombinieren. Z. B. als Poll mit 5 generierten Auswahlmöglichkeiten, wenn etwas neues benannt werden soll.
Konzept:

• Namen sollen Englisch klingen
• Namen sollen keine englischen Wörter sein

Erste Version:

• Leider noch nicht immer schöne Wortenden.
• Als Wörterbuchgrundlage (inklusive Wortwahrscheinlichkeiten) benutze ich momentan 18 Bücher aus dem Projekt Gutenberg (20 MB .txt).
• Um zu entscheiden, ob Wörter englisch klingen, betrachte ich die letzten 3 Buchstaben und wähle den nächsten Buchstaben nach Auftrittswahrscheinlichkeit der 4er-Kombination.
• Um zu entscheiden, ob Wörter aus dem Englischen sind, sortiere ich ale Wörter aus meiner Wörterbuchsgrundlage, sowie alle aus 2 Wörtern zusammengesetzten aus (ergibt Blacklist mit 10 Millionen Wörtern bei 65k Wörtern im Wörterbuch).

Todo:

• Wortenden in die Wahrscheinlichkeitsbetrachtung mit einbeziehen.
• Nicht nur Wörter aussortieren, die exakt gleich mit einem englischen sind, sondern auch alle Wörter, die zu einem englischen Wort eine Levenshtein-Distanz von maximal 1 oder 2 oder vielleicht 3 haben.
• Größere, uniformere Wörterbuchgrundlage. Vielleicht sogar spezielle Namenslisten.

Beispiel:
100 generierte Wörter (sortiert):

Accor
Amonis
Anythi
Aoudsom
Aslee
Awayst
Beded
Beent
Bergt
Bidew
Burness
Camessu
Castea
Chappla
Chisdai
Clowedd
Coldlyy
Conders
Conste
Coveryt
Crawi
Davin
Dismil
Dispota
Donelti
Eagreat
Easone
Elsehol
Entag
Esters
Famili
Felte
Fifte
Finge
Firmis
Firmlyl
Fronge
Gainedi
Gainedu
Gratash
Grospir
Haphi
Hastwa
Hearlet
Immis
Indst
Intoni
Israe
Janesti
Kingdra
Lenta
Litian
Loodn
Looken
Lordshi
Marves
Miniq
Miredi
Mosco
Murden
Neresti
Offid
Oftet
Onlylo
Outsif
Ovedwar
Overyt
Overyxi
Peoplex
Righwa
Rivial
Separ
Shalle
Shanc
Shrewar
Shutte
Simpos
Somet
Soons
Speede
Thatedf
Thathem
Thathis
Thatso
Themse
Themsel
Thousl
Tossedn
Totess
Treedl
Truthou
Untol
Untryve
Ventle
Walleg
Warrike
Weard
Whaten
Withhor
Yournc

Falls jemand soetwas braucht oder benutzen will, kann man mich gerne anschreiben, dann erstelle ich kurz ein Projekt mit den entsprechenden Klassen und veröffentliche das. Sprache ist C#.
EDIT: Natürlich mit Source Code. Ist auch nicht auf Englisch festgelegt, sondern hängt von den Texten ab, die man als Grundlage verwendet.

[Artificial Mind]

So jetzt gibt es ein größeres Update ;)

<story>
In meiner Welt gibt es vier große Rassen, die aus genetisch-magischer Mutation aus den Menschen heraus entstanden sind. Es sind also immer noch Menschen und sie leben auch alle in der Gesellschaft. Mit "Menschheit" sind also alle Rassen gemeint und "Die Menschen" sind je nach Kontext entweder die nichtmutierte Menschen oder eben sämtliche (mutierte und nichtmutierte) Menschen.
Die vier Rassen sind: (normale) Menschen, Elfen, Orks, Zwerge.
Die Weltbevölkerung ist durch Umweltkatastrophen, Seuchen und Kriege auf ca. 2 Millionen reduziert worden. Durch die Rückkehr der Magie sind viele Tierarten magisch aktiv geworden und wehren sich teilweise vehement gegen den Menschen. Die Reste der Menschheit lebt in ca. 10-20 Städten, die über die Welt verteilt sind und größtenteils autark sind. Es wird also der größte Teil des Bedarfes an Resourcen, Energie und Nahrung selbst in der Stadt bzw. im unmittelbaren Stadtgebiet (um Schutz zu gewährleisten) angebaut/gefördert. Jede Stadt hat eine Stadtregierung, wobei jede Stadt von genau einer Rasse regiert und dominiert wird. Es gibt allerdings durchaus große Bevölkerungsteile, die aus einer anderen Rasse stammen. Jede Stadt hat ihre eigenen gesellschaftlichen Normen und auch spezielles Akzeptanzverhalten gegenüber den anderen Rassen (es gibt durchaus sehr tolerante, als auch sehr intolerante/rassistische Städte). Jede Rasse hat ihre eigenen Vorlieben, welche Energien, Wälder, Metalle, Landschaften bevorzugt werden. Neue Städte werden immer dann gegründet, wenn die Überbevölkerung (Bevölkerung über den Kapazitätsgrenzen der Städte) groß genug ist, um die Gründung einer neuen Stadt zu rechtfertigen (ca. 100.000 Menschen). Die Rasse, die am meisten Überbevölkerung hat, bekommt die Regierung und entscheidet, wo die Stadt gebaut wird. Zwischen den Städten gibt es Reisemöglichkeiten per Suborbitalraketen.
</story>

Die Story birgt folgende Lösungen für einige Probleme, die bei einer so großen Welt auftreten:

• Es gibt eine überschaubare Anzahl von Städten
• Die Spieler treffen sich (in den Städten)
• Ich kann jedem einzelnen NPC-Mensch ein eigenes Leben geben (2 Millionen ist keine allzu große Zahl, wenn man die Simulationsschritte groß genug ansetzt)
• Trotz der kleinen Anzahl von Städten sind viele verschiedene Landschaften und Klimazonen "abgedeckt"
• Aufgrund der großen Abstände der Städte kann man mit den Suborbitalraketen schnell zwischen den Städten wechseln und muss nicht lange (mehrere Zeitstunden) laufen/fahren/reisen, um von A nach B zu kommen. (Macht das Ganze etwas plausibler und spieltechnisch angenehmer)
• Jede Stadt hat ein einzigartiges Layout, welches aus der Landschaft, den Energiequellen, den Metallresourcen, den Wäldern, dem Klima und der Rasse resultieren.

Jetzt etwas im Detail:
Zuerst einmal habe ich nun genügend Informationen beisammen, um die Metallressourcen der Erde zu approximieren.

Resourcen der Welt

Dabei habe ich mich auf die vier Metal-"Klassen" Edelmetalle, Arbeitsmetalle, Radioaktive Metalle und Silizium beschränkt.

Als nächstes gibt es verschiedene Quellen, um an Energie zu kommen.

Energiequellen der Welt

Hier gibt es die Quellen-"Klassen" Fossile Energie, Geothermie, Solarenergie, Windenergie, Wasserenergie, Kernkraft und Bioenergie.

Aus dem Klima kann ich die verschiedenen Waldbestände der Welt errechnen.

Wälder der Welt

Die großen Wald-"Klassen" sind (tropischer) Regenwald, (subtropischer) Monsunwald, (tropische) Savanne, (subtropischer) Dornenwald, Nadelwald, Laubwald und Mischwald.

Jede Rasse hat ihre eigenen Vorlieben. Dies ergibt folgende Standortvorlieben (gesamter Standortfaktor) pro Rasse:

Standortfaktoren der Rassen, Städte

Zusammen mit der Initialbevölkerung (momentan 800k Menschen, 600k Elfen, 400k Orks, 400k Zwerge) haben sich in dieser Welt z. B. 15 Städte ergeben, 6 Menschenstädte, 4 Elfenstädte, 3 Zwergenstädte, 2 Orkstädte.

Mit der Reliefhöhe, dem Klima und den Wäldern kann ich jetzt auch eine erste Approximation der Oberflächenfarbe geben.
Hier nochmal eine Karte mit der Oberflächenfarbe und den Städten (mit Namen aus meinem Zufallsgenerator):

Städtekarte

Ich habe die letzten Tage eigentlich gut was geschafft, mal gucken wieviel ich in der Woche noch schaffe (wenn einen das RL einholt ... *g*).
Der nächste Schritt ist ein Charakter Creation Screen mit Dummy-Modellen (ich befürchte, mehr als prozedurale 3D-Strichmännchen werden es noch nicht) und der Auswahl der Anfangsstadt.

Hoffentlich war das jetzt nicht zuviel Text/Information/Bild :?

[Zudomon]

Wenn es sich von der Story her um die Erben der Erde handelt und die vier Rassen von der Menschheit abstammen fände ich es schon besser, wenn die Kontinente den echten entsprechen würden... vielleicht etwas abgewandelt... je nachdem in welcher Zeit es spielt. Und dann wäre es auch cool, wenn man Artefakte oder andere Anzeichen findet, die auf die heutige Zivilisation hindeuten.

[Artificial Mind]

Also ich verstehe den Standpunkt, dass es der echten Erde ähneln sollte.
Auf der anderen Seite finde ich es auch unglaublich spannend, eine komplett neue Erde zu erkunden. Storytechnisch kann man sich vieles ausdenken, um die veränderte Oberfläche zu rechtfertigen.
Die momentane Architektur erlaubt sogar nahezu beliebige Daten als Eingabe. Man kann also fast alles nachbauen. Wenn Interesse besteht, kann ich ja auch ein "Paint-Your-Planet"-Editor schreiben ;)

[joeydee]

Lass es bei der "neuen" Erde - sonst ist man eher versucht, Ungereimtheiten zu finden.
In der Fantasyliteratur sind Parallelwelten mit ähnlicher Geschichte/Landschaften/Bewohnern(Menschen, Tiere) aber auch großen Unterschieden zur "echten" Welt ja durchaus akzeptiert, vielleicht sogar mehr als eine direkte Entwicklung aus der "echten" Welt.

[Artificial Mind]

Ich habe nun schon Teile der Städte:

Stadtbezirke mit Highways und Zubringerstraßen

Legende:
Bezirke:

• Gelb: (Schwer-)Industrie
• Violett: Wohngebiet
• Türkis: Mischgebiet
• Orange: Gewerbegebiet
• Limone: Sondergebiet

Bisher gibt es also die Highways, die zusammenhängende Cluster von Bezirken verbinden, und Zubringerstraßen in den Industriegebieten.

Momentan versuche ich ein vernünftiges initiales Straßenmodell für die eigentlichen Stadtgebiete zu finden. Später werden sich einzelne Straßen aufgrund des tatsächlichen Verkehrsaufkommen noch ändern, aber ich brauche ein solides Grundmodell.

[joeydee]

Bedenke aber, dass (Highway-)Straßen nicht unbedingt von A nach B-Stadtmitte und dann von B-Stadtmitte nach C gebaut werden, sondern dass sich (finanziell/kulturell/ressourcentechnisch etc.) wichtige Gebiete/Gegenden allein aus praktischen Gründen direkt verbinden und sich weniger wichtige (Wohngebiete, kleinere Gewerbe) links und rechts von Hauptstraßen als Siedlungen ansiedeln und so die Hauptverbindungen einfach mit ausnutzen.
Ebenso kann ein Highway quer durch ein ressourcenreiches Gebiet führen, ohne auch nur durch einen Industriestandort direkt zu führen.

In deinem Fall wäre es wohl natürlicher, Schwerindustrie-Süd mit -Nord und dem Meer (Küste wäre in dem Fall sowieso der attraktivere Standort) direkt zu verbinden und für die Wohn-/Mischgebiete oder kleinere Industriestandorte eine "Abfahrt" einzurichten. Auch die Doppelverbindung nach Norden ist für den Straßenbau wohl eher rausgeworfenes Geld ;-)

[kimmi]

Vielleicht wäre auch die Topologie ein Faktor, um die Form der Strassen zu gestalten. Schaut man sich Stadtbilder wie zum Beispiel Stuttgart an, wurden dort die Strassen genau aus diesem Grunde sehr kurvig gestaltet. Man will halt nicht dem Berggipfel hinauf fahren. Ansonsten sieht das schon klasse aus.

Gruß Kimmi

[Artificial Mind]

Danke euch beiden, ich habe jetzt ne gute Idee, wie ich meine Straßenprojekte erstellen könnte:
(Die folgende Beschreibung setzt ein elementares Grundverständnis von Flussalgorithmen voraus)

Jedes Gebiet bildet einen Knoten der Sorte G (ebiet)
Jeder Straßenknoten bildet einen Knoten der Sorte S (traßenknoten)

Alle G-Knoten sind mit allen in diesem Gebiet enthaltenen S-Knoten mit einer Kante der Sorte V (erkehrsaufkommen) verbunden.
Alle S-Knoten sind mit allen angrenzenden S-Knoten über die jeweiligen Straßen (Kante der Sorte S) verbunden.
Alle S-Knoten sind mit dem G-Knoten in ihrem Gebiet über eine Kante der Sorte Z (ielverkehr) verbunden.

V-Kanten haben als Kapazität jeweils das Verkehrsaufkommen, das an dem S-Knoten in dem Gebiet "freigesetzt" wird (also quasi die Leute, die dort losfahren).
Z-Kanten haben als Kapazität jeweils das Verkehrsaufkommen, das an dem S-Knoten in dem Gebiet "aufgesogen" wird (also quasi die Leute, die dort hinwollen).
S-Kanten haben als Kapazität je nach Ausbau, Straßenzustand, Topologie und Höchstgeschwindigkeit das maximale Verkehrsaufkommen, dass durch diese Straße "fließen" kann.

Optimalerweise ist Summe der Kapazitäten aller V-Kanten gleich der Summe der Z-Kanten (jeder will irgendwo hin), aber es sollte auch gehen, wenn es nur ungefähr gleich ist.

Die G-Knoten fungieren über die V-Kanten als Quellen und über die Z-Kanten als Senken (ist ne Variante der eigentlichen Flussproblematik).

Angenommen, ich habe nun einen maximalen Fluss auf diesem Straßen/Gebietsgraphen:
Ist der maximale Fluss kleiner als die Summe der Kapazitäten der V- bzw. Z-Kanten, so können die Straßen das benötigte Verkehrsaufkommen nicht aufnehmen.
Der andere Fall (maximale Fluss größer als die Summe => Straßen haben genügend Kapazität) ist uninteressant, weil Ideal-/Endzustand ;)
Wenn es also Kapazitätsengpässe gibt, dann gibt es S-Kanten, deren Flusswert gleich ihrer Kapazität ist. Dies sind Engpassstraßen, die entweder ausgebaut werden müssen, oder der Verkehr umgeleitet werden muss. Wenn es S-Kanten gibt, die in einer Richtung stark belastet sind und in die andere Richtung kaum, dann könnte man z. B. in die eine Richtung 3 Spuren und in die andere 1 Spur "schalten", bei Bedarf sogar tageszeitenabhängig.

Mit dieser Methode könnte ich inkrementell mein Straßensystem verbessern und anpassen (die Stadt wächst ja im nachhinein, also während des Spiels, immer noch).

Die Laufzeit ist vergleichsweise gut, nämlich O(n² * m), bei n Knoten und m Kanten und ordentlicher Dinic-Implementierung.

Ich müsste mir noch überlegen, ob man einige Erweiterungen (verschiedene Verkehrsarten, Vorfahrtsregelungen, Ampeln, Kreisel) einbauen kann, ohne das Problem nach NP zu schieben.

Für Leute die sich fragen, warum ich nicht einfach kürzeste Wege ausrechne und darauf entscheide, ob und wo ich neubauen will: Erstens sind die Flussalgorithmen für diese Art von Problemen wesentlich besser, da sie auch alternative Wege berücksichtigen und zweitens, kürzeste Wege zwischen allen Knoten (Floyd-Warshall z. B.) ist O(n³), was in meinem Straßennetz nicht wesentlich weniger als O(n² * m) ist und somit keinen Geschwindigkeitsvorteil.

[LONy]

Sehr sehr cool wie weit du schon gekommen bist, erstmal ein großes lob :)
Ich bin eher der Fan von Aufbau-Startegiespielen (Bin grad dabei ein Browsergame zu Programmieren, allerdings mit "richtiger" Grafik, ala ISODD wie in Stefan Zerbsts ersten Band^^ leider studier ich "nur" Elektrotechnik, wodruch ich nicht so viel Fachwissen hab...)
Was ich an WoW immer vermisst habe war, dass man selbst die Landschaft beeinflussen kann.. Gebäude bauen kann usw. Du könntest doch deine Stadt erstmal nur ganz grundlegend generiert werden und dann vom Spieler weiter ausgebaut werden. Deine Welt ist ja echt rießig groß.
Ganz krank und bisher einzigartig wäre ein Mix aus RPG und Aufbau Simulation. Die Führer von großen Gilden können Straßen bauen und baugebiete ausweisen wie in Sim City, kleine Gilden / Einzelspieler können dann Gebäude bauen. Du hast irgendwo geschrieben, das du nicht so der Grafiker bist (geht mir genauso^^). Ich weiß nicht wie Realistisch das ist, aber bei google earth kann man ja auch sein Wohnhaus und andere Gebäude selbst zeichnen und online stellen. Vielleicht kannst du eine solche Schnittstelle auch in deinem Spiel später einbauen.

Meine Gedanken sind noch weit weg von deinem jetzigen Stand, ich wünsch dir auf jedenfall noch viel Motivation und freue mich auf weitere Fortschritte bei deinem Spiel :)

[Artificial Mind]

Hi LONy,

herzlich Willkommen im ZFX Forum ;)
Ich studier parallel Informatik Bachelor und Elektrotechnik Bachelor und in Etechnik machen wir eigentlich auch relativ vernünftige Mengen an Informatik^^

Stell dein Browsergame doch auch hier im Vorstellungsforum vor!

Interessanterweise liegst du gar nicht so weit weg von meinen Ideen. Die Städte sind nämlich von Grund auf sehr flexibel gehalten und es werden auch während des Spieles ständig neue Gebäude gebaut, alte abgerissen (u. U. weil irgendwelche Spieler sie gesprengt haben). Gilden können Häuser/Gebiete mieten/kaufen/besetzen und entsprechend gegen Feinde verteidigen. (Oh, oder sie können sich auf einer tropischen Insel eine Basis bauen *g* )

Geplant ist auch, einen Teil der Kontrolle der Großkonzerne in ein Browsergame auszulagern, dass quasi parallel zur Welt läuft. Browsergamer und "Client"gamer interagieren dann, aber ja, das ist noch eine Weile hin, bis das funktioniert ;)

[Tiles]

Ganz krank und bisher einzigartig wäre ein Mix aus RPG und Aufbau Simulation.

Da hatte sich seinerzeit Jowood mit Cultures 2 dran versucht. Müsste so 2001 gewesen sein. War echt ein nettes Game :)

[Chromanoid]

Naja und bei "Die Fugger" und folgende gibt es ja auch ähnliche Ansätze. Wobei das Aufbauen Afaik erst in den späteren Teilen dazu kommt. Sind nicht auch die neueren Siedler Teile mit RPG Elementen? Naja aber das Gesptäch darüber sollte man vielleicht im Gamedesign Forum weiterführen :). @Artificial Mind: Weiter so! :)

[Artificial Mind]

Schade, meine Idee mit den Flussalgorithmen ist so nicht durchsetzbar, da ich verschiedene "Güter" im Flussnetzwerk brauche (da sonst der Verkehr nicht so fährt, wie ich will). Das nennt sich dann Mult-commodity flow problem und ist NP-vollständig. Na danke.

[pUnkOuter]

Musst es ja nicht unbedingt komplett lösen, vielleicht reicht ne Heuristik, schau doch mal bei den Schwarm-Intelligenz-Ansätzen nach.

[Artificial Mind]

Ich hab mir auch schon Approximationen dafür angeguckt, allerdings ist das echt harte Materie und ich bin mir nicht sicher ob die Aufwand/Nutzen-Ratio nicht unausgeglichen wird. Momentan versuche ich ein wenig unser Straßenbausystem nachzuahmen: man stellt verschiedene Varianten auf, unter anderem: Nullvariante (nichts bauen), Ausbauvariante (neues bauen, altes beibehalten) und Neubauvariante (altes abreißen, neues bauen) und berechnet für jede Variante die Kosten und Nutzen. Das beste Verhältnis wird realisiert.

[Krishty]

Hm. Also hier vor Ort entscheiden sie immer genau andersrum.

(Scnr)

[Artificial Mind]

Hm. Also hier vor Ort entscheiden sie immer genau andersrum.

Wenn ich an dem Punkt bin, wo ich Politik und Meinungsverschiedenheiten von verschiedenen Parteien habe, werde ich auf diesen Aspekt zurückkommen ;)

Unterdessen hat sich mein Ansatz als fruchtbar erwiesen:

Stadtkarte mit Highways und Bezirken

Hier gab es neben der Nullvariante jeweils nur "baue von Cluster Mittelpunkt A nach Cluster Mittelpunkt B". Die Baukostenfunktion ist eine einfache Gerade in Abhängigkeit der Strecke mit Fixkostenanteil und von jedem Bezirk will gleichmäßig viel Verkehr zu jedem anderen Bezirk "fließen".
Und trotz dieser sehr minimalistisch gehaltenen Bedingungen ist die Platzierung der Highways sinnvoll (im Sinne von Kosten-Nutzen-Effizienz)
(Die dunklen Linien im Hintergrund sind übrigens primitive Höhenlinien)

Der Algorithmus funktioniert also quasi wie folgt:
1. Stelle die Varianten auf
2. Berechne für jede Variante Kosten/Nutzen
2.1 Kosten sind die Summe der Baukosten/Abreißkosten/Umbaukosten der einzelnen Straßen der Variante
2.2 Nehme das Straßennetz inklusive der neuzubauenden Straßen und berechne die kürzesten Wege von jedem Bezirk zu jedem anderen
2.3 Für jedes Paar von Bezirken sei -1 * Entfernung * Verkehr zwischen den Bezirken der Nutzen (0 ist quasi "perfekt")
3. Nehme die Variante, die (Nutzen - Kosten) maximiert

Die Berechnung dauert zwar immer verhältnismäßig lange (ich denke so 50~100ms pro Variante), aber das muss später auch nur noch sporadisch berechnet werden, da die Stadt ja nicht jeden Frame eine neue Straße bekommt ;)

[Artificial Mind]

So, ich bin nun einigermaßen zufrieden mit der Platzierung der Highways:

Stadtkarte mit Highways und Höhenlinien

(Ignoriert einfach die umgedrehten Zahlen bei den Clustern, die zeigen an, wieviele Highways/Straßen in diesem Cluster sind, halt über Kopf)
Die Highways werden nun Stück-für-Stück aufgebaut, wobei für jeden Schritt 17 Ray-Sonden "ausgeschossen" werden und lokal jeweils ein Kompromiss zwischen niedrigem Gefälle und Abstand zum Ziel eingegangen wird.
Der Verkehr zwischen den Bezirken wurde nun auch quasi-sinnvoll approximiert (zum Beispiel kaum Verkehr zwischen Schwerindustrie und Wohngebiet, allerdings hoher Verkehr zwischen Wohn- und Gewerbegebiet (Arbeiter))
Zusätzlich wurde für jeden Bezirk der Abstand zum nächsten Highway mit in die Nutzenfunktion aufgenommen.

[Deadline]

Je öfter ich in diesen Thread schaue, desto beeidruckter werde ich. Allein alle diese Faktoren, die einberechnet werden, bei der Generierung - das haut mich schon um! Ich bin wirklich gespannt wie sich das Ganze weiterentwickelt :)

[LONy]

Sehr sehr krass was du da machst, ich verfolge sehr interresiert die Entwicklung :) Schön weiter machen, Bilder sind immer klasse.
Im Industriegebiet links gibt es zwischen den Straßen mal keine Verbindung, ebenso rechts oben... cool wäre es noch, wenn sich bei zu großer Steigung die Straße, wie bei einer Passstraße, den Berg hoch schlängelt :D