Daten speichern - Array, Vector, List, Stack? Was passt?

[Ooptimist]

Hallo

Erstmal Sorry, wenn ich gleich mehrere Fragen hab, aber irgendwie gehören sie zusammen.
Ich bin immer noch am Weg- und Transportsystem ala Siedler II und habe nun das Problem, dass ich jede Menge Daten doppelt und dreifach speichere, und ausserdem alle immer den gleichen Stand haben müssen.
Ich versuch mal, das so gut es geht zu beschreiben (mit Zettel und Stift wärs einfacher)

Grundprinzip:
Haus braucht Ware
-> Transportsystem gibt alle Fahnen die die Ware haben
-> Pfadfinder Algo gibt die Distanz und Wegbeschreibung
-> Transportsystem sucht die Nächstgelegene
-> und sendet Wegbeschreibung an Ware
-> Träger schaut auf Ware und sieht die nächste Fahne des Transportwegs, ist es seine geht er los.

Also, was ich habe sind Fahnen, in denen will ich die anliegenden Waren speichern. Und zwar als „Values“, jeweils maximal 8 pro Fahne. Ich dachte ich nehm ein Array.
Frage 1: Ist es günstiger, wenn der Träger den Array nach dem mit der höchsten Priorität durchsucht, oder wenn die Fahne bei jedem Zu- oder Abgang von Waren den Array nach Priorität sortiert?

Das Wegnetz merkt sich, an welchen Fahnen Waren eines Typs liegen. Also quasi für jeden Warentyp eine Liste. Die muss ja laufend aktualisiert werden, also viele inserts und removes.
Frage 2: Welcher Container ist da geeignet?

Ich habe ausserdem einen Graph:
Boost::adjacency_list
Dates
Edges -> std::list, Vertices -> std::vector
Property Maps
vertex_name string, vertex_index int
distance int, predecessor vertex
Hier kann ich die Daten für Distanz und Nachfolger aus den internen Property Maps auslesen. Muss natürlich mit jeder Aenderung im Netz (neue Fahnen und Wege, oder alte abreissen) upgedatet werden, also immer noch genügend oft insert oder remove plus den Algorithmus laufen lassen.
Frage 3: Nun will ich alle Wege zu allen speichern, nur wie? Eine 2D Map mit den Fahnen als Keys und der Distanz + Wegbeschreibung als Value? Keine Ahnung wie das effizient gehen könnte.

Dann hab ich ein Haus X, das Ware anfordert. Das Transportsystem soll dann 'ne Anfragen senden können: „Zeig mir alle verbundenen Gebäude von Haus X“, woraus es die auswählt, die eine benötigte Ware haben, und „Beschreib' mir den Weg von Haus A zu Haus X“ Der Graph soll die Fahnen aufgrund des Namens in der Map finden.
Dann brauche ich ja dann wieder ein Container mit den Rückgabewerten. Für erste Abfrage nur temporär, für die zweite muss ich ja den Weg in dem Warenobjekt speichern. Jedenfalls müsst ich ne Menge strings hin und her kopieren.
Dh. ich hab dann den Weg in den Waren gespeichert, muss den aber auch gegebenenfalls erneuern.
Da wollt ich eine Art Stack, wo jeweils die erreichten Fahne oben weg kommt und die nächste ansteht.
Frage 4: Was käme hier am günstigsten?

Frage 5: Ist das nicht alles ziemlich redundant?

Bevor ich jetzt anfang drauflos zu coden, wollt ich euch mal fragen, ob das Design so sinnvoll ist.
Bin also für Tipps und Kritik wie immer sehr dankbar

[Ooptimist]

zu 3)
Hab mir folgendes Konstrukt überlegt:

map< vertex.name, pair< priority_queue< vertex.name, vector, greater< int(distance) > >, vector< vertex.name > > 
Map
    Zielfahne 
    Pair
        Priority Queue
            Startfahne
            Vector als Sequenz
            Distanz zur Startfahne von Zielfahne
        Vector
            Fahnen des Pfads

Irgendwie selbstmörderisch, das zu entschlüsseln

[.filmor]

Ooptimist schrieb:

Frage 1: Ist es günstiger, wenn der Träger den Array nach dem mit der höchsten Priorität durchsucht, oder wenn die Fahne bei jedem Zu- oder Abgang von Waren den Array nach Priorität sortiert?

Kommt immer auf das "Spielverhalten" an. Wenn die globale Priorität oft verändert wird, dann ist ersteres besser, ansonsten letzteres. Mach einfach mal für das Durchsuchen eine eigene Implementierung mit dem Interface von priority_queue, dann kannst du das ggf. noch austauschen, bzw. gegeneinander testen.

Ooptimist schrieb:

Das Wegnetz merkt sich, an welchen Fahnen Waren eines Typs liegen. Also quasi für jeden Warentyp eine Liste. Die muss ja laufend aktualisiert werden, also viele inserts und removes.
Frage 2: Welcher Container ist da geeignet?

std::stack. Aber auch hier, halt es einfach austauschbar (z.B. mit einem typedef). Wieso merkt sich das eigentlich das Wegnetz die Waren? Ist es nicht praktischer, wenn du "intelligente" Träger hast? (Oder war das das, was im letzten Thread ausdiskutiert wurde? Den hab ich nicht so ganz verfolgt...)

Ooptimist schrieb:

Frage 3: Nun will ich alle Wege zu allen speichern, nur wie? Eine 2D Map mit den Fahnen als Keys und der Distanz + Wegbeschreibung als Value? Keine Ahnung wie das effizient gehen könnte.

Wozu willst du die Wege noch zusätzlich speichern?! Sie sind doch alle im Graph enthalten.

Ooptimist schrieb:

Dann hab ich ein Haus X, das Ware anfordert. Das Transportsystem soll dann 'ne Anfragen senden können: „Zeig mir alle verbundenen Gebäude von Haus X“, woraus es die auswählt, die eine benötigte Ware haben, und „Beschreib' mir den Weg von Haus A zu Haus X“ Der Graph soll die Fahnen aufgrund des Namens in der Map finden.

Dein Graph hat keine Häuser, nur Fahnen und Wege.

Ooptimist schrieb:

Frage 5: Ist das nicht alles ziemlich redundant?

Jep, s.o.
Eigentlich sollten die Träger das Transportsystem quasi durch ihr Verhalten sein.

Fahne1 - Träger - Fahne2:
 - Gehe zu Fahne1
 - Rechne mit einem komplizierten ;) Algorithmus aus, welche Ware in Anbetracht
   der globalen Priorität und der sich daraus ergebenden Entfernung als nächstes
   weiter muss
 - Nimm das oberste mit zu Fahne2, wiederhole für Fahne2

Mit diesem Prinzip ist die Lösung einer "dynamischen" Prioritätswarteschlange wohl besser, denn die kann ohne Probleme den "Algorithmus" benutzen.

[Ooptimist]

Meiner Meinung nach müssten die Träger "dumm" sein, dh. sie kennen nur ihre beiden Fahnen.

-Gehe zu Fahne 1
-Suche nach Ware mit "Adresse" Fahne 2 und höchster Prirität
-Bringe sie zu Fahne 2 und wiederhole

Über ev Verzweigungen wissen sie nichts. (Darum geht Priority Queue's top() nicht, es sei denn, ich mache eine für jeden angeschlossenen Weg) Darum müssten die Pakete einen Stack mit "Adressen" haben, der die Abfolge der Fahnen enthält, und eine Priorität. Diese wird global für den Warentyp festgelegt, und mit einem Faktor für die Entfernung verrechnet, und sie erhält einen Zuschlag, wenn es das einzige Paket des Typs ist im ganzen Reich.

.filmor schrieb:

Ooptimist schrieb:

schrieb:
Frage 3: Nun will ich alle Wege zu allen speichern, nur wie? Eine 2D Map mit den Fahnen als Keys und der Distanz + Wegbeschreibung als Value? Keine Ahnung wie das effizient gehen könnte.

Wozu willst du die Wege noch zusätzlich speichern?! Sie sind doch alle im Graph enthalten.

Stimmt. Der Graph speichert Distanz und Vorläufer. Dann kann auf Anfrage der Weg zurückgegeben werden.

[Simon2]

Ooptimist schrieb:

zu 3)
...

map< vertex.name, pair< priority_queue< vertex.name, vector, greater< int(distance) > >, vector< vertex.name > >

...

Hi,

ohne die Fachlichkeit beurteilen zu können/wollen, solltest Du Dir überlegen, die Objekte außerhalb des Containers zu erzeugen/vernichten und nur Verweise (Referenzen/Pointer) in dem Container abzulegen. (wenn Du das sowieso geplant hast, brauchst Du nicht weiterzulesen).

Dann kannst Du auch mehrere spezialisierte Container verwenden, so dass im jeweiligen Container nur der Objektzusammenhang abgelegt ist (also "Weg-Haus" und "Ware-Haus" trennen). So musst Du nicht alle möglichen Zusammenhänge in einen Container modellieren (und bei jeder Anpassung komplett neu strukturieren - inkl. Migration von Altdatenbeständen) und kannst vieles optmieren:
- Abfragen (jeweils optimierten Containertyp verwenden; du kannst z.B. auch C-Arrays nehmen)
- insert/remove/sort (nicht alle "Objektzusammenhangscontainer" müssen immer angefasst werden; außerdem geht der insert/remove bei Pointern sehr viel schneller und kosten weniger Speicher)
- Datenmanipulationen betreffen immer die Objekte selbst, so dass man nicht mehr jeden Container "informieren" muss, sondern jeder sofort auf dem "upgedateten" Objekt arbeitet.

Natürlich hat man dabei auch die Nachteile, dass man extern noch eine Objektverwaltung schreiben muss, die beim Erzeugen von Objekten das Eintragen in und beim Löschen das Austragen aus dem jeweiligen Container übernehmen muss. Das ist nicht trivial, weswegen dieses Konzept NICHT für "kurzlebige" Objekte geeignet ist.

Ist nur so ein allgemeiner Vorschlag, von dem Du selbst überlegen musst, ob er bei Dir passt.

Gruß,

Simon2.

[.filmor]

Ooptimist schrieb:

Meiner Meinung nach müssten die Träger "dumm" sein, dh. sie kennen nur ihre beiden Fahnen.

Jau.

Ooptimist schrieb:

-Gehe zu Fahne 1
-Suche nach Ware mit "Adresse" Fahne 2 und höchster Prirität
-Bringe sie zu Fahne 2 und wiederhole

Über ev Verzweigungen wissen sie nichts. (Darum geht Priority Queue's top() nicht, es sei denn, ich mache eine für jeden angeschlossenen Weg) Darum müssten die Pakete einen Stack mit "Adressen" haben, der die Abfolge der Fahnen enthält, und eine Priorität. Diese wird global für den Warentyp festgelegt, und mit einem Faktor für die Entfernung verrechnet, und sie erhält einen Zuschlag, wenn es das einzige Paket des Typs ist im ganzen Reich.

Nuja, das machts aber viel komplizierter. Wie gesagt, du kannst einfach einen Container mit dem Interface von priority_queue implementieren, der nach Algorithmus das höchste Feld aussucht (wobei du dann pop und top vereinen solltest, sonst wirds extrem ineffizient).

[phlox81]

Ooptimist schrieb:

Hallo
Grundprinzip:
Haus braucht Ware
-> Transportsystem gibt alle Fahnen die die Ware haben
-> Pfadfinder Algo gibt die Distanz und Wegbeschreibung
-> Transportsystem sucht die Nächstgelegene
-> und sendet Wegbeschreibung an Ware
-> Träger schaut auf Ware und sieht die nächste Fahne des Transportwegs, ist es seine geht er los.

Wäre es so nicht besser:
Haus braucht Ware
-> Transportsystem gibt alle Fahnen die die Ware haben // dito
-> Pfadfinder Algo gibt die Distanz und Wegbeschreibung //hm, also gehört für mich zu 3. oder 3 gehört zu 2.
-> Transportsystem sucht die Nächstgelegene // wenn du vorher von jeder die Distanz berechnest,
brauchst du eigentlich nicht mehr suchen. Denn wenn Distanz > beste Distanz
dann kannst du die doch eigentlich schon bei der pfadfinder algo verwerfen, bzw. abbrechen und die nächste Fahne beackern. Musst nur die beste Fahne dir merken.
-> und sendet Wegbeschreibung an Ware // hm, seit wann weiss der Sack Reis wohin er muss? Und wann er umfällt? *g*
-> Träger schaut auf Ware und sieht die nächste Fahne des Transportwegs, ist es seine geht er los.

bei 5). Hm, was ist so ein Träger? Trägt der nur? Und ist dein Gebäude auch
eine Fahne? Und gibt es keine anderen Wegpunkte ausser Fahnen evtl?
Oder gehört ein Träger zu einer Fahne? Hm, irgendwie bin ich jetzt verwirrt *g*

[Ooptimist]

phlox81 schrieb:

Ooptimist schrieb:

Hallo
Grundprinzip:
Haus braucht Ware
-> Transportsystem gibt alle Fahnen die die Ware haben
-> Pfadfinder Algo gibt die Distanz und Wegbeschreibung
-> Transportsystem sucht die Nächstgelegene
-> und sendet Wegbeschreibung an Ware
-> Träger schaut auf Ware und sieht die nächste Fahne des Transportwegs, ist es seine geht er los.

Wäre es so nicht besser:
Haus braucht Ware
-> Transportsystem gibt alle Fahnen die die Ware haben // dito
-> Pfadfinder Algo gibt die Distanz und Wegbeschreibung //hm, also gehört für mich zu 3. oder 3 gehört zu 2.
-> Transportsystem sucht die Nächstgelegene // wenn du vorher von jeder die Distanz berechnest,
brauchst du eigentlich nicht mehr suchen. Denn wenn Distanz > beste Distanz
dann kannst du die doch eigentlich schon bei der pfadfinder algo verwerfen, bzw. abbrechen und die nächste Fahne beackern. Musst nur die beste Fahne dir merken.
-> und sendet Wegbeschreibung an Ware // hm, seit wann weiss der Sack Reis wohin er muss? Und wann er umfällt? *g*
-> Träger schaut auf Ware und sieht die nächste Fahne des Transportwegs, ist es seine geht er los.

bei 5). Hm, was ist so ein Träger? Trägt der nur? Und ist dein Gebäude auch
eine Fahne? Und gibt es keine anderen Wegpunkte ausser Fahnen evtl?
Oder gehört ein Träger zu einer Fahne? Hm, irgendwie bin ich jetzt verwirrt *g*

Hm ja ich weiss, klar ausdrücken ist nicht meine Stärke..

Ein Haus "hat" eine Fahne, von der sie die Waren direkt nimmt. Die Fahnen sind die Wegpunkte. Ein Träger pendelt auf dem Weg zwischen 2 Fahnen, und nur da. Sielder halt.. :p
Das Netz aus Fahnen (Knoten) und Wegen (Kanten) stellt einen ungerichteten Graph dar.
Der "Pfadfinder" Algo gibt einfach die Distanz zu _allen_ angeschlossenen Fahnen mit dem kürzesten Weg in Form einer Abfolge von Fahnen.
Das "Transportleitsystem", eine globale Kontroller Klasse, muss dann aber die nächstgelegene finden, die auch noch die gewünschte Ware hat, und dann die Ware durchs Netz leiten.

@Simon2: gefällt mir gut, die Idee mit pointern die verschiedenen Maps zu machen. Muss die Objekte sowieso irgendwie Verwalten.

.filmor schrieb:

Nuja, das machts aber viel komplizierter. Wie gesagt, du kannst einfach einen Container mit dem Interface von priority_queue implementieren, der nach Algorithmus das höchste Feld aussucht (wobei du dann pop und top vereinen solltest, sonst wirds extrem ineffizient).

Wie meinst Du das "Nach Algorithmus"? Wie müsste der aussehn?
Das Problem ist doch bei Abzweigungen, das nicht alle Waren, die an der Fahne 1 liegen auch zur Fahne 2 müssen, sondern manche auch nach Fahne 3, und die soll der Träger 1-2 liegen lassen.

Jetzt bin ich auch total verwirrt, und weis gar nicht mehr wo anfangen

[.filmor]

Mit nach Algorithmus meine ich z.B. sowas:

max (globale_priorität * (Entfernung zu nächstem Ziel))

, also dass die Ware als nächstes mitgenommen wird, für die der höchste Wert herauskommt. Du kannst dann noch die rausfiltern, für die die Entfernung an Fahne2 größer ist als an Fahne1 und schon funktioniert das ganze (wenn auch möglicherweise nicht so wahnsinnig schnell, da zwei mal pro Wahre der Weg berechnet werden muss, aber das ist sehr einfach zu optimieren).
Doch merke, zu frühe Optimierung ist die Wurzel allen Übels. Beispielsweise bringt dir eine Vorausberechnung des Pfades nichts, denn niemand hält den Spieler davon ab, zwischendurch ein paar Straßen abzureißen oder die Priorität am Ziel zu ändern.

[Ooptimist]

.filmor schrieb:

...
Doch merke, zu frühe Optimierung ist die Wurzel allen Übels. Beispielsweise bringt dir eine Vorausberechnung des Pfades nichts, denn niemand hält den Spieler davon ab, zwischendurch ein paar Straßen abzureißen oder die Priorität am Ziel zu ändern.

Es ist doch sicher effizienter, nur bei Änderungen im Wegnetz die Pfade im Graph neu zu berechnen, als an jeder Fahne? Die Wegfindung im Graph dürfte ja der bottleneck sein. Ev. sollte ich statt All-Pairs-Shortest-Path einen Single-Pair-Shortest-Path(A*?) haben?