KI für Dummies

[DieFüchsin]

Nur eine kurze Frage: kann man mir die Frage: "Wie bestimmt eine KI den für sie kürzesten Weg zu einem Punkt?" erklären ohne dass ich Informatikstudent bin geschweige denn irgendetwas über die Funktionsweise von KIs weiß?

[flob]

Dazu braucht man keine KI, sondern nur einen guten Algorithmus. Das geht dann allerdings schon wieder sehr stark in Richtung Informatik bzw. Mathematik. Falls der kürzeste Weg also nicht grundsätzlich nur aus sehr wenigen Alternativen bestimmt werden muss, musst du berücksichtigen, wie lange der Algorithmus für sehr große Werte (Wegmöglichkeiten) braucht und wieviel Speicher er benötigt. Dafür wäre ein bisschen Ahnung von Mathematik und Algorithmen bzw. Programmieren aber schon wichtig, du solltest also entweder auf fertige Lösungen zurückgreifen, dir helfen lassen oder es sein lassen.

Eine interessante Visualisierung von Pathfinding-Algorithmen (das Java-Applet unten, einfach ein bisschen rumklicken): http://www.stefan-baur.de/priv.studies. ... minar.html

Eine kleine Einführung:
http://de.wikipedia.org/wiki/Pathfinding
http://de.wikipedia.org/wiki/K%C3%BCrzester_Pfad
http://de.wikipedia.org/wiki/A%2A
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
http://de.wikipedia.org/wiki/Kategorie: ... lgorithmus

[DieFüchsin]

Vom Programmieren hab ich schon ein wenig Ahnung. Danke erstmal für die Links, die schau ich mir bei Gelegenheit an. Wollte einfach erstmal nur wissen, ob man das Funktionieren von KIs auch verstehen kann, wenn man kein Superinformatiker ist.

[DasJan]

Mit KI hat das eigentlich nichts zu tun. Die Antwort auf deine Frage hängt stark davon ab, was genau du mit "kürzester Weg zu einem Punkt" meinst. Wo genau bewegst du dich? In einem Graphen (z.B. Straßennetz) dürfte Dijkstra der Algorithmus deiner Wahl sein. Wenn du dich frei innerhalb eines Polygons bewegen kannst (evtl. mit Löchern) sieht das schon etwas anders aus. Noch anders sieht es aus, wenn du z.B. einen Roboter durch ein Terrain bewegen musst, dass der Roboter erst noch selbst erkunden muss.

Das Jan

[DieFüchsin]

Hm sorry dass ich meine Frage so unbedacht ohne große Vorüberlegung gestellt hab.

Die Sache mit dem Graphen sieht ganz passend aus, danke dir.

[DieFüchsin]

So, nun hab ich mir die Erklärungen zu den verschiedenen Algorithmen mal durchgelesen und einigermaßen verstanden (glaub ich ).

Nun stellt sich mir aber die Frage, wie ich dem Computer - in diesem Falle dem AGS-Programm - "beibringe", wie das "Spielfeld" aussieht. Also sprich wo welche Knotenpunkte liegen und welcher mit welchem verbunden ist.

Kann mir jemand sagen, wie das zu bewerkstelligen ist?

[DasJan]

Wie sieht denn konkret deine Anwendung aus?

Das Jan

[DieFüchsin]

Also ich möchte in meinem Spiel eine Art Minispiel einbringen.
Gespielt wird auf einem Spielfeld, welches dieses Bild als Grundlage hat:


Man würfelt und kann dann eine entsprechende Anzahl Felder gehen. Danach würfelt der vom Spiel gesteuerte Verfolger.
Ich möchte erreichen, dass der Verfolger stets das Feld der fliehenden Spielfigur anpeilt und zu erreichen versucht.

[DasJan]

OK, du brauchst dann einen Knoten pro "grauem Plättchen" und zwei Knoten sind dann miteinander verbunden, wenn man zwischen den Plättchen hin- und herlaufen kann.

Ich weiß nicht mehr genau über die Fähigkeiten von AGS Bescheid, aber ich meine, das unterstützt inzwischen objektorientierte Programmierung, oder? Du bräuchtest dann ein "Knotenobjekt" für jeden Knoten und ein "Kantenobjekt" für jede Verbindung zwischen zwei Knoten. Ein Kantenobjekt enthält dann Pointer auf die zwei Knotenobjekte, die es verbindet, und ein Knotenobjekt enthält eine Liste mit Pointern auf die Kantenobjekte, die von diesem Knoten ausgehen.

Wenn du in AGS nicht in aller Allgemeinheit eine Graph-Klasse implementieren willst, kannst du auch ausnutzen, dass du einen ganz bestimmten Graphen betrachtest, der sich während des Spiels nicht ändert. Dann könntest du außerhalb von AGS zum Beispiel die "All Pairs Shortest Path"-Matrix berechnen. Die enthält eine Zeile und eine Spalte für jeden Knoten im Graphen. Im Eintrag (v, w) steht dann der Knoten v', für den gilt: Auf dem kürzesten Weg von v nach w ist v' der Knoten, der auf v folgt. Die Matrix könntest du dann einfach als konstante Matrix in den AGS-Code kopieren und da bei Bedarf nachschlagen. Das funktioniert aber natürlich nur, wenn sich dein Graph nicht ändert.

Jan

P.S.: Gerade erst gesehen: Cooler Escher-Effekt.

[DieFüchsin]

OK, du brauchst dann einen Knoten pro "grauem Plättchen" und zwei Knoten sind dann miteinander verbunden, wenn man zwischen den Plättchen hin- und herlaufen kann.

Ja, soweit dachte ich auch schon. Auf einem Plan habe ich mir alle "Knoten", also die Koordinaten auf den grauen Feldern notiert und mit den entsprechenden Kanten verbunden - allerdings nur auf dem Papier.

Ich weiß nicht mehr genau über die Fähigkeiten von AGS Bescheid, aber ich meine, das unterstützt inzwischen objektorientierte Programmierung, oder?

Genau das ist mein Problem: dass mein Wissen und meine Programmierfertigkeiten dafür nicht ausreichen.
Kannst du mir vielleicht einen Tipp geben, wo ich mich darüber schlau machen kann?

Wenn du in AGS nicht in aller Allgemeinheit eine Graph-Klasse implementieren willst, kannst du auch ausnutzen, dass du einen ganz bestimmten Graphen betrachtest, der sich während des Spiels nicht ändert. Dann könntest du außerhalb von AGS zum Beispiel die "All Pairs Shortest Path"-Matrix berechnen. Die enthält eine Zeile und eine Spalte für jeden Knoten im Graphen. Im Eintrag (v, w) steht dann der Knoten v', für den gilt: Auf dem kürzesten Weg von v nach w ist v' der Knoten, der auf v folgt. Die Matrix könntest du dann einfach als konstante Matrix in den AGS-Code kopieren und da bei Bedarf nachschlagen. Das funktioniert aber natürlich nur, wenn sich dein Graph nicht ändert.

Wie meinst du das? Der Graph ist ja sozusagen das Spielfeld, oder?
Nun, das bleibt gleicht, ja - aber Start- und Zielpunkt variieren.

Wie kann ich denn außerhalb von AGS etwas ausrechnen? Mit einem Hilfsprogramm, welches ich aus AGS aufrufe? Oder meinst du, dass ich die Tabelle vorher per Hand anlegen muss? (Immerhin geht es um über hundert Felder.)

P.S.: Gerade erst gesehen: Cooler Escher-Effekt.

Jepp, ist aber nicht mein Werk. Ich habe mich der unendlichen Weisheit des Internets bedient ...

[DasJan]

Kannst du mir vielleicht einen Tipp geben, wo ich mich darüber schlau machen kann?

Bei AGS selbst kennst du dich vermutlich besser aus, was es da für Dokumentationen / Tutorials / Wikis gibt.

Die erste "externe" Lösung, auf die ich gerade gestoßen bin, ist die hier:
http://px.sklar.com/code.html/id=1129

Wenn man das auf einen PHP-fähigen Webserver lädt und fw_example.php öffnet, sieht das so aus:
http://www.dasjan.de/temp/fw_example.php

Wenn du mir deinen Graphen in der Form schickst, wie er in fw_example.php steht, kann ich das auch bei mir hochladen, falls du keinen Webspace hast. Die Zahlen sind quasi die Längen der Kanten: Von a nach b sind es im Beispiel 15 Kilometer, von b nach d nur 2 Kilometer. Bei dir haben alle Kanten dieselbe Länge, also müssten dann in der Graph-Matrix nur Nullen (keine Kante) oder Einsen (Kante) stehen.

Die untere Matrix ("Predecessors") ist die, die für dich interessant ist. Angenommen, du willst von d nach c. Dann schaust du in der Predecessor-Matrix in Zeile "d" und der Spalte "c": Da steht eine 1. Die 1 bedeutet hier "b" (die Knoten sind nummeriert, also a=0, b=1, c=2...). Also: Auf dem kürzesten Weg von d nach c ist b der vorletzte Knoten.

So geht's dann weiter. Jetzt interessierst du dich für den kürzesten Weg von d nach b. Zeil "d", Spalte "b": Da steht eine 3 (= d). Also: Auf dem kürzesten Weg von d nach b ist d der vorletzte Knoten. Das ist aber auch dein Startknoten, also ist dein Gesamtweg jetzt fertig: d -> b -> c.

Da sich dein Spielbrett nicht verändert, ändert sich auch die Matrix nicht. Die kannst du also dann einfach in den AGS-Code kopieren und entsprechend auslesen.

Das Jan

[john_doe]

Diesen (englischen) Artikel finde ich auch äußerst hilfreich für diese Problematik: http://shatteredrealmproductions.com/Tw ... inding.htm
Es geht dort auch darum, wie man die angesprochene Matrix erstellt. Es ist auch etwas C-Quellcode dabei.

[Rocco]

Ohne jetzt die genaue Spielmechanik zu kennen die du beabsichtigst, ein paar Ideen zu den einzelnen Problemen:

Für die Suche nach dem schnellsten und direktesten Weg, brauchst du ja nur die interne AGS-Pathfinding Mechanik zu bemühen,
genauso wie in jedem normalen Adventure.

Du zeichnest einfach überall walkable areas ein und wenn der spieler auf einem punkt steht,
schickst du einfach den computerspieler zu den koordinaten wo der spieler steht.
CPU.Walk( player.x, player.y, eBlock, eWalkableAreas);
damit geht der Cpu player einmal automatisch auf den kürzesten Weg Richtung Computer Spieler.

Das andere Problem ist natürlich das Spielfeld, da gibts mehrere Möglichkeiten.
Auf jeden Fall wirst du Arrays brauchen.
Du könntest in einem 2D Array das gesamte Spielfeld "simulieren".
Ausserdem könntest du in einem anderen Array sämtliche Koordinaten der begehbaren Felder einlagern.
In diesen 2 Arrays könntest du das ganze Spiel simulieren und dann aufs sichtbare Spielfeld übertragen.


Soweit ich weiss unterstützt aber AGS bis jetzt nur 1 dimensionale Array, aber da kann man sich weiterhelfen:
Hab hier ein Modul gefunden, dass multidimensionale Arrays unterstützt. - http://www.bigbluecup.com/yabb/index.php?topic=32147.0

Bevors zu sehr ins Detail geht, noch ein paar Fragen:
Wie soll das Spiel im Detail funktionieren?
Was passiert nachdem der Spieler gewürfelt hat?

[DasJan]

CPU.Walk( player.x, player.y, eBlock, eWalkableAreas);

Das bewegt etwas über den Bildschirm, aber es berechnet nicht, auf welchem Weg der Computer nun zum Spieler gehen muss. Die Würfel-Distanzen zwischen den Feldern entspricht ja nicht der Pixelzahl.

Das Jan

[Rocco]

naja ich denke schon dass der computer spieler in zumindest geschätzten 97% den kürzesten weg zum spieler einschlagen wird.
es gibt wahrscheinlich ein paar grenzfälle wo das nicht der fall ist, aber die grundsätzliche wegfindung wäre damit wohl im akzeptablem umfang gelöst,
ohne einen eigenen pathfinding algo schreiben zu müssen.
mit dieser methode, könnte man beispielsweise berechnen auf welche felder der cpu theoretisch ziehen könnte, anhand der würfelanzahl.
und auf diesen (in frage kommenden) feldern könnte man dann regions freischalten, die den cpu stoppen sobald er eines der Felder betritt.


aber klar gibt es verschiedene methoden um zum ziel zu kommen.
um statusarrays die das grundsätzliche spiel simulieren, wird man ohnehin nicht herumkommen.
da ist wohl dann auch nicht mehr so extrem viel aufwand, einen eigenen pathfinding algo zu implementieren
und den char dann von feld zu feld zu schicken.