max_transfers Parameter entfernungsabhängig

[Oliver]

Also mal die Auswertung nach einem Monat.

Ich habe die Linien identisch angelegt und erhalte in etwa eine Steigerung der Passagiere um etwa 100%.
Zusätzlich kommt es zu Zustiegen von Passagieren, wo ich sie früher vermisst habe. Zaghaft sage ich jetzt mal, es könnte sein, dass das mit der ID der Linie gar nicht so daneben liegt...

Edit: Wäre dies tatsächlich der Fall, könnte man ein "Update Lines" einführen. Das geht sicher einfacher als dies manuell zu tun..

[Hans Dampf]

@Hajo

Die Wegsuche hat schon mal besser funktioniert. Erst bei einem bestimmten Änderungsstand ist es mir aufgefallen. Damals wollte ich nicht gleich wieder meckern. Da ich nur spiele ohne mich sonst zu beteiligen, kann ich auch ncihts anderes als meckern....... Natürlich kann es sein, das sich mein Spielstil weiterentwickelt hat. Und dieser Umstand eine Schwäche von Simutrans aufgedeckt hat. Ich meinte aber, es wäre etwa zu der Zeit, als die Flugzeuge eingeführt wurden. Und diese auch an Bushalstellen landeten...... Da musste natürlich was geändert werden. Ob dabei nun etwas anderes mitgeändert wurde oder die nötigen Änderungen eine vorhandene Schwäche aufdeckte, kann ich nicht sagen. Wie gesagt, ich kann nur die lange to do Liste durch mein meckern verlängern. Und da habe ich mich mal zurückgehalten.

mfG
Hans Dampf

[Hans Dampf]

@Oliver

Da habe ich was für Dich. Ich habe sonst meine einspurige Tram im Uhrzeigersinn und meine Schwebebahn gegen den Uhrzeigersinn laufen lassen, sozusagen die Gegenrichtung der Tram eine Etage höher verlegt. Dazu gehört, das dann alle Stationen nahezu gleichzeit gebaut werden. Und die Linie wurden auch gleichmäßig benutzt. Irgendwas wie die Leute benutzen nur die Tram und meiden die Schwebebahn konnte ich nicht feststellen.

mfG
Hans Dampf

[gpmfuchs]

@prissi wenn du 2-4 byte pro stations struct erübrigen kannst. (und nicht vor hast simutrans multicorefähig zu machen) Lässt sich das Problem linear lösen. indem du ne suchid generierst
und für einen konvoi die id und ne metrik (wievielte station) in der stationstruct speicherst. und für den nächsten geplanten konvoi alle stationen im fahrplan durchchecks ob die die aktuelle suchid haben und ob die metrik zusammen mit der neuen metrik kleiner ist als das bisherige optimum.

Dürfte dennoch einiges an overhead generieren. Wobei Ersatzstationen berechnen die ebenfalls überprüft gehören und sie durchchecken wohl auch erstmal nicht wesentlich besser aussieht.

[prissi]

Die Suchfunktion ist unabhängig vom Convoi und ist die Funktion, die Savegames gegen Ende langsamer macht (neben Signalen und Kreuzungen). Am Anfang kostet das Neuzeichnen der Bilder 20% der Rechenzeit, am Ende das Routing 20% und die Neuzeichnen 3%.

Jede Station hat eine Liste von direkt verbundenen Station für jeden Warentyp (also Passagiere, Post, Autos, Schüttgüter, ... ) Diese Listen sind sortiert nach Station-ID (waren früher unsortiert), damit der Test: Ist verbunden? deutlich schneller abläuft. (Man könnte noch die Zahl der Zwischenhalte bis zu dieser Station abspeichern, um Expresszüge zu bevorzugen.)

Ansonsten gibt es keine Metrik. Hätte ich eine, könnte ich A* drauf loslassen. Aber eine Metrik, die richtige Zahl von Umstiegen schätzt, ist praktisch unmöglich. Zumindest, wenn die Passagiere die Zahl der Umstiege und nicht die Zahl der Kästchen minimieren sollen.

[gpmfuchs]

Ich seh im Wesentlichen erstmal 2 möglichkeiten.
1. Simutrans wird auf abstand optimiert. Sprich Leute suchen sich den Kürzesten km technischen weg.
Dann wärn alles mit abstand etc. relativ einfach. um auf nen A* baum zu kommen

2. Simutrans wird auf umsteigezeiten + fahrplanhalte optimiert. Wobei es irgendnen faktor > 1 gibt der umsteige * f in fahrplanhalteinheiten umrechnet.
Soweit (wikipedia) brauchen wir kantenlängen. (die lassen sich bei der "verbindung zum nächsten knoten" berechnung aus den fahrplänen der beteiligten konvois errechnen).
Ich müsste noch mehr lesen um zu wissen ob die Kantenlänge von a nach b = der kantenlänge von b nach a sein muss. Was wir in unserem Fall ja nicht haben. (Ein fahrplan mit 3 eintragungen, ermöglicht ne fahrt von a nach b in 1 aber von b nach a brauchts 2 ). Sowie addieren wir zu ner Kantenlänge den globalgleichen Umsteigemalus (der sich aus der Verzögerung beim umsteigen ergibt).
So nun brauchen wir ne Heuristik die berechenbar ist. Das einzige was mir da einfällt ist eben den knotenabstand zu verwenden und mit dem Umsteigemalus zu multiplizieren.
Die Frage ist mehr ob wir so wie A* sucht, es schaffen den Knotenabstand vorrauszuberechnen.
Sonst hätten wir als Notlösung immer noch 0 für den zielpunkt 1 für alle damit verbundenen stationen und 2 für alle anderen, was die Bedingung erfüllt das A* den optimalen Weg findet.
(ich fürchte nur das sowas die Laufzeit ordentlich verhagelt)

Nachtrag:
Ne kleine verbesserung.
herutistik am ziel auf 0
alle mit ziel verbundenen auf 1
evtl start auf 4 (bzw 5 und mit dem start verbundenen auf 4 wobei wir da den A* analysieren müssen wenn wir ihn so betrügen wollen)
A* loslaufen lassen.
alle knoten die mit jemanden mit 1 verbunden sind auf 2
alle anderen auf 3

(hmm ein wenig suboptimal fällt mir gerade auf ich verstecke nur die laufzeit O(k^2) k verbindungen pro knoten in O(k*l) l durchsuchte knoten)

Wieviel Stationen hat so ein Riesenspiel spiel? sonst liesse sich ne n^2 Tabelle mit den Knotenlängen zwischeneinander einführen. Woraus die Heuristik in der passenden Zeile einfach ablesbar ist.

[prissi]

Riesenspiel ist gut: 256*256 Karte, 2000 Konvois, 600 Stationen. Liste kommt daher wohl nicht in Frage ...

Im übrigen habe ich mich schon recht lange an Optimierungen dort versucht. Schließlich optimiere ich ja die langsamsten Routinen zuerst.

[gpmfuchs]

600*600 ~ 36000 a 1 byte (verbindungen über 255 knoten sind eh nicht erlaubt). macht 360 kB pro Gütertyp 3MB?
(wenn wirs noch weiter optimieren wollen lassen wir mit bitspielereien maximal 15 umsteigeknoten zu und reduzieren den Speicherverbrauch auf die Hälfte)
(wobei bei solch grossen Speicherbereichen wohl ne pointerlistXspeicherbereich besser ist)
Ich denke rein Speicherplatzmäsig wäre das wohl noch im Rahmen.
Die Frage ist wohl mehr ob sich so ne Tabelle rechenschonend erzeugen lässt.
Eine neue Verbingung dürfte Recht einfach durch die Tabelle wandern.
Ein vernichtete Verbindung ...
Vielleicht ist der D* ein guter Gedankenansatz.
Ein neuer Knoten muss auch nicht viel kosten wenn wir in der Tabelle genug Platz für Zusatzknoten lassen.
und nen alten Knoten entfernen muss mit ner zusätzlichen bitlist welche Knoten gesetzt sind auch nicht teuer werden.

Wobei Verbindung dazu/weg ja nur bei Fahrplanänderungen statfinden. und Knoten dazu/weg nur bei Stationsbauten. wobei auch da erst noch ein Fahrplan drauf gesetzt werden muss. (Wenn man die Neuberechnung noch einige sekunden verzögert und in den Hintergrund verschiebt, kann der Benutzer friedlich bauen/zurückbauen)

Wir hätten damit A* mit ner relativ guten Heuristik ermöglicht und das maximum aus der Fahrstreckenberechnung rausgeholt, und es in Speicher + Berechungen bei Fahrplanänderung/Stationsbau verwurschtet.

[prissi]

Ich verstehe nicht, was du willst. Bevor man hier irgendwelche Vermutungen geäußert werden, rate ich zu einem Blick auf den Sourceode. simhalt.cc suche_route und alles was dazugehört. (Außerdem möchte ich wissen, wie du eine Route mit maximal 9 Stops als ein Byte speicherst. Das braucht midestens einen Pointer, einen counter und dann die Halthandles. Macht bei mir 4+9*2+2=24 Byte).

Die Stationen merken sich nur nächste Nachbarn. Ein vorberechnetes Routing ist völlig illusorisch, denn das müsste an jeder Station für alle Stationen sein. Das dauert aber recht heftig. Das Update nach einer Fahrplanberechnung geht schon jetzt nur nach und nach. Bei dem großen Spiel dauert es (schon extrem optimiert) über drei Minuten. Und dass muss bei jeder möglichen Fahrplanänderung (also auch Änderungen des Einzugsbereiches durch Stationsausbau) upgedated werden. Das Feststellen aller Direktverbindungen ohne Umsteigen ist nach ca. drei Minuten zu Ende.

(Zum Selbertesten mal nach Yoshi87.sve suchen.)

Wann glaubst wäre die Berechnung aller Routen abgeschlossen? (Einmal benutzte Routen bis zur nächsten Fahrplanänderung in einer Tabelle als Kompromiss cachen hatte nicht viel gebracht, da die Passagiere meistens genau dort hinwollen, wo noch keine berechnet war ...)

[Oliver]

Ich weiss nicht, ob es direkt mit der Diskussion zusammenhängt, aber im Logfenster erscheint regelmäßig folgender Fehler:

ERROR: haltestelle_t:tarte_mit_route(): route cannot contain us as first transfer stop => recalc route!

In etwa alle 2-4 Sekunden.