Worms KI

Übersicht

BlitzMax, BlitzMax NG

Allgemein

	coolo Betreff: Worms KI	Mo, Okt 26, 2009 15:50 Antworten mit Zitat
Hallo, im Moment arbeite ich an einem Worms Klon, und nun bin ich an den Punkt angelangt wo ich die KI implementieren will. Gesagt getan, doch schnell habe ich gemerkt, dass das nicht so einfach funktioniert. Doch leider bin ich nun nach einigen Stunden überlegen am Scheitern. Es gibt einfach zuviele verschiedene Kombinationen. Dazu habe ich folgende Rechnung aufgestellt: Wie viele Spieler gibt es? 8 Wieviele verschiedene Winkel gibt es, die die Waffe annehmen kann? 360 Wieviele verschiedene Geschwindigkeiten kann die Waffe annehmen? 100 Wieviele verschiedene Waffen gibt es? 20 Wie viele verschiedene Schusspositionen gibt es, die der Gegner annehmen kann? Seeehr viele Nun seht ihr das Problem es gibt einfach zuviele Kombinationen die die KI überprüfen muss. Außerdem brauche ich eine Art Pathfinding die berücksichtigt, dass man mit Jetpacks in die Luft fliegen kann und dass man nicht runter fliegen darf . Ich hoffe ihr könnt mir einen Ansatz erklären.
http://programming-with-design.at/ <-- Der Preis ist heiß! That's no bug, that's my project! "Eigenzitate sind nur was für Deppen" -Eigenzitat

coolo

Betreff: Worms KI

Mo, Okt 26, 2009 15:50
Antworten mit Zitat

Hallo,

im Moment arbeite ich an einem Worms Klon, und nun bin ich an den Punkt angelangt wo ich die KI implementieren will. Gesagt getan, doch schnell habe ich gemerkt, dass das nicht so einfach funktioniert.

Doch leider bin ich nun nach einigen Stunden überlegen am Scheitern. Es gibt einfach zuviele verschiedene Kombinationen.

Dazu habe ich folgende Rechnung aufgestellt:
Wie viele Spieler gibt es? 8
Wieviele verschiedene Winkel gibt es, die die Waffe annehmen kann? 360
Wieviele verschiedene Geschwindigkeiten kann die Waffe annehmen? 100
Wieviele verschiedene Waffen gibt es? 20
Wie viele verschiedene Schusspositionen gibt es, die der Gegner annehmen kann? Seeehr viele

Nun seht ihr das Problem es gibt einfach zuviele Kombinationen die die KI überprüfen muss. Außerdem brauche ich eine Art Pathfinding die berücksichtigt, dass man mit Jetpacks in die Luft fliegen kann und dass man nicht runter fliegen darf Sad

.

Ich hoffe ihr könnt mir einen Ansatz erklären.

http://programming-with-design.at/ <-- Der Preis ist heiß!
That's no bug, that's my project!
"Eigenzitate sind nur was für Deppen" -Eigenzitat

	ChaosCoder	Mo, Okt 26, 2009 16:23 Antworten mit Zitat
Jaja, das alte Thema der KI... Wie immer gibt es verscheidene Lösungsansätze. Einen will ich mal eben anreißen: Deine KI analysiert in jeder Runde die Situation. Erstellt eine Liste mit Informationen, wie sie bestimtme Ziele erreichen kann (z.B. wie sie Gegner X umbringen kann, das beinhaltet: Distanz zum Gegner, direkte Hindernisse zwischen mir und Gegner, HP des Gegners, spezielle Umstände (steht nah am Abgrund, weitere Gegner stehen daneben, etc.) Zusätzlich erstellst du eine Informationsliste zu den Waffen. Darin sollte z.B. stehen,unter welchen Voraussetzungen bestimmte Waffen anderen vorzuziehen sind. Eine Shotgun hat zum Beispiel dann Eigenschaften wie: Distanz < 10m, nur für direkten schuss, schaden: 100hp*(1-distanz/10m), Projektilmasse: gering, noch 3 mal vorhanden, priorität: 0.3 Je mehr Informationen du einbaust, desto intelligenter könnte deine KI auf Situationen reagieren. Sind mehrere Waffen für die Situaiton brauchbar, entscheidet eine Prioritätsangabe und eine Stückzahl die Wahl. Die Wahl impliziert natürlich die Berechnung möglicher Flugbahnen und die dazugehörigen Schussstärken und so => ein bisschen Mathe. So könnte deine KI auf alle Situationen reagieren, bei der sie Gegner töten muss. Zusätzlich brauchst du natürlich Pathfinding, das auch mit in die Entscheidung einfließt. Wenn du ne Kettensäge benutzen kannst, wenn du 2m zum gegner hingelaufen bist, ist das natürlich besser als dem Gegner einen Baseball an den Kopf zu werfen. Eine Standardwaffe (wie bei Worms die Bazooka) hilft dabei, eine unentscheidbare Situation zu lösen. Alles in allem sind gute KIs sehr kompliziert. Mit Jetpacks, die es der KI ermöglichen das Gelände viel mehr zu nutzen, steigt der Aufwand natürlich. Programmiere aber erstmal dein Spiel, du kannst es ja erstmal auf Netzwerk auslegen, wenn dus fertig hast, dann kann man immernoch mal drüber nachdenken, eine KI einzubauen. Der Vorteil dabei ist, dass du dann vor einem fertigen Spiel stehst. Es kann im Grunde keine große Veränderung mehr kommen, die die KI dann wieder völlig unbrauchbar macht. Vielleicht hilft dir das ja, ansonsten, viel Erfolg!
Projekte: Geolaria \| aNemy Webseite: chaosspace.de

ChaosCoder

Mo, Okt 26, 2009 16:23
Antworten mit Zitat

Jaja, das alte Thema der KI... Rolling Eyes

Wie immer gibt es verscheidene Lösungsansätze. Einen will ich mal eben anreißen:

Deine KI analysiert in jeder Runde die Situation. Erstellt eine Liste mit Informationen, wie sie bestimtme Ziele erreichen kann (z.B. wie sie Gegner X umbringen kann, das beinhaltet: Distanz zum Gegner, direkte Hindernisse zwischen mir und Gegner, HP des Gegners, spezielle Umstände (steht nah am Abgrund, weitere Gegner stehen daneben, etc.)

Zusätzlich erstellst du eine Informationsliste zu den Waffen.
Darin sollte z.B. stehen,unter welchen Voraussetzungen bestimmte Waffen anderen vorzuziehen sind.
Eine Shotgun hat zum Beispiel dann Eigenschaften wie: Distanz < 10m, nur für direkten schuss, schaden: 100hp*(1-distanz/10m), Projektilmasse: gering, noch 3 mal vorhanden, priorität: 0.3

Je mehr Informationen du einbaust, desto intelligenter könnte deine KI auf Situationen reagieren. Sind mehrere Waffen für die Situaiton brauchbar, entscheidet eine Prioritätsangabe und eine Stückzahl die Wahl. Die Wahl impliziert natürlich die Berechnung möglicher Flugbahnen und die dazugehörigen Schussstärken und so => ein bisschen Mathe.
So könnte deine KI auf alle Situationen reagieren, bei der sie Gegner töten muss.

Zusätzlich brauchst du natürlich Pathfinding, das auch mit in die Entscheidung einfließt. Wenn du ne Kettensäge benutzen kannst, wenn du 2m zum gegner hingelaufen bist, ist das natürlich besser als dem Gegner einen Baseball an den Kopf zu werfen. Wink

Eine Standardwaffe (wie bei Worms die Bazooka) hilft dabei, eine unentscheidbare Situation zu lösen.

Alles in allem sind gute KIs sehr kompliziert. Mit Jetpacks, die es der KI ermöglichen das Gelände viel mehr zu nutzen, steigt der Aufwand natürlich.

Programmiere aber erstmal dein Spiel, du kannst es ja erstmal auf Netzwerk auslegen, wenn dus fertig hast, dann kann man immernoch mal drüber nachdenken, eine KI einzubauen. Der Vorteil dabei ist, dass du dann vor einem fertigen Spiel stehst. Es kann im Grunde keine große Veränderung mehr kommen, die die KI dann wieder völlig unbrauchbar macht.

Vielleicht hilft dir das ja, ansonsten, viel Erfolg!

Projekte: Geolaria | aNemy
Webseite: chaosspace.de

	n-Halbleiter	Mo, Okt 26, 2009 16:27 Antworten mit Zitat
Verdammt, CC war schneller... Ich würde es genau so machen. Wen's interessiert, mein Text (in CCs steht eigentlich das alles ausführlicher). n-Halbleiter hat Folgendes geschrieben: Ich würde das Spielfeld gerastert in einem Array speichern, damit du einen Überblick über alle begehbaren Felder erhälst (Ist das Feld ein Bodenfeld und das darüber ein freies, ist das Bodenfeld begehbar). Anhand dieser Informationen kannst du nun günstige Schusspositionen anhand folgender Kriterien auswählen (nur Beispiele): Lage (ist das Feld auf einem Hügel, ist das gut; ist es eine Ecke oder gar in einem Tunnel, ist es schlecht). Hierfür kannst du einfach dein Array konsultieren (Nachbarberücksichtigung und so). Entfernung zum nächsten Gegner/ zur nächsten Gegnergruppe (bei großen Entfernungen ist es gut, wenn viel Munition von präzisen Waffen da ist) Wenn dann eine Position in die nähere Auswahl kommt, kannst du per A* den Weg herausfinden, mit dem zur Position zu gelangen ist. Zum Thema Schießen würde ich raten, dass du noch prüfst, ob in einer Richtung mehrere Gegner (mit nach Möglichkeit wenig Lebenspunkten) sind. Wenn es eine Gruppe von nahe beeinanderstehenden Gegnern gibt, sollte zu einer Explosivwaffe gegriffen werden, wenn es ein einzelner Gegner ist, sollte die Waffe genutzt werden, die am meisten Schaden macht und von der am meisten Munition da ist. Beim Waffe ausrichten muss berücksichtigt werden, ob das Geschoss sich wie eine Granate verhält (mit Wurfparabel, die durch den Wind und den Winkel beeinflusst wird), oder ob es wie eine Waffenkugel gehandhabt wird (Es muss nur direkt ausgerichtet werden). Du musst also Speichern: Ein Array, in dem gespeichert wird, ob das Feld: a) ein freies oder b) ein Bodenfeld ist. Eine Liste von begehbaren Bodenfeldern "Beschreibungen" für Waffen: Hierfür würde sich ein Type eignen, in dem du zusätzlich noch ein Array/eine Bank als Field hast, in der für verschiedene Eigenschaften (z.B. Explosionsradius, Schaden gesamthaft, Ungenauigkeit) der einzelnen Waffen gespeichert werden. Diese Werte können als Kriterien zur Waffenwahl genutzt werden.
mfg, Calvin Maschine: Intel Core2 Duo E6750, 4GB DDR2-Ram, ATI Radeon HD4850, Win 7 x64 und Ubuntu 12.04 64-Bit Ploing! Blog "Die Seele einer jeden Ordnung ist ein großer Papierkorb." - Kurt Tucholsky (09.01.1890 - 21.12.1935)

n-Halbleiter

Mo, Okt 26, 2009 16:27
Antworten mit Zitat

Verdammt, CC war schneller... Confused

Ich würde es genau so machen.

Wen's interessiert, mein Text (in CCs steht eigentlich das alles ausführlicher). n-Halbleiter hat Folgendes geschrieben:

Ich würde das Spielfeld gerastert in einem Array speichern, damit du einen Überblick über alle begehbaren Felder erhälst (Ist das Feld ein Bodenfeld und das darüber ein freies, ist das Bodenfeld begehbar). Anhand dieser Informationen kannst du nun günstige Schusspositionen anhand folgender Kriterien auswählen (nur Beispiele):

Lage (ist das Feld auf einem Hügel, ist das gut; ist es eine Ecke oder gar in einem Tunnel, ist es schlecht). Hierfür kannst du einfach dein Array konsultieren (Nachbarberücksichtigung und so). Wink

Entfernung zum nächsten Gegner/ zur nächsten Gegnergruppe (bei großen Entfernungen ist es gut, wenn viel Munition von präzisen Waffen da ist)

Wenn dann eine Position in die nähere Auswahl kommt, kannst du per A* den Weg herausfinden, mit dem zur Position zu gelangen ist.

Zum Thema Schießen würde ich raten, dass du noch prüfst, ob in einer Richtung mehrere Gegner (mit nach Möglichkeit wenig Lebenspunkten) sind. Wenn es eine Gruppe von nahe beeinanderstehenden Gegnern gibt, sollte zu einer Explosivwaffe gegriffen werden, wenn es ein einzelner Gegner ist, sollte die Waffe genutzt werden, die am meisten Schaden macht und von der am meisten Munition da ist. Beim Waffe ausrichten muss berücksichtigt werden, ob das Geschoss sich wie eine Granate verhält (mit Wurfparabel, die durch den Wind und den Winkel beeinflusst wird), oder ob es wie eine Waffenkugel gehandhabt wird (Es muss nur direkt ausgerichtet werden).

Du musst also Speichern:

Ein Array, in dem gespeichert wird, ob das Feld: a) ein freies oder b) ein Bodenfeld ist.

Eine Liste von begehbaren Bodenfeldern

"Beschreibungen" für Waffen: Hierfür würde sich ein Type eignen, in dem du zusätzlich noch ein Array/eine Bank als Field hast, in der für verschiedene Eigenschaften (z.B. Explosionsradius, Schaden gesamthaft, Ungenauigkeit) der einzelnen Waffen gespeichert werden. Diese Werte können als Kriterien zur Waffenwahl genutzt werden.

mfg, Calvin
Maschine: Intel Core2 Duo E6750, 4GB DDR2-Ram, ATI Radeon HD4850, Win 7 x64 und Ubuntu 12.04 64-Bit
Ploing!
Blog
"Die Seele einer jeden Ordnung ist ein großer Papierkorb." - Kurt Tucholsky (09.01.1890 - 21.12.1935)

	ChaosCoder	Mo, Okt 26, 2009 16:42 Antworten mit Zitat
Wobei wohl das größte Problem dann dein Array sein wird, n-Halbleiter. Denn ein Wormsfeld ist keine Tilemap sondern eher ein großes Bild, auf dem die Pixel "Boden" darstellen und die Pixel einer bestimmten Farbe maskiert werden und somit "Luft" darstellen. Also kommt man nich weit mit einer Einteilung in 16x16 oder was weiß ich wie großen Quadraten. Im Grudne hast du natürlich recht mit einem Array, denn auch das Bild ist ja nur ein 2D Array, allerdings sind die Bereiche dann auch 1px*1px groß. Also ist es ein Bisschen mehr Aufwand, zu prüfen, ob man irgendwo lang kann: Checken wo der Boden ist Gucken ob der Boden vom der aktuellen Höhe erreichbar wäre x Pixel darüber prüfen, ob sie auch Luft sind. (x=Höhe des Spielers) erst dann weiß man, das man 1 Pixel in diese Richtung gehen kann. Schlau wäre es, die Karte vorher zu analysieren und natürlich immer wenn sie verändert wird. Dann merkt man sich begehbare Bereiche.
Projekte: Geolaria \| aNemy Webseite: chaosspace.de

ChaosCoder

Mo, Okt 26, 2009 16:42
Antworten mit Zitat

Wobei wohl das größte Problem dann dein Array sein wird, n-Halbleiter. Denn ein Wormsfeld ist keine Tilemap sondern eher ein großes Bild, auf dem die Pixel "Boden" darstellen und die Pixel einer bestimmten Farbe maskiert werden und somit "Luft" darstellen. Also kommt man nich weit mit einer Einteilung in 16x16 oder was weiß ich wie großen Quadraten.

Im Grudne hast du natürlich recht mit einem Array, denn auch das Bild ist ja nur ein 2D Array, allerdings sind die Bereiche dann auch 1px*1px groß. Also ist es ein Bisschen mehr Aufwand, zu prüfen, ob man irgendwo lang kann:
Checken wo der Boden ist
Gucken ob der Boden vom der aktuellen Höhe erreichbar wäre
x Pixel darüber prüfen, ob sie auch Luft sind. (x=Höhe des Spielers)
erst dann weiß man, das man 1 Pixel in diese Richtung gehen kann.

Schlau wäre es, die Karte vorher zu analysieren und natürlich immer wenn sie verändert wird. Dann merkt man sich begehbare Bereiche.

Projekte: Geolaria | aNemy
Webseite: chaosspace.de

	FireballFlame	Mo, Okt 26, 2009 16:47 Antworten mit Zitat
Ich würde zuerst allen Gegnern eine "Bewertung" verpassen, die sich daraus zusammensetzt, wie leicht sie zu töten sind (hp, Nähe zum Abgrund). Dann bräuchste man die schon erwähnten Informationen zu den Waffen und könnte damit für jede Waffe errechnen, wie gut die Trefferchancen sind (zuerst vielleicht anhand der Entfernung zur nächsten gute Schussposition, später mit einem fortgeschrittenerem Pathfinding). Ich muss aber ChaosCoder zustimmen, dass man eine KI besser am Schluss machen sollte, wenn alles andere schon feststeht.
PC: Intel Core i7 @ 4x2.93GHz \| 6 GB RAM \| Nvidia GeForce GT 440 \| Desktop 2x1280x1024px \| Windows 7 Professional 64bit Laptop: Intel Core i7 @ 4x2.00GHz \| 8 GB RAM \| Nvidia GeForce GT 540M \| Desktop 1366x768px \| Windows 7 Home Premium 64bit

FireballFlame

Mo, Okt 26, 2009 16:47
Antworten mit Zitat

Ich würde zuerst allen Gegnern eine "Bewertung" verpassen, die sich daraus zusammensetzt, wie leicht sie zu töten sind (hp, Nähe zum Abgrund). Dann bräuchste man die schon erwähnten Informationen zu den Waffen und könnte damit für jede Waffe errechnen, wie gut die Trefferchancen sind (zuerst vielleicht anhand der Entfernung zur nächsten gute Schussposition, später mit einem fortgeschrittenerem Pathfinding).
Ich muss aber ChaosCoder zustimmen, dass man eine KI besser am Schluss machen sollte, wenn alles andere schon feststeht.

	coolo	Mo, Okt 26, 2009 16:54 Antworten mit Zitat
In einem Array ist das ganze schon wegen den Kollisionsabfragen, so gehts nämlich Ruckzuck. Sowie ChaosCoder es beschrieben hat, wollt ichs auch machen, nur hab ich da zwei probleme: 1. Das Pathfinding: A* kann ich ja nicht nehmen, da der mehr auf Tilemaps ausgelegt ist. Außerdem muss er ja wie gesagt die Schwerkraft und die einzelnen Fortbewegungsarten berücksichtigen 2. Wie erzeuge ich diese List? Das Problem ist ja eigentlich nicht die Liste sondern die "Antwort" auf die Liste. Also wie die KI entscheidet welcher Information sie nachgeht. Das Worms Spiel ist eigentlich fertig, es fehlenlediglich die KI und die Waffen (wobei da schon 5 implementiert wurden). Achja hab ich schon gesagt, dass das in Echtzeit ablaufen sollte? Aber wenns nicht geht, dann werde ich es doch rundenbasiert machen.
http://programming-with-design.at/ <-- Der Preis ist heiß! That's no bug, that's my project! "Eigenzitate sind nur was für Deppen" -Eigenzitat

coolo

Mo, Okt 26, 2009 16:54
Antworten mit Zitat

In einem Array ist das ganze schon wegen den Kollisionsabfragen, so gehts nämlich Ruckzuck.

Sowie ChaosCoder es beschrieben hat, wollt ichs auch machen, nur hab ich da zwei probleme:

1. Das Pathfinding: A* kann ich ja nicht nehmen, da der mehr auf Tilemaps ausgelegt ist. Außerdem muss er ja wie gesagt die Schwerkraft und die einzelnen Fortbewegungsarten berücksichtigen

2. Wie erzeuge ich diese List? Das Problem ist ja eigentlich nicht die Liste sondern die "Antwort" auf die Liste. Also wie die KI entscheidet welcher Information sie nachgeht.

Das Worms Spiel ist eigentlich fertig, es fehlenlediglich die KI und die Waffen (wobei da schon 5 implementiert wurden).

Achja hab ich schon gesagt, dass das in Echtzeit ablaufen sollte? Aber wenns nicht geht, dann werde ich es doch rundenbasiert machen.

http://programming-with-design.at/ <-- Der Preis ist heiß!
That's no bug, that's my project!
"Eigenzitate sind nur was für Deppen" -Eigenzitat

	n-Halbleiter	Mo, Okt 26, 2009 17:04 Antworten mit Zitat
coolo hat Folgendes geschrieben: 1. Das Pathfinding: A* kann ich ja nicht nehmen, da der mehr auf Tilemaps ausgelegt ist. Außerdem muss er ja wie gesagt die Schwerkraft und die einzelnen Fortbewegungsarten berücksichtigen Stimmt, hast Recht, ich hatte nur Pathfinding gelesen und dann direkt "A*" geschrieben... Du kannst ja erstmal eine imaginäre Linie zum Ziel ziehen und dann immer, wenn die Linie durch Luft unterbrochen wird, eine "Sprungmarke" setzen (sofern es kein Krater ist), und immer, wenn Boden in den Weg kommt, bis zum nächsten größeren Umbruch im Weg (beispielsweise ein Abfallen) eine weitere Linie ziehen. Das Verfahren kannst du dann ja wiederholen... Ich werde gleich mal eine Skizze machen, wie ich das meine. EDIT: So, ich habe mal eine Schemazeichnung des Algorithmus, wie ich ihn mir vorstelle, gemacht. Ich hoffe, das hilft dir weiter. Wenn nicht, schreibe hier ins Forum, ich werde dann erläutern, was ich meine.

n-Halbleiter

Mo, Okt 26, 2009 17:04
Antworten mit Zitat

coolo hat Folgendes geschrieben:

1. Das Pathfinding: A* kann ich ja nicht nehmen, da der mehr auf Tilemaps ausgelegt ist. Außerdem muss er ja wie gesagt die Schwerkraft und die einzelnen Fortbewegungsarten berücksichtigen

Stimmt, hast Recht, ich hatte nur Pathfinding gelesen und dann direkt "A*" geschrieben... Du kannst ja erstmal eine imaginäre Linie zum Ziel ziehen und dann immer, wenn die Linie durch Luft unterbrochen wird, eine "Sprungmarke" setzen (sofern es kein Krater ist), und immer, wenn Boden in den Weg kommt, bis zum nächsten größeren Umbruch im Weg (beispielsweise ein Abfallen) eine weitere Linie ziehen. Das Verfahren kannst du dann ja wiederholen... Ich werde gleich mal eine Skizze machen, wie ich das meine.

EDIT: So, ich habe mal eine Schemazeichnung des Algorithmus, wie ich ihn mir vorstelle, gemacht.

user posted image

Ich hoffe, das hilft dir weiter. Wenn nicht, schreibe hier ins Forum, ich werde dann erläutern, was ich meine.

	coolo	Di, Okt 27, 2009 18:24 Antworten mit Zitat
Danke für diesen Lösungsvorschlag er hat mir sehr geholfen das Thema zu verstehen. Aber das Problem an diesem Algorithmus: Er ist zu rechenaufwändig. Darum hab ich auf dieser Basis einen neuen Algo mir ausgedacht. Statt dem entlang "gehen" setzt er nun vorberechnete Punkte wo der Wurm gehen kann, wo er graben kann, und wo er fliegen kann und dann mit einem simplen Djiriska Algorithmus (Die Kostenschätzung funktioniert dadurch leider nicht) der Weg gesucht. Dabei haben bestimmt Wegpunkte mehr Vorrang (Der Wurm wird bevorzugt zum Spieler gehen als sich hinzugraben). Das Vorberechnen wird kein Problem sein, da man beim verändern der Map (sprich schießen) nicht alles neu berechnen muss, man kann auch ganz einfach nur diesen einen Bereich neu berechnen, welche Punkte der Wurm begehen kann / nicht begehen kann. Um es deutlicher zu erklären habe ich diese Skizze mit Paint gemacht: Weiß=graben Rot=gehen Gelb=fliegen türkises rechteck=Start Position gelbes Rechteck=Zielposition Die andere Frage mit der "Taktik" werde ich lösen sobald das Pathfinding einigermaßen läuft. Über Anmerkungen/Verbesserungsvorschlägen würde ich mich sehr freuen
http://programming-with-design.at/ <-- Der Preis ist heiß! That's no bug, that's my project! "Eigenzitate sind nur was für Deppen" -Eigenzitat

coolo

Di, Okt 27, 2009 18:24
Antworten mit Zitat

Danke für diesen Lösungsvorschlag er hat mir sehr geholfen das Thema zu verstehen.

Aber das Problem an diesem Algorithmus: Er ist zu rechenaufwändig. Darum hab ich auf dieser Basis einen neuen Algo mir ausgedacht. Statt dem entlang "gehen" setzt er nun vorberechnete Punkte wo der Wurm gehen kann, wo er graben kann, und wo er fliegen kann und dann mit einem simplen Djiriska Algorithmus (Die Kostenschätzung funktioniert dadurch leider nicht) der Weg gesucht. Dabei haben bestimmt Wegpunkte mehr Vorrang (Der Wurm wird bevorzugt zum Spieler gehen als sich hinzugraben).

Das Vorberechnen wird kein Problem sein, da man beim verändern der Map (sprich schießen) nicht alles neu berechnen muss, man kann auch ganz einfach nur diesen einen Bereich neu berechnen, welche Punkte der Wurm begehen kann / nicht begehen kann.

Um es deutlicher zu erklären habe ich diese Skizze mit Paint gemacht:
user posted image

Weiß=graben
Rot=gehen
Gelb=fliegen
türkises rechteck=Start Position
gelbes Rechteck=Zielposition

Die andere Frage mit der "Taktik" werde ich lösen sobald das Pathfinding einigermaßen läuft.

Über Anmerkungen/Verbesserungsvorschlägen würde ich mich sehr freuen Smile

http://programming-with-design.at/ <-- Der Preis ist heiß!
That's no bug, that's my project!
"Eigenzitate sind nur was für Deppen" -Eigenzitat

	n-Halbleiter	Di, Okt 27, 2009 22:03 Antworten mit Zitat
Ich weiß, er ist sehr rechenaufwendig, aber ich habe ihn spontan entworfen. Deine Lösung ist natürlich sehr schön, da bin ich ja echt froh, dass ich dir helfen konnte.
mfg, Calvin Maschine: Intel Core2 Duo E6750, 4GB DDR2-Ram, ATI Radeon HD4850, Win 7 x64 und Ubuntu 12.04 64-Bit Ploing! Blog "Die Seele einer jeden Ordnung ist ein großer Papierkorb." - Kurt Tucholsky (09.01.1890 - 21.12.1935)

n-Halbleiter

Di, Okt 27, 2009 22:03
Antworten mit Zitat

Ich weiß, er ist sehr rechenaufwendig, aber ich habe ihn spontan entworfen. Wink

Deine Lösung ist natürlich sehr schön, da bin ich ja echt froh, dass ich dir helfen konnte. Smile

	Dj$$$ Betreff: Ich kapiere es nicht	Do, Jun 02, 2011 9:42 Antworten mit Zitat
Kann mal bitte einer den kompletten Code posten,weil ich es einfach nicht kapiere. Ich bin ein Anfänger

Dj$$$

Betreff: Ich kapiere es nicht

Do, Jun 02, 2011 9:42
Antworten mit Zitat

Kann mal bitte einer den kompletten Code posten,weil ich es einfach nicht kapiere. Ich bin ein Anfänger

	Xeres Moderator	Do, Jun 02, 2011 12:22 Antworten mit Zitat
Nein, und zwar aus Prinzip nicht. Wir haben die Arbeit und du wirst nichts daraus lernen. Wenn du was lernen willst, musst du wohl oder übel selbst nachdenken und selbst tippen. Wenn du was geschafft hast, werden dir gerne Hinweise & Verbesserungsvorschläge gegeben. Wenn dir das zu schwer ist - mach was einfacheres! Ist ja nicht so, das dir was entgeht.
Win10 Prof.(x64)/Ubuntu 16.04\|CPU 4x3Ghz (Intel i5-4590S)\|RAM 8 GB\|GeForce GTX 960 Wie man Fragen richtig stellt \|\| "Es geht nicht" \|\| Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Xeres

Moderator

Do, Jun 02, 2011 12:22
Antworten mit Zitat

Nein, und zwar aus Prinzip nicht.
Wir haben die Arbeit und du wirst nichts daraus lernen. Wenn du was lernen willst, musst du wohl oder übel selbst nachdenken und selbst tippen. Wenn du was geschafft hast, werden dir gerne Hinweise & Verbesserungsvorschläge gegeben.
Wenn dir das zu schwer ist - mach was einfacheres! Ist ja nicht so, das dir was entgeht.

Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

	Hummelpups	Do, Jun 02, 2011 21:07 Antworten mit Zitat
ohne nun alles gelesen zu haben wird meist durch heuristik veruscht die beste bzw eine annehmbare Lösung für ein problem zu finden. Also nicht in jedem Fall die Beste Lösung finden sondern nur eine an der Besten kratzenden.
blucode - webdesign - Ressource - NetzwerkSim BlitzBasic 2D - BlitzMax - MaxGUI - Monkey - BlitzPlus

Hummelpups

Do, Jun 02, 2011 21:07
Antworten mit Zitat

ohne nun alles gelesen zu haben wird meist durch heuristik
veruscht die beste bzw eine annehmbare Lösung für ein problem zu finden.

Also nicht in jedem Fall die Beste Lösung finden sondern nur eine an der
Besten kratzenden.

blucode - webdesign - Ressource - NetzwerkSim
BlitzBasic 2D - BlitzMax - MaxGUI - Monkey - BlitzPlus

	das wurgel	Sa, Jun 04, 2011 4:13 Antworten mit Zitat
Zu der Sache mit dem Gehen hätte ich eine Idee, Graben und Fliegen ist schwierig, was wohl auch der Grund dafür ist, dass die KI in Worms World Party dazu zu dumm ist. Beim Gehen gibt es nicht so viele verschiedene mögliche Positionen, deshalb könnte man es vielleicht mit einer Art Netz-Struktur aus verknüpften Flächen lösen, welche rekursiv erstellt wird: 1. Zuerst wird geguckt, wie weit man von einem bestimmten Punkt aus nach rechts und links laufen kann, ohne zu springen oder weiter zu fallen, als man wieder hoch laufen kann. Dabei wird zu jeder laufbaren x-Entfernung die zugehörige Höhe gespeichert. Die KI ist nun in der Lage, zu jedem Punkt auf der blau-markierten Fläche im zweiten Bild zu laufen. 2. Jetzt wird in einer Routine überprüft, ob a) ein Sprung von irgendeinem dieser Punkte aus b) falls möglich das Übertreten einer der beiden Kanten zu einer Position führt, die nicht zu der blau-markierten Fläche gehört. 3. Falls der gefundene Punkt unbekannt ist, ruft die Funktion sich selbst mit dem gefundenen Punkt als Startpunkt auf, um die neue Fläche abzutasten. 4. Es wird eine Verzweigung vermerkt, die die Information enthält, dass von diesem Punkt zu jener Fläche gesprungen/gefallen werden kann. (Umgekehrt besteht diese Information noch nicht) Das passiert aber nur, wenn es noch keine in der Nähe befindliche Verzweigung zu der Fläche gibt, damit man jede Springmöglichkeit nicht gleich 10fach hat. 5. Die Funktion endet, wenn alle Punkte nach möglichen Verzweigungen untersucht wurden. Wenn ich keinen Denkfehler drin habe, müssten auf diese Weise die Würmer schonmal zu jeden erreichbaren Punkt kriechen könnten. Die Netze müsste man nur neu erstellen wenn etwas verändert wurde. Um es schneller zu machen, reicht es, nur jeden 5ten pixel oder so abzugehen. Ich hoffe ich konnte dir mit meinem Denkansatz weiterhelfen. edit: Och nein. Das ist peinlich. Und ärgerlich. Hab mir so viele Gedanken gemacht und alles umsonst. Viele böse Flüche.
1 ist ungefähr 3

das wurgel

Sa, Jun 04, 2011 4:13
Antworten mit Zitat

Zu der Sache mit dem Gehen hätte ich eine Idee, Graben und Fliegen ist schwierig, was wohl auch der Grund dafür ist, dass die KI in Worms World Party dazu zu dumm ist.
Beim Gehen gibt es nicht so viele verschiedene mögliche Positionen, deshalb könnte man es vielleicht mit einer Art Netz-Struktur aus verknüpften Flächen lösen, welche rekursiv erstellt wird:
user posted image

1. Zuerst wird geguckt, wie weit man von einem bestimmten Punkt aus nach rechts und links laufen kann, ohne zu springen oder weiter zu fallen, als man wieder hoch laufen kann. Dabei wird zu jeder laufbaren x-Entfernung die zugehörige Höhe gespeichert. Die KI ist nun in der Lage, zu jedem Punkt auf der blau-markierten Fläche im zweiten Bild zu laufen.

2. Jetzt wird in einer Routine überprüft, ob
a) ein Sprung von irgendeinem dieser Punkte aus
b) falls möglich das Übertreten einer der beiden Kanten
zu einer Position führt, die nicht zu der blau-markierten Fläche gehört.

3. Falls der gefundene Punkt unbekannt ist, ruft die Funktion sich selbst mit dem gefundenen Punkt als Startpunkt auf, um die neue Fläche abzutasten.

4. Es wird eine Verzweigung vermerkt, die die Information enthält, dass von diesem Punkt zu jener Fläche gesprungen/gefallen werden kann. (Umgekehrt besteht diese Information noch nicht)
Das passiert aber nur, wenn es noch keine in der Nähe befindliche Verzweigung zu der Fläche gibt, damit man jede Springmöglichkeit nicht gleich 10fach hat.

5. Die Funktion endet, wenn alle Punkte nach möglichen Verzweigungen untersucht wurden.

Wenn ich keinen Denkfehler drin habe, müssten auf diese Weise die Würmer schonmal zu jeden erreichbaren Punkt kriechen könnten. Die Netze müsste man nur neu erstellen wenn etwas verändert wurde. Um es schneller zu machen, reicht es, nur jeden 5ten pixel oder so abzugehen.

Ich hoffe ich konnte dir mit meinem Denkansatz weiterhelfen.

edit:
Och nein. Das ist peinlich. Und ärgerlich. Hab mir so viele Gedanken gemacht und alles umsonst. Viele böse Flüche.

1 ist ungefähr 3

Zuletzt bearbeitet von das wurgel am Sa, Jun 04, 2011 17:45, insgesamt einmal bearbeitet

	Xeres Moderator	Sa, Jun 04, 2011 12:30 Antworten mit Zitat
Bevor Dj$$$ den Thread wieder ausgegraben hat sind 2-3 Jahre ins Land gezogen - nur mal zur Info...
Win10 Prof.(x64)/Ubuntu 16.04\|CPU 4x3Ghz (Intel i5-4590S)\|RAM 8 GB\|GeForce GTX 960 Wie man Fragen richtig stellt \|\| "Es geht nicht" \|\| Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Xeres

Moderator

Sa, Jun 04, 2011 12:30
Antworten mit Zitat

Bevor Dj$$$ den Thread wieder ausgegraben hat sind 2-3 Jahre ins Land gezogen - nur mal zur Info...

Übersicht

BlitzMax, BlitzMax NG

Allgemein

Nach Oben

BlitzBasic Portal

Worms KI

Betreff: Worms KI

Betreff: Ich kapiere es nicht