Banner left   Banner center   Banner right

Germanenglish Home · News · Diary · Screenshots · Documentation (Wiki) · Downloads · Guestbook · Forum

Home · Benutzer registrieren · Suchen · Statistik · FAQ · Benutzerliste

Zur Zeit online: keiner ausser dir

 X-Force - Fight For Destiny - Forum —› Quellcode / Programmierung —› [Rewrite] Planung + Organisation

Seite: << [1] [2] [3] 4 [5] [6] [7] [8] [9] [10] >>

Autor Mitteilung
verfasst am: 09.02.2012, 15:15
Programmierer, allgemeines

Registrierdatum: 06.06.2004, 17:19

 Beiträge: 3186
Zitat: Kamor
Rundenbasierte Ki´s sind schnell vom Menschen ausgetrickst und die meisten rundenbasierten KI´s bekommen bei zunehmender Schwierigkeit meist mehr Resourcen. Also Masse statt Klasse.

Das liegt aber nicht immer an den beschränkten Möglichkeiten einer KI, sondern daran, dass ein Spiel Spass machen soll. Daher werden KIs bewusst beschnitten.
verfasst am: 09.02.2012, 19:33
Spielsatz Alliances

Registrierdatum: 14.07.2004, 14:47

 Beiträge: 1185
Zitat: Kamor
Auf jedenfall ne Möglichkeit für die Scripter, wenn nicht sogar nochmal eine eigene KI-Sprache drübergelegt.

Zu viele Köche verderben den Brei. Domain-Specific Languages sind cool, aber ich wüsste nichts, was man da anbieten könnte, was nicht eine beliebige gute Skriptsprache schon erlaubt. Und der Aufwand, zwei Skriptsprachen zu unterstützen (und im schlimmsten Fall noch eine zu entwickeln), ist wahrscheinlich nicht zu rechtfertigen.
Was allerdings durchaus drin ist, ist eine Art Bibliothek für Dinge, die viele KIs brauchen. Pfadfindung wäre eine Idee, wenn man das etwas weiter verallgemeinert und volles A* anbietet, könnte das auch für andere KI-Entscheidungen/-Planungen nützlich sein. Das sauge ich mir übrigens nicht aus den Fingern, dazu gibt's eine sehr coole Präsentation der F.E.A.R-Entwickler: Three States and a Plan: The A.I. of F.E.A.R.

Dann muss die Ki noch an Informationen kommen, je mehr desto besser,

Daher: So viele Events wie möglich anbieten, und möglichst viele Informationen angeben. Wenn mich nicht alles täuscht, sind aktuelle Events auf ein "TObject sender" beschränkt, daher können BE-Skripte AFAIK nicht herausfinden, wer beispielsweise einen Schuß abgefeuert hat, der grade ein Alien getroffen hat.

ausserdem sollte die KI ihre Einheiten über die gleichen finalen Routinen steuern, wie der Mensch,

Mir ist nicht ganz klar, was du damit meinst. Ich denke schon, dass man jede Menge Code zwischen Spieler- und KI-Einheiten teilen kann. Je abstrakter die BE-Engine an sowas rangeht, desto einfacher sollte es (in der Theorie) sein, Dinge wie neutrale Fraktionen, Seitenwechsel, mehr als zwei konkurrierende Teams, etc. zu unterstützen.
Aber ich kann nichts konkretes sagen, bevor sich nicht jemand eingehend mit dem Thema beschäftigt und ein bisschen Design-Arbeit leistet.

und ne gute Portion vom Speicher sollte man ihr auch geben.

Speicher ist kein Problem, ich wüsste nichtmal wie ich einem Skript auf einen gewissen Speicherverbrauch beschränken sollte.

Will man längerdenkende Ki-Strukturen entwickeln, sollte die KI auch noch Dateizugriff haben.

Gewisser Dateizugriff (oder die Möglichkeit, Daten zum Spielstand hinzuzufügen) ist auf jeden Fall drin, da bin ich auch für.

Zitat: Natter
Das liegt aber nicht immer an den beschränkten Möglichkeiten einer KI, sondern daran, dass ein Spiel Spass machen soll. Daher werden KIs bewusst beschnitten.

Naja, das ist nur eine Seite der Medallie. Eine (annährend) perfekt spielende KI ist wohl kaum von einer cheatenden zu unterscheiden und entsprechend nervig, und ständig verlieren macht auch keinen Spaß.
Aber wenn es zusätzlich noch eine überdurchschnittlich clevere KI gibt, freuen sich sicher einige ebenfalls clevere Spieler. Mal ganz davon zu schweigen, dass es interessant zu programmieren sein könnte ;)
Und letztlich ist es die Entscheidung des Spielsatzerstellers bzw Skripters, wie gut die KI wird.
verfasst am: 09.02.2012, 19:48
Registrierdatum: 20.07.2005, 00:01

 Beiträge: 203
Zitat: Natter
Das liegt aber nicht immer an den beschränkten Möglichkeiten einer KI, sondern daran, dass ein Spiel Spass machen soll. Daher werden KIs bewusst beschnitten.


Sehe ich nicht so. Es endet in allen Spielen immer ähnlich. Der Mensch lernt die Eigenheiten der KI und reitet dann auf jegliche KI-Fehler rum, die er finden kann. Die KI cheatet dafür an allen Ecken. Ich kenne keine komplexeren Spiele, wo ich die KI rein vom Algoryhmus her als Gegner betrachten würde, ausgenommen vielleicht Schach.

Zum Gegner wird die Ki eigentlich nur, dadurch das sie cheatet, z.B. kein Fog of War für sie gilt, sie also alles sieht oder sie bekommt meist nicht wenig zusätzliche Resourcen und in Echtzeit hat sie halt den massiven Geschwindigkeitsvorteil, weil sie das bessere(schnellere) Interface hat(sie ist direkt ins Spiel eingebunden, während der Mensch mit Bildschirmscrolling und Maus hantieren muss).

Ausserdem sehe ich den Spass nicht, wenn ich einen Gegner immer mit den gleichen Tricks wieder und wieder besiegen kann/muss.

Glaube kaum das jemand absichtlich ne KI klein gestaltet, damit das Spiel mehr Spass macht. Der Grund ist eher die Komplexität und der zeitliche Aufwand bessere Ki`s zu realisieren.

Für X-Force hiesse das z.B.

Aliens agieren global auf dem geoscape intelligent, im Bodeneinsatz agiert die Alientruppe als Team und das einzelne Alien hat auch noch eine persönliche KI. Das ganze kann noch getoppt werden, wenn über allen noch der Computer als eigene Intelligenz steht, der gerade mit dir spielt und dich an deinen Namen erkennt und Rückschlüsse aus Vorspielen daraus ziehen kann.

Nehmen wir als Kontrast eine schon wirklich gute KI, wie z.B. Age of Wonders, die dennoch nur genau eine Runde denken kann und schon in der nächsten Runde wieder alles vergessen hat, was vorher so als Ziele gesetzt wurde.

Also ich glaube die komplexere Ki würde wohl mehr Spass machen. Ist aber ziemlich Hardcore, das auch nur im Ansatz zu programmieren, was ich hier gerade beschrieben habe.
verfasst am: 10.02.2012, 09:53
Admin, Spielsatz GalWar

Registrierdatum: 31.08.2005, 21:51

 Beiträge: 5595
Das "Problem" bei den KI's in aktuellen Spielen besteht hauptsächlich darin, dass die Spiele zum einen für den Massenmarkt produziert werden (d.h. sich an den Durchschnittsspieler richten, und für viele ist selbst Schach schon zuviel Gedankenarbeit) und zum anderen kostengünstig sein müssen (die Entwicklung einer echten KI ist wesentlich aufwendiger als eine einfache KI mit Cheats).

X-Force (und wohl auch ein rewrite davon) sind zwar nicht für den Massenmarkt, aber dafür haben wir noch größere Kapazitätsprobleme an Programmierern.
Eine vernünftige KI ist erst dann realistisch, wenn jemand mal eben ein halbes Dutzend zusätzlicher Programmierer aus dem Hut zaubert :-(

Zitat: sujin
ausserdem sollte die KI ihre Einheiten über die gleichen finalen Routinen steuern, wie der Mensch,

Mir ist nicht ganz klar, was du damit meinst.


Er meint die Schnittstellenfrage, und ich bin da auch seiner Meinung.
Es sollte eine Engine geben, die die Figuren steuert und Informationen an die "steuernde Einheit" herausgibt.

Die KI sollte dann genau diejenigen Befehle aufrufen können, die der Mensch mit der Maus anklickt - sie sollte keine "Extrawürste" in Form eines direkten Engine-Zugriffes bekommen.

So etwas ist zwar etwas aufwendiger zu programmieren (beispielsweise würde dann in den Datenabfragen ein Switch sein, ob das Ergebnis aus der Engine für den Spieler auf dem Bildschirm dargestellt wird oder für ein Skript als Datenpaket übergeben wird), aber dafür kann man spätere Änderungen und Erweiterungen der Engine besser programmieren ohne die KI-Skripte durcheinander zu bringen.

Zitat: sujin
Dinge wie neutrale Fraktionen, Seitenwechsel, mehr als zwei konkurrierende Teams, etc. zu unterstützen.
Aber ich kann nichts konkretes sagen, bevor sich nicht jemand eingehend mit dem Thema beschäftigt und ein bisschen Design-Arbeit leistet.

Es gibt dazu intern schon einige Überlegungen und Arbeiten, die aber wegen anderen Problemen in der X-Force-Engine (speziell Forschungsliste) zurückgestellt wurden. Ich habe momentan keine Zeit, die Sachen herauszusuchen - aber wenn Du konkrete Fragen stellst, dann kann ich die hoffentlich aus dem Kopf beantworten.
verfasst am: 10.02.2012, 12:19 · Edited by: Natter
Programmierer, allgemeines

Registrierdatum: 06.06.2004, 17:19

 Beiträge: 3186
Zitat: Kamor

Sehe ich nicht so. Es endet in allen Spielen immer ähnlich. Der Mensch lernt die Eigenheiten der KI und reitet dann auf jegliche KI-Fehler rum, die er finden kann. Die KI cheatet dafür an allen Ecken. Ich kenne keine komplexeren Spiele, wo ich die KI rein vom Algoryhmus her als Gegner betrachten würde, ausgenommen vielleicht Schach.

Zitat: Kamor

Glaube kaum das jemand absichtlich ne KI klein gestaltet, damit das Spiel mehr Spass macht. Der Grund ist eher die Komplexität und der zeitliche Aufwand bessere Ki`s zu realisieren.

Erstmal bezog sich meine Aussage auf rundenbasierte Spiele. Ähnliches gilt aber wohl auch für viele Echtzeitspiele. Problem ist doch, dass in den meisten Spielen der Spieler die schwächere Ausgangsposition besitzt (in X-Force z.B. sind die Feinde in vielen Spielsätzen besser ausgerüstet). Daher muss die AI zumindest teilweise bewusst dumm agieren. Hinzu kommt, dass der Spieler in vielen Spielen einfach nochmal laden kann - ein ziemlich unfairer Vorteil.
Nur so als Beispiel - schon zu BG2-Zeiten wurden die Skripte der Gegner-KIs bewusst entschärft, weil die Kämpfe sonst zu schwer gewesen wären (die ursprünglichen Skripte wurden später für anspruchsvolle Spieler veröffentlicht; trotzdem gab es Gegner die auch nach mehreren Spieldurchläufen das Potential hatten, die ganze Gruppe des Spielers auszulöschen). In Shootern wäre es kaum ein Problem, die KI immer treffen zu lassen (bzw. immer richtig zielen zu lassen). Das passiert aber nicht - denn wie sollte der Spieler sonst gegen eine Übermacht bestehen können? Ansonsten hilft gegen den Lerneffekt (Schwachstelle in der KI finden) meist ein einfaches Mittel - Zufallselemente. Das ist so sogar in X-Force möglich. Gepaart mit abwechslungsreichen Gegnern hat ein Spieler kaum eine Chance im ersten Durchlauf für alle Gegner eine KI-Lücke zu finden.
verfasst am: 10.02.2012, 19:17
Spielsatz Alliances

Registrierdatum: 14.07.2004, 14:47

 Beiträge: 1185
Zitat: DirkF
Die KI sollte dann genau diejenigen Befehle aufrufen können, die der Mensch mit der Maus anklickt - sie sollte keine "Extrawürste" in Form eines direkten Engine-Zugriffes bekommen.

So etwas ist zwar etwas aufwendiger zu programmieren (beispielsweise würde dann in den Datenabfragen ein Switch sein, ob das Ergebnis aus der Engine für den Spieler auf dem Bildschirm dargestellt wird oder für ein Skript als Datenpaket übergeben wird), aber dafür kann man spätere Änderungen und Erweiterungen der Engine besser programmieren ohne die KI-Skripte durcheinander zu bringen.

Wenn ich euch jetzt richtig verstehe, sollen so Dinge wie:
- Von P nach Q zu bewegen
- Waffe nach P abfeuern
- Pfad nach P finden
- Ausrüstungslot A mit Gegenstand B ersetzen
- Animation A anstoßen
in der BE-Engine abgekapselt sein und nur über eine beschränkte API angestoßen werden, statt dass interne Details direkt manipuliert werden.
Das scheint mir ebenfalls sinnvoll.

Zitat: DirkF
(beispielsweise würde dann in den Datenabfragen ein Switch sein, ob das Ergebnis aus der Engine für den Spieler auf dem Bildschirm dargestellt wird oder für ein Skript als Datenpaket übergeben wird)

Ich würde noch weiter gehen. Daten abfragen und den aktuellen Zustand rendern sind zwei paar Schuhe. Daten sind da, die können Skripte wie auch der Rendering-Code abfragen.

Zitat: DirkF
Es gibt dazu intern schon einige Überlegungen und Arbeiten, die aber wegen anderen Problemen in der X-Force-Engine (speziell Forschungsliste) zurückgestellt wurden. Ich habe momentan keine Zeit, die Sachen herauszusuchen - aber wenn Du konkrete Fragen stellst, dann kann ich die hoffentlich aus dem Kopf beantworten.

Vielen dank für das Angebot. Aber eigentlich will ich zum BE noch nichts konkretes planen, der steht viel weiter unten auf der Liste. Ich bin froh wenn es in zwei Monaten eine simples, aber spielbare UFO-Hatz gibt. Also, ich komme dann in drei Jahren auf das Angebot zurück ;)
verfasst am: 11.02.2012, 02:42 · Edited by: Kamor
Registrierdatum: 20.07.2005, 00:01

 Beiträge: 203
Zitat: sujin
ausserdem sollte die KI ihre Einheiten über die gleichen finalen Routinen steuern,

wie der Mensch,

Mir ist nicht ganz klar, was du damit meinst.


Sind ja schon ein paar Dinge zu gesagt wurden. Eigentlich meine ich damit nur eine saubere Api, die alle möglichen Aktionen (Outputs) definiert. Sowohl Mensch, wie KI Aktionen gehen über diese Api. Ausserdem sollte diese Api per Script ansprechbar sein.

Die Trennung zwischen Mensch und Ki erfolgt dann durch zwei Interfaces. Das eine könnte man Menschinterface nennen, das andere Ki. Während das Menschinterface eigentlich nur Keyboard/Maus Input verarbeitet und dann daraus eine entsprechende Aktion ableitet und die Output-Api ansteuert, ist das Ki-Interface die Kernlogik für die KI. Wenn du schlau bist, lagerst du diesen ganzen Bereich in den Scriptbereich aus. Wie ich schon erwähnte solltest du hier den Scripter Memoryzugriff und vielleicht sogar Dateizugriff ermöglichen, vielleicht sogar auch über ne Api. Komplizierte Strukturen der Programmierung, die sich auf Speichermanagment oder Dateizugriff beziehen, sind hier eher hinderlich. Die Ki-Scripter sollen sich weitgehend auf Ki-Logik konzentrieren und nicht unnützt Balast nebenbei skripten müssen.

Fehlt noch das schwerste Thema. Der Input. Ok, wenn wir nur ne simple KI programmieren wollen, reicht es wie bisher ein paar Zustände zu triggern. Eigentlich reicht Alien sieht Gegner. Damit kann man schon fast spielen. Hier kann man den Alien aber noch ein paar mehr Sensoren geben. Z.B. Alien wurde getroffen, Alien bekommt mit, wie ein Kollege neben ihm zu Boden geht, Alien sieht zwar nichts, aber hört einen Schuss. Alien kann erkennen ob ein bestimmtest Feld frei ist, besetzt ist oder nicht begehbar ist, Alien erkennt, ob im Schussfeld evtl. ein Kollege steht, um nur ein paar zu nennen. Wenn man dies so umsetzt, hat man aber schon das Problem, das besagte Inputs eigentlich schon KI-Logik sind. Alles was Ki-Logik ist, sollte eigentlich ins Ki-Interface und dies am besten in Scriptform. Als reinen Input würde ich dann nur z.B. Sachen wie Feldstatus(frei, besetzt, unpassierbar) und sämtliche Unterbrecher, die auch für das Menschinterface auslösen, bezeichnen.

Man könnte noch ein Schritt weitergehen und der KI eine Umgebungserkennung geben. Dabei interessiert die Ki nicht, ob da jetzt eine Tanne oder ne Fichte steht, aber eine gute Ki könnte zumindest wissen, ob sie in einem Raum steht oder auf freier Fläche agiert. Ich habe dazu noch einen alten Versuch in Qbasic programmiert. Eigentlich sollte das damals die Optimierung einer Wegefindung werden. Ich zerlege da eine Dungeonmatrix (mit 1 oder 0 Werten) in Räume und Gänge (Objekte). Ausgehend von dem Gedanken, das der Dungeon sich nicht ändert, mache ich also jede Menge logische Vorarbeit für die Wegefindung einmalig zu Programmstart. Es entsteht dort eine Objektstruktur. Raum, Gang, Kreuzung. Im Gegensatz zur klassischen Wegefindung, geht meine Wegefindung durch diese Objekte, wobei ich mehrere Ebenen haben. Die kleinste Ebene ist der Dungeon 1:1, also die klassische, darüber liegen dann Raum oder Gang und diese werden dann logisch immer weiter verbunden. In der höchsten Ebene erkenne ich mit einer Abfrage sofort, ob ein Ziel überhaupt erreichbar ist. Befinde ich mich z.B. in einem langen Endgang oder in einem Raum mit nur einer Tür interressiert sich der Pathfinder gar nicht für das finale Ziel. Er fragt nur ab, ob das finale Ziel im gleichen Raum ist oder nicht. Wenn ja, kommt der klassische Algoryhtmus, wenn nein, ist das neue Ziel der Eingang zum Raum und erst wenn das Feld dort erreicht ist, muss ich mir Gedanken machen, wie es weitergeht. Der Geschwindigkeitsvorteil gegenüber einen Pathfinder, der jedesmal aufs neue wieder die gesamte Karte absucht, ist natürlich enorm. Das ganze habe ich damals in Qbasic programmiert, aber dann irgendwann eingestellt. Wenn sich wer dafür interessiert kann ich den mal wieder ausgraben. Die Erkennung ist fertig, der Zusammenschluß der Objekte auf den höheren Ebenen war noch nicht so optimal. Der Pathfinder durch diese Struktur muss glaube auch noch optimiert werden. Wenn das fertiggestellt ist, toppt das alle A* Algoryhtmen, wobei es umso stärker wird, je verzwickter die Raum/Gang-Strukturen sind.

Aufjedenfall sind dann solche Abfragen wie:
Kann ich das Ziel überhaupt erreichen?
Stehe ich in einen Raum?
Wieviel Ausgänge hat mein Raum?
Wo ist das Feld direkt neben dem Ausgang?
In welche Richtung muss ich gucken, damit ich aus dem Raum gucke?
...
möglich.
verfasst am: 11.02.2012, 14:49
Spielsatz Alliances

Registrierdatum: 14.07.2004, 14:47

 Beiträge: 1185
Danke für die Erläuterung. Ja, da bin ich voll auf deiner Seite.

Was Umgebungserkennung angeht: Klingt cool, aber ich bin nicht sicher ob sowas für alle Karten klappt oder ob gewisse Konventionen nötig sind.
Zitat: Kamor
Wenn das fertiggestellt ist, toppt das alle A* Algoryhtmen, wobei es umso stärker wird, je verzwickter die Raum/Gang-Strukturen sind.

Wie willst du entscheiden, durch welche Räume und Gänge du gehst, um von einem Raum zum nächsten zu gehen? Das ist vielleicht nicht klassische Pfadfindung, aber passt dennoch wunderbar zu A* - das ist nämlich ein sehr allgemeiner Algorithmus, der funktioniert mit allem was man als Graph beschreiben kann. Und wenn das entschieden ist, wie willst du entscheiden, welche Felder von den vielen, die in Räume und Gänge zusammengefasst wurden, tatsächlich begangen werden?
Klingt aber in jedem Fall interessant. Du hast nicht zufällig Zeit und Lust, mitzumachen? ;)
verfasst am: 11.02.2012, 16:27
Admin, Spielsatz GalWar

Registrierdatum: 31.08.2005, 21:51

 Beiträge: 5595
Eine solche Umgebungsanalyse der Karten hat eine ganze Reihe von Problemen, die man nicht so ohne weiteres unterschlagen sollte:

1)
Bei Spielen wie X-Force sind die Karten sehr wohl veränderlich, denn Mauern etc. werden durch Granaten zerstört.
Man muss also jeweils von der aktuellen Karte ausgehen können, sonst können die KI-Einheiten einfach ausmanövriert werden.

2)
Durch Fenster oder niedrige Zäune etc. gibt es Unterschiede zwischen erreichbar und sichtbar - zusätzlich zu der Frage, durch welche "Wände" man hindurchschießen kann etc.
Deshalb kann man nicht so einfach eine absolute 0/1-Struktur als Grundlage für die Analyse nehmen, man muss unterschiedliche Formen von Wänden berücksichtigen können.



Bei früheren Überlegungen zu Kartenstrukturen hatte ich deshalb eher einen anderen Ansatz zur Steuerung im Hinterkopf, bei dem der Kartenersteller spezifische Flags für die KI setzt.
Diese Flags sollten eine Art erweiteter Spawnpoint sein, und für die KI dann verschiedene Informationen wie "dies ist ein Punkt für Scharfschützen, dies ist ein Angriffsziel und der Punkt muss beschützt werden, dies ist der X. Punkt eines Patrouillenganges" sein.

Das ganze ist noch nie richtig ausgearbeitet worden, aber der Hintergedanke war dass der Kartenersteller der einzige ist, der bei einer Karte schon vorher abschätzen kann was eine sinnvolle Strategie für welche Seite sein kann (oder einfach was die jeweiligen Einheiten machen sollen).

Und wenn der Kartenersteller solche Spezialinfos an eine allgemeine KI geben kann und diese jeweils abfragt, welche Art von Spezialpunkten auf einer Karte überhaupt existiert, dann ist das wesentlich einfacher als eine KI die Karten ohne Vorab-Infos analysieren muss.
verfasst am: 11.02.2012, 18:29 · Edited by: Kamor
Registrierdatum: 20.07.2005, 00:01

 Beiträge: 203
Zitat: DirkF
Eine solche Umgebungsanalyse der Karten hat eine ganze Reihe von Problemen, die man nicht so ohne weiteres unterschlagen sollte


Da hast du recht, wenn sich die Kartenstruktur verändert, muss man darauf natürlich reagieren, z.B. die Erstanalyse einfach nochmal neu anstossen dann. Eine zerstörte Wand sehe ich hier nicht als Problem, ein größeres Problem ist da eher ein bewegliches Ziel, was zum Beispiel einen Gang oder eine Tür blockiert. Aber sind wir ehrlich, macht der A-Star da auch schlapp, er nimmt sich dann eine andere Route und man kann im schlimmsten Fall die KI veräppeln indem man immer abwechselnd den Eingang frei gibt und dann wieder besetzt.

Zur Sache mit den Fenstern und niedrigen Zäunen. Der Pathfinder soll ja nur den gehbaren Pfad finden. Wenn man in den Spiel sowas wie Fenster einbaut oder Zäune über die man schiessen kann, muss man dementsprechend noch andere Zustände, wie nur 0 und 1 mit einbeziehen. Wenn du aber so eine Thematik mit in den Bodenkampf einbauen willst, müsste man aber auch nach einem Schuss durch ein normales Fenster dann dort durchgekrabeln können. Zäune kann man auch leicht überklettern. Kostet halt nur mehr Bewegungspunkte. Interressant wären aber Schussnischen in Wänden. Aber das muss dann auch erstmal alles für den Non-KI Bereich programmiert werden. Hier wäre auch interressant Soldaten in Modi agieren zu lassen, liegen, hockend und stehend, vielleicht sogar noch laufend oder vorsichtig schleichend nur um das mal nebenbei erwähnt zu haben.

Aber du hast recht, wenn man Sniperspots direkt auf die Karte setzt, ist das erheblich einfacher. Solche Spots, genau wie die Spawnpunkte setzen dann aber eine statische Bodenkarte voraus, während eine analysierende KI wie ich sie beschreibe auch problemlos mit dynamischen erzeugten Raumstrukturen hantieren soll.

Aber der Arbeitsaufwand ist natürlich enorm einen solchen Algoryhmus sauber zum laufen zu bringen. Das ganze Ding, war auch mehr für Dungeon´s gedacht, wie für ne X-Force Bodenkarte. Ich versuche den Code mal auf Console nach C# zu konvertieren, um den später vielleicht mal ein bischen in objektorientiert zu biegen, derzeit ist das alles statisch und eine einzige Katastrophe.

Beim Thema statisch kann ich auch gleich nochmal zu den Bodenkarten kommen. Was ich beim Original Ufo so gut fand, waren die dynamisch erzeugten Karten. Im Gegensatz geht ihr bei X-Force den Weg von statischen Karten. Hier fände ich es stark, wenn bei den Bodeneinsätzen eine gewisse Dynamik eingebaut werden könnte.


Zitat: sujin
Wie willst du entscheiden, durch welche Räume und Gänge du gehst, um von einem Raum zum nächsten zu gehen?


Die Objekte haben untereinander Bindungen.
Eine Sackkasse z.B. hat nur eine Ausgangsbindung. Ein Ein-Türenraum genauso. Befinde ich mich in einen solchen Konstrukt, muss ich nur überprüfen, ob mein Ziel im selbigen Konstrukt ist. Wenn ja steht er ja schon fast neben mir, also klassische Pathfindung. Wenn nein ist mein neues Ziel die eine Ausgangsbindung zu erreichen.

Stehe ich in einen Raum mit zwei Ausgängen, muss ich zum einen die Schritte zu diesen beiden Ausgängen ermitteln und dann dementsprechend statt jedes einzelnde Feld zum Gesamtziel abzusuchen durch die Objekte suchen. Interessant ist es auch, wenn man schon vorher ermittelt hat, wieviel Schritte es von Eingang 1 zum Eingang 2 eines Raumes braucht. Angenommen von meinem Raum führen 2 Ausgänge weg und es gibt dahinter zwei Gänge, der eine ist 14 Felder lang, der andere nur 10, ich stehe aber fast schon am Ausgang zu dem 14 Feld großen Gang, also wäre der Weg durch den 14er Gang kürzer, usw, und so fort.

Von der anderen Seite betrachtet, komme ich von oben. Da Räume nach oben auch weiter zusammengeschlossen werden, bis ich schließlich ein finales Objekt habe, kann ich über dieses Objekt feststellen, ob ich mich überhaupt im gleichen finalen Konstrukt befinde. Angenommen ich befinde mich in einem Raum der überhaupt keine Verbindung zum Ziel hat. Dann befinden sich Ziel und Ausgang definitiv in zwei verschiedenen finalen Objekten.

Ist das Ziel aber erreichbar, also Ausgang und Ziel sind im gleichen finalen Objekt, gehe ich eine Ebene runter. Aus einen Objekt werden jetzt 2 Objekte, z.B. der südliche Bereich der Karte und der nördliche Bereich der Karte. Beide Objekte sollten ungefähr gleich groß sein, also an Feldgröße oder durch eine besondere dominate Logik getrennt sein, z.B. weil Nordbasis und Südbasis nur über einen Nordsüd-Korridor verbunden sind.

Sind wir also im gleichen finalen Objekt checke ich die Ebene darunter. Sind beide im Nordbereich gehe ich noch eine Ebene runter, falls nicht, ist mein neuer Zielpunkt erstmal auf möglichst kurzen Weg in den anderen Bereich zu kommen. Usw. und sofort. Also jede Menge Logikarbeit.

Es entsteht also sowas wie, "ich bin in ein Raum X, wenn ich den Ausgang 1 nehme, ist die gesamte Wegelänge dort am kürzesten, also ist mein neues Ziel erstmal Ausgang 1."

Das ganze ist sehr komplex, weil die Wegfindung parallel auf mehren abstrakten Ebenen geschieht.

Zitat: sujin
Klingt aber in jedem Fall interessant. Du hast nicht zufällig Zeit und Lust, mitzumachen? ;)


Zeit ist der Punkt und meine Gehirnzellen sind auch schon etwas am altern. ;-) Aber ich versuch den Algoryhtmus mal auf C# zu konvertieren. Mal sehen, ob ich da in das Chaos noch wieder reinkomme und das ganze optimieren kann? Alles was mit KI zu tun hat, fasziniert mich. Wenn du ne gute Schnittstelle bastelst, wo man ohne viel Balastprogrammierung später Ki-Logik programmieren kann, sollte das aber auf jedenfall den einen oder anderen verrückten "Kibernauten" anziehen.
verfasst am: 11.02.2012, 18:58 · Edited by: sujin
Spielsatz Alliances

Registrierdatum: 14.07.2004, 14:47

 Beiträge: 1185
Zitat: Kamor
Die Objekte haben untereinander Bindungen.
Eine Sackkasse z.B. hat nur eine Ausgangsbindung. Ein Ein-Türenraum genauso.

Tada, ein Graph! Und schon kannste A* benutzen, oder jede andere Graph-Suche. Und zwar nur, um zu entscheiden, welche Räume und Gänge du nimmst.

Zitat: Kamor
muss ich zum einen die Schritte zu diesen beiden Ausgängen ermitteln

A*? ;)

Zitat: Kamor
Angenommen von meinem Raum führen 2 Ausgänge weg und es gibt dahinter zwei Gänge, der eine ist 14 Felder lang, der andere nur 10, ich stehe aber fast schon am Ausgang zu dem 14 Feld großen Gang, also wäre der Weg durch den 14er Gang kürzer, usw, und so fort.

Wie händelst du Ausgänge/Gänge, die mehrere Felder breit sind? Wie stellst du die Länge eines solchen Gangs fest? Wenn es z.B. zwei Felder gibt, die gleich schnell erreicht werden können und in den gleichen Raum führen, wie entscheidet sich dein Algorithmus?

Ich sehe langsam wo das hinführt. Du opferst quasi detaillierte Informationen - die für einen (garantiert) optimalen Pfad nötig wären - um zu jedem Zeitpunkt nur Teile des Pfads bearbeiten zu müssen. Das hat natürlich Vorteile, wobei ich die eher bei dynamischen Karten sehe.

Wenn sich an der Belegung der Felder nie etwas ändert, kannst man einfach einmal A* laufen lassen und hat einen optimalen Pfad, und wahrscheinlich mit weniger Aufwand.
Aber wenn sich auf der zweiten Hälfte der Strecke etwas ändert, wenn man grade mal auf halbem Weg ist, dann war das Planen für den zweiten Teil der Strecke vergeblich und man müsste ohnehin neu planen - also hat sich der, der nur die halbe Strecke plant, 50% Arbeit gespart.
Dafür kann es natürlich sein, dass von den beiden möglichen Übergängen zwischen (um das Beispiel zu verwursten) Nord- und Südflügel grade den genommen hat, der irrsinnig weit weg vom Ziel ist.

Ich weiß ja nicht, ob das das wahre ist. Könnte man nicht einen ähnlichen Effekt erreichen, indem man konventionelle Pfadfindung laufen lässt und nach X Arbeitsschritten abbricht und den bisher optimalen Pfad vorläufig übernimmt?
verfasst am: 11.02.2012, 20:43
Admin, Spielsatz GalWar

Registrierdatum: 31.08.2005, 21:51

 Beiträge: 5595
Zitat: Kamor
Was ich beim Original Ufo so gut fand, waren die dynamisch erzeugten Karten. Im Gegensatz geht ihr bei X-Force den Weg von statischen Karten.

Das ist nicht korrekt - im Gegenteil basiert X-Force genauso auf Zufallskarten, die Kartenskripte liefern nur einen Rahmen für sinnvolle Zufallszusammenstellungen.

Das wurde nur deshalb nicht immer deutlich, weil die Auswahl an Kartenelementen nur begrenzt ist - selbst die Xeltaan-UFOs sind aus Zufallselementen zusammengesetzt, aber das sieht man erst bei den größeren UFOs. Denn für einige UFO-elemente ist die Zufallsmenge leider nur "1", weil ich nicht genug Zeit für mehr alternativen hatte...
verfasst am: 11.02.2012, 21:05 · Edited by: Kamor
Registrierdatum: 20.07.2005, 00:01

 Beiträge: 203
Zitat: sujin
Zitat: Kamor
Die Objekte haben untereinander Bindungen.
Eine Sackkasse z.B. hat nur eine Ausgangsbindung. Ein Ein-Türenraum genauso.

Tada, ein Graph! Und schon kannste A* benutzen, oder jede andere Graph-Suche. Und zwar nur, um zu entscheiden, welche Räume und Gänge du nimmst.

Zitat: Kamor
muss ich zum einen die Schritte zu diesen beiden Ausgängen ermitteln

A*? ;)

Jo, das ist die Situation, wo sich Start und Ziel im gleichen Raum befindet, da kann man A* anwenden, wobei A* so zu einem sehr hohen Prozentsatz gleich mit dem ersten Pathversuch das Ziel erreichen wird, auf dieser kurzen Distanz.

Zitat: sujin
Wie händelst du Ausgänge/Gänge, die mehrere Felder breit sind?

Die hatte ich bisher noch zu einem Raum zusammengefasst, hatte aber auch schon erste Überlegungen, wie ich die komplexeren Räume wie z.B. U-Räume in drei Teile zerlege, so das der A* gar nicht erst in die falsche Richtung anfängt zu suchen.

Zitat: sujin
Wie stellst du die Länge eines solchen Gangs fest?

Ja das ist noch ein Punkt, der zu lösen ist.

Zitat: sujin
Wenn es z.B. zwei Felder gibt, die gleich schnell erreicht werden können und in den gleichen Raum führen, wie entscheidet sich dein Algorithmus?


Bei gleich guten Möglichkeit, nimmt man den Würfel. ;-)

Zitat: sujin
Ich sehe langsam wo das hinführt. Du opferst quasi detaillierte Informationen - die für einen (garantiert) optimalen Pfad nötig wären - um zu jedem Zeitpunkt nur Teile des Pfads bearbeiten zu müssen. Das hat natürlich Vorteile, wobei ich die eher bei dynamischen Karten sehe.


Ich opfere keine Informationen. Ich kann wenn gewünscht, auf der untersten 1:1 Ebene denn exakt gleichen Pfad ermitteln, wie dein A*. Nur gibt es halt jede Menge Sonderzustände, die mir diese komplette Pfadsuche ersparen.

Bsp:
--------------------------------------------
start.....................................- ziel
--------------------------------------------

dein a* wird jedesmal aufs neue wieder versuchen zum ziel zu kommen. Mein Algorhytmus fängt erst gar nicht an zu suchen, er weiss, das es nicht möglich ist.

Bsp.
-------------------------------------------
start....................................-
.------------------------------------------
...........................................ziel

hier wird a* jedesmal erneut erst die sackkasse checken, mein algorythmus startet gleich mit dem weg nach unten, weil er weiss, das rechts eine sackkasse ist

Bsp
------------------------------------------
start.....................................ziel weit entfernt
------------------------------------------

bei großen karten mit zielen weit weit entfernt, wird a* nicht wenig Prozessorleistung fordern, weil er erstmal den ganzen Weg bis zum Ziel ermittelt, mein Algorhytmus sagt sich gleich, ist mir doch egal, wo das Ziel ist. Ist bin hier in einer Sackkasse und muss da erstmal raus, dannach können wir weitersuchen.

Am Beispiel von X-Force und meinem Script-Versuchen zur Psi-Ki, heisst das, das nach jedem Schritt, dort ein neuer A* aufgerufen wurde, weil ich nach jedem Schritt, die Situation neu analysiere. Meine Logik könnte in einen solchen Fall sich einen Zwischenstop-Position merken, die sie dann erstmal ansteuert.

Aber du hast recht, alleine wegen der Pathfindung lohnt sich ein solch komplexer Mechanismus für einen X-Force Rewrite nicht wirklich. Wir haben keine Echtzeitstrategie, die Karten sind doch recht überschaubar und meist dominieren die freien Flächen bei den X-Force Scenarien und die Rechner werden immer schneller.

Das ganze Thema hatte ich auch nur auf den Tisch gebracht wegen der Raumerkennung, die dort inclusive ist. Man könnte also auch die Pfadfindung einfach klassisch lassen und noch eine simple Logik entwickeln, die erkennt ob man in einem Raum steht oder halt nicht.

Zitat: sujin
Könnte man nicht einen ähnlichen Effekt erreichen, indem man konventionelle Pfadfindung laufen lässt und nach X Arbeitsschritten abbricht und den bisher optimalen Pfad vorläufig übernimmt?


Wenn A* den optimalen Pfad gefunden hat, ist sie schon einmal den ganzen Pfad durchgegangen, mitsamt allen Fehlversuchen bei bestimmten Raumstrukturen.

Aber was du aufjedenfall machen könntest, ist der Pathfindung eine Art Cache(Memory) einzubauen. Also der letzte gefundene Path, bleibt im Cache(wird gemerkt). Wird nun das gleiche Ziel erneut angesteuert, kann der Pathfinder dementsprechend schnell reagieren. Ausserdem wäre es gut, wenn man den Pathfinder auch nur mal theoretisch starten könnte, um so die tatsächliche Entfernung zum Ziel ermitteln zu können, ohne gleich losmarschieren zu müssen. Bei X-Force ist der Pathfinder alles andere, wie kontaktfreudig. Man kann ihn aufrufen und das war es. Wieviel Felder ist das Ziel entfernt oder ich möchte nur ein Feld auf diesen Pfad gehen, war nur mit Trickserei oder gar nicht möglich. Zeiteinheiten setzen, unterbrechen und dann immer und immer wieder die Pathfindung komplett neu anstossen. Ok heutzutage macht sich kaum einer mehr Gedanken um Rechenzeitoptimierung. Also den Cache kannst getrosst vergessen, wer Probleme bekommt soll sich einfach nen schnelleren Rechner kaufen. Aber die Information, wie weit ist der Alien laut Pathfinder entfernt oder ich möchte nur ein Feld auf den Path gehen, würde ich als sehr wichtige Voraussetzung für eine spätere Ki-Scriptprogrammierung sehen.
verfasst am: 12.02.2012, 00:50 · Edited by: sujin
Spielsatz Alliances

Registrierdatum: 14.07.2004, 14:47

 Beiträge: 1185
Zitat: Kamor
Bei gleich guten Möglichkeit, nimmt man den Würfel. ;-)

Dann hast du eine 50% Chance, einen suboptimalen Pfad zu wählen ;)
Das mag man ja in Kauf nehmen oder sogar begrüßen, muss dir aber bewusst sein.

Zitat: Kamor
Ich opfere keine Informationen. Ich kann wenn gewünscht, auf der untersten 1:1 Ebene denn exakt gleichen Pfad ermitteln, wie dein A*. Nur gibt es halt jede Menge Sonderzustände, die mir diese komplette Pfadsuche ersparen.

Mir ist noch nicht klar, was nun dein Ziel ist. Mein momentaner Eindruck ist, dass du bei der Pfadfindung Zeit sparen willst, indem du ein paar spezialfälle erkennst und geschickter händelst?

In dem Fall, ein paar alternative Vorschläge zu deinen Beispielen (o = Start; x = Ziel):
+-----------------+
| o               | x
+-----------------+
Karte in Disjoin Sets aufteilen. Das sollte sich mit Flood Fill extrem leicht regeln lassen - eine kleine Schleife pro Runde und eine simple Datenstruktur, und du kannst in O(2 * log anzahl_felder) rausfinden, ob zwei Felder verbunden sind. Vielleicht gibt's da auch noch einen besseren Ansatz um die zu pflegen, der nicht direkt die ganze Karte durchgeht.
+--------------------------------------------+
| o                                          |
|- ------------------------------------------|
|                                          x |
+--------------------------------------------+
Ist in der Tat fies, aber wenn mich nicht alles täuscht, dann hängt es sehr stark von ein paar Details ab, wie A* dabei abschneidet. Abhängig von Heuristik, dem Verhalten (LIFO oder FIFO) der Priority Queue bei Gleichständen und wahrscheinlich noch ein paar Sachen kann es genauso gut sein, dass A* zuerst nach Süden geht, im südlichen Korridor landet, und direkt auf den richtigen Pfad stößt.
+--------------------
| o
+--------------------                <ganz weit weg> x
Ja, wenn man ein unmodifiziertes A* auf einen sehr langen Pfad ansetzt, wird es den ganzen Pfad regeln wollen. Aber erstens ist diese Arbeit nicht umsonst, wenn der Pfad nicht ungültig gemacht wird (und wenn dich die Latenz stört, kann man wahrscheinlich inkrementell arbeiten, heißt dann nur nicht mehr A*), und zweitens kann man leicht nach einer Weile abbrechen und einen Teilpfad mitnehmen. OHNE sich einen ganz neuen Algorithmus aus den Fingern saugen zu müssen ;) Um mal ein Beispiel zu geben, mit dem dein Algorithmus (zumindest so wie ich ihn verstanden habe) Probleme kriegen sollte:
+---------------------+
|          o          |
|------ ------- ------|
|                     |
|------ --------------|
|                   x |
+---------------------+
Der optimale Pfad führt durch die rechte Tür, aber ich glaube nicht, dass dein Algorithmus das ohne weiteres herausfinden kann. Mit Heuristik kommst du hier jedenfalls nicht weit (die nordöstliche Tür ist laut Euklid näher am Ziel als die nordwestliche). Bliebe die Möglichkeit, sich die Entfernung zwischen allen Ein- und Ausgängen zu merken... Ach, und auf Flure mit mehreren Feldern zurückzukommen:
+--------- --------+
|  o               |
+-------+   +------+
        |   |
        |   |
        |   |
+-------+   +------+
|   x              |
+----------- ------+


Wie findet der Algorithmus heraus, dass er auf dem westlichen der beiden Flur-End-Felder rauskommen sollte, und sich ergo auf der westlichen Seite des Flurs halten sollte?

Der Punkt von dem allen ist nicht, dass A* ein Wundermittel sei oder das dein Algorithmus schlecht(er) sei. Beide haben ihre Tücken :) Und sei es in letzterem Fall nur die Komplexität.

Zitat: Kamor
Das ganze Thema hatte ich auch nur auf den Tisch gebracht wegen der Raumerkennung, die dort inclusive ist. Man könnte also auch die Pfadfindung einfach klassisch lassen und noch eine simple Logik entwickeln, die erkennt ob man in einem Raum steht oder halt nicht.

Wenn, dann sollte sowas ohnehin den Spielsätzen überlassen werden. Deshalb würde ich dazu:
Zitat: Kamor
Ausserdem wäre es gut, wenn man den Pathfinder auch nur mal theoretisch starten könnte, um so die tatsächliche Entfernung zum Ziel ermitteln zu können, ohne gleich losmarschieren zu müssen. [...] Aber die Information, wie weit ist der Alien laut Pathfinder entfernt oder ich möchte nur ein Feld auf den Path gehen, würde ich als sehr wichtige Voraussetzung für eine spätere Ki-Scriptprogrammierung sehen.

... sogar sagen: Lass uns noch weiter gehen! Die BE-Engine braucht garkeine Pfadfindung, nur die Positionen der Einheiten und die Karteninformationen sowie eine API um beides auszulesen und zu ändern. Das reicht, um in einer "externen" (jedenfalls außerhalb der Engine) Bibliothek eine Pfadfindung reinzuhauen (die auch nicht ungefragt Einheiten verschiebt). Die Standard-KI ist dann nur ein weiterer Benutzer dieser Bibliothek.
verfasst am: 12.02.2012, 08:58 · Edited by: DirkF
Admin, Spielsatz GalWar

Registrierdatum: 31.08.2005, 21:51

 Beiträge: 5595
Zitat: sujin
Die BE-Engine braucht garkeine Pfadfindung, nur die Positionen der Einheiten und die Karteninformationen sowie eine API um beides auszulesen und zu ändern.

Jein

Die BE-Engine braucht einen Befehl, um eine Einheit zu einer anderen Position zu bewegen und auf dem Weg dorthin alle Events zu ermitteln und auszulösen.

Dies kann entweder ein Befehl "Gehe zum Benachbarten Feld B" (ohne Pfadfindung) oder ein Befehl "Gehe zu Koordinate XY" (mit Pfadfindung) sein.

Wenn die Pfadfindung in die KI-Skripte ausgelagert wird, dann wird der Spieler wahnsinnig weil er seine Einheiten mit unzähligen Einzelklicks bewegen muss.
Theoretisch kann man zwar auch in die Spieler-API eine Wegfindung einbauen, aber dann kann man sie gleich besser in die Engine setzen - das wäre einfacher umzusetzen.


Allerdings überseht ihr bei der ganzen Diskussion über die Pfadfindung noch ein anderes Problem:
Der optimale Pfad ist auch von der jeweiligen Einheit abhängig...
Eine schnelle, leichte Einheit mit vielen ZE kann problemlos einen längeren Weg mit viel Deckung gehen während es für eine schwer gepanzerte und langsame Einheit effektiver wäre, ohne Deckung mitten auf einem freien Platz stehen zu bleiben.

Ihr solltet vielleicht eher mit einem default und einer Überlagerung arbeiten, d.h. in der Engine ist eine allgemeine Default-Pfadfindungsroutine. Diese prüft vor dem Aufruf aber, ob sich im Skript einer Einheit eine spezielle Pfadroutine befindet - wenn ja, wird diese anstatt des defaults aufgerufen.

Das hat auch den Vorteil dass die BE mit einem einfachen default schnell umgesetzt werden kann und verschiedene Beispielskripte mit einer individuellen, Einheitenbezogenen Pfadfindung später nachgeliefert werden können.
verfasst am: 12.02.2012, 11:35
Spielsatz Alliances

Registrierdatum: 14.07.2004, 14:47

 Beiträge: 1185
Zitat: DirkF
Die BE-Engine braucht einen Befehl, um eine Einheit zu einer anderen Position zu bewegen und auf dem Weg dorthin alle Events zu ermitteln und auszulösen.

Dies kann entweder ein Befehl "Gehe zum Benachbarten Feld B" (ohne Pfadfindung) oder ein Befehl "Gehe zu Koordinate XY" (mit Pfadfindung) sein.

Das ist mir klar, ich bin auf ersteres aus.

Zitat: DirkF
Wenn die Pfadfindung in die KI-Skripte ausgelagert wird, dann wird der Spieler wahnsinnig weil er seine Einheiten mit unzähligen Einzelklicks bewegen muss.

Nein, denn:
Zitat: DirkF
Theoretisch kann man zwar auch in die Spieler-API eine Wegfindung einbauen, aber dann kann man sie gleich besser in die Engine setzen - das wäre einfacher umzusetzen.

Wieso sollte man es in die Engine schmeißen (und sie damit verkomplizieren), wenn es genauso gut ohne Zugriff auf Engine-Interna, sprich nur mit der öffentlichen API, funktioniert? Das heißt ja nicht, dass man zweimal (für KI und für Spieler) die Pfadfindung machen muss. Es heißt nur, dass man sie auch vom Spieler-Code aus aufruft.

Zitat: DirkF
Eine schnelle, leichte Einheit mit vielen ZE kann problemlos einen längeren Weg mit viel Deckung gehen während es für eine schwer gepanzerte und langsame Einheit effektiver wäre, ohne Deckung mitten auf einem freien Platz stehen zu bleiben.

Wenn es Teil deiner Definition eines optimalen Pfades ist, dann nimm es in Kostenfunktion auf. Den Algorithmus schert es nicht, ob die Kostenfunktion die tatsächlich verbrauchten ZE sind oder eine abstrakere Größe, die irgendwie damit verbunden ist, wie gut es wäre, über dieses Feld zu gehen.
Oder wenn man Reaktionsfeuer in Kauf nimmt und nur in der Runden-Endposition in Deckung stehen will, dann nimm ein inkrementelles A* und such solange Pfade, bis alle Zwischenstops in Deckung liegen. Wenn das zu viel Aufwand ist, dann baut man (wie schonmal erwähnt) eine Bremse ein, die soweit sucht, bis sie einen Pfad hat, der (1) mit den verfügbaren ZE in einer Runde zu schaffen ist, (2) soweit optimal aussieht für das aktuelle Ziel und (3) auf einem Feld mit Deckung (oder sonst irgendeinem Kriterium, was grade wichtiger ist als der kürzeste Pfade).

Zitat: DirkF
Ihr solltet vielleicht eher mit einem default und einer Überlagerung arbeiten, d.h. in der Engine ist eine allgemeine Default-Pfadfindungsroutine. Diese prüft vor dem Aufruf aber, ob sich im Skript einer Einheit eine spezielle Pfadroutine befindet - wenn ja, wird diese anstatt des defaults aufgerufen.

Es sollte in der Tat eine Standard-Implementierung geben. Nur sähe ich die gerne in einem seperaten Skript. Weiterer Vorteil: Will man eigene Pfadfindung machen, kann man Teile davon recyceln.

Zitat: DirkF
Das hat auch den Vorteil dass die BE mit einem einfachen default schnell umgesetzt werden kann und verschiedene Beispielskripte mit einer individuellen, Einheitenbezogenen Pfadfindung später nachgeliefert werden können.

Ist das nicht bei beiden Ansätzen (in Engine eingebaut VS als Bibliothek mitgeliefert) der Fall?
verfasst am: 12.02.2012, 18:21
Registrierdatum: 22.08.2008, 15:51

 Beiträge: 403
Zitat: sujin
Zitat: DirkF
Eine schnelle, leichte Einheit mit vielen ZE kann problemlos einen längeren Weg mit viel Deckung gehen während es für eine schwer gepanzerte und langsame Einheit effektiver wäre, ohne Deckung mitten auf einem freien Platz stehen zu bleiben.

Wenn es Teil deiner Definition eines optimalen Pfades ist, dann nimm es in Kostenfunktion auf. Den Algorithmus schert es nicht, ob die Kostenfunktion die tatsächlich verbrauchten ZE sind oder eine abstrakere Größe, die irgendwie damit verbunden ist, wie gut es wäre, über dieses Feld zu gehen.


Ich glaub, hier überschneiden sich die Themen KI und Wegfindung sehr ungünstig. In meinen Augen muss die Wegfindung den besten Weg von A nach B finden und die KI entscheiden, ob Punkt B auch sinnvoll zum Stehenbleiben ist. Die KI könnte sich zum Beispiel alle Wegpunkte des Pfads geben lassen und dann entscheiden, ob sie wirklich den Pfad bis zum Ziel in nur einer Runde gehen will.

Ich würde A* als Wegfindung bevorzugen, da ich finde, dass es verständlicher ist und mit weniger Rechnungen zum Erklären auskommt.

DirkF: Wo steht eigentlich im XF-Source die Wegfindung bzw wie ist es da geregelt?

Noch etwas offtopic: sujin, bist du eigentlich ein ausggebildeter IT Spezailist oder woher weißt du soviel?
verfasst am: 12.02.2012, 18:37 · Edited by: sujin
Spielsatz Alliances

Registrierdatum: 14.07.2004, 14:47

 Beiträge: 1185
Zitat: Kreks
In meinen Augen muss die Wegfindung den besten Weg von A nach B finden und die KI entscheiden, ob Punkt B auch sinnvoll zum Stehenbleiben ist.

Prinzipiell ja.
Allerdings bröckelt diese strikte Trennung, wenn es der KI nicht mehr egal ist, ob und wo sie eine Zwischenstation einlegen muss. Dann muss die KI rausfinden, wo sie denn sinnvollerweise Zwischenstationen einlegen könnte, und das geht dann schon wieder in Pfadfindung über. Ein wenig mehr Kooperation lässt sich wohl nicht vermeiden.

Zitat: Kreks
Noch etwas offtopic: sujin, bist du eigentlich ein ausggebildeter IT Spezailist oder woher weißt du soviel?

Naja, inzwischen mache ich am Berufskolleg etwas in Richtung IT, aber auch wenn es sehr lehrreich ist, ist die Schnittmenge mit dem, was ich hier einbringe (z.B. Grafikprogrammierung, Pfadfindung, Datenserialisierung, Python), eher klein. Da bin ich größtenteils Autodidakt.
verfasst am: 13.02.2012, 08:01
Admin, Spielsatz GalWar

Registrierdatum: 31.08.2005, 21:51

 Beiträge: 5595
Bei der Wegfindung solltet Ihr auch bedenken, dass der gefundene Weg fast nie bis zum Ende gegangen werden wird.
Das liegt nicht nur an den begrenzten ZE, sondern auch an zwischenzeitlichen Events wie z.B. die Sichtung eines Feindes etc.

Bei einem längeren Weg von ca. 50 Feldern ist also meiner Meinung nach eine Optimierung oder Unterscheidung von 45 oder 55 Bewegungen eher wenig sinnvoll, da die meisten Einheiten sowieso nach 10-20 Feldern stehen bleiben müssen.
Und in der nächsten Runde kann die Situation schon wieder ganz anders aussehen und man muss sowieso neu berechnen.

Zitat: Kreks
DirkF: Wo steht eigentlich im XF-Source die Wegfindung bzw wie ist es da geregelt?

Kann ich nicht sagen, müsste ich selber suchen - da hat sich mehr Natter drum gekümmert.
verfasst am: 13.02.2012, 13:31 · Edited by: Natter
Programmierer, allgemeines

Registrierdatum: 06.06.2004, 17:19

 Beiträge: 3186
Zitat: Kreks

DirkF: Wo steht eigentlich im XF-Source die Wegfindung bzw wie ist es da geregelt?

Gibt dafür glaube eine extra unit pathfinding.pas (oder so ähnlich). Gegebenenfalls kann ich da später nochmal nachschauen. Als Algorithmus wird jedenfalls A* benutzt. Probleme mit ZickZack etc. lagen damals nicht am Algorithmus sondern an falscher Gewichtung (z.B. hat es früher keinen Unterschied bei den ZE gemacht, ob man gerade oder Diagonal lief).

Ich würde Kreks übrigens recht geben - Pathfinding sollte primär erstmal den kürzesten Weg von A nach B finden. Wenn man Sachen wie Deckung etc. aber wirklich mit dem Pathfinding abdecken will, sollte man das einfach durch zusätzliche Abzüge für bestimmte Felder realisieren. Dann könnte eine zusätzliche Routine z.B. für jedes Feld einen Malus bezüglich fehlender Deckung berechnen, und dieser würde dann optional beim Pathfinding berücksichtigt. Prinzipiell tendiere ich allerdings eher dazu, dass über den Zielpunkt zu lösen (also wo schickt die KI eine Einheit hin), und nicht über den Wegfindungsalgorithmus.

Seite: << [1] [2] [3] 4 [5] [6] [7] [8] [9] [10] >>




Du musst dich registrieren um auf dieses Thema zu antworten.
Login :: » Name » Passwort

Ladezeit (sec.): 0.026 · Powered by miniBB 1.6 with parts of 1.7 © 2001-2003