Algorithmus zur Routenführung und Wegfindung der CiMs

  • Sehr geehrte Gemeinde,


    während des Baus meiner Karte ist mir beim Testen der Karte immer wieder die Absurde und absolute krude Wegfindungslogik der CiMs aufgefallen. Es werden riesige Umwege gefahren, absolut sinnlos umgestiegen, mehrere Stunden Umweg liebend gern in Kauf genommen. Ich würde die Logik gerne komplett überarbeiten. Ich weiß nicht, ob CO bereit ist an dem Spiel noch Veränderungen vorzunehmen, vor allem eine solch Spielentscheidende und Grundliegende. Ich bin nach wie vor überzeugt, dass dieses Spiel unglaublich potenzial hat, aber hier und da immernoch an Kinderkrankheiten schwächelt, die wohl nicht gelöst werden.
    Nichtsdestotrotz habe ich die letzten Tage immer wieder gesessen und mir Gedanken gemacht, wie man die Wegfindung verbessern und das Spiel optimieren könnte. Ich habe mir Grundsätzlich zu einigen Punkten erst einmal Gedanken gemacht und versucht diese hier in Worte zu bringen, ich bin kein Programmierer, hatte auch nicht so den Nerv mich wieder so in das Thema reinzufuchsen, aber hier sind fähige Leute im Forum unterwegs, die damit noch mehr anfangen können als ich.


    Wichtig an meinem Verständnis der Wegfindung ist, das es keinen Haltestelleneinzugsbereiche gibt. Das ist unrealistisch und leider nur eine Möglichkeit sich das Leben leicht zu machen. Leider befürchte ich auch, das genau das zu den bekannten Problemen im Spiel führt, aber das sind nur Spekulationen.


    Jeder Fahrgast möchte so schnell wie Möglich sein Ziel erreichen, das hat immer oberste Priörität und ist Grundlage der Routenberechnung. Also dienen die Abfahrtszeiten der Fahrpläne als Berechnungsgrundlage, da die ohnehin ja irgendwo im Spiel festgeschrieben und verfügbar sein müssen.




    Bei jedem "Start" wird zuerst der Laufweg zum "Ziel" berechnet, außerdem die Zeit, die die Person mit dem Auto zurücklegen würde(Ich weiß nicht inwieweit es Möglich ist Staus z.B. mit einzuberechnen) und dazu die Pkw Kosten(100m*0.20€)?? (Man müsste natürlich einen passenden Wert hierfür finden) Je nach Schwierigkeitsgrad ließen sich hier und da die Parameter ändern.



    Laufwege z.B. unter 30min könnten generell gelaufen werden, ohne überhaupt auf PKW oder ÖPNV zurückzugreifen.
    Mir ist noch wichtig das das Umsteigen unbedingt mit Einberechnet wird, jedoch wusste ich nicht, wie ich das am Besten hier Visualisiere.
    Ich als Fahrgast bin zum Beispiel bereit eine Strecke von 10% bis 20% längerer Fahrzeit in Kauf zu nehmen, wenn ich dafür garnicht oder weniger Umsteigen muss. Das sollte unbedingt in die Berechnung mit einfließen.




    Ich hoffe hier im Forum stößt das Thema vielleicht bei dem ein oder anderen auch auf Gegenliebe und man kann hier zusammen einen ordentlichen Algorithmus entwickeln, ich finde CiM nach wie vor Spannend und würde mich freuen wenn wir alle unseren Beitrag dazu leisten könnten das Spiel zu verbessern. Ich hoffe das CO gewillt ist das Spiel nicht sterben zu lassen sondern sich hier und da Anregungen aus der Community holen.

  • Hallo liebe Gemeinde,


    also ich glaube die Wegfindung ist schon relativ ausgeklügelt auch mit solchen Algorithmen wie du sie hier geschrieben hast. Das Problem ist nur wir verstehen sie nicht richtig und niemand kann es wirklich Erklären wie sie aufgebaut ist. (es gibt ja leider keine offiziellen Daten dazu.)



    Ich hatte immer folgendes Problem (siehe Bild, die ist ein ausschnitt aus meinem Netz) Haltestelle 1 steigen 180 Personen in meine U-Bahn und 90% wollen zur Haltestelle 7. Logische folge sie fahren von 1-7 mit der U-Bahn durch ist am schnellsten.


    CIms fahren aber von 1 bis 2 steigen in die Monorail und fahren dann bis zur 7. Wo ist da der Sinn da es ja länger Dauert.


    Nun habe ich zu mindest für dieses Problem die Lösung gefunden
    Meine Preise waren alle auf Grün eingestellt was ungefähr diese Preise entsprach


    U-Bahn 8,50
    Monorail 2,50
    Einzeltickets, Zonen dementsprechend teurer.


    also war es für die Cims billger 2 Zonen U-Bahn und 2 Zonen Monorail zu fahren somit haben sie auch die längere Fahrzeit in kauf genommen.



    jetzt habe ich es so angepasst das die U-Bahn 4 Kostet (nun Blau) und die Monorail 3,30 (nun Weiß) jetzt teilen sich die Personen auf beide Fahrzeuge auf und ich mache mehr Gewinn und die Zufriedenheit steigt sowie die Fahrtdauer sinkt. Dazu kommt das meine Monorail nun nicht mehr im 5 min Takt komplett überfordert ist.



    Also mein Tipp ist es die Preise für die Verschiedenen Fahrzeug Typen ziemlich gleich zu halten selbst wenn dann ein Fahrzeug hellblau wird und ein anderes vielleicht orange letztendlich ist die Wegfindung für die CIM dann leichter und sie nehmen wirklich den kürzesten weg zu ihrem Ziel.


    würde mich freuen wenn jemand das Bestätigen oder auch wiederlegen könnte.

  • Ich muss ehrlich zugeben, dass ich bisher die Preise als Grund für das (bisher wahhlose) Umsteigen nie wirklich in betracht gezogen habe.
    Aber wenn man bedenkt, dass die Verkehrsmittel teilweise große Preisunterschiede aufweisen, gerade bei Zonenwechseln, wirkt der Wegfindungsalgorithmus wieder etwas sinnvoller ;)
    Zwar noch nicht 100% sinnvoll, es gibt immer noch einige nicht nachvollziehbare Wege, aber immerhin etwas verständlicher als vorher ;)


    In dem Zusammenhang würde ich mir wünschen, dass man als Spieler die Möglichkeit hat, die Preispolitik so zu reduzieren, dass es nur noch Zonentickets gibt, unabhängig vom genutzen Fahrzeug.
    Alternativ kann man natürlich auch jetzt schon einfach alle Preise auf ein Einheitliches Niveau setzen, aber das hat ja auch wieder auswirkungen auf die Beliebtheit der Firma.
    Naja jedenfalls weiß ich jetzt, wieso ich diese Umstiegsprobleme auf meiner Testkarte nicht hatte. Dort war nämlich der öffentliche Nahverkehr für alle Nutzer kostenlos ;)

  • Klingt sehr logisch ;)
    Zumal jetzt mal einer aus der Sicht der CiMs an die Sache herangegangen ist und nicht aus der Sicht des Verkehrsunternehmens. Soweit ich beobachten konnte, hat es nicht unbedingt eine große Auswirkung auf das Firmen-Image, wenn ein, zwei Fahrpreise mal auf Gelb sind. Vielmehr ist die Pünktlichkeit wichtig.


    Schreibt das mal einer schick ins Lexikon? Am besten zur Linienführung oder einen neuen Beitrag zur Preisgestaltung (oder beides :D )

  • Interessant, aber das das so ein Chaos im Spiel verursacht, das hätte ich nicht gedacht. Das erklärt aber immernoch nicht, wieso CiMs auch oft von einer Buslinie in eine andere Busline umsteigen, obwohl auch das keinen Sinn macht, weil beide Strecken parallel laufen und die selben Haltestellen anfahren. An der Geschwindigkeit und am Preis kann es ja dann nicht liegen ..

  • Das kann unter anderem daran liegen, dass die CiM Umwege in Kauf nehmen, um mit Fahrzeugen mit höherer Servicequalität zu fahren.
    Selbst wenn sie mit Linie A ans Ziel kommen, steigen sie breitwillig von Linie A in Linie B um dann wieder in Linie A zu steigen, nur weil auf Linie B Fahrzeuge mit höherer Qualität unterwegs sind.
    Nur wenn Preis, Qualität, Zeit, der Zufall, unbekannte Faktoren und das Werk der CiM2 Hexen stimmen, machen die CiM das, was man erwartet ;)

  • Vermutlich wird die Route vor Beginn der Reise berechnet. Jeder Linie wird wahrscheinlich eine Interne "Beliebtheit"-Wertung haben, die sich aus der Pünktlichkeit / Wartezeit / Beliebtheit /Servicequalität der Fahrzeuge zusammensetzt. Die KI wird letztendlich ein ganzen Batzen an Informationen zusammenwerfen und einen kurzen und preisgünstigen Weg errechnen. Dieser beruht dann aber auf Wahrscheinlichkeiten und die tatsächlichen Reisezeiten können dann deutlich schlechter sein.


    Aber auch das ist realistisch. Fahrgäste nehmen nicht immer den besten und einfachsten Weg. Sie irren sich schlichtweg auch mal. Am besten, man akzeptiert diese Pfadfindungsystem so, wie es ist und versucht es zu verstehen. Ändern wird sich vermutlich nichts daran.


    und das Werk der CiM2 Hexen stimmen


    Ich bin ab sofort für ein "Schwarze Katzen DLC", daß dann auch Hexen und Magier enthält. Diese können dann die CiMs auch von Station zu Station hexen. Die schwarzen Katzen laufen dagegen den Busfahrern über den Weg ... :D

  • CIM2 benutzt einen statischen Pseudo-Zufallszahlengenerator (damit beide Rechner synchron laufen) um zum Beispiel den Gebäudeeingang zu wählen und scheinbar auch die die Position wo eine wartender Passagier steht. Wenn zum Beispiel ein Fahrer einen Passagier ignorieren wird (weil sein Lohn zu niedrig ist) wird durch eine Zufallsentscheidung beeinflusst. Die genaue Position wo CIM2 auswählt eine Linie zu nutzten hab ich leider noch nicht gefunden, bzw. ich kann zurzeit nur Raten...


    -edit-
    Auf jedenfalls reagiert CIM2 intern nach Zeit, Qualität, Preis jeweils unterschiedlich nach sozialer Gruppe, wie viele Zonen genutzt werden wird auch berechnet.

  • Das erklärt immernoch nicht wieso sie umsteigen, wenn auf den parallel verlaufenden Linien die selben Fahrzeuge fahren, zwar bietet Mediziners Erklärung einen Ansatz, ist dennoch aber sehr nervig.
    Zumal mein Wert für Fahrgastzufriedenheit im Regelseteditor auf 200% gestellt wurde, d.h. alle Fahrzeuge ingame mit 100% Fahrgastqualität dargestellt werden und sich das als Erklärung eigentlich nicht eignet..

  • Frag CO nach dem Quelltext mit Kommentaren und eindeutigen Variablen Namen dann kann ich es dir sagen.
    Ich gehe mal davon aus, sobald ein Transport Vehicle stoppt, errechnet CIM2 für jeden Passagier eine neue Route.

  • Es scheint aber dennoch eine art interne Bewertung für Linien zu geben.


    Hier habe ich 2 O-Bus Linien die beide zu meinem Zentralen Umsteigepunkt führen. An Haltestelle 1 und 2 fahren 2 Linien, und ich habe beobachtet wie die Cims an Haltestelle 1 umsteigen und auf Linie 2 warten um zur letzten Haltestelle zu fahren. Auf beiden Linien fahren genau die selben Fahrzeuge, es kann also nicht nur an der Servicequalität oder an der Art des Fahrzeugs liegen.


    [Blocked Image: http://www.citiesinmotion.net/wcf/images/photos/thumbnails/small/photo-842-2e5bde9c.jpg]

  • Evtl hat es auch etwas damit zu tun, wie gut ausgebaut, die Haltestellen sind, an denen eine Linie stoppt. Unabhängig ob es für die von den CiMs benutzte Haltestelle zutrifft oder nicht? Das heißt, wenn die Mehrheit der Haltestellen von O-Buslinie 1 den vollen Standards entsprechen, die Mehrheit der Haltestellen von O-Buslinie 2 aber nur ein kahles Schild sind, dann ist Linie 1 einfach beliebter. Auch wenn es die gleichen Fahrzeuge sind.


    Dann kommt evtl. auch noch die Attraktivität der Fahrzeuge im Zusammenhang mit ihrem Verschleiß in Betracht? Auch wenn die Servicequalität aller Fahrzeuge die gleiche ist, so ist vlt Linie 1 länger als Linie 2, das heißt der durchschnittliche Verschleiß der Fahrzeuge größer und damit die Servicequalität niedriger als bei Linie 2. Das wäre eine weitere mögliche Erklärung.


    Irgendein Entwickler hat schon mal ein paar Infos über das System preisgegeben. Aber wirklich viel mit anfangen konnte man nicht. Es gibt wohl eine durchschnittliche Wartezeit für das gesamte System, die als Berechnungsgrundlage der CiMs genutzt wird. naja und dann kommen halt weitere Merkmale dazu. Er hat aber auch bestätigt, dass die optimale Route VOR Fahrtantritt einmalig berechnet wird, nicht immer wieder. dann würde das System bei einer Vielzahl von Berechnungen irgendwann kollabieren.


    Was ich auch interessant finde: Es gibt in CiM2 eigentlich gar keine Fußgänger. Zu Fuß gehen die Leute nur von der Haltestelle zu ihrem Haus und umgekehrt oder zu ihrem Auto. Lange Strecken laufen die CiMs nur dann zu Fuß, wenn sie wütend an der Haltestelle gewartet haben und kein Bus/Zug kam. dann laufen sie die Strecke, die sie eigentlich mit den öffentlichen zurücklegen wollten.


    All jene, die gar kein Auto haben, aber auch keinen Anschluss an die Öffentlichen, laufen nicht. Sie nutzen die aller komfortabelste Fortbewegungsart: Beamen. Müsst ihr mal drauf achten. In Gebieten, die ihr nicht bedient, ist der Anteil der "Beamer" recht hoch. Würde sagen jeder 2.

  • Ich baue immer nur die am besten ausgebauten Haltestellen, daan mag es also auch nicht liegen. (Zählen die Wartungskosten für Haltestellenhäuschen eigentlich in die Unterhaltskosten einer Linie mit rein? Wenn ja, werden die Wartungskosten geteilt wenn mehrere Linien die Haltestelle bedienen?)
    Der Verschleiß klingt in dem Zusammenhang noch logisch. (Und ich bin Stinksauer das ich seit Einführung des Regelseteditors den Verschleiß der Fahrzeuge nicht auf ein Minimum reduzieren kann)

  • Code
    werden die Wartungskosten geteilt wenn mehrere Linien die Haltestelle bedienen?


    Ich glaube nicht. Weil wenn man zum Beispiel eine Busstation in eine Bus/Tram Station upgradet, erscheinen plötzlich bei Trolleybussen auch wartungskosten, obwohl ich kein einzigen Trolley habe.... Denke eher dass jede Linie die Wartungskosten pro Haltestelle bezahlt, sprich wenn 3 Linien das gleiche Häuschen benutzen bezahlt mal 3 mal Unterhalt. :(

  • Code
    werden die Wartungskosten geteilt wenn mehrere Linien die Haltestelle bedienen?


    Ich glaube nicht. Weil wenn man zum Beispiel eine Busstation in eine Bus/Tram Station upgradet, erscheinen plötzlich bei Trolleybussen auch wartungskosten, obwohl ich kein einzigen Trolley habe.... Denke eher dass jede Linie die Wartungskosten pro Haltestelle bezahlt, sprich wenn 3 Linien das gleiche Häuschen benutzen bezahlt mal 3 mal Unterhalt. :(

    Kann man denn die Wartungskosten so pauschal auf die Linien umsetzen? Diese werden doch einfach anhand der Haltestellenanzahl berechnet. Eine Bushaltestelle verursacht demnach nur einmal Kosten, egal wie viele Linien diese bedienen. Der Grund warum auch beim Trolley Kosten auftauchen ist der, dass die Bushaltestellen auch gleichzeitig Trolleyhaltestellen sind - die Kosten werden in diesem Falle auf die beiden Transporttypen verteilt.

  • Ja, die für mich entscheidende Frage war, ob die Kosten in die Line reinzählen. Wenn man die Linie anwählt, dann hat man ja eine Übersicht über Kosten und Unkosten, werden die Haltestellenkosten da mit einberechnet?

  • Nachfragen nach dem funktionieren der Wegfindung ist im offiziellen Forum scheinbar nicht mehr gewünscht. "Thank you for posting! Your post will not be visible until a moderator has approved it for posting."

Participate now!

Don’t have an account yet? Register yourself now and be a part of our community!