Algorithmen zum Transport von Gütern zwischen Feldern
-
Hallo,
folgender Hintergrund:
Ich entwickle seit langem ein Aufbaustrategiespiel mit Wirtschaftssimulation.
Wie bei solchen Spielen üblich fördert der Spieler Bodenschätze und baut seine Industrie aus die dann andere Güter produziert etc.
Das Spiel wird auf einer Hex-Karte gespielt.
Ziel soll es nun sein, den Transport von Gütern über die Karte zu simulieren.
Dazu sollen berücksichtigt werden:
* Güter werden an bestimmten Stellen produziert. Dies benötigt evtl. andere Güter zur Produktion.
* Güter werden an bestimmten Stellen verbraucht.
* Der Transport zwischen Feldern kostet selbst wiederum bestimmte Güter (z.B. Benzin, Arbeitskraft etc.)
* Die Transportkapazitäten zwischen Feldern sind durch die dort bestehende Infrastruktur (Straßen, etc.) beschränkt.Alles soll möglichst automatisch ablaufen, d.h. der Spieler bestimmt lediglich,
* Welche Fabriken/Minen/etc. wo gebaut werden
* Die Infrastruktur zwischen Feldern
* Eventuell eine Prioritätsliste die angibt welche Güter mit welcher Priorität transportiert werden, falls man am Kapazitätslimit ist.Gibt es dazu irgendwelche Praxistauglichen Algorithmen?
Es handelt sich wohl um eine verschärfte Version dieses Problems:
http://de.wikipedia.org/wiki/Transportproblem
Wobei es halt bei mir mehrere Gütersorten gibt, die miteinander gekoppelt sind.
Hat jemand so was ähnliches schonmal implementiert oder kann Tipps geben wo man was darüber finden könnte?
Besteht eventuell Interesse gemeinsam einen Algorithmus dafür zu entwickeln?
Wäre wohl echt eine Herausforderung.
-
Ich würde auf jedes Sechseck einen unsichtbaren rosa Roboterhändler setzen und die Händler das alleine ausmachen lassen. Die Preise der Händler können echtes virtuelles Geld (hä?) sein oder geheimes Nur-Händler-Geld.
-
Wie gut ist denn dein Hintergrundwissen? Du beschreibst Multi-commodity Flows
-
Hi,
@Michael E.
mein Hintergrundwissen in Wirtschaft gleich Null.
Mein Hintergrundwissen in Mathe ok.
Wobei ich weder Netzwerk-, Graphentheorie oder lineare Programmierung je gemacht habe. Schreckt mich aber nicht ab mir das anzueignen.
Multi-commodity flow problem:
Cool. Hatte ich bisher noch nicht gefunden. Muss ich mich durcharbeiten.@volkard:
Ja! Das is auch eine meiner Herangehensweisen gewesen.
Probleme dabei:
Irgendjemand muss mal anfangen einen Preis für ein Gut zu bieten. Welchen?
Wie verhindern dass die Preise nach oben abheben?
Muss aber mal dazu ein Testprojekt machen.
Will mir jemand helfen?
-
Was willst du jetzt genau? Irgendeinen Weg? Den kürzesten Weg? Den billigsten Weg?...
-
Comeonandgetit schrieb:
Was willst du jetzt genau? Irgendeinen Weg? Den kürzesten Weg? Den billigsten Weg?...
Nee, die (möglichst) optimale Zustandsentwicklung pro Zeitschritt.
Das Spiel wird letztlich so ablaufen:
Von einer gegebenen Verteilung der Güter und Fabriken ausgehend, soll in einem diskreten Zeitschritt eine zukünftige Verteilung der Güter berechnet werden.
Und zwar so, dass
* eventuelle Bauaufträge des Spielers soweit möglich ausgeführt werden
und
* Die Zufriedenheit der Bevölkerung maximiert wird."Zufriedenheit" können wir dabei selbst als abstraktes Gut sehen, welches zu seiner Produktion eine Reihe anderer Verbrauchsgüter benötigt, welche am Ende der Produktionskette stehen (z.B. Nahrung, Wohnung, Energie, etc.)
Die Verbesserung des Zustands pro Zeitschritt ist dadurch beschränkt, dass
* die Produktion der Fabriken pro Zeitschritt,
* die Transportkapazität zwischen Feldern pro Zeitschritt
beschränkt ist.
-
scrontch schrieb:
@volkard:
Ja! Das is auch eine meiner Herangehensweisen gewesen.
Probleme dabei:
Irgendjemand muss mal anfangen einen Preis für ein Gut zu bieten. Welchen?
Wie verhindern dass die Preise nach oben abheben?Mein erster Versuch:
Preis am Verbraucher ist fest 2000€/Tonne.
Preis am Produzenten ist fest 1000€/Tonne.
Preis am Bot ist Mittelwert aller umliegenden Preise. Also der Nachbarbots und der eigenen Produzenten und Verbraucher. Die Startpreise sind egal. Zum Beispiel 1500€.
Das System konvergiert in Richtung dahin, was auch ein LGS für ein Widerstandsnetzwerk mit lauter gleichen Widerständen berechnen würde. Mit unterschiedlichen Widerständen (besser Leitwerten) geht's auch.Und jeder schickt soviel er kann in Richtung steigender Preise.
Perfekt ist das bestimmt nicht, aber wäre halt mein erster Versuch, um wenn es grafisch dargestellt wird, ein Gefühl für die Dynamik zu bekommen.
Und dann würde ich wohl versuchen, mir was anzulesen, ob man ein Routing-Protokoll klauen kann, das die Netzwerkbelastung miteinbezieht.
-
Die Wege sind also vorgegeben? Was kann man dann alles verändern?
