Forum



~Chronial am 15.10.2010 20:34 #6028


Ich habe eine Frage / Anregung zur Wegfindung:
Ich habe den Eindruck, dass die Wegfindung die Auslastung der Wege vollkommen ignoriert.
Deswegen funktioniert folgendes Konstrukt nicht (angenommen, dies sein eine schwer belastete Nord-Süd Verbindung).
Code:

   |
   +
  /|\
+ | +
  \|/
   +
   |


Die beiden Seitenwege werden nicht benutzt, obwohl der Weg in der Mitte völlig überlastet ist. Wenn mich nicht alles täuscht hat das auch im Original Siedler2 funktioniert.

Mir fällt allerdings dafür gerade auch keine schöne Lösung ein - mir ist klar, dass das Algorithmisch ziemlich schwierig ist. Offensichtlich sollten irgendwie die Waren, die auf dem Weg liegen als Kantengewichte miteinbezogen werden, allerdings hat man dabei dann das Problem, dass die blockierenden Waren evt. schon weg sind, bis die fragliche Ware da ankommt.

Kann mir jemand kurz anreisen, wie die Wegfindung im Moment läuft - vielleicht fällt mir ja dann was rafiniertes ein :). Also vor allem: wann wird die Wegfindung ausgeführt. Ich nehme mal an, es gibt eine Liste mit Waren, deren Position und deren Ziel. Wann und wie oft wird dann deren Weg bestimmt?


~Gast am 15.10.2010 20:35 #6029


mist, formatierung wollte nicht so ganz. Die mitlere Zeile (mit + | +) sollte ein Zeichen weiter nach rechts.


Spike am 15.10.2010 21:40 #6030

Im Ruhestand
Ehm spielst du die 0.6 oder eine nightly? also bei mir geht das eig...

---



Chronial am 15.10.2010 22:01 #6031


Mh, ist mir vor allem in der 1.6 aufgefallen, aber hatte in der nightly ein ähnliches Problem - allerdings war da die Situation ein wenig komplexer.

Also das generelle Problem ist, das es möglich ist, dass alles stillsteht, weil eine Kreuzung blockiert ist, obwohl es noch viele andere Wege gibt, die weder blockiert noch benutzt sind.


Chronial am 15.10.2010 23:11 #6033


So, hab mir mal die doku (source ^^) angeschaut, und die Ursache gefunden. Ich würde mich anbieten, das zu korrigieren - wenn daran Interesse besteht. Was m.E. zu verbessern wäre:

* Die aktuelle Wegberechnung ist weit davon entfernt, den optimlen Weg zu finden, da:
- Steigungen werden ignoriert
- Bootswege gelten also genauso schnell wie normale Wege (oder stimmt das evt?)
- Bei der Berechnung des Punishments für belegte Wege wird das Vorhandensein von Eseln ignoriert
- Blockierte (weil voll belegte) Flaggen werden überhaupt nicht gesondert beachtet - das kann insbesondere zum deadlock des gesammten Wegesystems führen (ich glaube das auch regelmäßig gesehen zu haben)

* Ich habe des öfteren gelesen, dass die Wegfindung ein zentraler Performancefaktor sei. Ist das irgendwie gesichert, oder nur eine Vermutung? Die aktuelle Implementierung ist nämlich sehr unoptimiert. Wenn das wirklich was bringt, würde ich auch anbieten, die mal richtig durchzuoptimieren. Punkte hierbei sind vor allem: Die gewählte Speicherstruktur (std::set) ist für diese Aufgabe nicht perfekt geeignet. Set sortiert beim einfügen (insert hat O(log(n))), nicht beim Auslesen (begin() hat O(1)). Die Wegfindung fügt aber typischerweise viel mehr (bei siedler bis 6mal so viele) Knoten ein, als sie ausliest. Ein heap wäre besser geeignet. Außerdem wird die Tatsache, dass das Wegesystem weitgehend statisch ist überhaupt nicht genutzt - die Berechnung beginnt jedes mal bei 0. Wenn man die Wegfindung etwas optimiert, sollte es möglich sein, sie um ein Vielfaches zu beschleunigen.


Da die Wegfindung in Siedler eine extrem zentraler Bestandteil des Spiels ist, der besonders bei größeren und belasteten Wegnetzwerken extrem Spielentscheident ist, würde ich doch sagen, dass es sich lohnt, da noch ein bischen Arbeit reinzustecken.


Chronial am 15.10.2010 23:29 #6034


oh, vergessen: die Berechnung des Punishments ignoriert vor allem auch die Länge des Weges. Als Resultat wird z.B. ein 2-Feld Weg mit 4 Waren als unattraktiver gesehen als ein 5-Feld Weg mit 3 Waren - dabei wäre der Transport auf dem 2-Feld Weg doppelt so schnell.

Nur zur Verdeutlichung: im Extremfall hat der 2-Feld noch einen Esel und der 5-Feld weg ist ein Schiff. Damit wählt der momentane Algo einen bei weitem mehr als 4-fach so langen Weg.

Diese Effekte werden noch weit verstärkt, wenn man nicht einfach nur 2 Wege vergleicht, sondern tatsächlich Netzwerke anschaut.


Chronial am 15.10.2010 23:47 #6035


Bis ich ne Antwort bekomme, ob es gewünscht ist, das ich da war implementiere missbrauche ich diesen Thread mal als Notizblock :P.

* Die Gewichtung von Waren an Kreuzungspunkten sollten wohl irgendwie mit der Entfernung vom aktuellen Punkt abnehmen - die Wahrscheinlichkeit, dass der Stau an der Stelle weg ist, bis die Ware da ist, steigt schließlich je weiter er weg ist.


Spike am 16.10.2010 10:22 #6037

Im Ruhestand
Also soweit ich weiß ist das pathfinding einer der performance faktoren.
Das die wege steigungen etc ignorieren sieht man auch daran ,wenn man 2 weit entfernte flaggen verbindet, da wird auch erstmal in eine richtung gebaut und dann in die andere.
                x
               /
              /
             /
            /
            \
             \
              \
               x

Auch wenn das direkt über einen Berg geht^^
Wenn du aber dabei bist, mach doch nen addon, wo man einstellen kann, dass bestimmte waren/menschen bestimmte wege nicht nutzen :D dann kann man mehrere kreisläufe bauen ;)

mfg Spike

---



Siegfried am 16.10.2010 10:56 #6038


Also zumindest von meiner Seite her ist eine Optimierung immer gewünscht. Wegen verschiedenen Gründen kann ich nämlich meist nur mit einem lahmen Atom-Prozessor spielen, der hoffnungslos überlastet ist.

Auch wenn ich gelesen hab, dass die großen Optimierungen erst nach dem erscheinen von 0.7 geplant sind, würde ich mich auch jetzt schon über jede Verbesserung freuen.


Spike am 16.10.2010 15:47 #6041

Im Ruhestand
naja 0.7 sollte ja eig bald kommen, werden ja eig nur noch crashes beseitigen^^

---



Chronial am 17.10.2010 15:32 #6044


Cool - hab grad keine Zeit mehr, das Spiel zu starten, aber kann das evt. mal jemand überprüfen: Leute laufen bergab nicht schneller. Dadurch werden Steigungen nochmal massiv verstärkt - bei einer steilen Steigung braucht der Träger 3mal so lang. So wird aus einem 2-Teil weg einfach mal ein 4-Teil weg ((6+2)/2).


Spike am 17.10.2010 17:36 #6045

Im Ruhestand
also die werden bergab eig schneller^^

---



Chronial am 19.10.2010 15:08 #6050


Ne, werden sie nicht :P

Das sieht nur so aus, weil der Weg am Berg in der Grafik weiter ist. In wirklichkeit laufen die aber so schnell wie im Flachen.


Spike am 20.10.2010 10:15 #6052

Im Ruhestand
naja, da würd ich mich jetzt mal nicht streiten wollen, dazu müsst ich mir das mal genau mit GFs ansehen^^
Da du ja auch das Original kennst, kam es dir auch manchmal so vor, als wenn Hügel über die Häufe menschen liefen geebnet wurden?

---



SilSie am 22.10.2010 11:46 #6072


Chronial: was du da alles erzählt, klingt auf jeden fall ausprobierenswert... wenn oli/flo nicht antworten, versuch es vielleicht mal im irc, da triffst du die eigentlich meistens an. ich glaube auch, dass das pathfinding ein wesentlicher performancefaktor ist, und wenn das tatsächlich jedes mal bei 0 berechnet wird... wundert mich nicht mehr warum meine cores immer ausgelastet sind, bei so einem "einfachen" spiel. und wesentlich mehr als das wegeberechnen gibt es bei S2 ja eigentlich nicht zu tun, sieht man von den basis-produktionsfunktionen (die ja einfach zeitlich gesteuert sind) und vom militär ab.
und sonst fang doch einfach mal an damit zu optimieren, ist ja schließelich open-source ;)


~dro1d am 22.10.2010 12:13 #6073


ich fände es aufjedenfall toll wenn du da was optimieren könntest, gerade in hinsicht auf die performance! weil momentan ist das spiel auf großen maps mit vielen lagern und großen verzweigten wegenetzen unspielbar!
das würde das spiel erheblich vorran bringen :)


Chronial am 22.10.2010 14:46 #6074


Könnt ihr mir mal hierzu eure Einschätzung geben:
Ich würde für die Stauerkennung gerne erkennen, ob ein Stau momentan oder konstant ist. Das ist relevant, weil ein Stau der weit entfernt ist auf eine Ware nur einen Einfluss haben sollte, wenn er auch wirklich permanent ist.

Meine Idee dazu war: Ein Stau ist vermutlich permanent, wenn er von Waren erzeugt wird, die aus produzierenden Gebäuden kommen (=Produktionsketten). Wenn der Stau von Waren erzeugt wird, die aus einem Lagerhaus kommen, wird er sich wahrscheinlich bald auflösen.

Was meint Ihr, wie gut diese Annahme im realen Spiel zutriff?


Oh, und da fällt mir ein: Noch eine zweite Annahme zu der ich euer Feedback brauchen könnte: Ich würde mal vermuten, dass gut mehr als die Hälfte des Wegnetzes Sackgassen sind. Also etwas in dieser Form:
Code:
   ___
  /
-+----
  \___


Auch hier meine Frage: stimmt das nach eurer Erfahrung?


Spike am 22.10.2010 15:50 #6075

Im Ruhestand
naja, also das mit den sackgassen kommt immer auf die karten drauf an, daher kann man das nicht pauschalisieren denke ich, meist läuft es aber auf einen kreis raus mit ablegern nach außen/innen, da man warenhäuser gut verteilt außerdem lasse ich die sackgassen meist nur zu bauernhöfen und integriere den rest direkt ins wegsystem.

das mit den staus kann man so sehen ja, ich denke aber es hat immer 2 gründe, denn ein lager mit 1 zugangsweg kann weniger einlagern als eines mit 4 anschlüssen, da wird es dann beim ersten einen stau geben, genauso beim auslagern aus dem lager denke ich, dass der Stau nur DIREKT an der flagge ist(es sei denn es ist ein hauptlager (großes land aber wenige lager)) und man muss viele waren in entgegengesetzte richtungen bringen, daher gibt es meiner ansicht nach einen stau, wenn man viele waren in entgegengesetzte richtungen transportiert (baustoffe zu den baustellen -><- Waren aus den Produktionsgebäuden) und wenn man zu wenige anschlüsse zu den lagern hat (vermutlich 10 Produzierende Gebäude und waren pro weg).

Weiß nicht wie weit das jetzt mit anderen erfahrungen übereinstimmt aber staus direkt habe ich seltener, man kann ja die wege direkt zu eselswegen machen und sollte ich dann dauerhaft stau haben, dann baue ich wege dazu, dann sind sie meist weg.

---



SilSie am 22.10.2010 20:43 #6079


Zitat von Chronial:

Könnt ihr mir mal hierzu eure Einschätzung geben:
Ich würde für die Stauerkennung gerne erkennen, ob ein Stau momentan oder konstant ist. Das ist relevant, weil ein Stau der weit entfernt ist auf eine Ware nur einen Einfluss haben sollte, wenn er auch wirklich permanent ist.

Meine Idee dazu war: Ein Stau ist vermutlich permanent, wenn er von Waren erzeugt wird, die aus produzierenden Gebäuden kommen (=Produktionsketten). Wenn der Stau von Waren erzeugt wird, die aus einem Lagerhaus kommen, wird er sich wahrscheinlich bald auflösen.

Was meint Ihr, wie gut diese Annahme im realen Spiel zutriff?


Ist die Herkunft der Waren den entscheidend? Stau ist Stau, auch wenn vorübergehend. Und für was planst du die Stauerkennung denn: um auf Parallelwege auszuweichen, wie in deinem Minibeispiel oder eher um einige größere Umwege in Kauf zu nehmen? Wenn es nur ersteres ist, sollte es egal sein, das Wegfindungssystem sollte ruhig großzügig auf nur minimal längere Weiche ausweichen. Wenn es um zweiteres geht, sollte man wirklich sehr vorsichtig sein, da ein vorübergehender Engpass tatsächlich durch Überproduktion oder Lagerhausaktivitäten entstehen kann.

Zitat von Chronial:

Oh, und da fällt mir ein: Noch eine zweite Annahme zu der ich euer Feedback brauchen könnte: Ich würde mal vermuten, dass gut mehr als die Hälfte des Wegnetzes Sackgassen sind. Also etwas in dieser Form:
Code:
   ___
  /
-+----
  ___


Auch hier meine Frage: stimmt das nach eurer Erfahrung?

Auch hier meine Frage: Wie willst du diese Information verwenden? Sackgassen generell ignorieren? Geschieht das nicht eh automatisch, da Waren niemals in eine Sackgasse befördert werden, sondern immer nur heraus? Und über den Anteil sollte man, wie Spike schon sagte, Vorsicht walten lassen... da baut wohl jeder anders.


Schimpanse am 23.10.2010 10:12 #6080


Ist denn folgender Ansatz nicht vielleicht einfacher einzubauen und vermeidet Stau:

Der Weg-Finde-Algorithmus (für Waren) beachtet nicht nur Länge des Weges und Steigungen, sondern auch, wieviele Waren dort auf dem Weg schon liegen und diese Werte fließen auch in die Berechnung ein?
Das sollte doch relativ einfach umzusetzen sein und falls es sowas schon gibt: Die Menge der Waren auf einem Weg hat wohl zu wenig Gewicht bei der Berechnung


jh am 23.10.2010 11:14 #6081


Hi Chronial,

wenn du Zeit & Lust hast das selber zu implementieren, kannst du das einfach als Patch an einen Bug-Report bei Launchpad anhängen.

Oder wenns komplexer wird einen eignen Branch davon anlegen.

jh


OLiver am 23.10.2010 12:40 #6083

FloSofts Coding-Sklave
Zitat von Chronial:

So, hab mir mal die doku (source ^^) angeschaut, und die Ursache gefunden. Ich würde mich anbieten, das zu korrigieren - wenn daran Interesse besteht. Was m.E. zu verbessern wäre:

* Die aktuelle Wegberechnung ist weit davon entfernt, den optimlen Weg zu finden, da:
- Steigungen werden ignoriert
- Bootswege gelten also genauso schnell wie normale Wege (oder stimmt das evt?)
- Bei der Berechnung des Punishments für belegte Wege wird das Vorhandensein von Eseln ignoriert
- Blockierte (weil voll belegte) Flaggen werden überhaupt nicht gesondert beachtet - das kann insbesondere zum deadlock des gesammten Wegesystems führen (ich glaube das auch regelmäßig gesehen zu haben)


Ja, das könnte man sicherlich machen und ja, die Bootswege sind in der Tat genauso schnell.


Zitat von Chronial:

* Ich habe des öfteren gelesen, dass die Wegfindung ein zentraler Performancefaktor sei. Ist das irgendwie gesichert, oder nur eine Vermutung? Die aktuelle Implementierung ist nämlich sehr unoptimiert. Wenn das wirklich was bringt, würde ich auch anbieten, die mal richtig durchzuoptimieren. Punkte hierbei sind vor allem: Die gewählte Speicherstruktur (std::set) ist für diese Aufgabe nicht perfekt geeignet. Set sortiert beim einfügen (insert hat O(log(n))), nicht beim Auslesen (begin() hat O(1)). Die Wegfindung fügt aber typischerweise viel mehr (bei siedler bis 6mal so viele) Knoten ein, als sie ausliest. Ein heap wäre besser geeignet. Außerdem wird die Tatsache, dass das Wegesystem weitgehend statisch ist überhaupt nicht genutzt - die Berechnung beginnt jedes mal bei 0. Wenn man die Wegfindung etwas optimiert, sollte es möglich sein, sie um ein Vielfaches zu beschleunigen.


Ja, das ist schon richtig, dass sie ein großer, wenn nicht sogar der entscheidende Performancefaktor spieltechnisch gesehen ist (also abgesehen vom Rumgezeichne), also quasi auch bestimmt wie lange das Vorspulen in Replays dauert.

Und was willst du da für einen Heap nehmen? Fibonacci-Heap? Weil bei einem normalen Binärheap hast du ja immer O(log n) beim Einfügen und Extrahieren und std::set wird vielleicht auch so implementiert sein. Die Frage ist dann, ob dieser zusätzliche Aufwand, den er verursacht kleiner ist als der vermiedene konstante Faktor, der ja ungefähr bei 5 liegt, weil du an jedem Punkt in 5 weitere Richtungen gehen kannst. Kann ich mir ehrlich gesagt nicht vorstellen, aber ich kenn mich mit Fibonacci-Heaps auch nicht aus.

Desweiteren war mir aufgefallen folgendes aufgefallen: Ich hatte ja vor der Sache mit dem set das Ganzen mit einer einfachen Liste implementiert, also hatte einen O(n^2)-Algorithmus. Der war lustigerweise immer schneller gewesen als das jetzt der Fall ist, d.h. da ja meistens nicht so viele Elemente im Set bzw. der Liste enthalten sind (außer bei langen Wegen mit großen Umwegen, was ja in der Praxis eher selten der Fall ist), war anscheinend der set-Overhead größer als die Ersparnis durch die bessere asymptotische Laufzeit. D.h. das Performanceproblem kommt nicht durch lange Wege sondern durch viele kurze mit großen konstanten Faktoren bei der Wegberechnung. Evtl. wäre es ja klug, beides zu kombinieren.

Ja, und über das statische Wegesystem hatten wir auch oft nachgedacht, aber insbesondere wenn du halt die Warenauslastung mit einbeziehst, ist das alles andere als statisch, weil sich ja die Gewichte deiner Kanten des "Weg-Graphen" ständig ändern. Dazu kommt natürlich auch die Tatsache, dass der Weg an jeder Flagge neu berechnet wird, aber auch das ist halt nicht so einfach zu vermeiden. Aber wenn du da gute Ideen hast, kannst du das natürlich gerne einbauen.

---
Warum heißt der Staatsbürger "Staatsbürger"?
-> Weil er für den Staat bürgt.


Chronial am 23.10.2010 14:44 #6087


Zitat:
Ja, das ist schon richtig, dass sie ein großer, wenn nicht sogar der entscheidende Performancefaktor spieltechnisch gesehen ist (also abgesehen vom Rumgezeichne), also quasi auch bestimmt wie lange das Vorspulen in Replays dauert.
Vorspulen? Wie ist der hotkey dafür? :) (btw. ne Hilfe für die Hotkeys im Replayplayer wäre nice ^^)



Zitat:
Und was willst du da für einen Heap nehmen? Fibonacci-Heap? Weil bei einem normalen Binärheap hast du ja immer O(log n) beim Einfügen und Extrahieren und std::set wird vielleicht auch so implementiert sein. Die Frage ist dann, ob dieser zusätzliche Aufwand, den er verursacht kleiner ist als der vermiedene konstante Faktor, der ja ungefähr bei 5 liegt, weil du an jedem Punkt in 5 weitere Richtungen gehen kannst. Kann ich mir ehrlich gesagt nicht vorstellen, aber ich kenn mich mit Fibonacci-Heaps auch nicht aus.
std::set ist in ein Binärbaum. Das gibt log(n) beim Einfügen, und O(1) für begin() und erase(). Für den A* Algorithmus nimmt man gewöhnlich einen Fibonacci-Heap. Ein Fibonacci-Heap ist auch nicht wirklich kompliziert. Hab hier mal ne Pseudocode-Implementation aufgetan:
http://www.cs.princeton.edu/~wayne/cs423/fibonacci/FibonacciHeapAlgorithm.html

Ich denke schon, dass das noch etwas rausholen könnte. Insbesondere, da die momentane Compare-Funktion sündhaft teuer ist - aber das sollte mit minimalem Aufwand behebbar sein.

Und deine Beobachtung stützt auch meine These: Die Liste hatte nämlich O(1) beim Einfügen, und O(n) nur beim Auslesen ;).

Zitat:
Ja, und über das statische Wegesystem hatten wir auch oft nachgedacht, aber insbesondere wenn du halt die Warenauslastung mit einbeziehst, ist das alles andere als statisch, weil sich ja die Gewichte deiner Kanten des "Weg-Graphen" ständig ändern. Dazu kommt natürlich auch die Tatsache, dass der Weg an jeder Flagge neu berechnet wird, aber auch das ist halt nicht so einfach zu vermeiden. Aber wenn du da gute Ideen hast, kannst du das natürlich gerne einbauen.

Genau das gleiche habe ich auch gedacht. Daher meine Frage nach den Sackgassen. Ich würde einen Vorlaufschritt über den Graphen laufen lassen, der den Graph in Kreise und Bäume ("Sachgassen") zerlegt. Dann werden alle Kreise, die sich in mehr als einem Punkt berühren zusammengelegt. Das erzeugt einen neuen, wesentlich kleineren und kreisfreien Graphen, dessen Knoten "Kreisblöcke" und "Baumblöcke" sind. Dieser Graph ist statisch gegenüber Staus: da es keine Wegwahl mehr gibt, sind auch Staus egal. Auf diesem Graph kann jetzt ein APSP (All Pairs Shortest Path Algoritmus) ausgeführt werden. Das geht sogar extrem einfach, da der Graph ein Baum ist (=Kreisfrei).

Wenn wir nun konkrete Wegfindung machen, müssen wir nur rausfinden, in welchem Block die Start- und Zielfahnen liegen. Dann bekommen wir in O(n) die n Blöcke, die auf diesem Weg liegen (durch APSP). Jetzt schauen wir uns jeden Block an, wobei wir in einem Block Eingangs- und Ausgangsfahne Kennen. Im Block wird dann ein A* angewandt - da wir die Größe des Block kennen, könnte man hier auch auf deine Listenimplementation zurückgreifen, wenn der Block klein ist (was er häufig sind wird). Da der Block wesentlich kleiner ist als das gesamte Wegenetzwerk hat A* hier auch eine extrem bessere Laufzeit.

Das schöne an der Sache ist noch, dass dieser "Block-Graph" sehr einfach zu managen ist. Wenn ein neuer Weg gebaut wird, muss er entweder nur an in einen Baum angehängt werden, oder etwas wird zu einem Kreis gemerget. Wenn ein Weg zerstört wird, muss erstmal überhaupt nichts getan werden - der Algo läuft ohne Probleme weiter, da der A* natürlich die fehlenden Wege bemerkt. Es geht nur bis zu einem Update des Block-Graphen evt. ein klein wenig Performance verloren.


So weit so gut - ich glaube dieser Algo könnte eine extreme Performanceverbesserung für große Wegnetze darstellen. Aber nur unter einer Bedingung: Wenn nicht das ganze Wegesystem ein rießiger Kreis ist. Daher meine Frage. Aber ich glaube um die Frage sinnvoll zu beantworten muss man Graphentheorie kennen und den Algo von oben verstehen ^^. Wer das tut, bitte mal schätzen: Wie gut lässt sich das typische Wegenetz wohl in Blöcke zerteilen?


Zitat:

Auch hier meine Frage: Wie willst du diese Information verwenden? Sackgassen generell ignorieren? Geschieht das nicht eh automatisch, da Waren niemals in eine Sackgasse befördert werden, sondern immer nur heraus?
s.o. - zur Optimierung. Und nein: im Moment wird in jede Sackgasse, die sich auf dem Weg befindet reingeschaut.

Zitat:
Ist die Herkunft der Waren den entscheidend? Stau ist Stau, auch wenn vorübergehend. Und für was planst du die Stauerkennung denn: um auf Parallelwege auszuweichen, wie in deinem Minibeispiel oder eher um einige größere Umwege in Kauf zu nehmen? Wenn es nur ersteres ist, sollte es egal sein, das Wegfindungssystem sollte ruhig großzügig auf nur minimal längere Weiche ausweichen. Wenn es um zweiteres geht, sollte man wirklich sehr vorsichtig sein, da ein vorübergehender Engpass tatsächlich durch Überproduktion oder Lagerhausaktivitäten entstehen kann.
Es geht natürlich um letzteres. Aber wie kann eine Überproduktion einen Stau verursachen / wie wahrscheinlich ist das? Es wird keine Möglichkeit geben, dass alles perfekt abzuschätzen - die Schätzung muss nur ausreichen gut sein.

Zitat:
ist denn folgender Ansatz nicht vielleicht einfacher einzubauen und vermeidet Stau:

Der Weg-Finde-Algorithmus (für Waren) beachtet nicht nur Länge des Weges und Steigungen, sondern auch, wieviele Waren dort auf dem Weg schon liegen und diese Werte fließen auch in die Berechnung ein?
Das sollte doch relativ einfach umzusetzen sein und falls es sowas schon gibt: Die Menge der Waren auf einem Weg hat wohl zu wenig Gewicht bei der Berechnung

Das hat Probleme - dadurch ist der Algorithmus extrem schnell bereit rießige Umwege zu gehen, wenn gerade irgendwo auf dem eigentlichen Weg ein Stau ist (kleine Staus sind sehr häufig). Und vor allem: Mit so einem Algorithmus kann es dir extrem häufig passieren, dass die Waren ihr Ziel nie erreichen, da sie aufgrund veränderter Stausituation immer wieder hin- und hergetragen werden, ohne dabei dem Ziel näher zu kommen.


Hui, das was ein langer Post - bekomm ich nen Keks? ^^


Schimpanse am 23.10.2010 16:15 #6088


Ist denn folgender Ansatz nicht vielleicht einfacher einzubauen und vermeidet Stau:

Der Weg-Finde-Algorithmus (für Waren) beachtet nicht nur Länge des Weges und Steigungen, sondern auch, wieviele Waren dort auf dem Weg schon liegen und diese Werte fließen auch in die Berechnung ein?
Das sollte doch relativ einfach umzusetzen sein und falls es sowas schon gibt: Die Menge der Waren auf einem Weg hat wohl zu wenig Gewicht bei der Berechnung


Chronial am 23.10.2010 16:40 #6089


? Das hast du schon vorher geschrieben, und ich hab darauf btw. auch schon geantwortet.

Vergessen zu erwähnen: Die von mir vorgeschlagene Block-Methode hat auch den Vorteil, dass bei jeder Neuberechnung (die ja an jeder Kreuzung passiert) nur der Weg durch einen Block mit A* berechnet werden muss.


Schimpanse am 24.10.2010 01:47 #6096


Sorry, die Seite war noch im Browser offen beim refreshen, daher der selbe Post nochmal


Ich werd es mir mal selbst anschauen in den nächsten Wochen.


Das Spiel benötigt dringend eine Performance-Steigerung, denn bei meinen letzten Spielen gab es immer mindestens eine Person, die einen älteren Rechner hatte und durch die das Spiel gewaltig gelaggt hat, irgendwann war es praktisch unspielbar. Das Wegeproblem ist dabei wohl der Schwerpunkt, denn ich kann mir nicht vorstellen, dass der Rest vom Spiel (außer die bescheidene Grafik) soviele Berechnungen benötigt, wie Wege.


Was mich aber dabei wundert:
Im Original hatte ich nie Probleme damit, obwohl ich es auf viel langsameren Rechnern gespielt hatte. Und das selbst bei riesigen Karten und ich bin einer, der lieber mal einen Weg zuviel als zu wenig baut, um auf Esel zu verzichten...


SilSie am 24.10.2010 20:39 #6101


Zitat von Schimpanse:

Was mich aber dabei wundert:
Im Original hatte ich nie Probleme damit, obwohl ich es auf viel langsameren Rechnern gespielt hatte. Und das selbst bei riesigen Karten und ich bin einer, der lieber mal einen Weg zuviel als zu wenig baut, um auf Esel zu verzichten...


Ich habe großen Karten mehrmals erlebt, dass das Spiel das Wegenetz nicht mehr handhaben konnte. Erstens wurden zum Teil neue Wegen trotz vorhandener Gehilfen nicht neu besetzt, und zweitens konnte es passieren, dass Waren (z.B. Nahrung) am westlichen Ende der Karte niemals berücksichtigt wurden für Produktionsstätten im Osten (z.B. Bergwerke). Ich musste die Waren dann erst manuell per Lagerhäuser verschieben...
Ich vermute mal, dass bei großen Karten einfach nur noch Teile des Wegenetztes betrachtet wurden.


Shen Long am 24.10.2010 22:51 #6102


SilSie: Meinst du partiell eins nach dem andern? (im alten Spiel)

---
mfg Shen Long
Tuxer mit Leib und Seele
__________________________
"Linux will nicht die Weltherrschaft, aber schön wärs schon." Linus Torvalds
PS: Sorry for my bad English


SilSie am 25.10.2010 15:05 #6103


Shen Long: wie, partiell eins nach dem andern?


Shen Long am 25.10.2010 16:42 #6104


Naja, das über das Wegnetz eine Art Raster drübergelegt wird, je nach dem wie groß das Wegnetz ist, und jedes Raster für sich angeschaut. Ich weiß das nicht, aber ich dachte das du so denkst.

---
mfg Shen Long
Tuxer mit Leib und Seele
__________________________
"Linux will nicht die Weltherrschaft, aber schön wärs schon." Linus Torvalds
PS: Sorry for my bad English


SilSie am 25.10.2010 16:53 #6105


das weiß ich nicht, ich bezog mich ja eh aufs original, was ich schon lange nicht mehr gespielt habe...
ich glaube allerdings fast eher, dass das eine art bug war, da der spielstand irgendwann komplett unspielbar wurde und ich danach auch in anderen (neuen) spielen schneller probleme mit den wegen bekam.


Shen Long am 25.10.2010 16:56 #6106


Ja okay. Möglicherweiße.

---
mfg Shen Long
Tuxer mit Leib und Seele
__________________________
"Linux will nicht die Weltherrschaft, aber schön wärs schon." Linus Torvalds
PS: Sorry for my bad English


~Gaßt am 25.10.2010 17:48 #6107


Ich glaube, je nach Karte gibt es manchmal ziemlich große Zyklen im Wegenetz. Eigentlich immer, wenn sich das Reich nicht nur horizontal oder vertikal ausbreitet. Ich denk da baut fast jeder so viele Verbindungen wie möglich, falls man eben mal ne Brauerei rechts unten und nen Bauernhof links unten baut. Man will ja nicht, dass das Zeug erst ganz nach oben zum HQ gebracht wird.
In dem Fall schätze ich sind 50% der Wege ein riesen Zyklus.

Spontane Idee:
Könnte man nicht einen Cache für gefundene Routen anlegen? Der müsste natürlich bei jedem Abreißen eines Weges geleert werden (nicht jedoch beim hinzufügen, wenn man kurzzeitige Umwege in Kauf nehmen will)
Dann berechnet man statt an jeder Fahne einfach je nach verbleibender Länge des Transportweges den Weg nur jede 2. oder 3. Fahne neu. Erst ab sagen wir 5 Flaggen vorm Ziel dann jedes mal.


Spike am 25.10.2010 20:38 #6108

Im Ruhestand
Hmm hatte gerade überlegt, ob ich das richtig verstanden hatte, dass jede ware einen Weg vorberechnet bekommt, jedesmal wenn sie an einer fahne landet, wäre es da nicht schneller von anfang an an jeder fahne den schnellsten weg zu berechnen und diesen dann den waren zuzuteilen?
kenn mich ja nicht weiter aus, hört sich aber nach weniger an^^ man könnte den weg ja auch nur aktualisieren lassen, wenn die fahnen benutzt werden dann.

---



jh am 25.10.2010 21:13 #6109


Spike: Die Auslastung der Wege ändert sich ja dynamisch - Du willst ja dass die Ware einen anderen Weg geht, wenn ein Weg überlastet ist. Das kannst du als nicht "einfach" vorberechnen.


Spike am 25.10.2010 22:08 #6110

Im Ruhestand
Ah achso, macht natürlich sinn :p
Naja, ich sollt mich eh lieber raushalten hab ja keine Ahnung, aber mehr leistung wäre schon, was ist eig zu den 0.1er und so anders geworden, dass das spiel so langsam ist?

---



SilSie am 26.10.2010 00:36 #6111


Zitat von Spike:

Ah achso, macht natürlich sinn :p
Naja, ich sollt mich eh lieber raushalten hab ja keine Ahnung, aber mehr leistung wäre schon, was ist eig zu den 0.1er und so anders geworden, dass das spiel so langsam ist?


Das würde mich (und ein paar andere) auch tierisch interessieren! Letztens beim Spielen sind wir auch eine Version vom März ausgewichen... nicht mal so sehr wegen Performanceproblemen, sondern auch weil wir kurz nach Start immer Abstürze hatten.


Spike am 26.10.2010 10:43 #6112

Im Ruhestand
Naja, wenn ihr Abstürze habt, sollte ihr schauen ob die Replays crashen und das dann reporten, dann gehen die ja auch mal weg.

---



~Gaßt am 29.11.2010 14:16 #6327


Genau SilSie, reporte mal!


SilSie am 01.12.2010 14:54 #6343


Zitat von Gaßt:

Genau SilSie, reporte mal!


Sagt ein "~Gaßt"? o.O




Feel free to post in English!

Antwort schreiben

Username:
Security code:
Text:

   
  Convert smilies like :), ;) etc. into small graphics?
  Convert WWW-addresses into clickable links?
  Soll Boardcode in ihrer Nachricht aktiviert werden?