Ein Entscheidungsrad in Python – drehen, bremsen, entscheiden

Was du hier lernst

• Dreiecksfächer (GL_TRIANGLE_FAN)
• translate, scale und rotate
• Zustände in der Animationsschleife
• Bremsen mit Reibung
• Zufall und Wahrscheinlichkeit
• Monte-Carlo-Simulation

Ein Rad, das entscheidet

In den Quelltexten zum Buch liegt neben den Kapitelordnern ein kleines Programm namens decisionMaker.py: ein Rad aus sechs Feldern in Rosa und Mintgrün, das sich mit OpenGL endlos dreht. Gedruckt ist es im Buch nicht – es ist eine Fingerübung aus der Zeit, in der das Bildschirmschoner-Kapitel entstand, und es teilt sich den Aufbau mit einem zweiten Programm, screenSaver.py. Der Name verrät, wofür das Rad eigentlich gedacht war: Man dreht es, es bleibt stehen, und das Feld oben entscheidet. Genau diesen letzten Schritt hat das Original nie bekommen. Hier holen wir ihn nach.

Ein Entscheidungsrad klingt nach Spielerei, aber es steckt ein ernster Gedanke dahinter: Wenn zwei Möglichkeiten wirklich gleich gut sind, ist langes Grübeln verschwendete Zeit. Dann darf der Zufall entscheiden – vorausgesetzt, er ist fair. Ob unser Rad fair ist, prüfen wir am Ende mit einer Simulation.

Ein Rad aus Dreiecken

OpenGL zeichnet am liebsten Dreiecke. Für runde Flächen gibt es dafür eine praktische Form, den Dreiecksfächer (GL_TRIANGLE_FAN): Zuerst kommt ein Mittelpunkt, dann eine Folge von Punkten auf dem Rand. Jeder neue Randpunkt bildet mit dem Mittelpunkt und seinem Vorgänger ein Dreieck. Mit sechs Randpunkten – plus einem siebten, der wieder auf dem ersten liegt – entstehen sechs Dreiecke, die zusammen ein Sechseck ergeben. Ein Rad mit geraden Kanten also; mit 24 Feldern sieht es schon fast rund aus.

Die Funktion drawWheel ist aus dem Original übernommen. Nur schickt sie die Punkte nicht an OpenGL, sondern zeichnet jedes Dreieck selbst:

def drawWheel(numberOfParts):
    fullAnkle = 360.0
    partAnkle = fullAnkle / numberOfParts
    radius    = 2.0

    # GL_TRIANGLE_FAN: erst der Mittelpunkt, dann die Punkte auf dem Rand –
    # jeder neue Punkt bildet mit dem Mittelpunkt und seinem Vorgänger ein Dreieck
    center   = (0.0, 0.0)
    previous = None
    for i in range(numberOfParts + 1):
        if i % 2 == 0:
            color = glColor(1.0, 0.5, 0.8)
        else:
            color = glColor(0.5, 1.0, 0.8)
        radian = math.radians(i * partAnkle)
        x, y   = math.cos(radian) * radius, math.sin(radian) * radius
        if previous:
            # glShadeModel(GL_FLAT): das Dreieck bekommt die Farbe seines letzten Punkts
            surface.polygon([center, previous, (x, y)], color)
        previous = (x, y)

Die Randpunkte berechnet dieselbe Trigonometrie wie bei den Uhrzeigern der analogen Uhr: Ein Punkt im Abstand radius beim Winkel α liegt bei (cos α · radius, sin α · radius). Wer genau liest, stolpert über fullAnkle und partAnkle – »ankle« ist der Knöchel, gemeint war »angle«, der Winkel. Die Namen stehen so im Original, und wir lassen sie stehen.

In OpenGL hat jeder Punkt seine eigene Farbe. Welche Farbe das ganze Dreieck bekommt, entscheidet das Shading-Modell: Bei GL_FLAT gilt die Farbe des letzten Punkts, bei GL_SMOOTH verlaufen die Farben fließend von Punkt zu Punkt. Das Original schaltet GL_FLAT ein, und weil sich die Farben der Randpunkte abwechseln, wechseln sich auch die Farben der Felder ab. glColor rechnet dabei die OpenGL-Farbwerte von 0.0 bis 1.0 in die 0 bis 255 der Leinwand um.

Drehen wie OpenGL

Das Original zeichnet das Rad in »Welteinheiten« mit dem Radius 2.0 und überlässt OpenGL den Rest: Eine Perspektive mit 60 Grad Öffnungswinkel, eine Kamera 5 Einheiten vor dem Rad und bei jedem Bild ein glRotatef(3.0, 0.0, 0.0, 1.0) – eine Drehung um 3 Grad um die Achse, die aus dem Bildschirm heraus zeigt. Weil vor dem Zeichnen nie glLoadIdentity() aufgerufen wird, addieren sich die Drehungen: Das Rad dreht sich mit jedem Bild weiter.

Die Leinwand kennt dieselben Werkzeuge unter anderen Namen, und draw setzt sie in derselben Reihenfolge ein:

surface.push()
surface.translate(screen[0] / 2, screen[1] / 2)
surface.scale(pixelsPerUnit, -pixelsPerUnit)  # y zeigt nach oben – wie bei OpenGL
surface.rotate(angle)                          # wie glRotatef(angle, 0.0, 0.0, 1.0)
drawWheel(numberOfParts)
surface.pop()

translate schiebt den Nullpunkt in die Mitte der Leinwand. scale rechnet Welteinheiten in Pixel um und dreht mit dem Minuszeichen die y-Achse um – auf der Leinwand zeigt sie nach unten, bei OpenGL nach oben. rotate dreht, und push und pop merken sich den Zustand vorher und stellen ihn danach wieder her, genau wie glPushMatrix und glPopMatrix. Danach kann drawWheel in Welteinheiten zeichnen, als wäre nichts gewesen.

Wie viele Pixel eine Welteinheit ist, verrät die Perspektive: Bei 60 Grad Öffnungswinkel und 5 Einheiten Abstand sieht die Kamera 2 · 5 · tan(30°) ≈ 5,8 Einheiten in der Höhe. Auf 600 Pixel verteilt, sind das rund 104 Pixel pro Einheit – das Rad hat also einen Radius von gut 200 Pixeln, wie im Original.

Anhalten und entscheiden

Jetzt kommt der neue Teil. Das Programm kennt drei Zustände: Das Rad dreht sich frei, es bremst, oder es steht und zeigt die Entscheidung. Solange remaining den Wert None hat, dreht sich das Rad ungebremst um turnPerFrame Grad pro Bild. Ein Klick legt fest, wie weit es noch laufen darf, und berechnet daraus die Bremse:

remaining = brakeDistance()
brake     = speed * speed / (2 * remaining)

Die Formel kennst du vielleicht aus der Fahrschule: Wer gleichmäßig bremst, braucht den Bremsweg v² / (2a). Umgestellt ergibt sich die Verzögerung a, die das Rad auf genau remaining Grad zum Stehen bringt. In jedem Bild wird speed um brake kleiner, und remaining schrumpft um den zurückgelegten Winkel. Ist nichts mehr übrig, steht das Rad, und segmentUnderPointer stellt fest, welches Feld unter dem Zeiger oben liegt:

return int(((90 - angle) % 360) // partAnkle) % numberOfParts

Der Zeiger steht bei 90 Grad, und das Rad ist um angle weitergedreht. Welcher Winkel des Rads gerade oben liegt, ergibt also 90 - angle, und % 360 holt negative Werte in den Bereich von 0 bis 360 zurück. Geteilt durch die Breite eines Feldes und abgerundet, ist das die Nummer des Feldes.

Damit ein versehentlicher Klick beim Start nichts auslöst, wertet get_event Eingaben erst nach der ersten Sekunde aus – das ist der Trick aus dem Buch, mit dem der Farbbalken-Schoner verhindert, dass ihn schon die Mausbewegung beim Starten beendet. Mit decide = False wird das Programm übrigens wieder zu dem reinen Bildschirmschoner aus den Quelltexten: keine Beschriftung, kein Zeiger, und die erste Eingabe nach einer Sekunde beendet es.

Ist das Rad fair?

Sechs Felder, abwechselnd Ja und Nein: Das klingt nach 50 zu 50. Aber ein Rad ist nur dann fair, wenn auch jemand, der seinen Klick perfekt timen kann, das Ergebnis nicht in der Hand hat. Darum würfelt brakeDistance den Bremsweg aus:

return random.uniform(120, 480)

Der Bremsweg liegt gleichmäßig verteilt zwischen 120 und 480 Grad – der Spielraum ist also genau eine volle Umdrehung. Egal, bei welchem Winkel du klickst: Jede Stelle des Rads kann mit derselben Wahrscheinlichkeit unter dem Zeiger landen. Bei sechs Feldern hat jedes Feld die Chance 1/6, und Ja und Nein stehen je auf drei Feldern.

Ob das stimmt, musst du nicht glauben – du kannst es ausprobieren, und zwar nicht von Hand, sondern mit einer Monte-Carlo-Simulation. Die Variante »Ist das Rad fair?« hält das Rad 1000-mal an, immer im selben Moment, ganz ohne Bild. Mit dem zufälligen Bremsweg kommt ungefähr halb Ja und halb Nein heraus, mit kleinen Schwankungen von Lauf zu Lauf. Mit Reibung gewinnt dagegen eine Antwort deutlich öfter.

Das Verfahren ist genau das, was im Statistikkapitel des Buchs beim Ziegenproblem und bei der Roulette-Simulation passiert: Wenn eine Rechnung zu kompliziert oder zu unsicher ist, lässt man den Computer einfach sehr oft würfeln. Und es funktioniert auch in die andere Richtung – mit ["Ja", "Ja", "Nein"] aus der Variante »Eigene Antworten« zeigt die Simulation, dass das Rad gezinkt ist: Ja gewinnt zwei von drei Malen.

Probier mal

Jede Variante ändert den Code oben. Ein Klick auf »Ausprobieren« übernimmt die Änderung in den Editor und startet das Programm. »Zurücksetzen« holt das Original zurück.

1. 01Der Bildschirmschoner mit 24 Feldern

   In den Quelltexten zum Buch gibt es noch eine zweite Fassung, screenSaver.py: 24 Felder in Lachsrot und Hellgrau, eine gemächliche Drehung um 0,5 Grad pro Bild bei 100 Bildern pro Sekunde – und kein Zeiger, keine Entscheidung. Mit 24 Dreiecken wirkt der Fächer schon fast rund. Wie jeder Bildschirmschoner endet sie bei der ersten Eingabe nach einer Sekunde. Der Rotwert 5.0 stand wirklich so im Original; OpenGL kappt ihn auf 1.0.

   - decide        = True            # False: ein reiner Bildschirmschoner wie im Original
   + decide        = False           # ein reiner Bildschirmschoner wie im Original
   - numberOfParts = 6
   + numberOfParts = 24
   - surface.controls([("SPACE", "Anhalten / neu drehen")])
   + surface.controls([("SPACE", "Beenden")])
   - turnPerFrame  = 3.0             # Grad pro Bild, wie glRotatef(3.0, 0.0, 0.0, 1.0)
   + turnPerFrame  = 0.5             # screenSaver.py: glRotatef(0.5, 0.0, 0.0, 1.0)
   - maxfps        = 50
   + maxfps        = 100
   -             color = glColor(1.0, 0.5, 0.8)
   +             color = glColor(5.0, 0.5, 0.5)  # 5.0 wird auf 1.0 gekappt
   -             color = glColor(0.5, 1.0, 0.8)
   +             color = glColor(0.8, 0.8, 0.8)
   - print("Klick ins Bild oder drück die Leertaste: Das Rad hält an und entscheidet.")
   + print("Nach der ersten Sekunde beendet jede Eingabe den Bildschirmschoner.")

   Ausprobieren

2. 02Eigene Antworten

   Die Liste choices legt fest, was auf den Feldern steht. Sechs Antworten für sechs Felder ergeben ein Rad fürs Mittagessen. Gibt es weniger Antworten als Felder, wiederholen sie sich reihum – mit ["Ja", "Ja", "Nein"] steht Ja auf vier von sechs Feldern, und das Rad sagt im Schnitt doppelt so oft Ja wie Nein.

   - choices       = ["Ja", "Nein"]  # die Felder bekommen reihum diese Antworten
   + choices       = ["Pizza", "Pasta", "Salat", "Sushi", "Curry", "Suppe"]

   Ausprobieren

3. 03Weicher Farbverlauf mit GL_SMOOTH

   Im Original steht eine auskommentierte Zeile: glShadeModel(GL_SMOOTH). Damit hätte OpenGL die Farben zwischen den Punkten fließend ineinander übergehen lassen, statt jedes Dreieck einfarbig zu füllen. Die Leinwand kennt so etwas nicht, also teilen wir jedes Feld in zwölf schmale Dreiecke und mischen ihre Farben mit mix – von der Farbe des einen Randpunkts zur Farbe des nächsten.

   - from c4f import Screen, time, KEYDOWN, MOUSEDOWN, K_SPACE, K_ESCAPE
   + from c4f import Screen, time, mix, KEYDOWN, MOUSEDOWN, K_SPACE, K_ESCAPE
   -         if previous:
   -             # glShadeModel(GL_FLAT): das Dreieck bekommt die Farbe seines letzten Punkts
   -             surface.polygon([center, previous, (x, y)], color)
   -         previous = (x, y)
   +         if previous:
   +             # glShadeModel(GL_SMOOTH): die Farbe wandert fließend von Punkt zu Punkt
   +             steps = 12
   +             for s in range(steps):
   +                 a0 = math.radians((i - 1 + s / steps) * partAnkle)
   +                 a1 = math.radians((i - 1 + (s + 1) / steps) * partAnkle)
   +                 p0 = (math.cos(a0) * radius, math.sin(a0) * radius)
   +                 p1 = (math.cos(a1) * radius, math.sin(a1) * radius)
   +                 surface.polygon([center, p0, p1], mix(previousColor, color, (s + 0.5) / steps))
   +         previous      = (x, y)
   +         previousColor = color

   Ausprobieren

4. 04Ist das Rad fair? 1000-mal anhalten

   Bevor du dem Rad eine wichtige Entscheidung überlässt, solltest du prüfen, ob es fair ist – und zwar auch für jemanden, der immer im selben Moment klickt. Statt tausendmal zu klicken, hält der Computer das Rad 1000-mal an, immer bei 210 Grad, ganz ohne Bild. Das nennt man eine Monte-Carlo-Simulation. Zum Vergleich bremst er dasselbe Rad auch mit »echter« Reibung. Der zufällige Bremsweg liefert etwa halb Ja, halb Nein – mit Reibung gewinnt je nach Klickmoment eine Antwort deutlich öfter.

   - print("Klick ins Bild oder drück die Leertaste: Das Rad hält an und entscheidet.")
   + def simulate(spins, clickAngle):
   +     # das Rad sehr oft anhalten – immer im selben Moment, ganz ohne Bild
   +     uniform, friction = {}, {}
   +     for n in range(spins):
   +         # 1) so bremst das Programm: das Rad läuft genau brakeDistance() weiter
   +         answer = choices[segmentUnderPointer((clickAngle + brakeDistance()) % 360) % len(choices)]
   +         uniform[answer] = uniform.get(answer, 0) + 1
   +         # 2) zum Vergleich: echte Reibung, deren Stärke der Zufall bestimmt
   +         angle, speed, f = clickAngle, turnPerFrame, random.uniform(0.975, 0.99)
   +         while speed >= 0.05:
   +             angle  = (angle + speed) % 360
   +             speed *= f
   +         answer = choices[segmentUnderPointer(angle) % len(choices)]
   +         friction[answer] = friction.get(answer, 0) + 1
   +     for name, counts in (("Bremsweg", uniform), ("Reibung", friction)):
   +         print(name + ":", "  ".join(f"{a} {c / spins:.0%}" for a, c in sorted(counts.items())))
   + 
   + 
   + simulate(1000, 210.0)
   + print("Klick ins Bild oder drück die Leertaste: Das Rad hält an und entscheidet.")

   Ausprobieren

'''
Created on 28.01.2010

@author: Lars Heppert
'''
from OpenGL.raw.GLUT import glutSolidSphere

import pygame
from sys import exit

from OpenGL.GL import *
from OpenGL.GLU import *

screen  = (800,600)

pygame.init()
start = pygame.time.get_ticks()
pygame.event.clear()
surface = pygame.display.set_mode(screen, pygame.OPENGL|pygame.DOUBLEBUF, 16)
pygame.display.set_caption("Hallo Welt!")

def reshape((width,height)):
    glViewport(0, 0, width, height)
    glMatrixMode(GL_PROJECTION)
    glLoadIdentity()
    gluPerspective(60, 1.0*width/height, 0.1, 1000.0)
    glMatrixMode(GL_MODELVIEW)

def init():
    glClearColor(1.0, 1.0, 1.0, 1.0)
    reshape(screen)

def get_event():
    event = pygame.event.poll()
    now = pygame.time.get_ticks()
    if now - start > 1000:            
        if event.type == pygame.QUIT:
            exit()
        elif event.type == pygame.KEYDOWN:
            exit()
        elif event.type == pygame.MOUSEMOTION:
            exit()
        elif event.type == pygame.MOUSEBUTTONDOWN:
            exit()

import math
def drawWheel(numberOfParts):
    fullAnkle       = 360.0
    partAnkle       = fullAnkle/numberOfParts
    radius          = 2.0

    glBegin(GL_TRIANGLE_FAN)
    glVertex3d(0.0, 0.0, 1.0)
    for i in range(numberOfParts+1):
        if i % 2 == 0:
            glColor3d(1.0, 0.5, 0.8)
        else:
            glColor3d(0.5, 1.0, 0.8)
        radian  = math.radians(i*partAnkle)
        x, y    = math.cos(radian)*radius, math.sin(radian)*radius
        glVertex3d(x, y, 1.0)
    glEnd()
    

def draw():

    glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT)
    glRotatef(3.0, 0.0, 0.0, 1.0)
    drawWheel(6)

    pygame.display.flip()

def main():
    init()
    maxfps = 50
    clock = pygame.time.Clock()
#   glShadeModel(GL_SMOOTH)
    glShadeModel(GL_FLAT)
    glLoadIdentity()
    gluLookAt(0, 0, 6, 0, 0, -100, 0, 1 ,0)
    while True:
        clock.tick(maxfps)
        draw()
        get_event()

if __name__ == "__main__":
    main()

'''
Created on 28.01.2010

@author: Lars Heppert
'''
from OpenGL.raw.GLUT import glutSolidSphere, glutSwapBuffers

import pygame
from sys import exit

from OpenGL.GL import *
from OpenGL.GLU import *

screen  = (800,600)

pygame.init()
start = pygame.time.get_ticks()
pygame.event.clear()
surface = pygame.display.set_mode(screen, pygame.OPENGL|pygame.DOUBLEBUF|pygame.FULLSCREEN, 16)
pygame.display.set_caption("Hallo Welt!")

def reshape((width,height)):
    glViewport(0, 0, width, height)
    glMatrixMode(GL_PROJECTION)
    glLoadIdentity()
    gluPerspective(60, 1.0*width/height, 0.1, 1000.0)
    glMatrixMode(GL_MODELVIEW)

def init():
    glClearColor(1.0, 1.0, 1.0, 1.0)
    reshape(screen)

def get_event():
    event = pygame.event.poll()
    now = pygame.time.get_ticks()
    if now - start > 1000:            
        if event.type == pygame.QUIT:
            exit()
        elif event.type == pygame.KEYDOWN:
            exit()
        elif event.type == pygame.MOUSEMOTION:
            exit()
        elif event.type == pygame.MOUSEBUTTONDOWN:
            exit()

import math
def drawWheel(numberOfParts):
    fullAnkle       = 360.0
    partAnkle       = fullAnkle/numberOfParts
    radius          = 2.0

    glBegin(GL_TRIANGLE_FAN)
    glVertex3d(0.0, 0.0, 1.0)
    for i in range(numberOfParts+1):
        if i % 2 == 0:
            glColor3d(5.0, 0.5, 0.5)
        else:
            glColor3d(0.8, 0.8, 0.8)
        radian  = math.radians(i*partAnkle)
        x, y    = math.cos(radian)*radius, math.sin(radian)*radius
        glVertex3d(x, y, 1.0)
    glEnd()

def drawFunction():
    glColor3d(1.0, 0.0, 0.0)
    glBegin(GL_LINE)
    glVertex3d(0.0, 0.0, 0.0)
    glVertex3d(1.0, 0.0, 0.0)
    glEnd()

def draw():
    glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT)
    glRotatef(0.5, 0.0, 0.0, 1.0)
    color = [1.0,0.,0.,1.]
    drawWheel(24)
    #drawFunction()
    pygame.display.flip()

def main():
    init()
    maxfps = 100
    clock = pygame.time.Clock()
#   glShadeModel(GL_SMOOTH)
    glShadeModel(GL_FLAT)
    glLoadIdentity()
    gluLookAt(0, 0, 6, 0, 0, -100, 0, 1 ,0)
    while True:
        clock.tick(maxfps)
        draw()
        get_event()

if __name__ == "__main__":
    main()