Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Aufbaustrategie im Geiste der Anno-Serie

Werbeanzeige

TheLizard

Frischling

  • »TheLizard« ist der Autor dieses Themas

Beiträge: 12

  • Private Nachricht senden

21

12.04.2014, 11:19

Hallo Sancaldur,

danke erstmal für den ausführlichen Kommentar. Es beschreibt ziemlich exakt mein Problem. ;)


Zitat von »Sacaldur«


Im Grunde ist das übertragen auf deine Situation nicht übermäßig schwierig:
Beim Platzieren eines Gebäudes guckt dieses in seiner Umgebung nach allen Gebäuden, die in irgendeiner Weise relevant sein könnten (eine Eisenschmelze würde nach Lagerhäusern, Eisenminen, Köhlereien, Kohleminen, Werkzeugschmieden). Alle gefundenen Gebäude werden natürlich vermerkt.


Genau da liegt jedoch mein Problem. Wie genau kann ich dem Code quasi vermitteln, was er als "Umgebung" für das jeweilige Gebäude/Objekt versteht? Wenn du dazu vielleicht ein Tutorial oder gerne auch einen Beispiel-Code kennst, glaube ich, dass mir das echt weiter helfen würde.

Aber erstmal danke nochmal für die Beschreibung. Ich hoffe, dass es somit auch für die anderen Mitglieder besser verständlich ist, was ich suche.

Nimelrian

Alter Hase

Beiträge: 1 216

Beruf: Softwareentwickler (aktuell Web/Node); Freiberuflicher Google Proxy

  • Private Nachricht senden

22

12.04.2014, 11:22

Das hängt davon ab, wie dein Speicherprinzip aussieht.
Speicherst du alle Gebäude deiner Map in einer struktur (std::vector, etc), oder teilst du die Map in kleinere Bereiche auf und speicherst alle Gebäude pro Bereich (So wie Minecrafts Chunks)?
Ich bin kein UserSideGoogleProxy. Und nein, dieses Forum ist kein UserSideGoogleProxyAbstractFactorySingleton.

TheLizard

Frischling

  • »TheLizard« ist der Autor dieses Themas

Beiträge: 12

  • Private Nachricht senden

23

12.04.2014, 11:27

Zitat von »Nimelrian«

Das hängt davon ab, wie dein Speicherprinzip aussieht.
Speicherst du alle Gebäude deiner Map in einer struktur (std::vector, etc), oder teilst du die Map in kleinere Bereiche auf und speicherst alle Gebäude pro Bereich (So wie Minecrafts Chunks)?


Ich habe bisher mit Vektoren gearbeitet. Bei den angesprochenen Chunks seh ich zwei Probleme. 1) Hab ich davon keine Ahnung. :whistling: 2) Glaube ich nicht, dass sich dies bei einem Aufbauspiel, wo die Objekte mit einander kommunizieren sollen gut eignet. Bei Minecraft ist ja der Vorteil grade, dass die Blöcke/Objekte nur sehr begrenzt miteinander interagieren.

Aber ich lasse mich da gerne eines besseren belehren. Wenn die Community also denkt, dass es durch aus Sinn macht, die Welt in einzelne "Berechnungsabschnitte" aufzuteilen, bin ich gerne für Anregungen bei der Umsetzung offen. ;)

Sacaldur

Community-Fossil

Beiträge: 2 301

Wohnort: Berlin

Beruf: FIAE

  • Private Nachricht senden

24

12.04.2014, 11:30

Zitat von »Nimelrian«

Das hängt davon ab, wie dein Speicherprinzip aussieht.
Speicherst du alle Gebäude deiner Map in einer struktur (std::vector, etc), oder teilst du die Map in kleinere Bereiche auf und speicherst alle Gebäude pro Bereich (So wie Minecrafts Chunks)?

Das sollte im Grunde egal sein, da die Struktur eine Schnittstelle anbieten sollte, die X- und Y-Koordinaten entgegennimmt.

In Anno war es grundsätzlich so, dass das Einzugsgebiet annähernd ein Kreis (abgesehen vielleicht von der Getreidefarm) war. Ob du bei dir nun eine Funktionalität schreibst, die kreisförmig um das Gebäude die entsprechenden Felder/Koordinaten ermittelt, abhängig vom angegebenen Radius, oder ob du bereits vorher für die verschiedenen Radien die entsprechenden Einzugsgebiete bestimmst ist deine Sache.
Wenn du dann alle Felder hast, musst du nur noch prüfen, welche Gebäude sich darin befinden.


Nachtrag:
In Minecraft gibt es schon seit Ewigkeiten die Redstone-Leitungen, die keine Probleme mit Chunks haben. (Eben weil die Berechnungen grundsätzlich unabhängig von der Struktur sind, in der die Daten gehalten werden.)
Spieleentwickler in Berlin? (Thema in diesem Forum)
---

Zitat von »Jonathan_Klein«

Es ist ja keine Schande etwas falsch zu machen, als Programmierer tu ich das täglich, [...].

TheLizard

Frischling

  • »TheLizard« ist der Autor dieses Themas

Beiträge: 12

  • Private Nachricht senden

25

12.04.2014, 11:52

Zitat von »Sacaldur«


Nachtrag:
In Minecraft gibt es schon seit Ewigkeiten die Redstone-Leitungen, die keine Probleme mit Chunks haben. (Eben weil die Berechnungen grundsätzlich unabhängig von der Struktur sind, in der die Daten gehalten werden.)


Da muss ich dir zum Teil widersprechen. Du hast zwar recht, dass es beim Übergang zu benachbarten Chunks keine Probleme gibt, aber das gilt nicht für Chunks die auf Grund der Distanz zur Spielerposition nicht geladen sind. Hier brechen Redstone-Verbindungen ab. Auch bei sehr langen Bahnstrecken kann es zu Problemen dadurch kommen. In einem Aufbauspielen würden sich somit sehr große Problem ergeben. Wenn bspw. Waren von einer Seite der Karte zur anderen transportiert werden sollen, würde der Lieferweg nur soweit durchgeführt werden, wie entsprechende Chunks abhängig von der Bildschirmposition im Radius geladen worden. Deswegen glaube ich nicht, dass sich diese Methode hier eignet. Sonst hätte ein ensprechendes System bestimmt auch schon in einigen Aufbaugames platz gefunden. ;)

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »TheLizard« (12.04.2014, 11:58)

TheLizard

Frischling

  • »TheLizard« ist der Autor dieses Themas

Beiträge: 12

  • Private Nachricht senden

26

18.04.2014, 20:56

Auch wenn es den erfahrenen C++-Leuten hier schon etwas zu den Ohren raushängen mag, will ich nochmal auf die Verwaltung der Transportaufträge eingehen. Besser gesagt, in wie welcher Reihenfolge die einzelnen Partner angesprochen werden. Erstmal eine kleine Übersicht dazu, in welcher Form die eigentliche Sachabfolge behandelt wird/ werden soll:

  • 1) Produktion (in Gebäude A)
  • 2) neues Item im Lager <-- Auslösung des Events
  • 3) Anweisung: Gehe Liste der Reihenfolge nach durch. Frage jedes Objekt in der Liste, ob sie das Item abholen können.
  • 4) Stoppe beim ersten Objekt, das eine positive Anwort gibt (bejaht).
  • 5) Löse holen-"Befehl" beim Objekt (Gebäude B) aus.

Das entscheidende Problem entfalltet sich nun am Punkt 3! Besser gesagt bei der Sortierung, Verwaltung und dem Zugriff auf die Elemente der Liste. Die Elemente sind quasi die "Adressen" der verbundenen Objekte (Gebäude).
Lange Rede, garkein Sinn.
Ich hab mich mit verschiedenen Möglichkeiten bei der Erstellung einer solchen Liste herumgeschlagen und bin davon auch etwas erschlagen. Die Auswahl an Möglichkeiten hat bei mir zu einiger Konfusion geführt. Hier eine Reihe möglicher Opfer die ich mit meinen Programmierfähigkeiten zur möglichen Folterung auserkoren habe: Vektoren (vector), einfach verkettete Listen (forward_list), Mengen (multiset) und Felder (multimap). Was sind die Kritierien die aus meiner Sicht wichtig sind bzw. die von den Kanidaten erfüllt sein müssen.

  1. Schneller Zugriff auf die Elemente der Liste ( wobei ein freier Zugriff, also unsortierte Ansprache der Elemente nicht nötig ist [korrigert mich, wenn ich das falsch sehe]).
  2. Elemente müssen schnell und ressourcenschonend verschiebbar, einfügbar und löschbar sein.
  3. Die eigentliche Sortierung der Liste ist wohl das Hauptkriterium. Die Elemente der Liste sollen anhand der Entfernung des zugehörigen Objekts zum Listeninhaber sortiert werden. Also nahe Gebäude nehmen Positionen vor Gebäuden mit höherer Entfernung ein.
Mein bisheriger Favorit ist hier bis jetzt multimap! Die Idee, die mir durch den Kopf spuckt wäre, dass der Schlüssel, nach dem die Liste sortiert würde, die Entfernung zwischen den Objekten sein sollte. Das zweite Elemente, welches in der jeweiligen multimap-Position gespeichert würde, wäre dann die eigentliche ID des Objekts. Womit dann dieses angesprochen (holen-Befehl übermittelt) werden könnte. Möglicherweise lässt sich das aber auch mit den anderen Anwertern im Rahmen der ansprochenen Kriterien besser und für mich als Noob simpler realisieren. :rolleyes: :whistling:

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

27

18.04.2014, 22:32

mein Vorschlag für eine Zwischenstruktur: std::map<WARE, std::piority_queue<ZEIGER_ODER_SMARTPTR> >
Ansonsten geh doch anfangs einfach die Liste aller Gebäude der Welt durch. Wenn das zu langsam ist, kannst du immernoch eine Zwischenstruktur einbauen. Versuch am besten Anfangs garnicht "schlau" zu programmieren in Hinsicht auf Algorithmen, sondern straight forward. Du hast ne Ware und willst sie loswerden? Dann klapper halt alle Gebäude ab und frag sie, ob sie die Ware abnehmen. Oder auch:

C-/C++-Quelltext

 
1
2
3
4
5

building::update(...)
{
for each building in buildings_on_map:
    if building.wanna_nice_stuff(stuff, amount, this):   this.send_stuff()
}
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

TheLizard

Frischling

  • »TheLizard« ist der Autor dieses Themas

Beiträge: 12

  • Private Nachricht senden

28

20.04.2014, 08:32

Zitat von »Nox«

mein Vorschlag für eine Zwischenstruktur: std::map<WARE, std::piority_queue<ZEIGER_ODER_SMARTPTR> >
Ansonsten geh doch anfangs einfach die Liste aller Gebäude der Welt durch. Wenn das zu langsam ist, kannst du immernoch eine Zwischenstruktur einbauen. Versuch am besten Anfangs garnicht "schlau" zu programmieren in Hinsicht auf Algorithmen, sondern straight forward. Du hast ne Ware und willst sie loswerden? Dann klapper halt alle Gebäude ab und frag sie, ob sie die Ware abnehmen.


Danke erstmal für die Anregung. Der Ansatz mit der multimap scheint erstmal richtig zu sein, so wie ich das aus deinem Post herauslese (korrigiere mich, wenn ich das falsch verstehen).
Allerdings weiss ich nicht, ob so eine "provisorische" Lösung soviel bringt. Letztlich ist es (zumindest für mich) viel Arbeit, die auf längere Sicht sich kaum auszahlt. Daher denke ich, dass es besser ist gleich den etwas schwierigeren Weg zu gehen, der dafür aber auch direkt zum Ziel führt. ;)

Ich habe mir nochmal Gedanken gemacht, wie neue Objekte in eine entsprechende multimap des Objekts (bzw. der in Beziehung stehenden Objekte) aufgenommen und verarbeitet werden können.
Als Anmerkung vor weg. Es gibt eine zentrale Datenbank, in der unteranderem die ID des Objekts, sowie die Positionsangaben (Koordinaten) gespeichert sind.

Hier nun die mögliche Abfolge:

[ein neues Gebäude wird errichtet]

  1. Durchlaufe alle Felder im Radius (Realisierung mittels Bresenham-Algorithmus).
  2. Prüfe, ob das Feld von einem Objekt belegt ist.
  3. Wenn ja, dann hole dir aus der zentralen Datenbank durch Abgleich der Position die ID und anderen relevante Parameter des Objekts. Übergebe deinerseits dem anderen Objekt deine relevanten Parameterdaten (damit die Liste des jeweils anderen Objekts sich direkt auf den neuen Partner aktualisieren kann).
  4. Ermittle Distanz zwischen der eigenen Position und dem Objekt (Satz des Pythagoras).
  5. Verwende Distanz als Parameter für die Sortierung der Objekte in deiner Liste. Objekte mit niedrigerer Distanz erhalten Positionen vor Objekten mit höherer.

Wie immer die zentrale Frage: Macht das so Sinn? Wo gibt es noch Verbesserungs-/Optimierungsmöglichkeiten?

Sollte das so grundsätzlich in Ordnung gehen, dann würde mich vorallem interessieren, wie man den Brensenham-Algorithmus sinnvoll implementiert, so das eine einfache Iteration und Prüfung aller Felder im Einflussbereich machbar ist.

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

29

20.04.2014, 09:29

Es gibt einen deutlichen Unterschied zwischen std::multimap und std::map<...,std::priority_queue <...>> . Oder anders gesagt: ich halte ne Multimap an dieser Stelle für eher ungeeignet, da du ja durchaus eine Sortierung haben willst, die eine multimap nicht darstellen kann.

Zum Thema Feldprüfung eine kurze Überlegung: Wieviele Felder wirst du auf deiner Karte haben? Wieviele Gebäude wirst du auf deiner Karte haben? Ich vermute erstere werden eine deutlich höhere Anzahl haben und somit ist das Iterieren über die Felder auf keinen Fall sinnvoll meiner Meinung nach.
Analogie: Wie würdest du am ehsten die Telefonnummern aller Einwohner auf Helgoland rauszufinden?
Du kannst natürlich auf Helgoland jeden Quadratmeter besuchen, schauen ob ein Haus drauf steht und dann nachfragen wer da wohnt bzw was seine Telefonnummer ist. Wenn du aber wirklich so vorgehen würdest, hättest du meinen vollen Respekt-soviel Eifer habe ich schon lange nicht mehr angetroffen. Ich hingegen würde ja eher das Einwohnerverzeichnis bemühen...

Und an dieser Stelle nochmals. Straight forward ist kein "Provisorium". Es ist erstmal die einfachste Lösung. Du kannst natürlich immer gleich ne sechsspurige Autobahn bauen, aber ohne zu wissen, wo der Verkehr wirklich rollt, ist das eine reichlich unökonomische Lösung. Du wirst eh nicht die perfekte Lösung am Anfang haben und noch x-mal umbauen. Aber bei jedem Umbau (refactoring) werden die Ansätze und Klassen sauberer und besser. Doch woran gearbeitet werden muss, kann man nur sehr schwer vorher wissen. Viele Probleme kann man natürlich vermeiden (Stichwort saubere Kapselung), aber nicht alle. Ich kann es dir wirklich nur nahe legen. Du hast schon über ne Woche verloren nur weil du eine "bessere" Lösung haben willst. Dabei könnten deine Gebäude schon längst liefern...
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

TheLizard

Frischling

  • »TheLizard« ist der Autor dieses Themas

Beiträge: 12

  • Private Nachricht senden

30

20.04.2014, 11:30

Zitat von »Nox«

Es gibt einen deutlichen Unterschied zwischen std::multimap und std::map<...,std::priority_queue <...>> . Oder anders gesagt: ich halte ne Multimap an dieser Stelle für eher ungeeignet, da du ja durchaus eine Sortierung haben willst, die eine multimap nicht darstellen kann.

Zum Thema Feldprüfung eine kurze Überlegung: Wieviele Felder wirst du auf deiner Karte haben? Wieviele Gebäude wirst du auf deiner Karte haben? Ich vermute erstere werden eine deutlich höhere Anzahl haben und somit ist das Iterieren über die Felder auf keinen Fall sinnvoll meiner Meinung nach.
Analogie: Wie würdest du am ehsten die Telefonnummern aller Einwohner auf Helgoland rauszufinden?
Du kannst natürlich auf Helgoland jeden Quadratmeter besuchen, schauen ob ein Haus drauf steht und dann nachfragen wer da wohnt bzw was seine Telefonnummer ist. Wenn du aber wirklich so vorgehen würdest, hättest du meinen vollen Respekt-soviel Eifer habe ich schon lange nicht mehr angetroffen. Ich hingegen würde ja eher das Einwohnerverzeichnis bemühen...

Und an dieser Stelle nochmals. Straight forward ist kein "Provisorium". Es ist erstmal die einfachste Lösung. Du kannst natürlich immer gleich ne sechsspurige Autobahn bauen, aber ohne zu wissen, wo der Verkehr wirklich rollt, ist das eine reichlich unökonomische Lösung. Du wirst eh nicht die perfekte Lösung am Anfang haben und noch x-mal umbauen. Aber bei jedem Umbau (refactoring) werden die Ansätze und Klassen sauberer und besser. Doch woran gearbeitet werden muss, kann man nur sehr schwer vorher wissen. Viele Probleme kann man natürlich vermeiden (Stichwort saubere Kapselung), aber nicht alle. Ich kann es dir wirklich nur nahe legen. Du hast schon über ne Woche verloren nur weil du eine "bessere" Lösung haben willst. Dabei könnten deine Gebäude schon längst liefern...


Ok, also dann folgende Modifikation:

  1. Suche aus der Datenbank alle Objekte deren Position (Koordinaten) <= der "Randkoordinaten" des Einflussradius des Gebäudes sind. (Ist Bresenham-Algorithmus zur Festlegung der Radiuskooridnaten geeignet, oder gibs hier bessere Alternativen?)
  2. Hole dir alle relevanten Parameter der Objekte aus der Datenbank und übergebe umgekehrt den Objekten deine Werte.
  3. Ermittle Distanz zwischen der eigenen Position und dem Objekt (Satz des Pythagoras).
  4. Verwende Distanz als Parameter für die Sortierung der Objekte in deiner Liste. Objekte mit niedrigerer Distanz erhalten Positionen vor Objekten mit höherer.
Das sollte so besser deinem Ansatz entsprechen. (Hoffe ich zumindest!)

p.s. Ich kann dich beruhigen, hab damit keine Woche verschwendet. Höchstens eine Stunde heute Morgen. ^^ Bin im Moment im Trainee-Programm und hab unter der Woche im Moment sowieso kaum Zeit. ;)

Werbeanzeige

Ähnliche Themen