1. Dashboard
  2. Forum
  3. Filebase
  4. Lexikon
  5. Artikel
  6. Spieletest
  7. Mitglieder
    1. Letzte Aktivitäten
    2. Benutzer online
    3. Team
    4. Mitgliedersuche
  8. Zur Transport Fever Community
  • Anmelden
  • Registrieren
  • Suche
Dieses Thema
  • Alles
  • Dieses Thema
  • Dieses Forum
  • Artikel
  • Seiten
  • Forum
  • Filebase-Eintrag
  • Lexikon
  • Artikel (Bewertungssystem)
  • Erweiterte Suche
  1. WiSim Welt
  2. Forum
  3. Spiele
  4. Cities in Motion 2
  5. Allgemeines

Algorithmus zur Routenführung und Wegfindung der CiMs

  • Sotrax
  • 2. Januar 2014 um 18:52
1. offizieller Beitrag
  • Sotrax
    Fortgeschrittener
    Beiträge
    542
    • 2. Januar 2014 um 18:52
    • #1

    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.

    Code
    Es werden bei jedem "Start" die 10 nähesten Haltestellen abgefragt.
    	Sind Haltestellen vorhanden?
    		Ja - Linien1 in 10min Fußweg zur Hst, Linie2 8min Fußweg zur Hst, Linie3 20min Fußweg zur Hst
    			Linie1 - 10min Fußweg + 30min Fahrtweg + 15min Fußweg = 55min
    			Linie2 - 8min Fußweg + 49min Fahrtweg + 4min Fußweg = 61min
    			Linie3 - 20min Fußweg + 15min Fahrtweg + 10min Fußweg = 45min
    
    		Nein
    			Beträgt der Laufweg mehr als 1h?
    			Ja - Fahre mit Auto
    			Nein - Laufe
    
    
    	Wie hoch sind die Fahrkosten?
    		Günstiger als PKW?
    			Ja - Fahre ÖPNV
    			Nein - Fahre Auto
    
    
    	Wie lange ist die Fahrzeit, verglichen mit dem PKW?
    	Fahrzeit mit ÖPNV weniger als 2x die Fahrzeit mit PKW?
    		Ja - Fahre ÖPNV
    		Nein - Fahre PKW
    Alles anzeigen

    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.

    Kutscher am Hofe Berlins.

    Einmal editiert, zuletzt von Sotrax (2. Januar 2014 um 18:56)

    • Zitieren
  • Agitelos
    Anfänger
    Beiträge
    47
    Filebase Einträge
    1
    • 12. Januar 2014 um 16:18
    • #2

    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.

    Multiplayer Let's Play (In Arbeit)
    auf einer freien Map ohne vorhandene Straßen oder Gebäude
    Google+ Seite

    • Zitieren
  • Xanos
    wcf.user.rank.superModerator
    Reaktionen
    3
    Beiträge
    1.018
    Filebase Einträge
    5
    • 12. Januar 2014 um 16:30
    • #3

    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 ;)

    Xanos Let's Play

    Einmal editiert, zuletzt von Xanos (12. Januar 2014 um 17:21)

    • Zitieren
  • mediziner
    Administrator
    Reaktionen
    2
    Beiträge
    1.924
    Filebase Einträge
    10
    Einträge
    4
    • 12. Januar 2014 um 17:15
    • Offizieller Beitrag
    • #4

    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 )

    • Nächster offizieller Beitrag
    • Zitieren
  • Sotrax
    Fortgeschrittener
    Beiträge
    542
    • 12. Januar 2014 um 17:50
    • #5

    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 ..

    Kutscher am Hofe Berlins.

    • Zitieren
  • Xanos
    wcf.user.rank.superModerator
    Reaktionen
    3
    Beiträge
    1.018
    Filebase Einträge
    5
    • 12. Januar 2014 um 18:25
    • #6

    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 ;)

    Xanos Let's Play

    • Zitieren
  • mediziner
    Administrator
    Reaktionen
    2
    Beiträge
    1.924
    Filebase Einträge
    10
    Einträge
    4
    • 12. Januar 2014 um 18:38
    • Offizieller Beitrag
    • #7

    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.

    Zitat von Xanos

    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

    2 Mal editiert, zuletzt von mediziner (12. Januar 2014 um 18:38)

    • Vorheriger offizieller Beitrag
    • Nächster offizieller Beitrag
    • Zitieren
  • eis_os
    Profi
    Beiträge
    1.025
    Filebase Einträge
    2
    • 12. Januar 2014 um 18:42
    • #8

    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.

    Einmal editiert, zuletzt von eis_os (12. Januar 2014 um 18:54)

    • Zitieren
  • Sotrax
    Fortgeschrittener
    Beiträge
    542
    • 12. Januar 2014 um 18:45
    • #9

    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..

    Kutscher am Hofe Berlins.

    • Zitieren
  • eis_os
    Profi
    Beiträge
    1.025
    Filebase Einträge
    2
    • 12. Januar 2014 um 19:01
    • #10

    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.

    • Zitieren
  • Xanos
    wcf.user.rank.superModerator
    Reaktionen
    3
    Beiträge
    1.018
    Filebase Einträge
    5
    • 12. Januar 2014 um 19:03
    • #11

    Das glaube ich nicht.
    Die Passagiere stellen sich ja an Haltestellen und legen sich schon dann auf eine gewisse Route fest. Auch wenn ein Fahrzeug einer anderen Route anhält, welche auch zum Ziel führt, wird dieses Fahrzeug nicht benutzt.

    Aber naja, wirklich wissen kann man das ja alles nicht :(

    Xanos Let's Play

    • Zitieren
  • Satan
    Schüler
    Beiträge
    74
    Filebase Einträge
    1
    • 17. Januar 2014 um 18:15
    • #12

    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.

    • Zitieren
  • Sotrax
    Fortgeschrittener
    Beiträge
    542
    • 17. Januar 2014 um 19:16
    • #13

    Danke Satan, das ist exakt die selbe Problemstellung die ich auch ständig habe, danke für die bildliche Untermalung. :D

    Kutscher am Hofe Berlins.

    • Zitieren
  • deejay
    Gast
    • 18. Januar 2014 um 18:24
    • #14

    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.

    • Zitieren
  • Sotrax
    Fortgeschrittener
    Beiträge
    542
    • 18. Januar 2014 um 18:48
    • #15

    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)

    Kutscher am Hofe Berlins.

    • Zitieren
  • galippo
    Schüler
    Beiträge
    70
    • 19. Januar 2014 um 22:27
    • #16
    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. :(

    • Zitieren
  • X-Mex
    Schüler
    Beiträge
    115
    Filebase Einträge
    1
    • 19. Januar 2014 um 23:03
    • #17
    Zitat von galippo
    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.

    150 Jahre London Tube Map!

    • Zitieren
  • Sotrax
    Fortgeschrittener
    Beiträge
    542
    • 19. Januar 2014 um 23:09
    • #18

    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?

    Kutscher am Hofe Berlins.

    • Zitieren
  • rovapasi
    Gast
    • 26. Februar 2014 um 22:02
    • #19

    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."

    • Zitieren
  • Sotrax
    Fortgeschrittener
    Beiträge
    542
    • 26. Februar 2014 um 22:03
    • #20

    Oh nett, da kann jemand mit Kritik nicht umgehen? :D

    Kutscher am Hofe Berlins.

    • Zitieren

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!

Benutzerkonto erstellen Anmelden

Twitch

  1. Datenschutzerklärung
  2. Impressum
Community-Software: WoltLab Suite™