Wegesystem ala Siedler: Hin- und herschleppen verhindern

[Lolz]

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

[Ooptimist]

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.

[Ooptimist]

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*

[Gast]

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

[Ooptimist]

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.

[Ooptimist]

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

[Saxony007]

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

[Saxony007]

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

[mot]

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

[Saxony007]

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

[Saxony007]

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

[MisterX]

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.

[Ooptimist]

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

[Ooptimist]

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

[Ooptimist]

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:

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

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

[I2]

Hi,
hab auch mal so einen Algo. programiert(zwar in java, aber egal)
Ich hab ein Lager zur Vorraussetzung gemacht und dann hat jeder Knoten
seine Entfehrnung zu den Lagern berechnet(in Knoten bzw. Fahnen).
Gebäude/Baustellen liegen immer an Knoten.Wenn diese etwas brauchen dann
übergeben sie dieses Bedürfniss an den Knoten weiter der wiederum an den nächsten Knoten,der am nahesten am nächsten Lager liegt.Das Lager bekommt dann die bedürfnisse und gibt seinem Knoten die Waren, damit ist dann ein Bedürfniss befriedigt und ein anderer Knoten kann die Ware abholen und damit sein Bedürfniss befriedigen...usw...(wenn das lager die ware nicht hat wird das andere lager benutzt..oder gewartet) bis es an der Baustelle ist. Das selbe gilt wenn ware Abgeholt werden soll.Außerdem kann dann ein Knoten der Holz möchte und von einem Holzfäller
der an dem Knoten will beliefert wird sein Bedürfnis bei den anderen Knoten löschen(muss ja).....somit muss nicht alles zum Lager und zurück....usw.

Wollt nur ein anderen gedanken anstoss bringen(nicht der effektiveste weg aber damit wird jedenfals ein schlechter ausgeschlossen ^^

sry wegen der Rechtschreibung jaja ich weiß
MFG I2

[Ooptimist]

I2 schrieb:

Hi,
hab auch mal so einen Algo. programiert(zwar in java, aber egal)
Ich hab ein Lager zur Vorraussetzung gemacht und dann hat jeder Knoten
seine Entfehrnung zu den Lagern berechnet(in Knoten bzw. Fahnen).
Gebäude/Baustellen liegen immer an Knoten.Wenn diese etwas brauchen dann
übergeben sie dieses Bedürfniss an den Knoten weiter der wiederum an den nächsten Knoten,der am nahesten am nächsten Lager liegt.Das Lager bekommt dann die bedürfnisse und gibt seinem Knoten die Waren, damit ist dann ein Bedürfniss befriedigt und ein anderer Knoten kann die Ware abholen und damit sein Bedürfniss befriedigen...usw...(wenn das lager die ware nicht hat wird das andere lager benutzt..oder gewartet) bis es an der Baustelle ist. Das selbe gilt wenn ware Abgeholt werden soll.Außerdem kann dann ein Knoten der Holz möchte und von einem Holzfäller
der an dem Knoten will beliefert wird sein Bedürfnis bei den anderen Knoten löschen(muss ja).....somit muss nicht alles zum Lager und zurück....usw.

Wollt nur ein anderen gedanken anstoss bringen(nicht der effektiveste weg aber damit wird jedenfals ein schlechter ausgeschlossen ^^

sry wegen der Rechtschreibung jaja ich weiß
MFG I2

Sry, das hab ich jetzt echt nicht kapiert, nicht nur wegen der Rechtschreibung

[volkard]

ich bin wiedermal anderer meinung.

kein träger sollte mehr sehen können, als seine unmittelbare umgebung. wo kämen wir sonst hin? zu "effizenten" wegfindungsalgorithmen?

jeder träger hat ne menge von zeugs auf dem buckel und wenn er am ende seines wegsankommt, ist er an einer kreuzung. jetzt muss er nur per fernglas auf alle benachbarten kreuzungen gucken, welche nachbarkreuzung für sein produkt am meisten virtuelle kohle für sein produkt zahlt. und da geht er hin.

machen wir es erstmal doof. wir setzen für einen holzproduzenten fest 0.0 und für einen holzverbraucher 1.0 als holzpreis preis an. außerdem berechnen wir gelegentlich für jede andere kreuzung als preis fest: den mittelwert aller nachbarkreuzungen.

so erreichen wir eine drift in richtung verbraucher. alles ist gut und so.

denke, das dürfte auch erstmal deine probleme lösen. und zwar vollständig.

[Ooptimist]

volkard schrieb:

kein träger sollte mehr sehen können, als seine unmittelbare umgebung. wo kämen wir sonst hin? zu "effizenten" wegfindungsalgorithmen?

Wär doch noch was?
Ein Träger kennt nur seine zwei Fahnen, und was er als nächstes transportieren muss.

volkard schrieb:

jeder träger hat ne menge von zeugs auf dem buckel und wenn er am ende seines wegsankommt, ist er an einer kreuzung. jetzt muss er nur per fernglas auf alle benachbarten kreuzungen gucken, welche nachbarkreuzung für sein produkt am meisten virtuelle kohle für sein produkt zahlt. und da geht er hin.

machen wir es erstmal doof. wir setzen für einen holzproduzenten fest 0.0 und für einen holzverbraucher 1.0 als holzpreis preis an. außerdem berechnen wir gelegentlich für jede andere kreuzung als preis fest: den mittelwert aller nachbarkreuzungen.

so erreichen wir eine drift in richtung verbraucher. alles ist gut und so.

Das wird nicht funktionieren, weil Wegsysteme nicht immer optimal angelegt werden, grade für Baustellen würde es fatal:

Sägerei 1     (0.5)      Baustelle 1
       o-------o---------o (1)
      (0)      |
               |
               |         Baustelle 2
(ev.Zulieferer)o---------o (1)
             (0.75)

In Klammern die "virtuellen Kohle" (im weiteren Nachfrage genannt). Baustelle 2 würde völlig leer ausgehn bis Baustelle 1 fertig ist.
Der Weg wurde aber so gelegt, weil am Knoten ev. ein Zulieferergebäude liegt. Man kann dem User ja nicht zumuten, für Baustellen nen direkten Weg zu bauen, um den nach Vervollständigung umzuändern auf beste Verbindung zu Zulieferern.