Einführung
In meinem ersten Blog zum Thema "Pygame" - Python: Eine Einführung in pygame - habe ich kurz erklärt wie Animationen mittels pygame realisiert werden können. Auch ein fundamentales Thema, nämlich die Kollisionserkennung wurde kurz behandelt. In diesem zweiten Blog, befassen wir uns intensiv mit dem Thema "Chasing and Evading", was übersetzt heisst: Jagen und Ausweichen. Dabei geht es um zwei Objekte, die sich animiert über das Surface (Windows-Oberfläche des Spiels) bewegen. Die zwei Objekte heissen im Spielekontext Prey (Opfer/Beute) und Predator (Raubtier/Plünderer). Dabei ist der computer kontrollierte Spieler meistens der Predator und der Prey, der vom Gamer kontrollierte Spieler.
Chasing and Evading wird schon in den Kontext von Künstlicher Intelligenz gestellt, obschon im Hintergrund kein grosses "neuronales Netz" oder irgendein selbst lernender Algorithmus steckt. Die Verfolgung durch den Computer basiert eigentlich auf einem Cheat (einem Trick/Schwindel). Der Computer verfügt nämlich bei seiner Berechnung wie er den Prey einholen kann, über sämtliche Daten des Preys. In der Realität müsste aber der Predator über umfassende und kaum zu überbietende Sensoren verfügen, um ein solches Resultat zu erreichen...
Chasing/Evading
Der zugrundeliegende Algorithmus vermindert einfach die Position des Jägers zum Opfer. Bei jedem neuen Durchgang wird der Pixelabstand (oder der Teileabstand) verkleinert. Am Schluss holt so der Jäger das Opfer ein, wenn dieser schneller ist. Hindernisse oder Waffen können dies natürlich verhindern. Beim Evading (im Falle des Computers) basiert genau das Gegenteil. Die Position wird vergrössert.Wie das konkret nun aussieht, demonstrieren wir an einem kleinen Beispiel. Und zwar werden auf dem Bildschirm zwei ausgefüllte Kreise dargestellt. Der Predator veringert seinen Abstand zusehends zum Prey. Der Prey kann mit der Tastatur gesteuert werden. Das Spiel endet, wenn der Prey mit dem Predator zusammenstösst.
class Player(pygame.sprite.Sprite):
_screen = 0
MOVESPEED = 6
TOP = 1
BOTTOM = 2
RIGHT = 4
LEFT = 8
def __init__(self, color, screen):
super().__init__()
self._screen = screen
self.image = pygame.Surface([50, 50])
self.image.fill((0, 0, 9))
self.image.set_colorkey((0, 0, 0))
pygame.draw.circle(self.image, color, (25, 25), 20, 0)
self.image.convert()
self.rect = self.image.get_rect()
def setInitalPosition(self, x, y):
self.rect.centerx = x
self.rect.centery = y
def get_rect(self):
return self.rect
def draw(self, screen):
screen.blit(self.image, self.rect)
def _screenCollision(self):
area = self._screen.get_rect()
left = self.rect.left
top = self.rect.top
right = self.rect.right
bottom = self.rect.bottom
result = 0
if left <= 0:
result = Player.LEFT
elif right >= area.width:
result = Player.RIGHT
if top <= 0:
result = result + Player.TOP
elif bottom >= area.height:
result = result + Player.BOTTOM
return result
Die Klasse Player dient als Superklasse für die konkreten Klassen Predator und Prey. Diese Superklasse konstruiert den entsprechenden Kreis für die Figur und beinhaltet einige Methoden. Mit der Methode setInitialPosition wird der Figure eine Position innerhalb des Spielfeldes ganz am Anfang des Spiels zugeteilt. Die Methode draw übernimmt das Zeichen der Figur auf das Surface. Die wichtigste Methode ist _screenCollision, die wir als protected deklarieren. In ihr überprüfen wir, ob die Figur mit dem Rand der Surface zusammestösst. Je nach dem wo die Figur mit dem Screen zusammenstösst, wird eine unterschiedliche Bitmaske als Resultat zurückgegeben. Es gilt ja nicht nur die Seitenränder zu betrachten, sondern auch die Ecken (TOP/LEFT, TOP/RIGHT, BOTTOM/LEFT und BOTTOM/RIGHT).
Damit eine Figur, die in pygame als Sprite definiert werden kann, ihren Zustand verändern kann, gibt es die von der Basis-Spriteklasse vorgegebene Methode update. Sie kann hervorragend für jedes einzelne konkrete Sprite (Prey/Predator) gebraucht werden, um die Position zu verändern. Nachfolgend die konkreten Spriteklassen:
class Predator (Player):
__preyCoords = 0
def __init__(self, color, screen):
super().__init__(color, screen)
def setPreyCoordinates (self, xCoord, yCoord):
self.__preyCoords = (xCoord, yCoord)
def update(self):
if self.__preyCoords == 0:
return
ownx = self.rect.centerx
owny = self.rect.centery
x, y = self.__preyCoords
if ownx - x > 0:
if ownx - x < Player.MOVESPEED/2:
self.rect.move_ip(x-ownx, 0)
else:
self.rect.move_ip(-Player.MOVESPEED/2, 0)
elif ownx - x < 0:
if abs(ownx - x) < Player.MOVESPEED/2:
self.rect.move_ip(x-ownx, 0)
else:
self.rect.move_ip(Player.MOVESPEED / 2, 0)
if owny - y > 0:
if owny -y < Player.MOVESPEED/2:
self.rect.move_ip(0, y-owny)
else:
self.rect.move_ip(0, -Player.MOVESPEED/2)
elif owny - y < 0:
if abs(owny-y) < Player.MOVESPEED/2:
self.rect.move_ip(0, y-owny)
else:
self.rect.move_ip(0, Player.MOVESPEED/2)
class Prey (Player):
NOMOVE = 0
MOVELEFT = 1
MOVERIGHT = 2
MOVEUP = 3
MOVEDOWN = 4
_dvector = (0, 0)
def __init__(self, color, screen):
super().__init__(color, screen)
def nextMove(self, move):
if move == Prey.NOMOVE:
self._dvector = (0, 0)
return
if move == Prey.MOVEDOWN:
self._dvector = (0, Player.MOVESPEED)
elif move == Prey.MOVEUP:
self._dvector = (0, - Player.MOVESPEED)
elif move == Prey.MOVELEFT:
self._dvector = (- Player.MOVESPEED, 0)
elif move == Prey.MOVERIGHT:
self._dvector = (Player.MOVESPEED, 0)
def update(self):
collide = self._screenCollision()
cont = True
if collide & Player.LEFT:
cont = self._dvector[0] > 0 or self._dvector[1] != 0
elif collide & Player.RIGHT:
cont = self._dvector[0] < 0 or self._dvector[1] != 0
elif collide & Player.TOP:
cont = self._dvector[1] > 0 or self._dvector[0] != 0
elif collide & Player.BOTTOM:
cont = self._dvector[1] < 0 or self._dvector[0] != 0
if (collide & Player.LEFT) and (collide & Player.TOP):
cont = self._dvector[0] > 0 or self._dvector[1] > 0
elif (collide & Player.RIGHT) and (collide & Player.TOP):
cont = self._dvector[0] < 0 or self._dvector[1] > 0
elif (collide & Player.LEFT) and (collide & Player.BOTTOM):
cont = self._dvector[0] > 0 or self._dvector[1] < 0
elif (collide & Player.RIGHT) and (collide & Player.BOTTOM):
cont = self._dvector[0] < 0 or self._dvector[1] < 0
if cont:
self.rect.move_ip(self._dvector[0], self._dvector[1])
Die Klasse Prey enthält die wichtige Methode nextMove. Dieser Methode wird übergeben, wie sich der Prey nach Tastatureingabe bewegen soll. Auch die Methode update ist recht komplex, weil dort geprüft wird, ob sich der Prey an den Bildschirmrändern überhaupt bewegen darf. In Falle, dass der Kreis mit dem linken Bildschirmrand zusammenstösst, darf sich ja der Kreis nur noch nach rechts und oben/unten bewegen.
Zum Schluss noch die Klasse Game, wo das Spiel lapidar definiert ist:
import pygame, sys
from pygame.locals import *
import random
import time
class Game:
__predator = 0
__prey = 0
__windowsSurface = 0
__TEXT = "Chase and Evading - Simple"
__spriteGroup = 0
def __init__(self):
pygame.init()
self.__initWindow()
self.__displayCaptions()
self.__predator = Predator((23, 134, 85), self.__windowsSurface)
self.__prey = Prey((23, 42, 123), self.__windowsSurface)
self.__initState()
def __initWindow(self):
# Richtet das Fenster ein
self.__windowsSurface = pygame.display.set_mode((500, 400), 0, 32)
def __displayCaptions(self):
# Setzt den Titel im Fenster
pygame.display.set_caption(Game.__TEXT)
def __initState(self):
self.__prey.setInitalPosition(random.randint(25,476), random.randint(25,375))
self.__predator.setInitalPosition(random.randint(25,476), random.randint(25,375))
if self.__spriteGroup == 0:
self.__spriteGroup = pygame.sprite.Group(self.__predator)
while pygame.sprite.spritecollide(self.__prey, self.__spriteGroup, False, pygame.sprite.collide_circle):
self.__prey.setInitalPosition(random.randint(25, 476), random.randint(25, 375))
self.__predator.setInitalPosition(random.randint(25, 476), random.randint(25, 375))
return
def __detectCollision(self):
return pygame.sprite.spritecollide(self.__prey, self.__spriteGroup, True, pygame.sprite.collide_circle_ratio(0.7))
def play(self):
self.__initState()
self.__spriteGroup.draw(self.__windowsSurface)
self.__predator.setPreyCoordinates(self.__prey.get_rect().centerx, self.__prey.get_rect().centery)
self.__prey.draw(self.__windowsSurface)
pygame.display.update()
while True:
for event in pygame.event.get():
# bei Schliessen des Fensters Anwendung beenden
if event.type == QUIT:
pygame.quit()
sys.exit()
if event.type == KEYDOWN:
if event.key == K_LEFT or event.key == K_a:
self.__prey.nextMove(Prey.MOVELEFT)
if event.key == K_RIGHT or event.key == K_d:
self.__prey.nextMove(Prey.MOVERIGHT)
if event.key == K_UP or event.key == K_w:
self.__prey.nextMove(Prey.MOVEUP)
if event.key == K_DOWN or event.key == K_s:
self.__prey.nextMove(Prey.MOVEDOWN)
if event.type == KEYUP:
if event.key == K_ESCAPE:
pygame.quit()
sys.exit()
if self.__detectCollision():
print("Game Over!")
self.__spriteGroup.update()
self.__predator.setPreyCoordinates(self.__prey.get_rect().centerx, self.__prey.get_rect().centery)
self.__prey.update()
self.__spriteGroup.draw(self.__windowsSurface)
self.__prey.draw(self.__windowsSurface)
time.sleep(0.05)
pygame.display.flip()
self.__windowsSurface.fill([0, 0, 0])
game = Game()
game.play()
Interception Algorithmus
Mit obigen "Line of sight" Algorithmus für das Vermindern der Position von Prey und Predator ist schon viel erreicht, aber die Bewegungsabläufe des Predators könnten besser sein.Mit dem Interception Algorithmus wird ein anderer Algorithmus im Bereich "Chasing and Evading" vorgestellt. Line of sight heisst übrigens übersetzt Sichtlinie und Interception kann mit Abfangen übersetzt werden.
Die Mathematik dahinter:
Grundsätzlich braucht der Prey und der Predator eine Zeit T, um dann zusammenzustossen. Was störend ist, ist ve, weil der Geschwindigkeitsvektor des Predators (e für enemy) nur betragsmässig bekannt ist.
Aus der Vektorrechnung ist bekannt, dass folgendes gilt:
a) y(T) = x + vp*T
b) y(T) = |ve|*ee*T
Die bekannten Grösse in diesen zwei Gleichungen sind: vp, x und |ve|
ee ist ein Einheitsvektor in Richtung y vom Predator aus gesehen.
Ein Einheitsvektor hat für einen Winkel theta=t die Darstellung:(cost, sint)
=> ve = |ve|*(cost, sint)
Damit ergeben sich vier Komponentengleichungen:
y1 = |ve|*cost*T
y2 = |ve|*sint*T
y1 = x1 + vp1*T
y2 = x2 + vp2"T
Wir können dann für T folgende Formeln ermitteln:
i) T = -x2/vp2*(1-|ve|*sint/vp2)
ii) T = -x1/vp1*(1-|ve|*cost/vp1)
Wie eine Dimensionsanalyse zeigt, erhalten wir tatsächlich eine Zeit.
Es liegt nun nahe, diese zwei Gleichungen gleichzusetzen. Das ist aber für unsere Zwecke ungeeignet, weil die Gleichungen analytisch nicht lösbar sind.Wir gehen deshalb einen anderen Weg und würfeln theta als Zufallszahl im Bereich [0, 2Pi). Die Gleichungen i) und ii) werden so unterschiedliche Resultat zurückgeben. Die absolute Differenz bezeichnen wir mit dT=abs(T1-T2).
Wir wählen nun einen Winkel kleiner als theta und einen Winkel grösser als theta und berechnen wiederum die absolute Differenz dT1 und dT2.
Wenn nun dT1 < min (dT ,dT2) ist, so wissen wir, dass theta kleiner als das ursprüngliche theta zu wählen ist. Analoge Überlegungen kann man sich für dT2 überlegen.
Damit kann ein Algorithmus zur Lösung von i) und ii) entwickelt werden. Ohne weiter gross auf den Algorithmus einzugehen, verweisen wir auf den nachfolgenden Code, wo der Algorithmus implementiert wurde. Jedenfalls erhalten wir so ein theta und damit ein T zurück, Damit wissen wir im nächsten Zeitschritt, wie der Predator bewegt werden sollte. Ändert die Richtung von Prey, so muss dementsprechend T und theta wiederum berechnet werden.
Hinweis: in i) und ii) wurde vorausgesetzt, dass vp2 und vp1 nicht 0 sein dürfen. Das kann aber der Fall sein. Auch wenn Komponenten von x 0 sind müssen diese Fälle separat behandelt werden. Dabei ergeben sich allerdings dann geschlossene Lösungen, die nicht über einen Algorithmus behandelt werden müssen.
<<to be continued>>
Keine Kommentare:
Kommentar veröffentlichen