Seite 1 von 2 12 LetzteLetzte
Ergebnis 1 bis 15 von 23

Thema: Algorithmen und Metriken für die Erstellung fairer Karten

  1. #1
    Registrierter Benutzer Avatar von Ziankali
    Registriert seit
    15.03.13
    Beiträge
    4.969

    Algorithmen und Metriken für die Erstellung fairer Karten

    Im PB-Forum ist eine Diskussion darüber entstanden, wie man Algorithmen und Metriken bei der Kartenerstellung nutzen kann, um möglichst faire Ausgangsbedingungen zu schaffen. Es geht dabei nicht (vorrangig) um komplette Skripts, die selbständig eine Karte generieren, sondern erstmal um Teilaufgaben (später kann man daraus vielleicht ein Komplett-Skript basteln).

    Ich schlage vor, wir fangen mit den Grundlagen an. D.h. bevor wir über Algorithmen reden, die irgendwas automatisch generieren, brauchen wir Metriken, die die Qualität des Generierten bewerten (die Metriken können auf Algorithmen zurückgreifen, wenn es nicht anders geht).


    Ich habe eine Metrik implementiert, die prognostiziert, welche Ziv ein bestimmtes Feld unter ihre Kontrolle bringen wird. Die kam bereits bei der Erstellung der Karte für das PB 72 zum Einsatz. Da die Implementierung relativ unübersichtlich ist, möchte ich aber lieber von vorne anfangen. Deshalb hier nur die grobe Funktionsweise:

    - Genutzt wird eine Art Dijkstra-Algorithmus ohne Ziel.
    - Ausgehend von der Startposition wird berechnet, wie "teuer" es für eine Ziv ist, ein bestimmtes Feld unter Kontrolle zu bringen.
    - Die Kosten steigen mit der Entfernung und erhöhen sich zusätzlich, wenn der billigste Weg vom Startpunkt zum Feld über bestimmtes Gelände verläuft.
    - solche Extrakosten entstehen für den Wechsel zwischen Land und Wasser, für den Wechsel zwischen Küste und Ozean, für Dschungel und für Tundra. Hier muss man überlegen, ob man bestimmte Kosten nur einmal anrechnet. Bspw. erfordert die Bewegung über Ozean eine hohe Anfangsinvestition, danach ist es aber relativ egal, ob man über ein Ozean-Feld fährt oder über zehn.
    - Schließlich wird prognostiziert, dass die Ziv mit den niedrigsten Kosten für ein Feld dieses unter ihre Kontrolle bringen wird.

    Ich bin mir sicher, dass das ausbaufähig ist
    Zitat Zitat von TeeRohr Beitrag anzeigen
    Es will hier ja auch keiner ein Problem lösen. Schließlich gibts ja keins...jedenfalls nicht so richtig, aber dafür ein umso größeres...prinzipielles, was aber eigentlich nicht interessiert.

  2. #2
    Qualitätssicherung 2.0 Avatar von Der_Blob
    Registriert seit
    21.10.14
    Beiträge
    1.796
    Das geht nur vom Weg aus, was für gleiche Anzahl an Feldern je Ziv gut ist. Für Elefanten wandert man aber auch ein paar Felder.

    Wer bekommt Gipfel?
    "Die Sprache ist die Quelle aller Missverständnisse." - Antoine de Saint-Exupéry

    Storys:

  3. #3
    Registrierter Benutzer Avatar von Strat
    Registriert seit
    08.01.15
    Ort
    HGW
    Beiträge
    3.889
    Man müsste noch die Felder bewerten
    Zitat Zitat von Schlumpf Beitrag anzeigen
    Strat ist doch so ein verkorkster Linker
    Zitat Zitat von Isaac Newton; in einem Brief an Robert Hooke
    Wenn ich weiter geblickt habe, so deshalb, weil ich auf den Schultern von Riesen stehe.
    Storys

    Civ 4: Weg in den Olymp
    Civ 4 PBEM 474 Das Steigen und Fallen der Kurse

  4. #4
    Qualitätssicherung 2.0 Avatar von Der_Blob
    Registriert seit
    21.10.14
    Beiträge
    1.796
    Das ist eine andere Kiste. Hier geht es um Landfläche und nicht um Qualität. Das kann man späte machen.
    "Die Sprache ist die Quelle aller Missverständnisse." - Antoine de Saint-Exupéry

    Storys:

  5. #5
    Registrierter Benutzer Avatar von Strat
    Registriert seit
    08.01.15
    Ort
    HGW
    Beiträge
    3.889
    Aber die Karte muss doch im Bezug auf Lnadfläche und Qualität stimmen. Wie dein Beispiel vorhin. Wenn Kupfer näher am Gegenr liegt als bei mir würde ich es ja trotzdem versuchen, wenn der woanders hingeht.
    Zitat Zitat von Schlumpf Beitrag anzeigen
    Strat ist doch so ein verkorkster Linker
    Zitat Zitat von Isaac Newton; in einem Brief an Robert Hooke
    Wenn ich weiter geblickt habe, so deshalb, weil ich auf den Schultern von Riesen stehe.
    Storys

    Civ 4: Weg in den Olymp
    Civ 4 PBEM 474 Das Steigen und Fallen der Kurse

  6. #6
    Registrierter Benutzer Avatar von Ziankali
    Registriert seit
    15.03.13
    Beiträge
    4.969
    Ich denke auch, dass Ressourcen und Landqualität einen Einfluss darauf haben, in welche Richtung eine Ziv expandiert. Wir müssten sie also berücksichtigen, wenn wir vorhersagen wollen, welcher Spieler welches Land besiedelt.

    Zitat Zitat von TeeRohr Beitrag anzeigen
    Es will hier ja auch keiner ein Problem lösen. Schließlich gibts ja keins...jedenfalls nicht so richtig, aber dafür ein umso größeres...prinzipielles, was aber eigentlich nicht interessiert.

  7. #7
    Qualitätssicherung 2.0 Avatar von Der_Blob
    Registriert seit
    21.10.14
    Beiträge
    1.796
    Für Ressourcen kann man den Bewegungsaufwandwert auf dem Feld mit der Ressi und darum senken. Das sollte aber prozentual gemacht werden, da linear praktisch keinen Einfluss hat (Differenz zwischen 2 Zivs bleibt gleich).

    Den Bewegungsaufwandwert an sich würde ich daran berechnen, wie viele Runden ein Siedler brauch, das Feld zu überqueren. Grasland=0.5 Wald/Hügel=1.0
    "Die Sprache ist die Quelle aller Missverständnisse." - Antoine de Saint-Exupéry

    Storys:

  8. #8
    Beyond Mars Avatar von [VK]
    Registriert seit
    05.02.08
    Beiträge
    59.406
    Das Problem bei reiner Landmasse ist, dass das Land unterschiedliche Qualität hat. 5 Tundrafelder sind was anderes als 5 Schwemmlandfelder. Eine Beurteilung der Felder wäre daher auch nötig.

  9. #9
    Ignoriert Mauern Avatar von Argonir
    Registriert seit
    27.12.07
    Beiträge
    2.666
    Man muss auch beachten, ob eine Civ zwischen anderen liegt oder eine Randposition einnimmt. Es hängt ja nicht nur an den Bewegungspunkten des Siedlers, sondern in noch größeren Maßstab an den Produktionskosten und natürlich auch an den Entfernungskosten.

    Um ein Beispiel zu geben: In einer ovalen Landmasse sitzen die Civs A, B und C. A sitzt ganz im Westen, B genau in der Mitte und C im Osten, aber nicht am Rand, sondern ca. 1/6 der Breite der Landmasse nach Westen versetzt, also Mittig im letzten Drittel. Der Einfachheit halber, wird angenommen, dass die Landmasse komplett aus Grasland besteht. Nach dem Entfernungsalgorithmus müsste dann A 1/6 des Landes bekommen (Grenze Mittig zwischen A und B), C 1/3 des Landes und den Rest würde B bekommen.
    In der Realität würde aber C erstmal versuchen gegen B zu siedeln und erst dann sein sicheren Hinterland einnehmen. B dagegen müsste in zwei Richtungen gegensiedeln, so dass es für B schwer werden dürfte die Grenze zu A genau zwischen den HS zu halten, jedenfalls nicht, wenn nicht gleichzeitig die Grenze zu C im Osten vernachlässigt werden würde. Das Ergebnis würde (wenn alle gleichmäßig siedeln und gleichschnell Siedler produzieren) wahrscheinlich so aussehen: A hat 1/3 vom Land, vielleicht ein bisschen weniger, wenn B schnell von C im Osten zugesiedelt wird und Siedler nach Westen umlenkt. C wäre der große Gewinner, er kann zuerst gegen B siedeln und wenn alle anderen ausgesiedelt haben, in Ruhe sein Hinterland urbar machen. Er könnte sich sicherlich 1/12 des Landes von B schnappen, während B selbst der große Verlierer wäre.

    In einem normalen Spiel kommen dazu natürlich noch Ressourcen etc. mit denen man die Siedler ein bisschen lenken kann. Das wichtigste bei der Kartenerstellung ist meiner Meinung nach aber, dass entweder alle (auf eine Weltkarte unmöglich) oder keiner ein sicheres Hinterland haben darf, mit dessen Besiedelung er sich Zeit lassen kann. Das war auch eine der Bedingungen bei der Erstellung der 72er Karte.
    Bitte weitergehen, es gibt hier nichts mehr zu lesen!

    Immortals sterben nicht

  10. #10
    Registrierter Benutzer Avatar von Ziankali
    Registriert seit
    15.03.13
    Beiträge
    4.969
    Man könnte das Siedlungsverhalten eines Spielers simulieren . Lieber wäre mir aber eine Heuristik, die ohne das auskommt...

    Hier ist mal eine grobe Idee:

    - Bei einem Spieler mit vielen Nachbarn werden höhere Entfernungskosten berechnet bzw. die Kurve für die Entfernungskosten ist konvexer.

    - Wertvolle Ressourcen senken die Kosten eines Weges dorthin (die Feld-Kosten im Dijkstra-Algorithmus). Evtl. ist es sinnvoll, jedem Feld eine Einflusssphäre zu geben, oder andersrum: Für jedes Feld werden die Ressourcen aufaddiert, die eine Stadt auf dem Feld im FC hätte. Nennen wir das Feld x und die Summe der Ressourcen im Radius einer entsprechenden Stadt R(x). Dann sollten im Dijkstra-Algorithmus die Feld-Kosten von R(x) abhängen, z.B. umgekehrt proportional.
    Zitat Zitat von TeeRohr Beitrag anzeigen
    Es will hier ja auch keiner ein Problem lösen. Schließlich gibts ja keins...jedenfalls nicht so richtig, aber dafür ein umso größeres...prinzipielles, was aber eigentlich nicht interessiert.

  11. #11
    Civ4 BASE Coder Avatar von rucivfan
    Registriert seit
    10.07.11
    Ort
    Antarktika
    Beiträge
    19.015
    Zitat Zitat von Ziankali Beitrag anzeigen
    Man könnte das Siedlungsverhalten eines Spielers simulieren . Lieber wäre mir aber eine Heuristik, die ohne das auskommt...
    Könnte man mit der Simulation nicht gleich eine neue Siedler-KI coden? Eine Heuristik ist in der Tat besser, aber hier auch sehr komplex, wie man an der Diskussion hier schon sieht.
    Geändert von rucivfan (19. Juli 2015 um 19:43 Uhr)

  12. #12
    Registrierter Benutzer Avatar von Strat
    Registriert seit
    08.01.15
    Ort
    HGW
    Beiträge
    3.889
    Sollte man noch die Eigenschaften miteinbeziehen von Spielern ? Aber vielleicht sollte man es für den Anfang nicht zu kompliziert machen
    Zitat Zitat von Schlumpf Beitrag anzeigen
    Strat ist doch so ein verkorkster Linker
    Zitat Zitat von Isaac Newton; in einem Brief an Robert Hooke
    Wenn ich weiter geblickt habe, so deshalb, weil ich auf den Schultern von Riesen stehe.
    Storys

    Civ 4: Weg in den Olymp
    Civ 4 PBEM 474 Das Steigen und Fallen der Kurse

  13. #13
    Say My Name Avatar von Zulan
    Registriert seit
    13.03.08
    Beiträge
    8.901
    Eine gute Diskussion hier .

    Ich denke es braucht ein einfaches Modell was irgendwie "gut genug" ist. Man kann sicher viele interessante Feinheiten diskutieren aber spaetestens bei strat. Ressourcen wird es schlicht unmoeglich den nutzen sinnvoll zu modellieren.

    Ich bin uebrigens kein Fan davon die Karte an die Spieler/Civs anzupassen (z.B. Rom muss Eisen haben), weil damit die Karte versuchen wuerde die Civs zu balancen - und das ist imho nicht die Aufgabe der Karte. D.h. die Karte sollte nicht wissen welcher Startpunkt von welcher Civ bespielt wird.

  14. #14
    Ignoriert Mauern Avatar von Argonir
    Registriert seit
    27.12.07
    Beiträge
    2.666
    Sehe ich zumindest teilweise anders. Ich bin zwar auch der Meinung, dass Rom nicht umbedingt Eisen braucht, allerdings wäre es sowieso generell unfair einem Spieler kein Eisen zu geben. Das wird ja auch noch für andere wichtige Sachen (Kanonen etc.) gebraucht.

    Der Kartenbauer sollte aber auf jeden Fall Einfluss darauf nehmen, wenn eine Civ gegen eine andere chancenlos wäre. Der klassische Fall ist der Nachbar vom Indianer, der zumindest die Chance haben muss, sich gegen Dogs zu verteidigen, ohne das er sein Spiel komplett ruiniert. Das kann man mit einem größeren Abstand oder mit Kupfer in der Nähe der HS regeln.
    Auch wenn zwei HS dicht beieinder sind, muss man irgendwie die Starttechs einkalkulieren. Dem einen Spieler darf es nicht gelingen, mit einer Axt zum anderen zu gelangen, bevor dieser nicht selbst die Chance gehabt hat, eine Axt zu produzieren.
    Auch ist zu beachten, dass eine Fin/Org-Civ sich gegebenenfalls eine Blockstadt leisten kann, an der jeder andere Pleite gehen würde.

    Ich plädiere hier nicht dafür alle Vorteile aus den Starttechs und den Eigenschaften zu negieren, aber als Kartenbauer sollte man darauf achten, dass die spezifischen Vorteile keine ideale Symbiose mit der Position auf der Karte eingehen, die den Nachbarn chancenlos lässt.
    Bitte weitergehen, es gibt hier nichts mehr zu lesen!

    Immortals sterben nicht

  15. #15
    Qualitätssicherung 2.0 Avatar von Der_Blob
    Registriert seit
    21.10.14
    Beiträge
    1.796
    Um nochmal auf Ziankalis erste Metrik einzugehen. Diese bestimmt ja den Aufwand an Bewegung zu einem Feld zu gelangen. Erweitert man dies darum das nach der Ermittlung des Bewegungsaufwands Punkte für die Stärke der Felder abzieht (wie viele Runden würde man für ein Feld wandern). Kann ein Algorithmus entlang der niedrigsten Werte bestimmen in welche Richtung eine Zivilisation expandiert. Daran kann man dann ableiten, wo zwei Zivilisation aufeinander treffen und wie viel Platz einer Zivilisation zum Gründen vom Städten bleibt.

    @Argonir: Ich bin der gleichen Meinung wie Zulan, die Karte sollte balanciert sein ohne das Wissen, wo welche Zivilisation startet.
    "Die Sprache ist die Quelle aller Missverständnisse." - Antoine de Saint-Exupéry

    Storys:

Seite 1 von 2 12 LetzteLetzte

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •