Nur die wenigsten Algorithmen können an einem Stück in eine leeres Dokument getippt werden und funktionieren sofort. Weitaus häufiger tritt der Fall auf, dass man Debuggen muss. Dabei ist es unglaublich wichtig, dass man sich selbst entsprechende Debug-Ausgabe anlegt, mit welchen man erkennt, was genau schief gelaufen ist.
Die Vorstellungskraft reicht für den eigenen Algorithmus meist aus, um daraus auf Fehler schließen zu können. Arbeitet man längere Zeit nicht an einem Algorithmus oder möchte man für einen Kollegen etwas visualisieren oder auf Konferenzen vortragen, so sind Debug-Ausgaben oder Kommentare definitiv nicht mehr ausreichend, um zu beschreiben, was der Algorithmus eigentlich tut.
Jetzt kommen Grafiken in’s Spiel, die einen Verlauf einer Größe oder ähnliches darstellen können. Doch was ist, wenn auch das nicht sehr anschaulich ist?
Als Beispiel soll eine Bahnplanung (auch Path-Planning) genutzt werden. Ein Algorithmus also, der von einem Start zu einem Zielpunkt (mit Hindernissen auf dem Weg) einen optimalen Pfad berechnet. Ein populärer Bahnplanungs-Algorithmus ist der A*.
A* Path Planning in Blender
Der Algorithmus wird sehr gut im Udacity CS373 Kurs erläutert, sodass darauf an dieser Stelle verzichtet werden kann.
httpvh://www.youtube.com/watch?v=lxCCtgHk5Vs
In Python würde die Definition des Grids folgendermaßen aussehen:
[python]
grid = [[0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 1, 0, 1, 1, 1, 1],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0]]
[/python]
Der A*-Algorithmus in Python implementiert könnte beispielsweise so aussehen:
[python]
delta = [[-1, 0 ], # go up
[ 0, -1], # go left
[ 1, 0 ], # go down
[ 0, 1 ]] # go right
delta_name = [‚^‘, ‚<‚, ‚v‘, ‚>‘]
cost = 1
# A* Algorithmus
def search():
closed = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
closed[init[0]][init[1]] = 1
expand = [[-1 for row in range(len(grid[0]))] for col in range(len(grid))]
action = [[-1 for row in range(len(grid[0]))] for col in range(len(grid))]
x = init[0]
y = init[1]
g = 0
h = heuristic[x][y]
f = g+h
open = [[f, g, x, y]]
found = False # flag that is set when search is complete
resign = False # flag set if we can’t find expand
count = 0
while not found and not resign:
if len(open) == 0:
resign = True
return "Fail"
else:
open.sort()
open.reverse()
next = open.pop()
x = next[2]
y = next[3]
g = next[1]
f = next[0]
expand[x][y] = count
count += 1
if x == goal[0] and y == goal[1]:
found = True
else:
for i in range(len(delta)):
x2 = x + delta[i][0]
y2 = y + delta[i][1]
if x2 >= 0 and x2 < len(grid) and y2 >=0 and y2 < len(grid[0]):
if closed[x2][y2] == 0 and grid[x2][y2] == 0:
g2 = g + cost
f2 = g2 + heuristic[x2][y2]
open.append([f2, g2, x2, y2])
closed[x2][y2] = 1
# Memorize the sucessfull action for path planning
action[x2][y2] = i
print(‚\nA* Result:‘)
for i in range(len(expand)):
print(expand[i])
[/python]
Wie bereits angedeutet: Es ist schwer sich vorzustellen, was dabei passiert. Python Entwickler greifen zur Visualisierung oft zu PyGames. PyGames ist, wie der Name schon sagt, eher zur Spieleentwicklung gedacht, somit wird viel Overhead benötigt, um eine Animation zum laufen zu bekommen.
Blender
Blender ist eine OpenSource Software, welche lediglich 50MB groß und ohne Installation zu starten ist. Blender ist für alle gängigen Betriebssysteme erhältlich und wird durch eine aktive Community begleitet. Diese Software ist vorrangig zur Animation und Erstellung von 3D Objekten sowie zum Rendering erstellt worden, hat aber unzählige andere Anwendungsgebiete, welche ebenfalls interessant sind. Unter anderem das so genannte „Scripting“.
Scripting erlaubt es, Python Code direkt in Blender auszuführen. Somit kann ein Algorithmus in einer Blender Datei integriert werden. Nach Import von bpy kann jede Blender Schaltfläche, Objekt oder sonstige Einstellung über ein Python-Skript angesprochen werden.
Das eingangs definierte „Grid“ wird somit im Handumdrehen zu einem 3D Objekt:
[python]
import bpy
grid = [[0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 1, 0, 1, 1, 1, 1],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0]]
init = [0, 0]
goal = [len(grid)-1, len(grid[0])-1]
def creategrid(grid,init,goal):
# Grid löschen
bpy.ops.object.select_by_type(type=’MESH‘)
bpy.ops.object.delete(use_global=False)
for row in range(len(grid)):
for col in range(len(grid[0])):
#print(grid[row][col])
if grid[row][col]==0:
# wenn 0 in grid dan Ebene
bpy.ops.mesh.primitive_plane_add(location=(row,col,0), radius=.5)
elif grid[row][col] == 1:
# wenn 1 in grid dann Würfel
bpy.ops.mesh.primitive_cube_add(location=(row,col,.5), radius=.5)
else:
print(‚Grid nur 0 oder 1‘)
print(‚Grid erstellt‘)
creategrid(grid,init,goal)
[/python]
Der A* Algorithmus kann ebenfalls als def() in das Python Script in Blender eingefügt werden. Es ist noch eine Heuristic notwendig, welche sich zum Beispiel aus der euklidischen Distanz zum Ziel ergibt und für jede „Zelle“ des Grid berechnet wird.
[python]
def calcheuristic(grid,goal):
for row in range(len(grid)):
for col in range(len(grid[0])):
# Euklidische Distanz für jede Zelle zum Ziel berechnen
dist=((row-goal[0])**2+(col-goal[1])**2)**(1/2)
heuristic[row][col]=dist
for i in range(len(heuristic)):
print(heuristic[i])
return heuristic
[/python]
Nun kann der A*-Algorithmus die Planung des optimalen Pfades von Start zum Ziel übernehmen. Es wird eine so genannte Policy berechnet, welche als Debug-Ausgabe so aussieht:
[python]
Policy (Path):
[‚v‘, ‚ ‚, ‚ ‚, ‚ ‚, ‚ ‚, ‚ ‚, ‚ ‚, ‚ ‚]
[‚v‘, ‚ ‚, ‚>‘, ‚>‘, ‚v‘, ‚ ‚, ‚ ‚, ‚ ‚]
[‚v‘, ‚ ‚, ‚^‘, ‚ ‚, ‚v‘, ‚ ‚, ‚ ‚, ‚ ‚]
[‚v‘, ‚ ‚, ‚^‘, ‚ ‚, ‚v‘, ‚ ‚, ‚ ‚, ‚ ‚]
[‚>‘, ‚>‘, ‚^‘, ‚ ‚, ‚>‘, ‚>‘, ‚>‘, ‚*‘]
[/python]
Mit dem Ergebnis der Pfadplanung kann nun zum Beispiel Suzanne (der Affe in Blender) animiert werden.
Animation von Objekten
[python]
# Animation von Suzanne berechnen
def move(grid, policy, init, goal):
x = init[0]
y = init[1]
frame = 1
# Add Suzanne, the monkey
bpy.ops.mesh.primitive_monkey_add(radius=0.3, location=(x, y, .3), rotation=(0, 0, 90/180*pi))
monkey = bpy.context.object
while x != goal[0] or y != goal[1]:
# For Animation purpose
frame += 5
monkey.keyframe_insert(data_path="location", frame=frame)
monkey.keyframe_insert(data_path="rotation_euler", frame=frame)
if policy[x][y]=='<‚:
monkey.rotation_euler[2] = 0/180*pi
frame += 1
monkey.keyframe_insert(data_path="rotation_euler", frame=frame)
monkey.location[1] -= 1
y-=1
elif policy[x][y]==‘>‘:
monkey.rotation_euler[2] = 180/180*pi
frame += 1
monkey.keyframe_insert(data_path="rotation_euler", frame=frame)
monkey.location[1] += 1
y+=1
elif policy[x][y]==’^‘:
monkey.rotation_euler[2] = 270/180*pi
frame += 1
monkey.keyframe_insert(data_path="rotation_euler", frame=frame)
monkey.location[0] -= 1
x-=1
elif policy[x][y]==’v‘:
monkey.rotation_euler[2] = 90/180*pi
frame += 1
monkey.keyframe_insert(data_path="rotation_euler", frame=frame)
monkey.location[0] += 1
x+=1
# Goal Position
frame += 5
monkey.keyframe_insert(data_path="location", frame=frame)
monkey.keyframe_insert(data_path="rotation_euler", frame=frame)
[/python]
Dabei werden die Positionen des Objekts berechnet und für diese „Keyframes“ eingefügt. Die Bewegung zwischen den diskreten Punkten wird von Blender interpoliert, wodurch eine Animation entsteht. Man kann direkt in Python entwickelt, aber zusätzlich die Ergebnisse umfassend visualisieren.
httpvh://www.youtube.com/watch?v=3tpj6LgGhs0