Wegesystem ala Siedler: Hin- und herschleppen verhindern

Hallo,

also mal folgender Vorschlag.

Jede Fahne (FLAG) besitzt einen Container (GOODS) für die dort abgelegten Waren.
Ein Element des Containers (GOOD) besitzt unter anderem Zielort und Art der Ware. Global gibt es für jede Warenart ein Prioritätensystem für den Transport.
Tritt nun an einer Fahne ein Event (Ware wird abelegt) ein, sortiert man nach der jeweiligen Priorität der Ware diese in den Container für Waren der Fahne ein. Soll an der Fahne etwas bestimmtes abgeholt werden, fällt das nicht unter die Priorität und wird einfach so abgeholt und an der entsprechenden Stelle aus dem Container entfernt. Alles anderen "Abgänge" einer Fahne (zum Beispiel einlagern in ein Warenhaus) erfolgen durch Entnahme des ersten (wegen Sortierung auch erstes Element des Containers) Elementes des Containers.

FLAG
 |
 |
  GOODS
    |
    [0] STONE, LOT_01
    [1] LUMBER, LUMBERMILL_03
usw.

Nachteil ändert sich global die Transportpriorität, müssen alle "Fahnen" neu sortiert werden.

Besser ist hier vielleicht:
Geht ein Arbeiter ohne speziellen Abholauftrag an eine Fahne schaut er ob im Container der Fahne zu erst eine Ware der höchsten Priorität liegt wenn ja dann nimmt er die und bringt diese zum einlagern mit, wenn nein dann schaut er nach Waren der zweiten Priorität usw.
Nachteil hier: der Arbeiter kann dann an einer Fahne recht lange "überlegen".

mfg Saxony

Hallo Saxony007

Dein Vorschlag tönt gut.
Ich glaub ich machs jetzt so, speichere neben dem Warentyp eine Zahl für die Reihenfolge des Eingangs und eine für die Priorität. Der Träger muss dann halt den Array durchsuchen, entweder nach benötigitem Gut oder nach Prioritärem oder zuletzt nach dem schon am längsten rumliegenden.
Hmm frag mich wie Bluebyte das gelöst haben, sicher auch nicht perfekt, denn bei Siedler2 kams ja des öftern zu Staus oder liegengebliebenen Sachen an den Fahnen.

Hallo,

ich nochmal.

Nachtrag:

Hat wie im obigen Beispiel Holz eine höhere Priorität als Stein, aber Baustellen eine höhere Priorität in der Belieferung als Sägewerke, dann sortiert man erst nach Transportpriorität und dann nach Ablieferungsort.
So das wie im Beispiel Stein an erster Stelle liegt und dann erst Holz fürs Sägewerk.
Ist das Holz an der Fahne aber das einzige im gesamten "Reich", dann wird es schon wieder knifflig. Hierzu muss der Arbeiter mit dem gezielten Auftrag des Holztransportes an der Fahne ankommen, um dieses ohne Beachtung der Transport priorität zu entnehmen.

das sind so meine ersten Gedanken für den Transport. Hab auch recht lange Siedler gezockt. Interessant wird eine Umsetzung der Warentransporte wie in Siedler III oder höher.
Ansosnten mal bei BlueByte fragen wann der Source zu Siedler I rauskommt. ID Software macht das auch immer nach spätestens 10 Jahren.

mfg Saxony

Hi

Danke nochmal

Werde wohl die Waren unsortiert an der Fahne liegen lassen, und den Trägern etwas mehr Intelligenz zutrauen (einbauen). Schwierig stell ich mir noch vor, eine Anfrage für ein Holz über mehrere Wegabschnitte durchzureichen, muss ich wohl ne Art Nachrichtensystem einbauen, dass durch die Wege düst und schaut wo das nächstliegende (in Wegabschnitten, nicht echte Strecke, wie im Siedler 1+2 ) Holz liegt. Der Träger hätte dann immer ein bestimmtes Warengut zu tragen. Das Lager sendet dann immer von jeder Ware eine Anfrage mit niedrigster Priorität. Wenn also nichts anderes ansteht kommt alles ins Lager.

In Siedler 4 funktionier der Transport ja zum Teil gar nicht gut. Da liegt das Zeug monatelang in einer Ecke rum, und es wird erst mal Holz durchs ganze Land geschleppt. Und das mit den Eselkarren, naja. Stellt man auf endlos, liefern die Träger das Zeug an den Marktplatz, die Karren bringen es zum andern, und wenn es da ist holt es ein Träger und bringts zum ersten Marktplatz zurück. Naja hauptsache sie sind beschäftigt

Erinnert mich irgendwie an die Wirklichkeit, da transportieren die Unternehmen die Waren auch oft in den LKWs spazieren, weil die Lagerplätze fehlen

Hätte jemand eine Idee für ein Benachrichtigungssystem für Warenanfragen?
Das Wegnetz könnte ja ziemlich komplex werden, und es müsste an alle Verzweigungnen weitergehn, bis eine Ware gefunden wird.

Habe ein Problem mal grob umschifft.
Soll einfach eine unbestimmte Ware aufgenommen werden, wird die erste genommen. Die anderen werden dann nachgeschoben, so dass die leeren Plätze immer zuhinterst sind. Auch wenn bestimmte Waren aus der Mitte raus genommen werden, schiebt es den Rest auf, so enstehen nie Lücken.
Das sieht im Moment so aus, nicht sehr schön, aber es tut mal was es soll.

GoodType Flag::take_stack()
	{
		for( int i = 0; i < STACK_MAX; ++i ) {
			if( stacks_[i] != NULLGOOD ) {    //Durchsuche stacks nach einer beliebigen Ware
				GoodType temp = stacks_[i];    //Speichere den Typ zwischen
				for( i; 
                     ( ( i <  STACK_MAX-1 ) && stacks_[i+1] != NULLGOOD );
					 ++i ) {
					stacks_[i] = stacks_[i+1];    //Schaufelt den Rest bis zur ersten Null eins vor
				}
				stacks_[i] = NULLGOOD; //Setzt das letzte Null
				std::cout << "Flag: Stack was taken " << temp <<std::endl;
				print_stacks();
				notify_observers( FREESPACE );
				return temp;
			}
		}
		return NULLGOOD;
	}
	void Flag::take_stack( GoodType good )
	{
		for( int i = 0; i < STACK_MAX; ++i ) {
			if( stacks_[i] == good ) {        //Durchsucht stacks nach einer bestimmten Ware
				for( i; 
                    ( ( i <  STACK_MAX-1 ) && stacks_[i+1] != NULLGOOD );
					 ++i ) {
					stacks_[i] = stacks_[i+1];    //Schaufelt den Rest bis zur ersten Null eins vor
				}
				stacks_[i] = NULLGOOD;    //Setzt das letzte Null
				std::cout << "Flag: Stack was taken " << good << std::endl;
				print_stacks();
				notify_observers( FREESPACE );
				return;
			}
		}
	}

Ist sicher noch Optimierbar.
Das mit den Prioritäten muss ich noch machen. Meine TODO Liste wird sowieso immer länger *puuh*

Hi Ooptimist, du machst das Spiel doch in der Konsole:D oder. Wirst du es dann auch zum Download anbieten, würde es nämlich mal gerne sehen wie sowas in der Konsole aussieht

Hi

Ja sicher, irgendwann in den nächsten Jahren werd ich mal fertig sein
Dann werd ichs sicher online stellen, und im Forum veröffentlichen. Schliesslich haben mir hier schon ne Menge Leute geholfen.

Hier mal ein Auszug des aktuellen Standes. Ist halt nur ein Testaufbau, (deshalb die vielen Ausgaben, will sehen was passiert):
eine Farm, eine Mühle und ein Lager, dazwischen je ein Weg.

farm                  mill                 storage
flag1-----------------flag2-----------------flag3

Round 16
Farm Stocks: 2 0
Farm: Working!
Farm: Putting Stack on Flag
Farm Stocks: 2 0
flag1: Stack was placed
flag1 Stacks: 2 0 0 0 0 0 0 0
flag1: Stack was taken 2
flag1 Stacks: 0 0 0 0 0 0 0 0
flag2: Stack was placed
flag2 Stacks: 2 0 0 0 0 0 0 0
Building: Taking Stack from Flag
flag2: Stack was taken 2
flag2 Stacks: 0 0 0 0 0 0 0 0

Mill Stocks: 3 0 Raw1: 2 1
Mill: Working!
Mill: Putting Stack on Flag
Mill Stocks: 3 0 Raw1: 2 0
flag2: Stack was placed
flag2 Stacks: 3 0 0 0 0 0 0 0
flag2: Stack was taken 3
flag2 Stacks: 0 0 0 0 0 0 0 0
flag3: Stack was placed
flag3 Stacks: 3 0 0 0 0 0 0 0
flag3: Stack was taken 3
flag3 Stacks: 0 0 0 0 0 0 0 0
Storage: New stack of 3
Storage: 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

Nächst höheres Ziel wäre ne graphische Umsetzung, aber das werd ich sicher nicht alleine schaffen.

Aktuelles Problem ist nach wie vor, dass die Waren hin- und hergeschippert werden, wenn das Lager voll wird.

flag2: Stack was placed
flag2 Stacks: 3 0 0 0 0 0 0 0
flag2: Stack was taken 3
flag2 Stacks: 0 0 0 0 0 0 0 0
flag3: Stack was placed
flag3 Stacks: 3 0 0 0 0 0 0 0
flag3: Stack was taken 3
flag3 Stacks: 0 0 0 0 0 0 0 0
flag2: Stack was placed
flag2 Stacks: 3 0 0 0 0 0 0 0
flag2: Stack was taken 3
flag2 Stacks: 0 0 0 0 0 0 0 0
flag3: Stack was placed
flag3 Stacks: 3 0 0 0 0 0 0 0
flag3: Stack was taken 3
flag3 Stacks: 0 0 0 0 0 0 0 0
flag2: Stack was placed
//...und so weiter bis zum stack-overflow

Hallo,

hier mal ein paar weiterführende Anregungen zum Warentransport.

Grundlage für folgende Beschreibung ist das Bild hier.

Also jede Fahne hat ja eine Liste mit Waren die dort liegen. Global wird zu jedem Warentyp eine Liste geführt an welcher Flagge das jeweilige Gut zu finden ist. Im Bild gibt es Holz an Fahne 10 und Fahne 5.
Hat nun Haus 1 einen Bedarf an Holz festgestellt, passiert folgendes.
Ausgehend von der Fahne des Hauses werden alle an die Fahne angeschlossenen Wege untersucht. Man kann hier zum Beispiel alle angeschlossenen Wege analog zu den Waren einer Fahne auch in einem Container Speichern oder auf 4 begrenzen (das wäre dann eine 2-dimensionale doppeltverkette Liste) - wie auch immer.

North
        |
West--Fahne_0--East
        |
      South

----------------------

    |         |         |
--Fahne_0---Fahne_1---Fahne_2--
    |     \
  Fahne_4---Fahne_5--
              |       \
            Fahne_6---Fahne7

Trifft man auf eine Gabelung wird auch die Suche gesplittet. Intern wird die Anzahl der Wegabschnitte (auch für jede gesplittete Sub-Suche) mitgezählt. Erreicht man eine Fahne schaut man ob dort Holz liegt - wenn ja wird die Suche abgebrochen.
Haben mehrere der gesplitteten Suche mit Holz als Ergebniss geendet nimmt man die Fahne mit der kleinsten Anzahl der mitgezählten Wegabschnitte.
Jetzt gibt es natürlich die Frage wie ich eine Fahne auf Holz untersuche.
Entweder ich schaue in der globalen Liste für Holz ob die aktuelle Fahne dort eingetragen ist oder ich durchsuche an der aktuellen Fahne den Warencontainer.
Bei letzterem entfällt dann die globale Warenliste.
Man kann aber auch wenn man die globale Warenliste beibehält, von allen darin enthaltenen Fahnen simultan (Threads) eine Suche nach dem Ziel durchführen. Die Suche mit den wenigsten Wegabschnitten gewinnt natürlich wieder.
Wichtig ist das Mitloggen der zurückgelegten Wegabschnitte während der Suche, damit man dann auch die Ware dort entlang transportiert. Nicht das man am Ende zwar weiß ich brauche das Holz von Fahne 5 für das Haus 1, hat aber den Weg dazwischen vergessen.

naja das wars erstmal
bye Saxony

Hallo,

wenn dein Lager voll ist werden ja die Waren trotzdem noch darumgeschleppt.

Wie kommt es eigentlich zu den Transportaufträgen wenn das Lager voll ist?
Also wer gibt dann die Aufträge raus? Das Lager kann es ja dann nicht mehr sein - weil voll.

bye Saxony

Der Thread hat gar nix mit C++ an sich zu tun und sollte verschoben werden.

Yep ist mittlerweile mehr in Algorithmen und Datenstrukturen abgerutscht.

Heimdall83

Hallo,

also denke bei Siedler 2 kamen die Waren-Staus, wenn auf einem Weg in beide Richtungen viel transportiert wurde. Da half dann oft nur Laden, oder evtl. weg abreissen.
Meine Idee dazu waere eine Art Dieb einzubauen (Im Grunde besser so programmieren, dass solche Fehler nicht auftreten)
1. Waren haben eine Art 'timeout ', bleiben sie an einer Fahne zu lange liegen, kommt der Dieb aus dem Nichts und klaut sie einfach.
2. Der Dieb kommt, wenn irgendwo ein Stau entdeckt wurde und klaut dort dann wahllos Waren.

Sowas koennte man, ab er auch bei einem gut funktionierendem System einbauen, FALLS doch mal ein Stau entsteht. Ausserdem ist der Dieb lustig

MfG, Heimdall83

Hallo,

am besten der Dieb klaut immer die Waren mit dem höchsten Wert zuerst.
Also erst Gold, dann Waffen, dann Eisenbarren usw.

bye Saxony

Ich würde emfehlen, du überlegst dir erstmal wie genau der Wegfindungsalgorithmuß EFFIZIENT gestaltet werden kann, bevor du Lösungen für Spezialfälle suchst. (Der Benutzer neigt dazu sehr gerne VIELE Wege anzulegen)

z.B Wie speichet man am besten die Knoten ab?
- Adjazenzliste oder Adjazenzmatrix?
(Adjazenzmatrix ist einfacher zu verwalten( denkt man zuerst, aber Knotenentfernung wird lustig ), Adjazenzliste wird DEUTLICH effizienter sein, da die Matrix bei Siedler wohl sehr spärlich besetzten ist)

- Welchen Algorithmuß verwendet man am besten?
Ich empfehle den Algorithmus von Dijkstra (Seite 143)
http://ls2-www.cs.uni-dortmund.de/lehre/sommer2005/dap2/skript.pdf

usw.

Einfach drauflosproggen bringt in diesem Fall nur noch mehr Probleme.

DANN kanste dich mit weiteren Detail Problemen befassen.

Dazu gehört dann z.B dass der Benutzer einfach nen Weg entfernen kann, der
zu einem Bereits berechneten Pfad für z.B. ein Goldbarren gehört. Das muß dann auch erkannt werden und ein neuer Weg berechnet werden. Dabei kann es natürlich auch wieder passieren, dass das Ziel nicht mehr erreicht werden kann.
usw.

Ich würde außerdem empfehlen nicht von "Wo kann ein Erzeuger eine Wahre hinschicken" auszugehen, sondern von "wo bekommt ein Verbraucher die Wahre her". So vermeidest du die Überflutung von Verbrauchern mit Wahren. Allerdings muß ein Verbraucher mitgeteilt bekommen, das eine breits auf dem Weg befindliche Wahre z.B aufgrund von Wegveränderungen gar nicht mehr ankommen wird.

Insgesamt ist das doch ein sehr komplexes Gebiet und ich gehe davon aus, dass die "Siedler macher" auch einige male geflucht haben bevor das funktionierte.

Erstmal besten Dank für die vielen Antworten.

Ich dachte mir schon das es komplexer wird, aber ich bin da optimistisch
Nehme mir all eure Tipps nun zu Herzen und stelle mein Design zum x-ten Mal auf den Kopf, so langsam machts spass
Das mit den Transportaufträgen ist eine gute Idee. Nur was gebraucht wird, wird geliefert.
Werd mich jetzt mal schlau machen, was ne Adjazenzliste ist, und wie die aussehen könnte.
Das Skript zum Algorithmus von Dijkstra versteh ich leider nicht wirklich auf Anhieb, zuviele Formeln. Muss wohl weiter oben anfangen zu lesen.

Danke nochmal, ich meld mich mit konkreten Fragen bestimmt bald wieder

Wie gut das es in der Boost Graph Library
schon den Dijkstra's Shortest Paths Algorithmus und die Adjacency List gibt.
Nach langem lesen und stöbern in Pseudo Codes wollt ich schon anfangen das selbst zu machen, aber das wär bestimmt subsuboptimal rausgekommen.
Hmm als Übung vielleicht?

Greez

Sry, ich bins schon wieder

Die Boost Docu hat ja einiges hergegeben. Ich hab grad ein 2h Shorty in Graphentheorie bekommen.

Konkretes zum Thema Siedler:

IIRC sind in Siedler1+2 die Verbindungen zwischen zwei Fahnen nicht gewichtet, es gilt nur die Anzahl Fahnen für die Distanz (da waren tolle Abkürzungen möglich..) ,

Boost Doku schrieb:

Use breadth-first search instead of Dijkstra's algorithm when all edge weights are equal to one.

dH wenn ichs richtig verstanden hab, wär der Breath-First-Algo schneller.
Eine Gewichtung nach Distanz und Gelände wär zwar irgendwie schöner, will ich auch so machen.

Was wäre denn effektiver:
-Ich habe eine Globale Liste mit den Fahnen, bei welcher die gesuchte Ware liegt, und erstelle jeweils einen Graph mit Startpunkt Verbraucher und eben dieser Liste.

-Ich ermittle auf Anfrage aus dem globalen Graph aller Fahnen und Wege alle kürzesten Wege zu allen vom Verbraucher aus erreichbaren Fahnen, und suche unter denen nach einem, der die benötigte Ware hat.

-Oder ich erstelle die schnellsten Wege von allen Fahnen zu allen, jedesmal wenn ich eine Fahne baue oder Abbreise, speichere die Distanzen, und wenn eine Verbraucheranfrage kommt, schaue ich nach, welcher der Anbieter am nächsten ist (Macht für mich am meisten Sinn)

Bitte an alle, die schon Erfahrungen in die Richtung gemacht haben, schubst mich mal in die richtige Richtung, wäre super.

Sagte ich bereits, dass es mir langsam wirklich Spass macht

_______________
@Bitte an Mods:
Verschiebt den Thread doch mal nach "Rund um die Programmierung"