Softwareentwicklung für Moderne Computerspiele und Künstliche Intelligenz

Softwareentwicklung für Moderne Computerspiele und Künstliche Intelligenz

Naturwissenschaftliches Kolloquium am Gymnasium Norf

Marius Politze

[email protected]

Rechen- und Kommunikationszentrum der RWTH Aachen

Über Mich I

Quelle: http://theculinarycook.com/wp-content/uploads/2012/04/grilled-steak.jpg
Quelle: http://ufischerhirchert.hs-harz.de/Hochfrequenztechnik.htm
Quelle: Alexander Rettke
Quelle: http://www.flickr.com/photos/veganfeast/4358515562/in/photostream/
Quelle: http://www.flickr.com/photos/veganfeast/4358515562/in/photostream/
Quelle: http://www.flickr.com/photos/veganfeast/4358515562/in/photostream/
Quelle: http://upload.wikimedia.org/wikipedia/commons/thumb/6/6e/HTML5-logo.svg/500px-HTML5-logo.svg.png

Über Mich II

Abitur

Gymnasium Norf, 2006

Studium: Computational Engineering Science

RWTH Aachen, 2006 - 2008

Duales Studium: Scientific Programming, B.Sc.
Ausbildung zum MATSE

FH Aachen / RWTH Aachen, 2008 - 2010

Quelle: http://www.rz.rwth-aachen.de

Über Mich III

Quelle: http://www.maastrichtuniversity.nl/web/Schools/DKE/Thema/ContactAndVisitDKE.htm

Studium: Künstliche Intelligenz, M.Sc.

Universität Maastricht, 2010 - 2012

Projektkoordinator, Entwickler und Dozent für Skriptsprachen und C#

Rechen- und Kommunikationszentrum der RWTH Aachen, 2010 - 2012

Wissenschaftlicher Mitarbeiter im Bereich eLearning

Rechen- und Kommunikationszentrum der RWTH Aachen, seit 2012

Quelle: http://www.rz.rwth-aachen.de/ca/k/omk/?lang=en

Übersicht

Quelle: http://www.upwallpapers.net/mountain-road-landscape/

Was sind moderne Computerspiele?

Beispiele und
Einsatzgebiete von KI

Womit beschäftigt sich KI?

Verschiedene Disziplinen und
Beispiel: Wegsuche

Wie wird Software entwickelt?

Methoden und
die Anwendung im Alltag

Künstliche Intelligenz

Suchen & Finden

  • Data Mining
  • Text Mining
  • Optimierung
Quelle: http://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Clustering/Expectation_Maximization_(EM)
Quelle: http://www.jaychakravarty.com/?p=75
Quelle: http://www.oellermann.com/node/70

Spiele

  • Klassische
  • Moderne
Quelle: http://de.wiktionary.org/wiki/Datei:Go_board.jpg
Quelle: http://www.designboom.com/technology/nao-programmable-humanoid-robot/
Quelle: http://en.wikipedia.org/wiki/Nash_equilibrium

Autonome Agenten

  • Robotik
  • Kollaboration & Kommunikation

Was sind moderne Computerspiele? I

Pac-Man (1980)
Tetris (1984)
Commander Keen (1990)
Super Mario (1985)
Pong (1972)
Metroid (1986)

Was sind moderne Computerspiele? II

Sonic the Hedgehog (1991)
Pokemon (1996)
Gran Tourismo (1998)
Mortal Comabat (1992)
Doom (1993)
Starcraft (1997)
Diablo (1996)
Half-Life (1998)

Was sind moderne Computerspiele? III

Die Sims (2000)
Angry Birds (2009)
Starcraft 2 (2010)
Warcraft III (2002)
Diablo 3 (2012)
World of Warcraft (2004)
Farmville (2009)
Skyrim (2011)

Wegsuche ist wichtig...


Quelle: YouTube, AI-Blog

Wegsuche Problemstellung

auch Wegfindung oder Pathfinding

  • Gesucht ist ein Algorithmus der:
  • eine (die kürzeste) Verbindung zwischen zwei Punken A und B findet.
  • A und B sind dabei i.d.R. nur indirekt verbunden.
  • Sonderfall: A und B sind gar nicht miteinander verbunden.
Quelle: http://www.ai-blog.net/archives/000152.html

Beispiel

Bewegungsrichtung

  • L, R, U, D
  • (immer in dieser Reihenfolge)

Abstände

  • Manhatten
  • Euklid

Drei Algorithmen

  • Bugging (Blind)
  • Tiefensuche (Blind)
  • Breitensuche (Blind)
  • A*

Bugging Algorithmus

  1. Solange nicht am Ziel:
  2. Laufe immer gerade aus, bis zur nächsten Wand.
  3. Wähle an der Wand die erste freie Richtung aus L, R, U, D
  4. Gibt es eine freie Richtung, die bis jetzt noch nicht abgelaufen ist geht zu 1.
  5. Sonst gehe zurück zur letzten Entscheidung und suche die nächste freie Richtung.

Bugging Beispiel

Step

Bugging Zusammenfassung

Pro

  • Blind: Ja
  • Unbekannte Karten: Ja
  • Speichernutzung: Gering

Contra

  • Kürzester Weg: Nein
  • Geschwindigkeit: Langsam
  • Implementierung: Einfach aber Fehleranfällig

Anwendungsgebiete in der KI

Bugging eignet sich insbesondere für unbekannte Karten. Der Algorithmus ist in der Robotik beliebt zum Erkunden von Arealen.

Tiefensuche Algorithmus

  1. Solange nicht am Ziel:
  2. Markiere das aktuelle Feld als besucht
  3. Wähle nach jedem Schritt die nächste freie Richtung aus L, R, U, D
  4. Gibt es noch eine freie Richtung, gehe einen Schritt in die Richtung, weiter mit 1.
  5. Sonst gehe einen Schritt zurück und suche die nächste freie Richtung.

Tiefensuche Beispiel

Step

Tiefensuche Zusammenfassung

Pro

  • Blind: Ja
  • Unbekannte Karten: Ja
  • Speichernutzung: Gering
  • Implementierung: Einfach

Contra

  • Kürzester Weg: Nein
  • Geschwindigkeit: Sehr Langsam

Anwendungsgebiete in der KI

Tiefensuche wird nur sehr selten verwendet. Die Wahrsscheinlichkeit sich "zu verlaufen" ist zu groß.

Breitensuche Algorithmus

  1. Solange nicht am Ziel:
  2. Markiere das aktuelle Feld als besucht
  3. Merke dir alle angrenzenden, freien Felder L, R, U, D
  4. Gehe zum Feld, das am längsten vorgemerk ist, weiter mit 1.

Breitensuche Beispiel

Step

Breitensuche Zusammenfassung

Pro

  • Blind: Ja
  • Implementierung: Einfach
  • Kürzester Weg: Ja

Contra

  • Speichernutzung: Hoch
  • Unbekannte Karten: Nein
  • Geschwindigkeit: Sehr Langsam

Anwendungsgebiete in der KI

Breitensuche wird nur sehr selten verwendet. Der Algorithmus benötogt i.d.R. zu viel Speicher.

A* Algorithmus

  1. Solange nicht am Ziel:
  2. Markiere das aktuelle Feld als besucht
  3. Merke dir alle angrenzenden, freien Felder L, R, U, D
  4. Merke dir zu den Feldern:
    • Distanz: Wie weit war es bis hier?
    • Schätzung: Wie weit ist es mindestens noch bis zum Ziel? (Heuristik)
  5. Gehe zum Feld mit der kleinsten Summe aus Distanz und Schätzung

A* Beispiel: Manhattan Distanz

Step

A* Beispiel: Diagonal Distanz

Step

A* Beispiel Euklidische Distanz

Step

A* Zusammenfassung

Pro

  • Kürzester Weg: Ja
  • Speichernutzung: Mittel
  • Implementierung: wenig Fehlerquellen

Contra

  • Blind: Nein
  • Unbekannte Karten: Nein
  • Geschwindigkeit: Mittel

Anwendungsgebiete in der KI

A* ist der quasi standard Algorithmus zur Wegsuche für Navigation auf bekannten Karten.

Durch Anpassungen an der Heuristik können die Eigenschaften von A* gesteuert werden:

  • H(n)=0, A* wird zum Dijkstra-Algorithmus
  • H(n)<=reale Distanz, A* liefert garantiert den kürzesten Pfad
  • H(n)=reale Distanz, A* durchsucht nur Knoten, die zum kürzesten Pfad gehören
  • H(n)>reale Distanz, Der kürzeste Pfad ist nicht mehr garantiert
  • H(n)=∞, A* wird zur Breitensuche

Warum is Wegsuche so schwer? I

  • Moderne Spiele sind häufig nicht so "eckig"
  • 3D Welten machen die Suche komplizierter
  • Dynamische Objekte
  • Der Kürzeste Weg ist nicht immer der beste Weg
  • Koordination mehrerer Bewegungen, halten von Formationen

Warum is Wegsuche so schwer? II

Andere Parkettierungen

Warum is Wegsuche so schwer? II

Auch in Blockwelten gibt es schöne Pfade

GraphenEin anderes Modell für Wegsuche

Statt gleichförmiger Flächen werden einzelne Wegpunkte miteinander verbunden
Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten, die die Knoten verbinden

Navigationsgitter

In einem Navigationsgitter werden aneinander grenzende Wegpunkte zu konvexen Polygonen zusammengefasst
Alle Punkte innerhalb eines konvexen Polygons lassen sich mitenander verbinden, sodass die Verbindung komplett im Polygon liegt.

Software Entwicklung

Organisieren & Planen

  • Modellierung
  • Algorithmen
  • Anforderungen
Quelle: http://www.executiveboard.com/towergroup-blog/making-the-case-for-customer-experience-technology/#more-1268
Quelle: http://de.wikipedia.org/wiki/Gantt-Diagramm
Quelle: http://en.wikipedia.org/wiki/Scrum_(development)

Support

  • Qualität
  • Wartbarkeit
  • Testbarkeit
Quelle: http://www.iqualityconcepts.com/testing.html
Quelle: http://en.wikipedia.org/wiki/Entity%E2%80%93relationship_model
Quelle: http://de.wikipedia.org/wiki/Microsoft_Visual_Studio

Implementieren

  • Programmiersprachen
  • Datenbanken

Wozu Planen?

  • Häufig weiß nicht mal der Kunde, was er haben möchte
  • Planung von Mitarbeitern und Ressourcen
  • Kostenkalkulation
  • Wiederverwendbarkeit
  • Finden der Steakholder und der "Betroffenen" im Projektumfeld
Quelle: http://www.projectcartoon.com/

ProgrammierungTeure Fehler: Mars Climate Orbiter (1999), Ariane 5 (1996)

Quelle: http://de.wikipedia.org/wiki/Mars_Climate_Orbiter
Quelle: http://www.dlr.de/DesktopDefault.aspx/tabid-4836/8021_read-26026/gallery-1/gallery_read-Image.1.16543/

ProgrammierungAus dem Handbuch der PDP-8 (1972)

Quelle: http://www.rz.rwth-aachen.de/global/show_document.asp?id=aaaaaaaaaaciyvl
Quelle: http://www.projectcartoon.com/

Vorgehensmodelle IWasserfallmodell ca. 1970

Die Entwicklung eines Programms wird in einzelne Schritte unterteilt:

Die Schritte werden einfach nacheinander Abgearbeitet.

Quelle: http://www.projectcartoon.com/

Vorgehensmodelle IIScrum ca. 2003

Statt der Entwicklungsphasen werden Aktivitäten bestimmt.

Die Aktivitäten werden während des Projekts immer wiederholt. Die genauen Aufgaben werden erst während des Projekts definiert.

Quelle: http://www.projectcartoon.com/

ProgrammierungVerschärfung der Probleme

  • Die Komplexität von Programmen nimmt ständig zu
  • Umfang und Lebensdauer nehmen zu
  • Neue Anwendungen werden für den Rechnereinsatz erschlossen
  • Immer mehr Entwickler sind mit der Pflege von Altsystemen beschäftigt
  • Die Wirtschaft aller industrialisierten Länder hängt von Software ab
  • Immer mehr Systeme werden durch Software gesteuert
Quelle: http://www.projectcartoon.com/

Vielen Dank für die Aufmerksamkeit

Vielen Dank für die Aufmerksamkeit!

Zum Weiterlesen...

Fork me on GitHub

Bonus


Quelle: YouTube, AI-Blog

Bonus


Quelle: YouTube