Felder zweimal betreten zu müssen ist ein echter Killer. Man kann es ggf. lösen indem man den Plot als Datenstruktur verdoppelt, aber die Performance könnte doch arg darunter leiden.
Nee, du musst dem Schiff einfach erlauben, alle Felder zu betreten. Dann sollte es immer ein Anrainerfeld geben, das noch nicht im bisherigen Pfad drin ist.
A* nimmt übrigens nicht nur die bisherigen Bewegungskosten, sondern addiert eine Schätzung der verbleibenden Kosten. Dürfte in Civ4 einfach min(delta x, delta y) sein.
Das wäre eine Option, die bis auf Kartenränder funktioniert. In einem Postprocessing-Schritt könnte man dann noch die nicht-betretbaren Felder durch ihre Nachbarfelder austauschen, sofern möglich, und ansonsten abbrechen.
Fast, sie wählten max(delta x, delta y)A* nimmt übrigens nicht nur die bisherigen Bewegungskosten, sondern addiert eine Schätzung der verbleibenden Kosten. Dürfte in Civ4 einfach min(delta x, delta y) sein.
Code:int pathHeuristic(int iFromX, int iFromY, int iToX, int iToY) { return (stepDistance(iFromX, iFromY, iToX, iToY) * PATH_MOVEMENT_WEIGHT); } inline int stepDistance(int iX1, int iY1, int iX2, int iY2) // Exposed to Python { return std::max(xDistance(iX1, iX2), yDistance(iY1, iY2)); }
Habe aufgrund der Komplexität nun doch erst einmal ein Pythonskript geschrieben, um die Idee der modifizierte A*-Suche
genauer zu untersuchen.
Ich bin wegen dem Problem, dass in Civ4 die A*-Knoten genau den Feldern entsprechen, zur einseitigen Behandlung der Flussfelder zurückgekehrt. Anderenfalls erhält man ein Problem mit Flüssen an gegenüberliegenden Seiten eines Feldes.
Das müsste man ggf. zweimal betreten, aber Felder, die vom A*-Algo schon in die Closed-List aufgenommen wurden, sind, können nicht erneut betreten werden.
Aber man kann sich auf eine Seite bei einem Fluss einschränken. Sofern das Feld (Berg/fremde Kultur, etc.) nicht betretbar ist, muss man die Betretbarkeit von der anderen Seite des Flusses übertragen.
Leider gibt es noch ein Problem bei der Berechnung der Kosten. Hat man den Fall, dass ein Feld B von zwei Vorgängern betreten werden kann, so sind die Kosten der Wege A₁-B-C, A₂-B-C im allgemeinen nicht gleich.
In unteren Beispiel wäre das bei den Feldern mit den Kosten "C 4", "C 5" und "C 7" der Fall.
Aufgrund der (Standard—)Heuristik wurden die Kosten von C vor A₂ berechnet.
Die Heuristik auf f() = g(x) + 0 zu ändern, führt aber zum Greedy-Algo der dann doch signifikant langsamer ist
Edit: Stellt sich heraus, dass A₂ doch vor B/C abgehandelt wird. Es wird nur auf den leicht ungünstigeren Vorgängerknoten verwiesen.
Code:┌┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┐ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼ ┊ ┊ ┊ ┊ ┊ 🏠 🏠 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 7 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ C 8 ┊ ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈╁┈┈┈┈┈┈┼┈┈┈┈┈┈┼ ┊ ┊ ┊ ┊ ┊ C ┃ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 6 ┃ ┊ ┊ ┊ ┊ ┊ ┊ ┊ C 7 ┃ ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈╂┈┈┈┈┈┈┼┈┈┈┈┈┈┼ ┊ ┊ ┊ ┊ 🌊A₁🌊 ┊ B ┃ ┊ ┊ ┊ ┊ ┊ 3 ┊ 4 ┊ 5 ┃ ┊ ┊ ┊ ┊ ┊ C 3 ┊ C 4 ┊ C 5 ┃ ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈╆━━━━━━┽┈┈┈┈┈┈┾━━━━━━╉┈┈┈┈┈┈┼┈┈┈┈┈┈┼ ┊ ┊ ┃ ┊ ┊ A₂ ┃ ┊ ┊ ┊ ┊ 2 ┃ ┊ ┊ ┃ ┊ ┊ ┊ ┊ C 2 ┃ ┊ ┊ C 4 ┃ ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈╂┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈╂┈┈┈┈┈┈┼┈┈┈┈┈┈┼ ┊ ┊ ┃ ┊ ┊ ┃ ┊ ┊ ┊ ┊ 1 ┃ ┊ ┊ ┃ ┊ ┊ ┊ ┊ C 1 ┃ ┊ C 1 ┊ C 2 ┃ ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈╀┈┈┈┈┈┈┾━━━━━━┿━━━━━━╃┈┈┈┈┈┈┼┈┈┈┈┈┈┼ ┊ ┊ ┊ 🏠 🏠 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 0 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 🏠 🏠 ┊ ┊ ┊ ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼
Geändert von Ramkhamhaeng (08. Februar 2019 um 22:11 Uhr)
Jetzt sehen die Resultate schon ganz gut aus. Hoffe der Browser stellt die Ausgabe halbwegs passabel da. Die Unicodezeichen brechen die fix Zeichenbreite im Code-Tag
Jetzt muss ich noch eine schlaue Wahl bei den Plots treffen, die über eine Kante mit „Kosten 0“ verbunden sind, dann kann ich den Code hier mal auch mal posten. Ist vllt. für diejenigen, interessanter die noch nicht davon überzeugt sind, dass die Pfadsuche allgemein funktionieren kann.
Beispiele zur derzeitigen Pfad-Auswahl.
Code:┌┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┐ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼ ┊ ┊ ┊ ┊ ┊ C C ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ End ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ C6.9 ┊ ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈╁┈┈┈┈┈┈┼┈┈┈┈┈┈┼ ┊ ┊ ┊ ┊ ┊ ┃ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 5 ↑ ┊ ┊ ┊ ┊ ┊ ┊ ┊ C5.9 ┃ ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈╂┈┈┈┈┈┈┼┈┈┈┈┈┈┼ ┊ ┊ ┊ ┊ W W ┊ ┃ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 4 ↑ ┊ ┊ ┊ ┊ ┊ C3.0 ┊ C4.0 ┊ C4.9 ┃ ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈╆━━━━━━┽┈┈┈┈┈┈┾━━━━━━╉┈┈┈┈┈┈┼┈┈┈┈┈┈┼ ┊ ┊ ┃ ┊ ┊ ┃ ┊ ┊ ┊ ┊ ┃ ┊ ┊ 3 ↑ ┊ ┊ ┊ ┊ C2.0 ┃ ┊ ┊ C4.0 ┃ ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈╂┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈╂┈┈┈┈┈┈┼┈┈┈┈┈┈┼ ┊ ┊ ┃ ┊ ┊ ┃ ┊ ┊ ┊ ┊ ┃ ┊ 1 ┊ 2 ↑ ┊ ┊ ┊ ┊ C1.0 ┃ ┊ C1.0 ┊ C2.0 ┃ ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈╀┈┈┈┈┈┈┾━━→━━━┿━━→━━━╃┈┈┈┈┈┈┼┈┈┈┈┈┈┼ ┊ ┊ ┊ C C ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ Start┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ C C ┊ ┊ ┊ ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼Code:┌┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┐ ┊ ┃ ┃ M M ┊ ┊ ┊ ┃ C C ┊ C - Stadt ┊ ┃ ┃ ┊ ┊ ┊ ┃ ┊ W - Wasser ┊ ┃ C6.0 ┃ M M ┊ ┊ ┊ ┃ C C ┊ M - Berg ┼━━━━━━╃┈┈┈┈┈┈╀┈┈┈┈┈┈┼┈┈┈┈┈┈╁┈┈┈┈┈┈┼┈┈┈┈┈┈╄━━━━━━┽ ┊ ┊ W W ┊ W W ┊ ┃ ┊ W W ┊ ┊ ┊ ┊ ┊ ┊ ┃ ┊ ┊ ┊ ┊ ┊ C5.0 ┊ C5.0 ┊ ┃ ┊ W W ┊ ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈╁┈┈┈┈┈┈┼┈┈┈┈┈┈╀┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┼ ┊ M M ┊ ┃ ┊ W W ┊ ┊ W W ┊ C C ┊ ┊ ┊ ↑ End ┊ ┊ ┊ ┊ ┊ ┊ M M ┊ C5.0 ┃ C5.0 ┊ C6.0 ┊ ┊ W W ┊ C C ┊ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈╀┈┈┈┈┈┈╁┈┈┈┈┈┈╁┈┈┈┈┈┈╁┈┈┈┈┈┈╆━━━━━━╅ ┊ ┊ W W ┊ ┃ M M ┃ ┃ M M ┃ C C ┃ ┊ ┊ 4 ┊ ┃ ┃ ┃ ┃ ┃ ┊ ┊ C4.0 ┊ ┃ M M ┃ ┃ M M ┃ C C ┃ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈╁┈┈┈┈┈┈╄━━━━━━╇━━━━━━╋━━━━━━╋━━━━━━╃ ┊ W W ┊ ┃ ┊ ┊ ┃ ┃ ┊ ┊ ┊ 3 ↑ 2 ┊ ┊ ┃ ┃ ┊ ┊ C5.0 ┊ C3.0 ┃ C2.0 ┊ ┊ ┃ ┃ ┊ ┼┈┈┈┈┈┈╁┈┈┈┈┈┈╊━━←━━━╅┈┈┈┈┈┈┼┈┈┈┈┈┈╂┈┈┈┈┈┈╄━━━━━━┽ ┊ M M ┃ ┃ ┃ ┊ M M ┃ ┊ ┊ ┊ ┃ ┃ 1 ↑ Start┊ ┃ ┊ ┊ ┊ M M ┃ C2.0 ┃ C1.0 ┃ ┊ M M ┃ ┊ ┊ ┼━━━━━━╉┈┈┈┈┈┈╊━━━━━━╋━━━━━━┽┈┈┈┈┈┈╀┈┈┈┈┈┈┼┈┈┈┈┈┈╁ ┊ M M ┃ ┃ ┃ ┊ W W ┊ W W ┊ ┃ ┊ ┃ ┃ ┃ ┊ ┊ ┊ ┃ ┊ M M ┃ C2.0 ┃ C1.0 ┃ ┊ C1.0 ┊ C2.0 ┊ ┃ ┼┈┈┈┈┈┈╄━━━━━━╇━━━━━━╃┈┈┈┈┈┈┼┈┈┈┈┈┈┼┈┈┈┈┈┈┾━━━━━━╃
Geändert von Ramkhamhaeng (10. Februar 2019 um 16:51 Uhr) Grund: Unicode-Symbole ersetzt
So, mein Testprogramm für den Algorithmus liefert jetzt recht nachvollziehbare Pfade ab
Hänge es hier mal an. Startbar mit 'python3 main [seed-nr.]' Falls der Output falsch aussieht, bitte die Seed-Nr. posten.
Sobald ich sicher bin, dass der Algo passt, kann ich beginnen ihn in die DLL zu übertragen.
Edit: Das doppelte „Betreten“ eines Feldes ist im Algo jetzt enthalten. Hier ein Beispiel (6/8), bei dem erst die Südkante und dann die Nordkante benutzt wird.
Code:┌━━━━━━┽┈┈┈┈┈┈┾━━━━━━┿━━━━━━╃┈┈┈┈┈┈╀┈┈┈┈┈┈┾━━━━━━╃┐ ┊ M M ┊ ┊ ┊ ┃ ┃ ┊ ┃ ┊ ┊ ┊ ┊ ┃ ┃ ┊ ┃ ┊ M M ┊ ┊ ┊ ┃ ┃ ┊ C 5.0┃ ┼━━━━━━╈━━━━━━╈━━━━━━┽┈┈┈┈┈┈╀┈┈┈┈┈┈╀┈┈┈┈┈┈╆━━━━━━╃ ┊ M M ┃ ┃ M M ┊ ┊ ┊ M M ┃ ┊ ┊ ┃ ┃ ┊ 1 ┊ ┊ ┃ ┊ ┊ M M ┃ ┃ M M ┊ C 1.0┊ ┊ C 3.0┃ ┊ ┼━━━━━━╇━━━━━━╉┈┈┈┈┈┈╆━━←━━━┽┈┈┈┈┈┈┾━━━━━━╉┈┈┈┈┈┈┼ ┊ C C ┊ ┃ ┃ ┊ W W ┊ ┃ ┊ ┊ ┊ ┃ Start↓ ┊ 2 ┊ ┃ ┊ ┊ C C ┊ ┃ ┃ C 1.0┊ C 2.0┊ C 3.0┃ C 4.0┊ ┼━━━━━━┽┈┈┈┈┈┈╀┈┈┈┈┈┈╄━━━━━━┽┈┈┈┈┈┈╆━━━━━━╋━━━━━━╅ ┊ ┊ ┊ M M ┊ M M ┊ ┃ M M ┃ ┃ ┊ ┊ ┊ ┊ ┊ 3 ↑ ┃ ┃ ┊ ┊ ┊ M M ┊ C 8.0┊ C 3.0┃ C 4.0┃ C 5.0┃ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈┾━━━━━━╈━━━━━━┽┈┈┈┈┈┈╂┈┈┈┈┈┈╀┈┈┈┈┈┈╂ ┊ W W ┊ ┊ M M ┃ ┊ ┃ M M ┊ ┃ ┊ ┊ ┊ ┃ 5 ┊ 4 ↑ ┊ ┃ ┊ C 9.0┊ ┊ C 7.0┃ C 6.0┊ C 4.0┃ M M ┊ C 6.0┃ ┼┈┈┈┈┈┈┼┈┈┈┈┈┈┾━━→━━━╇━━→━━━┿━━→━━━╃┈┈┈┈┈┈╁┈┈┈┈┈┈╀ ┊ ┊ W W ┊ ┊ ┊ ┊ ┃ M M ┊ ┊ ┊ 7 ┊ 6/ 8 ┊ End S┊ ┊ ┃ ┊ ┊ C 9.0┊ C 8.0┊ C 9.0┊ C10.0┊ ┊ ┃ M M ┊ ┼━━━━━━┽┈┈┈┈┈┈┾━━←━━━┿━━←━━━╅┈┈┈┈┈┈╁┈┈┈┈┈┈╀┈┈┈┈┈┈╁ ┊ ┊ W W ┊ ┊ ┃ ┃ ┊ ┃ ┊ ┊ ┊ ┊ ┃ ┃ ┊ ┃ ┊ ┊ C 9.0┊ ┊ ┃ ┃ ┊ ┃ ┼━━━━━━┽┈┈┈┈┈┈┾━━━━━━┿━━━━━━╃┈┈┈┈┈┈╀┈┈┈┈┈┈┾━━━━━━╃
Geändert von Ramkhamhaeng (25. Februar 2019 um 01:20 Uhr) Grund: Zip wegen Bugfixes ausgetauscht
Ist das für die PAE-Kanäle/Flüsse?
Pucc's Lets Plays BASE 6.0: #1 #2 #3 #4 #5
Download von BASE 6.4 [D]: HIER (klick mich!) (Stand: 08.07.2022)
Ja, aber ich will es auch noch ins nächste PB mit den Kulturellen Festungen schummeln
Leider hab ich schon wieder fehlerhafte Wege gefunden. Sind also doch noch Fehler enthalten
Wäre ein gutes Projekt für für Test-Driven-Development.
Die Funktion "CvUtil.findInfoTypeNum" in Python ist ein schlechter Witz, da sie nur "gc.getInfoTypeForString" mit dem letzten Argument aufruft und die ersten beiden einfach ignoriert. Keine Ahnung, was das soll, aber meine Frage ist:
Stellen wir uns vor, man könnte mit der Funktion tatsächlich "gc.getInfoTypeForString" auf eine bestimmte Datei einschränken - würde das merkliche Vorteile bei der Ladezeit bringen? Also, gesetzt den Fall, dass man ein Vielfaches der im Basisspiel enthaltenen Einträge in seinen Spieldateien hat, wie bei Caveman to Cosmos, oder aber bei meinem eigenen Mod. Und: Wäre das überhaupt umsetzbar (abgesehen davon, dass man diese neue Funktion dann auch an genügend Stellen verankern müsste, damit sie merklich aufgerufen wird)?
That's why I am here: Mein Mod
Mehr Technologien, mehr Einheiten, mehr Zivilisationen, mehr Gebäude
Die aktuelle Story zum Mod:
Die Vereinigten Staaten von Amerika
Alte Stories zu alten Versionen:
Alte Storys
Meiner Erfahrung nach ist getInfoTypeForString ziemlich flott. Da intern auf eine HashMap zurückgegriffen wird ist die Anzahl der Einträge nicht wichtig.
Edit:
Ich hatte auch mal ein Skript geschrieben, welches alle Aufrufe von getInfoTypeForString für konstante Argumente durch ihr Resultat ersetzt. Dadurch wollte ich auch noch den Overhead (Pythonfunktion ruft DLL-Funktion auf) eliminieren. Hat auch kaum was geändert.
Okay, danke für deine Erfahrung. Ich dachte, es würde relativ lange dauern, wenn das Programm alle Einträge durchgehen muss (hatte ich irgendwann einmal so verstanden, weshalb ich dann angefangen habe, die Python-Aufrufe von getInfoTypeForString etwas zu reduzieren). Die Ladezeiten sind bei meinem Mod inzwischen relativ lange, also wenn ich den Mod lade, deswegen hatte ich das einmal überlegt.
That's why I am here: Mein Mod
Mehr Technologien, mehr Einheiten, mehr Zivilisationen, mehr Gebäude
Die aktuelle Story zum Mod:
Die Vereinigten Staaten von Amerika
Alte Stories zu alten Versionen:
Alte Storys
Hat eigentlich schon einmal jemand Diplomatieoptionen dazugemoddet? Hat jemand Erfahrung, wie viel Arbeit und Probleme das macht?
Ich dachte an so etwas wie: (Frei-)Handelsabkommen (nur möglich, wenn man schon offene Grenzen hat): Verdoppelt den Ertrag aus Handelswegen mit diesem Partner
Gebietskarte (wie Weltkarte, aber eben nur von dem Gebiet, das man selber kennt)
Spionagedaten (wie Gebietskarte, aber eben von einem anderen Spieler: All das Gebiet, das man kennt)
Kontakt herstellen (Stellt den Kontakt mit einer dritten Zivilisation her, die der eine Handelspartner kennt, der andere aber nicht)
eventuell noch "Grenzkonflikt beilegen bei (Stadt)": Entfernt im Fatcross dieser Stadt die Kultur des Handelspartners, so dass diese eindeutig dem anderen gehört
That's why I am here: Mein Mod
Mehr Technologien, mehr Einheiten, mehr Zivilisationen, mehr Gebäude
Die aktuelle Story zum Mod:
Die Vereinigten Staaten von Amerika
Alte Stories zu alten Versionen:
Alte Storys
Base hat verschiedene OG-Arten.
Dann vermute ich einmal, Rucivfan hat Erfahrung und könnte mir sagen, wie viel Aufwand das ist
Ehe ich mich damit befasse, wüsste ich doch ganz gerne, ob es schaffbar ist.
That's why I am here: Mein Mod
Mehr Technologien, mehr Einheiten, mehr Zivilisationen, mehr Gebäude
Die aktuelle Story zum Mod:
Die Vereinigten Staaten von Amerika
Alte Stories zu alten Versionen:
Alte Storys