[Projekt] CyberDive (MARPG)

[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

[Artificial Mind]

Man Dankt ;)

@Industriegebiete:
es gibt dort keine Verbindung zwischen den Highways, das ist richtig, das darf passieren. Dass es dort allerdings keine Verbindung der Zufahrtsstraßen gibt, ist etwas ärgerlich, das werd ich bei Gelegenheit korrigieren. Momentan sind grade die Straßen in der Stadt dran.

@Serpentinen:
Also prinzipiell können die das, einen Ansatz davon sieht man zwischen dem linken Industriegebiet und der Stadt. Allerdings habe ich momentan die Straßenteilstücklänge auf 2km (nach unten) beschränkt, damit meine Graphen (auf denen ich kürzeste Wege berechne) nicht mehrere tausend Knoten und Kanten haben. Mal gucken, wie ich diese gescheit einbaue.

[Artificial Mind]

Mein Sonntagsupdate ;)

Straßenkarte des Stadtkerns

(Achtung, Auflösung 6k x 6k)
Auch wenn ich noch nicht endgültig zufrieden bin mit der Stadtkarte, so bleibt es das erstmal. Ich möchte mich mal wieder anderen Baustellen zuwenden ;)
Als nächstes werde ich entweder ein eigenes GUI für Ogre implementieren oder eine 3D-Ansicht der Stadtkarte.

Allerdings fängt morgen das Semester an und am Wochenende ist die devmania und die Woche drauf darf ich mich von zwei Weisheitszähnen verabschieden, also wird das nächste Update wohl erstmal ein bisschen brauchen. Vielleicht kann ich zwischendurch was posten, vielleicht nicht.

[joggel]

Als nächstes werde ich entweder ein eigenes GUI für Ogre implementieren oder ...

Was ist eigentich mit CEGUI?
Oder kann man das wegen C# nicht benutzen?
Ansonsten Das?

[Artificial Mind]

Ich habe CEGUI, Miyagi und MyGUI probiert und MyGUI ist das beste imho davon.
Allerdings sind die alle mehr oder minder unschön (programmtechnisch, implementierungstechnisch).

Features die ich sehr vermisse und nicht mal eben nachgepatcht sind:
- Tooltips (ganz wichtig)
- Animationen
- ausgereiftes Event-System

Ich wollte mich prinzipiell an WinForms orientieren, allerdings Rendering und Logik trennen, damit das einfach portiert/angepasst werden kann.

[Tejio]

Was ist eigentlich mit XAML und WPF? Dank Visual Studio und Expression Blend sehr einfach einzusetzen. Dabei hast du gleich Tooltips, Animationen, Trennung von Rendering und Logik dank MVVM und ein Event-System. Nicht wundern, ich arbeite mich momentan in das Thema erst ein. Noch ist alles gut und schön....

[Artificial Mind]

Und das kann ich in 3D-Applikationen benutzen? In Mogre integrieren?
Als tooltips meine ich auch nicht einzeilige Descriptoren oder meinetwegen mehrzeilige Balloons, sondern eigene Controls quasi. z. B. Anzeigen für Items, wo dann potentiell parallel mehrere andere Tooltips aufgehen und einen Vergleich anzeigen und soetwas. Außerdem muss ich das Mouse-Handling selber kontrollieren können wenn z. B. die GUI in die 3D-Welt integriert ist und somit verzerrt/rotiert ist.

[Chromanoid]

http://www.codeproject.com/KB/WPF/OgreInTheWpf.aspx / http://www.ogre3d.org/forums/viewtopic.php?t=44263 / http://www.ogre3d.org/addonforums/viewt ... =8&t=14094 evt. interessant, habs kurz gegooglet, weil ich es selbst interessant fand...

[Artificial Mind]

Ich hab grade auch ein wenig background-research betrieben und es scheint ne anstängide Portion von der Performanz zu schlucken, wenn man das WPF GUI in Mogre einbetten will (Und selbst Mogre in WPF eingebettet scheint signifikant zu bremsen). Man müsste wohl über quasi-hacks an die WPF Texturen direkt kommen ...
Und dann steht immer noch das Problem, den Input vernünftig zu mappen.
Eigentlich würde ich gerne WPF nutzen weil es vielversprechend aussieht und ich mich seit längerem mal etwas genauer damit beschäftigen will. Aber ich bin mir nicht sicher ob die Hürden für den produktiven Einsatz in einem Game nicht etwas zu hoch sind.

EDIT:
@Chromanoid:
Die Links behandeln soweit ich das sehe Ogre in WPF und nicht WPF in Ogre.

[LONy]

Hi,
wie geht es dir und deinen Löchern wo vorher die Weißheitszähne waren? :D
Wann gibt es mal einen neuen Screenshot? Jeden Tag schau ich hier ins Forum und warte sehnsüchtig drauf ;)

Gruß, LONy

[Artificial Mind]

Ja mittlerweile geht es wieder etwas besser, danke der Nachfrage ;)

Als nächstes bastel ich mir nen vernünftiges GUI, davon sollte ich auch vernünftig Screenies machen können. Aber ein bisschen musst du dich noch gedulden :)

[FlashbackOwl]

In welcher Sprache programmierst du das eigentlich ?
Das Projekt interessiert mich sehr und ich freue mich drauf neues zu lesen :)

[Artificial Mind]

C# ;) Ja, ich tue mein bestes, ich will auch das das was wird :D

[Zudomon]

lol... guckst du hier jede Minute ins Forum, dass du so eine kurze Responsezeit hast?

[Artificial Mind]

Ich krieg ne mail *g*

[Artificial Mind]

Kurzupdate: die Control-Klasse ist bei 640 Zeilen ... das passiert halt wenn man ein vernünftiges Event-System macht :)