18-03-2007, Sunday-03:13:44
@prissi es ist deadlock frei (bis auf Spezialfälle), Richtung ist komplet egal.
Es gibt auch Passagierschiffe und manchmal müssen Schiffe 2 Kontinente Verbinden (dazu noch apoteken versorgen etc).
Und da Schiffe relativ langsam sind, braucht man tatsächlich für längere Strecken deutlich mehr Schiffe. Was dazu führt das pro Linie schonmal 2 oder 3 Schiffe notwendig waren, ich hab z.B. jetzt einen Hafen der von 11 Schiffen angesteuert wird wovon 3-6 an ihm warten. Und der hafen ist genau ein Feld breit, deswegen kam ich auf die Idee)
Der Grundgedanke hinter der ganzen Geschichte mit Deadlock ist, das nur 2 Schiffe stehen können 3 aber gleichzeitig auf ein Feld dürfen. Damit ist immer ein Slot fuer Wege frei. (ich hab anno dazumal ein 2D Echtzeittestspiel gebaut, was auf dem Prinzip aufbaut. Deadlocks sind bei entfernteren Zielorten nicht möglich)
Also 3 Slots pro Feld. Das Schiff reserviert seinen Weg bis zu einem Feld an dem es stehen kann.
Wenn das nicht geht, weil bei einem Zwischenfeld alle 3 Slots voll sind, wird sich dieses bald geleert haben, nachdem ja ein Slot nur eine Bewegung ist und das Schiff darauf nicht stehen kann. Das wartende Schiff selbst verursachte keine Regelbrüche weil es ja auf seinem Feld sowieso nen WarteSlot reserviert hat.
(das ist der Grund warum es keine Deadlocks geben kann, der Gedanke dahinter ist ähnlich wie meine Deadlockfreie Bauweise beim alten Signalsystem mit Vorsignalen, oder der Grund warum es beim jetzigen Zugsystem kein Deadlocks zwischen Haltestellen gibt und die Deadlocks die man durch falsche Haltstellenwahl aufbauen kann, wird es bei Schiffen nicht geben, weil sie an jedem Feld dazwischen ne Pause einlegen können, und ausserdem Metrisch fahren (sprich es gibt keine Richtungsschilder).)
Das Verzichten auf Richtungsschilder ist tatsächlich nötig um immer Deadlockfrei zu sein. Wer sie verwendet, macht sich allerdings normalerweise Gedanken darüber (bei schiffen sind sie selbst dann noch extrem unwahrscheinlich). Das ganze System verändert tatsächlich nur was an den Häfen.
Beweis:
Ein Deadlock entsteht wenn A->b will von C daran gehindert wird und C->d will und (ueber mehrere Schritte) von a daran gehindert wird. Oder Das A->b will und sich selbst im Weg steht
Fall 0
A steht sich selbst im Weg, ist nicht möglich. Weil a auf seinem Feld bereits nen Warteslot belegt und dort warten darf. Bzw garnicht erst losfährt.
Also:
Annahme >->b wird von C gehindert.
Fall 1 C steht da nur rum.
Fall 1a C Steht auf dem Weg und nicht dem Ziel
da Anzahl stehender Schiffe < als Anzahl fahrender Schiffe. gibt es fuer a die Möglichkeit über das Feld zu fahren. Falls A diese Möglichkeit nicht hat liegt es also nicht an C sondern an einem Schiff E was wiederum nicht rumsteht ->Fall 2. (ausser wir haben alte Karten geladen, aber da gilt die sonderregel das wenn mehr als 2 schiffe auf dem feld sich befinden sie als 2 Schiffe eingetragen werden).
Sollte E auch rumstehen gilt das gleiche wie hier und es muss an F liegen was nicht rumstehen darf (nach der maximal 2 Schiffe dürfen stehen Regel)
Fall 1b C Steht auf dem Ziel
Fall 1b' Entweder das feld ist mit C und einem Weiteren die dort warten besetzt, dann kann A da nicht hin, (aber A kann relativ nahe meist Nachbarfeld hinfahren) deswegen gibts ja die Regelung. (aber das ist nicht der deadlock fall, weil C ja garnicht vorhat weiterzufahren, das ist ein ganz normaler Ladestau wie ihn ne LKWkolone einer Linie an nem Frachthof hat, der genau wie dort den Verkehr dorthin oder zum Nachbarfeld einschränkt).
In der Erweiterung würde sich A einfach einen anderen Platz an dem Hafen suchen, und diesen Ansteuern. (Auch dabei wird kein Livelock entstehen können, das liegt an der metrikstruktur von Simutrans)
Fall 1b'' C steht dort wird aber von A daran gehindert wegzufahren.
Das geht nur unter den Umständen das A zum Deadlockeintritt genau auf dem Feld Stand, zu dem C hinwill. (Das ist tatsächlich der einzige Deadlock Fall mehr unten). Falls C nicht dahinwill wo A steht kann es nachdem auf jedem Weg ein Slot frei ist auf den nur drübergefahren werden darf aber nicht gehalten. zum nächsten Feld auf seiner Route fahren an dem es Halten darf ->kein Deadlock
Fall 2 C steht da nicht rum sondern fährt über das Feld (und ist in bewegung oder hat dieses Feld nur reserviert)
Fall 2a C ist in Bewegung Widerspruch zu Deadlock
Fall 2b C hat dieses Feld nur Reserviert.
Wenn C das getan hat, dann hat es eine durchgehende Strecke bis zu seinem Punkt an dem es Stehen bleiben kann reserviert -> es gibt keine Behinderungen die Bewegung von C kann beginnen -> kein Deadlock
Fall 1b''
man nehme einen Kanal - ist ein feld
A----------db----------C
wenn die Zielendfelder direkt nebeneinander liegen wie hier gezeigt, ist tatsächlich ein Deadlock möglich.
(sollten sie weiter auseinander liegen, gibt es ein feld dazwischen wo a oder C pausieren kann und das andere Schiff vorbeilassen)
-----------AC--------- deadlock
alles andere wie
A--------dXb----------C
führt zu
----------AXC------
----------bAC-----
----------bCA----
----------CXA-----
(wobei X ein eventuel wartendes schiff ist verursachte keine deadlocks)
Der lässt sich aber mit einer einfachen Abfrage testen. Wenn das Schiff an seinen Endzielort nicht kommt (und nur dann), kann es testen ob ein Schiff darauf geblockt ist, was über das Feld fahren möchte auf dem es steht. dann gibt es nurnoch einen Dreiecksdeadlock.
Das war die Bewertung meines ersten Vorschlags. Ich werd das ganze Model nochmal überarbeiten um sicherzugehen das es wirklich keine Deadlocks geben kann.
Es gibt auch Passagierschiffe und manchmal müssen Schiffe 2 Kontinente Verbinden (dazu noch apoteken versorgen etc).
Und da Schiffe relativ langsam sind, braucht man tatsächlich für längere Strecken deutlich mehr Schiffe. Was dazu führt das pro Linie schonmal 2 oder 3 Schiffe notwendig waren, ich hab z.B. jetzt einen Hafen der von 11 Schiffen angesteuert wird wovon 3-6 an ihm warten. Und der hafen ist genau ein Feld breit, deswegen kam ich auf die Idee)
Der Grundgedanke hinter der ganzen Geschichte mit Deadlock ist, das nur 2 Schiffe stehen können 3 aber gleichzeitig auf ein Feld dürfen. Damit ist immer ein Slot fuer Wege frei. (ich hab anno dazumal ein 2D Echtzeittestspiel gebaut, was auf dem Prinzip aufbaut. Deadlocks sind bei entfernteren Zielorten nicht möglich)
Also 3 Slots pro Feld. Das Schiff reserviert seinen Weg bis zu einem Feld an dem es stehen kann.
Wenn das nicht geht, weil bei einem Zwischenfeld alle 3 Slots voll sind, wird sich dieses bald geleert haben, nachdem ja ein Slot nur eine Bewegung ist und das Schiff darauf nicht stehen kann. Das wartende Schiff selbst verursachte keine Regelbrüche weil es ja auf seinem Feld sowieso nen WarteSlot reserviert hat.
(das ist der Grund warum es keine Deadlocks geben kann, der Gedanke dahinter ist ähnlich wie meine Deadlockfreie Bauweise beim alten Signalsystem mit Vorsignalen, oder der Grund warum es beim jetzigen Zugsystem kein Deadlocks zwischen Haltestellen gibt und die Deadlocks die man durch falsche Haltstellenwahl aufbauen kann, wird es bei Schiffen nicht geben, weil sie an jedem Feld dazwischen ne Pause einlegen können, und ausserdem Metrisch fahren (sprich es gibt keine Richtungsschilder).)
Das Verzichten auf Richtungsschilder ist tatsächlich nötig um immer Deadlockfrei zu sein. Wer sie verwendet, macht sich allerdings normalerweise Gedanken darüber (bei schiffen sind sie selbst dann noch extrem unwahrscheinlich). Das ganze System verändert tatsächlich nur was an den Häfen.
Beweis:
Ein Deadlock entsteht wenn A->b will von C daran gehindert wird und C->d will und (ueber mehrere Schritte) von a daran gehindert wird. Oder Das A->b will und sich selbst im Weg steht
Fall 0
A steht sich selbst im Weg, ist nicht möglich. Weil a auf seinem Feld bereits nen Warteslot belegt und dort warten darf. Bzw garnicht erst losfährt.
Also:
Annahme >->b wird von C gehindert.
Fall 1 C steht da nur rum.
Fall 1a C Steht auf dem Weg und nicht dem Ziel
da Anzahl stehender Schiffe < als Anzahl fahrender Schiffe. gibt es fuer a die Möglichkeit über das Feld zu fahren. Falls A diese Möglichkeit nicht hat liegt es also nicht an C sondern an einem Schiff E was wiederum nicht rumsteht ->Fall 2. (ausser wir haben alte Karten geladen, aber da gilt die sonderregel das wenn mehr als 2 schiffe auf dem feld sich befinden sie als 2 Schiffe eingetragen werden).
Sollte E auch rumstehen gilt das gleiche wie hier und es muss an F liegen was nicht rumstehen darf (nach der maximal 2 Schiffe dürfen stehen Regel)
Fall 1b C Steht auf dem Ziel
Fall 1b' Entweder das feld ist mit C und einem Weiteren die dort warten besetzt, dann kann A da nicht hin, (aber A kann relativ nahe meist Nachbarfeld hinfahren) deswegen gibts ja die Regelung. (aber das ist nicht der deadlock fall, weil C ja garnicht vorhat weiterzufahren, das ist ein ganz normaler Ladestau wie ihn ne LKWkolone einer Linie an nem Frachthof hat, der genau wie dort den Verkehr dorthin oder zum Nachbarfeld einschränkt).
In der Erweiterung würde sich A einfach einen anderen Platz an dem Hafen suchen, und diesen Ansteuern. (Auch dabei wird kein Livelock entstehen können, das liegt an der metrikstruktur von Simutrans)
Fall 1b'' C steht dort wird aber von A daran gehindert wegzufahren.
Das geht nur unter den Umständen das A zum Deadlockeintritt genau auf dem Feld Stand, zu dem C hinwill. (Das ist tatsächlich der einzige Deadlock Fall mehr unten). Falls C nicht dahinwill wo A steht kann es nachdem auf jedem Weg ein Slot frei ist auf den nur drübergefahren werden darf aber nicht gehalten. zum nächsten Feld auf seiner Route fahren an dem es Halten darf ->kein Deadlock
Fall 2 C steht da nicht rum sondern fährt über das Feld (und ist in bewegung oder hat dieses Feld nur reserviert)
Fall 2a C ist in Bewegung Widerspruch zu Deadlock
Fall 2b C hat dieses Feld nur Reserviert.
Wenn C das getan hat, dann hat es eine durchgehende Strecke bis zu seinem Punkt an dem es Stehen bleiben kann reserviert -> es gibt keine Behinderungen die Bewegung von C kann beginnen -> kein Deadlock
Fall 1b''
man nehme einen Kanal - ist ein feld
A----------db----------C
wenn die Zielendfelder direkt nebeneinander liegen wie hier gezeigt, ist tatsächlich ein Deadlock möglich.
(sollten sie weiter auseinander liegen, gibt es ein feld dazwischen wo a oder C pausieren kann und das andere Schiff vorbeilassen)
-----------AC--------- deadlock
alles andere wie
A--------dXb----------C
führt zu
----------AXC------
----------bAC-----
----------bCA----
----------CXA-----
(wobei X ein eventuel wartendes schiff ist verursachte keine deadlocks)
Der lässt sich aber mit einer einfachen Abfrage testen. Wenn das Schiff an seinen Endzielort nicht kommt (und nur dann), kann es testen ob ein Schiff darauf geblockt ist, was über das Feld fahren möchte auf dem es steht. dann gibt es nurnoch einen Dreiecksdeadlock.
Das war die Bewertung meines ersten Vorschlags. Ich werd das ganze Model nochmal überarbeiten um sicherzugehen das es wirklich keine Deadlocks geben kann.