Vekehrssimulation: NaSch-Modell

[Jazzman_Marburg]

Moin, Moin werte Experten!

Ich bin gerade dabei mich mit dem Nagel-Schreckenberg Modell auseinanderzusetzen, und hoffe mal, daß sich hier jamand von euch schon mal damit beschäftigt hat. Mein (Kopf) Problem ist nun, dass ich eine Klasse TStrasse habe, die die Fahrzeuge erzeugt und um die Zellen-Abstände zu ermitteln müßte man ja die zu simulierende Gesamtstrecke in Zellen (da ein zellulärer Automat) einer bestimmten Länge unterteilen.
Meine Frage ist nun: Sollte man die einzelnen Zellen wiederum als TZelle-Klasse implementieren (und anschließend in TObjectList packen) oder ist ein einfacher Record Typ (den man dann anschließend in ein Array packt) für die Implementierung der Zellen besser? Oder vielleicht ganz anders?

(Nur um Mißverständnissen vorzubeugen: Es geht nicht um die grafische Darstellung -- sondern zunächst nur um das Modell selbst.)

Ich hoffe es liest ein NaSch-Experte mit...

Vielen Dank & Gruß
Jazzman

[r2c2]

Du brauchst zuallererst mal eine Auto-Klasse. Das Auto hat ne Geschwindigkeit, ne Trödelwahrscheinlichkeit, etc.

Ein Auto kann beschleunigen, bremsen, trödeln und fahren. Der interessante Schritt ist das Bremsen: Ein Auto muss erkennen können, ob "vorne Platz ist". Das kann man auf mehrere Arten tun. Eine Möglichkeit wäre, dass die Autos einfach "auf die Straße gucken", d.h. die Straße fragen "ob noch frei ist" (sowas wie

Code:

distanceTo(road.getNextCar(Self))

).

Die Zellen werden so nicht direkt modelliert. Die Straße hat einfach ne Liste von Autos (nach Position sortiert) und jedes Auto kennt seine Position. Das wäre der schön lesbare objektorientierte Ansatz.

Es gibt noch mehr Möglichkeiten: Man könnte das tatsächlich als Zellulärautomaten implementieren. Also nur die Zellen, nicht aber die Autos modellieren. Wüde ich aber nicht vorschlagen, wenn du dazu keinen besonderen grund hast.

Sehr einfach, aber nicht mehr objektorientiert wäre der Ansatz die Straße als Array of Integer zu sehen, wobei jedes Element eine Zelle darstellt. In jedem Arrayelement steht die Geschwindigkeit und falls kein Auto drauf ist, -1. Du bräuchtest dann zwei Arrays. Ein aktuelles und eins für den nächsten Schritt.

mfg

Christian

[Jazzman_Marburg]

Hallo Christian,
danke für die prompte Reaktion!

Zitat von r2c2:

Du brauchst zuallererst mal eine Auto-Klasse. Das Auto hat ne Geschwindigkeit, ne Trödelwahrscheinlichkeit, etc.

Ist schon da: TFahrzeug mit V als aktuelle Geschwindigkeit, aktuelle Position (Nr. der Zelle), VMax, Trödelwahrscheinlichkeit und den Methoden Beschleunigen und Bremsen.

Zitat von r2c2:

Eine Möglichkeit wäre, dass die Autos einfach "auf die Straße gucken", d.h. die Straße fragen "ob noch frei ist" (sowas wie

Code:

distanceTo(road.getNextCar(Self))

).

Die Zellen werden so nicht direkt modelliert. Die Straße hat einfach ne Liste von Autos (nach Position sortiert) und jedes Auto kennt seine Position. Das wäre der schön lesbare objektorientierte Ansatz.

Dieser Ansatz gefällt mir gut -- aber ich habe damit noch Probleme:
Meine TStrasse erzeugt am Anfang sagen wir 10 Fahrzeuge und vergibt allen eine Position und alle anderen Parameter. Im nächsten Schritt werden dann die Modell-Schritte für jedes Fahrzeug ausgeführt:
1. Anz freier Zellen zum Vordermann
2. Beschleunigen
3. Bremsen
4. Trödeln
5. Fahren (Fahrzeuge auf die neuen Positionen gemäß V).
(6. Die Liste aller Fahrzeuge and die Grafik-Abteilung übergeben.)

Mein Problem: Nehmen wir an, ich möchte eine Strecke von 30 Kilometern simulieren. Jedes Strassen-Segment (Zelle) ist 7,5 m lang (es passt genau ein Fahrzeug rein) -- das hiesse 30.000 m / 7,5 m = 4000 Strassen-Segmente. Wo taucht jetzt diese 40000 auf, wenn ich die Zellen selbst nicht modeliere?

Ich hoffe meine Frage ist klar geworden: Ja, Zellen selbst nicht modellieren ist gut -- aber so ganz geht das doch nicht. Ich denke immer noch, ich bräuchte ein Array mit diesen Zellen. Jede dieser Zellen kann drei verschiedene Werte annehmen: 0 = frei, 1 = Auto steht, 2 Auto fährt mit V.

Oder ist das immer noch eine schräge Sicht der Dinge?

Vielen Dank & Gruß
Jazzman

[Medium]

Diese Werte kannst du dir doch aus einer "virtuellen Zellen-ID" ableiten. Jedes Auto merkt sich seine ganz aktuelle ID, und über entsprechende Properties der Straßenklasse (die ja ihre Autos kennt) iterierst du dann drüber und ermittelst live den Wert.

So als Gerüst in etwa sowas:

Delphi-Quellcode:

type
  TStrasse = class
  private
    FAutos: TList<TAuto>;
    function GetIsCellFree(cellIndex: Integer): Boolean;
  public
    property IsCellFree[cellIndex: Integer]: Boolean read GetIsCellFree;
  end;

implementation

TStrasse.GetIsCellFree(cellIndex: Integer): Boolean;
begin
  result := true;
  foreach a: TAuto in FAutos do
  begin
    if a.MyCurrentCellIndex = cellIndex then
    begin
      result := false;
      Exit;
    end;
  end;
end;

Sieht von aussen aus wie ein Array über die (nicht existenten) Zellen, ist aber keines. Es spart das tatsächliche Modelieren der Zellen als eigene Daten, erzeugt aber natürlich Such-Overhead. Overhead hast du aber natürlich auch, an anderer Stelle und potenziell weniger, beim Mitführen separater Zellklassen, die ja auch bei jeder Bewegung ihre Inhalte neu berechnen müssen. Welche der Varianten in der Praxis mit weniger Verwaltung "hinter den Kulissen" auskommt vermag ich aber nicht ganz abzuschätzen gerade. Im Mittel könnte das ggf. sogar aufs gleiche rauskommen.

[Jazzman_Marburg]

Hi!

Zitat von Medium:

Diese Werte kannst du dir doch aus einer "virtuellen Zellen-ID" ableiten. Jedes Auto merkt sich seine ganz aktuelle ID, und über entsprechende Properties der Straßenklasse (die ja ihre Autos kennt) iterierst du dann drüber und ermittelst live den Wert.

Sieht von aussen aus wie ein Array über die (nicht existenten) Zellen, ist aber keines.

Ich glaube der Groschen ist gefallen! Ich werde es mal genau so ausprobieren.

Super -- vielen Dank an euch beiden!

Gruß
Jazzman

[r2c2]

Zitat von Jazzman_Marburg:

Ist schon da: TFahrzeug mit V als aktuelle Geschwindigkeit, aktuelle Position (Nr. der Zelle), VMax, Trödelwahrscheinlichkeit und den Methoden Beschleunigen und Bremsen.

Und fahren()! Das tut das Auto ja auch selbst.

Zitat:

Meine TStrasse erzeugt am Anfang sagen wir 10 Fahrzeuge

Das ist eigentlich nicht Aufgabe der Straße. Die Straße sollte von Außen die Autos bekommen (DependencyInjection) und vielleicht noch ein AddCar(car: TCar) oder so haben.

Zitat:

1. Anz freier Zellen zum Vordermann

Brauchst du erstmal nicht berechnen. Das passiert im "Bremsen"-Schritt.

Zitat:

Mein Problem: Nehmen wir an, ich möchte eine Strecke von 30 Kilometern simulieren. Jedes Strassen-Segment (Zelle) ist 7,5 m lang (es passt genau ein Fahrzeug rein) -- das hiesse 30.000 m / 7,5 m = 4000 Strassen-Segmente. Wo taucht jetzt diese 40000 auf, wenn ich die Zellen selbst nicht modeliere?

Implizit über die Position der Autos. Und du kannst ja die Autos von der Straße entfernen, wenn die 4000 überschritten sind. Also TRoad.OnCarLeaving oder sowas.

Zitat:

Ich hoffe meine Frage ist klar geworden: Ja, Zellen selbst nicht modellieren ist gut -- aber so ganz geht das doch nicht. Ich denke immer noch, ich bräuchte ein Array mit diesen Zellen. Jede dieser Zellen kann drei verschiedene Werte annehmen: 0 = frei, 1 = Auto steht, 2 Auto fährt mit V.

Du brauchst das gar nicht. Die Autos müssen nur ihren Vordermann kennen. Wie lang die Straße ist, wie viele Autos noch da sind und was die tun ist denen doch egal.

Zitat:

So als Gerüst in etwa sowas:

Das geht, aber wie gesagt: eigentlich ist die Info gar nicht nötig. Und sie beraubt einem der Optimierungsmöglichkeiten. Wenn es nämlich - so wie ich oben vorgeschlagen hatte - nur eine Methode getNextCar() gibt, die einfach den Vordermann ausspuckt, ist es egal wie das implementiert wird. Man kann da schön optimieren. Beispielsweise ne HashMap nehmen, was den linearen in konstanten Aufwand verwandeln würde. Man könnte auch über verkettete Listen oder sowas nachdenken... Möglichkeiten gibts da viele. Wenn aber über die Array-Property zugegriffen wird, hat man kaum ne andere Wahl als die hier gezeigte. Nur mal so als Denkanstoß...

mfg

Christian