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? ^^