Wegesystem ala Siedler: Hin- und herschleppen verhindern

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"

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

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.

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.

volkard

fein. ich schrieb damals

machen wir es erstmal doof

, weil ich ein fetteres handelssystem im kopf hatte, aber weil ich das nicht ausarbeiten wollte hab ich dann den weiteren teil des postings nicht geschrieben.

kleine ideen:

die nachfrage zu senken, wenn ware ankommt.

und vielleicht einen centimeter (im game 0 cm) vor den verbraucher (baustelle) die entscprechende kreuzung zu setzen (damit der verbaucher bedarf 1.0 halten kann und die sichtbare kreuzung dennoch am markt spielt).

vielleuicht sollte ne baustelle nicht konstant 1.0 halten, sondern einen lokalen puffer von 5 holz haben und als bedarf während des baus 1.0-pufferfüllstand/5 melden und danach 0 melden. das würde die träger eher zu nicht-satten bauistellen schicken und zusammen mit der kreuzungsmittelung sogar zu eher (nichtsatten (obwohl kreuzungen eh keine waren lagern)) kreuzungen. wenn die baustelle dann fertig ist, werden die übrigen hölzer dann schon von allein zu anderen orten getragen.

Hallo,

also zusammenfassend lässt sich folgendes sagen.

Es ist vielleicht besser du spielst einfach nur Siedler I oder II und erfreust dich an einem schon fertigen Transportsystem.

bye Saxony

Saxony007 schrieb:

Hallo,

also zusammenfassend lässt sich folgendes sagen.

Es ist vielleicht besser du spielst einfach nur Siedler I oder II und erfreust dich an einem schon fertigen Transportsystem.

bye Saxony

Danke für die Aufmunterung, aber ich geb nicht auf!
Sagte ich bereits, dass ich ein Optimist bin?

@Ooptimist

Kannst du ein wenig mehr über das Projekt erzählen. Was es alles kann, wie es aussieht usw.

Bin sehr interessiert wie du das alles anstellst.

Gruss,
Prem

P.S. keine Angst, ich werde dein Projekt schon nicht kopieren, ich habe erst gerade angefangen C++ zu lernen :).

Hi Prem

Freut mich dass dich das interessiert. Schau dir mal die Threads hier an, dann kriegste mal ne Ahnung, wie ich angefangen hab. Echt super das Forum hier, hab ne Menge gelernt.
Dicke Props an .filmor, SideWinder, Optimizer, Saxony007, MisterX, Volkard und alle die ich vergas..

Am Anfang war es dunkel und ich wollte erstmal ein Menu für die Konsole.
Dann überlegte ich, was ich alles brauche: Hmm Gebäude wären ganz nett
Also fing ich mit dem Klassendesign der Gebäude an, und merkte bald, das es nicht so leicht ist, wie ich dachte. Aber dafür hab ich gelernt, was ne Factory ist, und hey echt praktisch. Nun hatte ich die Factory für Gebäude und Observers für deren Beziehung untereinander.
Die nächste Frage war: Wie mach ich den jetzt die Wege? Und auf den Wegen sollten ja Träger die Waren hin- und herschleppen - und die Sache fing an richtig kompliziert zu werden.
Drum war ich die letzten drei Tage dran mir die Boost Graphic Lib (BGL) zu Gemüte zu führen. Hatte nen Crashkurs in Graphentheorie und habe nun einen Graph (adjacency list) aus Fahnen und Wegen, und suche mit dem Dijkstra shortest path alle Wege von einem bestimmten Gebäude aus.

Weiter bin ich noch nicht gekommen. Denn das nächste Problem steht schon vor der Tür. Muss nun die Transportaufträge irgendwie geschickt verwalten; was? wohin? mit welcher Priorität?
Aber da überleg ich mir noch was, mit den Vorschlägen aus diesem Thread komm ich sicher weiter, da bin ich optimistisch.

.filmor

Ooptimist schrieb:

Weiter bin ich noch nicht gekommen. Denn das nächste Problem steht schon vor der Tür. Muss nun die Transportaufträge irgendwie geschickt verwalten; was? wohin? mit welcher Priorität?
Aber da überleg ich mir noch was, mit den Vorschlägen aus diesem Thread komm ich sicher weiter, da bin ich optimistisch.

Und wenn nicht, dann machst du nen neuen Thread auf. Wenn du so weiter machst haben wir bald eine komplette "Wie baue ich mir mein eigenes Siedlerspiel"-Anleitung ;).

Ist nicht in einem Programmierforum eine Gruppe die versucht Siedler 2.5
zu programmieren? Meine vor einigen Monaten irgendwo mal was gesehen zu
haben. Soll von der Spielidee her auf Siedler II basieren.

MfG f.-th.

Schau dir www.widelands.org an. Das ist ein Opensource-Projekt, das versucht Siedler 2 nachzumachen und auch schon recht weit damit ist.

Bluebyte arbeitet gerade auch an einem Remake von Siedler 2. Dieses mal allerdings mit 3D-Grafik.

Antworter schrieb:

Schau dir www.widelands.org an. Das ist ein Opensource-Projekt, das versucht Siedler 2 nachzumachen und auch schon recht weit damit ist.

Bluebyte arbeitet gerade auch an einem Remake von Siedler 2. Dieses mal allerdings mit 3D-Grafik.

Hehe niedlich, die haben ja auch die grottenschlecht erkennbaren Buttons nachgebildet
Aber ich will ja kein "Remake" oder Siedler 2 3/4 machen. Ist halt ein tolles Wirtschafts- und Transportsystem. Dachte das schaff ich auch, weil's einfach Punkt zu Punkt Verbindungen sind, und Rohstoff -> Produkt pro Gebäude auch einfacher zu erweitern sein sollte, als komplexe Fertigung aus einem Zentralen Rohstoffpool ala CnC. Aber falsch gedacht, einfach wirds nicht..

.filmor schrieb:

Ooptimist schrieb:

Weiter bin ich noch nicht gekommen. Denn das nächste Problem steht schon vor der Tür. Muss nun die Transportaufträge irgendwie geschickt verwalten; was? wohin? mit welcher Priorität?
Aber da überleg ich mir noch was, mit den Vorschlägen aus diesem Thread komm ich sicher weiter, da bin ich optimistisch.

Und wenn nicht, dann machst du nen neuen Thread auf. Wenn du so weiter machst haben wir bald eine komplette "Wie baue ich mir mein eigenes Siedlerspiel"-Anleitung ;).

Ich hoff, ich nerv hier niemanden

Ich bleib aber noch bei dem Thread, weils noch ums Wegesystem geht.
Nun suche ich noch nach geeigneten Datenstrukturen zum Speichern diverser Infos, hoff das unten ist irgendwie übersichtlich.
Fett die Klassen, kursiv die Member,
Jeweils in eckigen Klammern die Daten -> Array, Vector, Liste..
und das unterstrichene sind Abläufe, Algos...

[b]Flagge:[/b]
[i]Waren[/i]
[Wasser][Weizen][Wasser][Mehl][Weizen]           (fixe Anzahl, sortiert nach Priorität)

[u]Update bei Anlieferung oder Wegnahme von Waren[/u]

[b]Welt:(Global/Wirtschaftsraum)[/b]
[i]
Warentyp -- Flaggen[/i]
Wasser     [F01][F02][F05][F07]                  (variable Anzahl, unsortiert)
Weizen     [F02][F03][F04]
Mehl       [F02][F05][F06]
Brot       [..]

[u]Update bei Update von Flaggen[/u]

[b]Wegfinder:[/b]
[i]x ----- Zielflaggen+Pfad (erreichbare von x aus)[/i]
F01    [F02][F03][F04][F05][F06][F07]           (variable Anzahl, sortiert nach Distanz, Struktur enthält Pfad)
F02    [F01][F03][F04][F05][F06][F07] 
[b]Pfad:[/b]
[i]Flaggen[/i]
[F01][F03][F04][F06]                            (variable Anzahl, feste Abfolge )

[u]Update bei Änderung im Wegnetz[/u]

[u]Auf Waren-Anfrage:[/u]
Suche Flaggen mit Ware in „Welt“
[F01][F02][F05][F07]                            (temporär, variable Anzahl, unsortiert)
Finde daraus nächste erreichbare in „Wegfinder“
[F01]      (temporär)
Kopiere „Pfad“ von A nach B auf Ware X
[F01][F03][F04][F06]                            (variable Anzahl, Stack)

[b]Ware:[/b]
[i]Flaggen (Adressen)[/i]
[F01][F03][F04][F06]                            (variable Anzahl, Stack)
Priorität: Integer

[u]Träger an Flagge:[/u]
Durchsuche Flagge nach Waren mit Zielort „Andere Flagge“
[u]Ankommen bei anderer Flagge:[/u]
Entferne erste Adresse aus Stack

Suche also geeignete Container für:

Objekte
(fixe Anzahl, sortiert nach Priorität)    Array?

Pointer oder Referenzen
(variable Anzahl, unsortiert)             Vector?
(variable Anzahl, sortiert)               Sortierte Liste?
(variable Anzahl, feste Abfolge )         Sortierte Liste?
(temporär, variable Anzahl, unsortiert)   Vector?
(variable Anzahl, Stack)                  Liste oder Queue?

Ich könnte auch alles mit Pointern und Arrays machen, was aber echt viel Handarbeit wäre und doch eher Fehleranfällig und ineffizient.

ps: ein bisschen doof, das Tabstops nur mit code-tags funktionieren

.filmor

Ooptimist schrieb:

.filmor schrieb:

Und wenn nicht, dann machst du nen neuen Thread auf. Wenn du so weiter machst haben wir bald eine komplette "Wie baue ich mir mein eigenes Siedlerspiel"-Anleitung ;).

Ich hoff, ich nerv hier niemanden

Unsinn.

Ooptimist schrieb:

Ich bleib aber noch bei dem Thread, weils noch ums Wegesystem geht.
Nun suche ich noch nach geeigneten Datenstrukturen zum Speichern diverser Infos, hoff das unten ist irgendwie übersichtlich.

Es geht aber nicht mehr um das Verhindern des Hin- und Herschleppens. Also mach bitte einen neuen Thread.

Schonmal vorläufig (== nicht ganz so intensiv nachgedacht):

Objekte
(fixe Anzahl, sortiert nach Priorität)    Array?

Kommt drauf an, ob du lieber jedesmal, wenn sich die Priorität ändert umschmeißen willst oder mehr "alltäglichen" Aufwand haben willst. Das Interface bleibt aber immer dasselbe, nämlich das von priority_queue.

Pointer oder Referenzen
(variable Anzahl, unsortiert)             Vector

Aber eigentlich würde ich das an den Flaggen eher mit einer Map von (Ware -> Anzahl) machen, IMHO ist das Speichern von Zeigern hierfür unnötiger Overhead (und Referenzen ist bei Containern eh nicht).

(variable Anzahl, sortiert)               Sortierte Liste?
(variable Anzahl, feste Abfolge )         Sortierte Liste?
(temporär, variable Anzahl, unsortiert)   Vector?
(variable Anzahl, Stack)                  Liste oder Queue?

Da steig ich jetzt ehrlich gesagt nicht mehr richtig durch. Wie gesagt, mach einen neuen Thread auf und schreib ganz genau, wo das Problem liegt.

Ooptimist schrieb:

Ich könnte auch alles mit Pointern und Arrays machen, was aber echt viel Handarbeit wäre und doch eher Fehleranfällig und ineffizient.

Jep, richtig erkannt ;).

Ok danke erstmal.

Werd dann zuhause nochmal in Ruhe überlegen, und dann entsprechend neu posten.

Oder vl kann auch ein Mod vor meinem letzten Post splitten, wenn er das hier zufällig liest