SuperPad64 und Race+ - Entwicklungsinfos

Nun, da die Arbeit an RACE+ und SuperPad64 getan ist (siehe hier und hier), möchte ich zum Projekt in losen Abständen ein paar Hintergrund- und technische Informationen hier im Forum geben. Ich hoffe das interessiert den einen oder die andere.

Im Prinzip ging es für mich dabei um die Rückkehr zum guten, alten C64. In der 80ern war es mein Traum ein Spiel für den C64 zu entwickeln. Es gab mehrere Versuch unter Verwendung von BASIC, SIMON'S BASIC und später auch ASSEMBLER. Aber dank mangelnder Kenntnisse sowie mangelndem Durchhaltevermögen bin ich nie weit damit gekommen

In der Zwischenzeit habe ich programmieren gelernt und irgendwann in meinem Leben habe ich mich an dieses alte Ziel erinnert: und hier ist mein C64-Spiel nun endlich!

Die Idee war ein Mehrspieler-Spiel zu implementieren, welches eine Mischung aus "Rally Speedway" von John Anderson (welches wiederum selbst durch das Mattel Intellivision Spiel "Auto Racing" inspiriert war) und einem einfachen Spiel namens "Cave" darstellt, welches ich auf einem Palm-PDA gesehen hatte.

Die Generierung der Rennstrecken ist gleich durch drei Urgesteine der Spieleentwicklung inspiriert. Das ist zum einen David Crane mit "Pitfall!". Alle Bildschirme seines Klassikers sind durch ein einziges Byte festgelegt. Die Bits bestimmen dabei den Untergrund, das Baummuster, den Fallentyp und das Pfadobjekt. Deshalb hat "Pitfall!" 256 Bildschirme. Bei "RACE+" gibt es entsprechend für jede der angebotenen Umgebungen – Stadt, Wüste und Landstraße – ebenfalls ein Streckennummer-Byte und damit pro Umgebung 256 Rennstrecken.

In "Elite" generieren David Braben und Ian Bell ganze Galaxien mittels eines Pseudozufallszahlengenerators aus einem Sechs-Byte-Startwert. Damit wird sichergestellt, dass bei jedem neuen Spielstart immer wieder genau dieselben Galaxien erzeugt werden. In "RACE+" wird das erwähnte Streckennummer-Byte als Startwert für den Pseudozufallszahlengenerator genommen und so für jede einzelne Streckennummer immer wieder genau dieselbe Rennstrecke generiert.

In Spielen wie "Wizard of Wor" und "Bruce Lee" können sich die Spieler entscheiden, ob sie sich gegenseitig unterstützen oder lieber bekämpfen wollen. Dieser Ansatz, der nicht oft in C64-Spielen zu finden ist, wurde auch in "RACE" verfolgt und so entstand neben dem Highscore für einzelne Spieler auch ein Highscore für das gesamte Team. Jeder Spieler kann so für sich alleine kämpfen, alle zusammen können sich aber auch für das Team einsetzen. Damit können auch ganze Teams gegeneinander antreten.

Um die Machbarkeit zu prüfen, habe ich mittels Python/Pygame einen Prototyp auf dem PC entwickelt. Damit wurden Basistechniken wie 8-Bit-taugliche Fahrphysik sowie Kollisionsreaktionen auf Fahrzeuge und Hindernisse erprobt. Diese Techniken wurden anschließend auf den Commodore 64 übertragen.

Nun zu einigen Daten und Fakten über das Spiel.

Werkzeuge:
========
Heutzutage ist es ungleich leichter Spiele für den C64 zu entwickeln als damals in den 80ern. Im Internet finden sich sehr viele Informationen über Themen, die zur Programmierung des C64 benötigt werden bis hin zu zahlreichem Beispiel-Code. Und es gibt natürlich grandiose Werkzeuge, welche einem die Entwicklung vereinfachen. Ein dickes "Dankeschön" an alle die diese Informationen, Code und Werkzeuge zur Verfügung stellen! Das ist einfach großartig und so macht das Programmieren Spaß!

Für "RACE+" wurden folgende Werkzeuge verwendet:
cc65
acme
exomizer
makedisk
DirMaster
SpritePad
CharPad
CSAM Super
CBM prg Studio
Vice
python/pygame

Entwicklungszeitraum
==============
2013-2017 - als C64 Hobby-Entwickler braucht man einen langen Atem

Code-Größen gemessen in Codezeilen:
=========================
16571 C
3397 Assembler
6164 Python (unterstützende Scripte für die Entwicklung)

Beteiligte Personen
=============
Code und Graphik - Steffen Görzig
Titelbild - Johan Janssen
Musik - Jan Harries
Spieletester - Jakob Chen-Voos, Jörg Heyltjes, Oliver Tscherwitschke
SuperPad64 Adapter - Oliver Tscherwitschke
Adapter Original Design - Wolfgang Sang

Verpackungsgestaltung
===============
Cover Art: Ralph Niese
Verpackung und Anleitungsdesign: Sebastian Bach (poly.play)
Anleitungstext: Steffen Görzig

Zitat von ogd

WIe hast du sichergestellt, dass der Python-Prototyp die C 64 Limitationen beachtet hat?

Die Python-Prototypen waren bei mir bislang dazu da, einzelne kritische Aspekte einer C64-Implementierung vorab schnell und effektiv testen zu können.

Im Fall von "RACE+" ging es mir um die 8-Bit-taugliche Fahrphysik, Kollisionen und auch die Steuerung. So konnte ich bequem testen, wie sich möglichst gute Fahrphysik mit möglichst wenig Rechnen- und Speicherbedarf umsetzen läßt. Das habe ich dann quasi nur auf dem C64 portiert. Wie die Gleichungen dazu genau aussehen folgt in weiteren Beiträgen - ab jetzt wird es also technischer

Bei brotCASTen habe ich ebenfalls zuerst einen Phython-Prototyp geschrieben, da habe ich bereits 1.1 fixed point Arithmetik eingesetzt und den Char-Grafikmodus emuliert (char+colorram) um sicherzustellen, dass es dann auf dem C64 auch läuft.

Die Grundfunktionalität für jedes Rennspiel ist die Fahrzeugphysik. Für 8-Bit Systeme sollte diese natürlich möglichst effizient umsetzbar sein. Nach kurzer Suche bin ich auf folgenden Artikel gestoßen:
Marcin Pancewicz and Paul Bragiel. “Vehicle Physics Simulation for CPU-Limited Systems”. In Game Programming Gems 4, Charles River Media, 2004, pp. 221–230.

Die Fahrzeugphysik von "RACE+" basiert grundsätzlich auf diesem Ansatz, ist allerdings in Teilen modifiziert (um die Komplexität weiter zu verringern) und natürlich um weitere für das Spiel benötigte Funktionalität ergänzt. Der im Artikel beschriebene Ansatz nutzt einen X- und einen Y-Vektor um die Fahrzeuggeschwindigkeit ("velocity") abzubilden und einen Rotationswinkel ("angle") für die Fahrtrichtung. Die Geschwindigkeitsberechnung verwendet eine Kraft ("power") für die Beschleunigung und einen Widerstand ("drag" mit 0.0<=drag<1.0) um die Geschwindigkeit wieder zu verlangsamen:

velocityX = velocityX * drag // erst verlangsamen
velocityY = velocityY * drag
velocityX = velocityX + cos(angle) * power // dann beschleunigen, wenn vom Spieler gewünscht
velocityY = velocityY + sin(angle) * power

Um die Komplexität zu reduzieren erfolgt die Lenkung etwas anders als im Artikel beschrieben. In "RACE+" wird eine Lenkgeschwindigkeit ("angularVelocity") verwendet, die Rückstellkraft in die Geradeausfahrt wird durch einen Widerstand ("angularDrag") auf die Lenkgeschwindigkeit abgebildet:
angularVelocity = turnVelocity // bei Lenkrichtungswechsel (z. B. von links nach rechts)
angularVelocity = angularVelocity + turnVelocity // bei Beibehaltung einer Lenkrichtung (z. B. immer weiter nach rechts lenken)
angularVelocity = angularVelocity // keine Änderung der Geschwindigkeit wenn nicht gelenkt wird
angularVelocity = angularVelocity * angularDrag // diese Geschwindigkeitsreduzierung erfolgt anschließend in jedem Fall

Mit diesen wenigen Gleichungen lässt sich ein Fahrzeug nach Wahl geeigneter Parameter bereits sehr gut fahren! Nun zu ein paar Erweiterungen dieses Ansatzes, um für "RACE+" gewünschte Funktionalitäten umsetzen zu können.

Um eine mögliche unendliche Beschleunigung zu vermeiden könnten physikalisch korrekt die Widerstände abhängig von der Geschwindigkeiten gewählt werden. Um gute Spielbarkeit zu erreichen reicht es jedoch völlig aus, die Maximalgeschwindigkeiten zu beschränken. Das hat neben der einfacheren Berechnung noch den Vorteil, dass Fahrzeuge recht schnell bis zur Maximalgeschwindigkeit beschleunigen können, wenn dies spielerisch von Vorteil ist. Ein naheliegendes Vorgehen wäre folgendes:
if(velocityX>maxVelocity){velocityX = maxVelocity;}

Eine flexiblere Lösung ist jedoch die Beschleunigung zu unterdrücken, sobald das Maximum erreicht ist:
if(velocityX<maxVelocity){velocityX = velocityX + cos(angle) * power;}

Was ist der Unterschied? Bei der ersten Variante ist das Fahrzeug in seiner Höchstgeschwindigkeit fest beschränkt, bei der zweiten Variante können Fahrzeuge durchaus höhere Geschwindigkeiten als den Grenzwert erreichen. Im Spiel wird beispielsweise ein Fahrzeug nach rechts gestoßen, wenn es den linken Rand erreicht. Dabei erreicht es eine höhere Geschwindigkeit als die eigentliche Maximalgeschwindigkeit. Der Widerstand bremst anschließend das Fahrzeug ab. Ist die Geschwindigkeit dann unter den Grenzwert gefallen kann der Spieler wieder beschleunigen.

Für die Geschwindigkeiten ("velocity"), die Kraft ("power") und den Widerstand ("drag") werden 1.1 Festkommazahlen verwendet mit einem zusätzlichen positive/negativ-Status falls benötigt. Wählt man geeignete Parameterwerte, so lassen sich die Geschwindigkeiten als gute Näherung auch direkt zur Berechnung der neuen Fahrzeugposition verwenden:
posX = posX + vorkommaanteil(velocityX)
posY = posY + vorkommaanteil(velocityY)

Der Lenkwinkel ("angle") wird durch ein Byte dargestellt. Eine Drehung erfolgt somit in Schritten von 360/256=1,40625 Grad, was für die Auflösung des C64 genau genug ist. Damit lässt sich der Lenkwinkel direkt zur Auswahl des richtigen Fahrzeug-Sprites verwenden:
spriteNummer = angle
Das gilt natürlich nur bei der Verwendung von in 256 Stufen gedrehten Sprites. Aber auch wenn die Drehung durch weniger Sprites dargestellt wird genügen wenige Additionen und Schiebe-Operationen für die Abbildung von Lenkwinkel auf Sprite-Nummer.

Um die erhöhte Haftreibung der Reifen beim Fahren einer Kurve zu simulieren werden während des Lenkvorgangs die Geschwindigkeiten "velocityX" und "velocityY" reduziert - das Fahrzeug fährt damit in Kurven also etwas langsamer als bei Geradeausfahrt. Das Verlassen der Fahrbahn führt ebenfalls zu einer Verminderung der Geschwindigkeit, dieses Mal durch Manipulation des Widerstandes:
if(drivingOverBackground){drag = higherDrivingNextToRoadDrag;}
else{drag = lesserDrivingOnRoadDrag;}

Durch die geringe Auflösung der 1.1 Festkomma-Arithmetik können Artefakte bei der Lenkung entstehen: nach einem beendeten Lenkvorgang kann es vorkommen, dass sich das Fahrzeug nach einer längeren stabilen Phase nochmals einen Schritt dreht (das gilt besonders, wenn weniger als 256 Sprites für die Drehung verwendet werden). Das ist zwar rechnerisch korrekt aber für den Spieler ein unschönes Verhalten. Um dies zu vermeiden wird die Fahrtrichtung exakt auf die aktuelle Sprite-Ausrichtung gesetzt, falls es längere Zeit keine Lenkeingabe (links oder rechts) mehr gab. Der geeignete Zeitpunkt dazu kann abhängig von der gewählten Drehgeschwindigkeit ("turnVelocity") fix gesetzt werden.

Diese vereinfachte Fahrphysik deckt einen erstaunlichen Umfang von Fahrcharakteristiken ab: wählt man den Widerstand Null oder sehr nahe Null und die Geschwindigkeiten hoch, so "klebt" das Fahrzeug förmlich auf der Strecke. Am anderen Ende der Skala erhält man ein Fahrverhalten wie bei einem Luftkissenboot, wenn man die Widerstände nahe 1.0 wählt.

Eine weitere grundlegende Funktionalität ist die Behandlung von Kollisionen. Das Spiel unterscheidet zwischen Fahrzeug mit Fahrzeug und Fahrzeug mit Hindernis Kollisionen.

Die Reaktion auf Fahrzeug mit Fahrzeug Kollisionen sollte den Erwartungen des Spielers für ein Rennspiel dieser Art entsprechen. Deshalb ist sie als zentraler elastischer Stoß umgesetzt. Die Kollisionsberechnung kann separat für die Fahrzeuggeschwindigkeiten "velocityX" und "velocityY" erfolgen. Seien m1 und m2 die Massen, v1 und v2 die Geschwindigkeiten vor der Kollision und u1 und u2 die Geschwindigkeiten der Fahrzeuge nach der Kollision, so gilt:
u1 = (m1*v1 + m2 * (2*v2-v1)) / (m1+m2)
u2 = (m2*v2 + m1 * (2*v1-v2)) / (m1+m2)

Im Spiel sind die Massen der Fahrzeuge identisch, damit ergibt sich:
m1 = m2
u1 = (v1 + (2*v2-v1)) / 2
u2 = (v1 + (2*v1-v2)) / 2

Diese Berechnungen können recht schnell auf einem C64 durchgeführt werden (für Multiplikationen und Divisionen mit dem Faktor zwei können Schiebeoperationen verwendet werden). Für kleine Geschwindigkeiten kann es vorkommen, dass die Kollisionsreaktion nicht ausreicht um die Fahrzeuge voneinander zu trennen. Deshalb wird ein zusätzlicher Faktor >1.0 benötigt:
u1 = u1 * extraBumpFactor
u2 = u2 * extraBumpFactor

Somit ist die Summe der Geschwindigkeiten nach der Kollision großer als vor der Kollision. Im Spielmodus "BATTLE" erhalten bereits ausgeschiedene Fahrzeug einen weiteren Faktor >1.0:
u1Out = u1 * extraBumpFactorOut

Ausgeschiedene Fahrzeuge können damit deutliche höhere Geschwindigkeiten erreichen als im Spiel verbliebene Fahrzeuge wodurch sie sehr gut als "Geschosse" gegen gegnerische Fahrzeuge eingesetzt werden können! Bei Kollisionen zwischen Spielern und Robotern erhalten vom Roboter gesteuerte Fahrzeuge eine Sonderbehandlung:
u1Robot = u1 * extraBumpFactorRobot

Damit können Roboterfahrzeuge vom Spieler leichter zur Seite gedrängt werden als die Fahrzeuge anderer Spieler. Dies gilt nur für Kollisionen zwischen Spieler und Roboter, Kollisionen zwischen von zwei von Robotern gesteuerten Fahrzeugen erfahren ebenso keine Sonderbehandlung wie Kollisionen zwischen zwei von Spielern gesteuerten Fahrzeugen.

Eine sehr spezielle Funktionalität des Spieles ist, dass Kollisionen zwischen Fahrzeugen nicht nur deren Geschwindigkeiten und Positionen verändern, sondern - abhängig vom Kollisionspunkt - auch deren Lenkwinkel:
diffVelocities = (velocityX[car1]-velocityX[car2]) + (velocityY[car1]-velocityY[car2])
collisionTurnVelocity = offset + diffVelocities
angularVelocity = angularVelocity + collisionTurnVelocity
angle = angle + valueBeforeDecimalPoint(angularVelocity)

Der Lenkwinkel wird so abhängig von den Geschwindigkeitsunterschieden stärker oder schwächer verändert. Um auch bei sehr kleinen Geschwindigkeitsunterschieden eine Lenkwinkeländerung zu erzielen wird zusätzlich ein Wert "offset" addiert. Ob eine Lenkwinkeländerung erfolgt oder nicht hängt von der Position des Kollisionspunktes relativ zur Fahrzeugmitte ab. In welche Richtung die Lenkwinkeländerung erfolgt hängt davon ab, aus welcher Richtung das andere Fahrzeug kommt.

Erfolgt die Kollision recht zentral am Fahrzeug, so wird das Fahrzeug zur Seite geschoben ohne den Lenkwinkel zu verändern (siehe Bilder 1 und 2). Anders bei den Bildern 3 und 4: hier werden auch die Lenkwinkel verändert. Die Abhängigkeit der Richtung der Lenkwinkeländerung von der Fahrtrichtung des anderen Fahrzeuges zeigt sich hier deutlich: obwohl der Kollisionspunkt in beiden Fällen der gleiche ist wird das getroffene Fahrzeug einmal nach links (Bild 3, anderes Fahrzeug kommt von oben) und einmal nach rechts (Bild 4, anderes Fahrzeug kommt von links) gedreht.

Um diese Funktionalität im Spiel "RACE+" selbst einmal auszuprobieren muss das Fahrverhalten auf "EXPERT" oder "FUN" eingestellt sein. Die Einstellung "EASY" schaltet solche Drehungen aus um die Steuerung für Fahranfänger zu erleichtern.

Kollisionen zwischen Fahrzeugen und Hindernissen sind ein Spezialfall des zentralen elastischen Stoßes: Hindernisse sind am Boden fixiert was gleichbedeutend ist mit den Annahmen das die Masse eines Fahrzeuges (m1) sehr viel kleiner ist als die Masse des Hindernisses (m2) und die Geschwindigkeit des Hindernisses Null ist:
m1 << m2
v2=0

In diesem Fall ergibt sich für die neuen Geschwindigkeiten:
u1=-v1 // Fahrzeug
u2=0 // Hindernis bewegt sich nicht

Im Spiel wird noch eine zusätzliche Geschwindigkeit addiert:
u1=-v1 + extraBumpValue

Dies geschieht aus zwei Gründen: bei kleinen Fahrzeuggeschwindigkeiten können Fahrzeuge in Hindernissen "hängenbleiben". Die Zusatzgeschwindigkeit hilft das Fahrzeug vom Hindernis zu trennen. Zum zweiten wird dadurch eine Art
Flipper-Effekt generiert und so der Party-Charakter des Spieles unterstrichen. Die Zusatzgeschwindigkeit wurde andererseits klein genug gewählt, dass Fahrzeuge bei sehr kleinen Geschwindigkeiten trotzdem direkt durch Hindernisse fahren können. Das soll den Spieler vor Frustration schützen falls er in Sackgassen oder in Hindernisse gedrängt wurde.

Eine weitere Sonderbehandlung erfahren Roboter, die immer wieder auf das gleiche Hindernis stoßen: durch eine falsche Pfadberechnung kann es passieren, dass der Roboter direkt durch ein Hindernis steuern will. Natürlich kann eine solche Situation durch eine bessere Pfadberechnung vermieden werden. Das kostet auf 8-Bit Computern allerdings wertvolle Rechenzeit. In "RACE+" werden solche Situationen erkannt und der Roboter wird zur Seite versetzt (nach rechts für oben/unten Kollisionen und nach oben für rechts/links Kollisionen). Damit wird die Pfadberechnung so lange verändert, bis der Roboter das Hindernis umfahren hat.

Prozedurale Generierung von Rennstrecken

Der Meisterschaftsmodus umfasst 768 Rennstrecken. Alle diese Strecken erst zu entwerfen und dann in das Spiel einzufügen überschreitet den zur Verfügung stehenden Speicher des Commodore 64 bei Weitem – selbst wenn die Strecken extrem detailarm gestaltet und anschließend sehr gut gepackt würden.

Deshalb wird in "RACE+" eine Technik eingesetzt, die sich prozedurale Generierung nennt: abhängig von einem Ausgangswert werden verschiedene Rennstrecken erzeugt. Die Generierung selbst stellt dabei sicher, dass bei gleichem Ausgangswert immer die gleiche Strecke entsteht. Die einzelnen Rennstrecken sind so bei jedem Spielstart identisch gestaltet. In "RACE+" wird das bereits erwähnte Streckennummer-Byte als Ausgangswert für den Pseudozufallszahlengenerator genommen:
seed = selectedTrack + offset

Der Wert "offset" ist für jede der drei Umgebungen (Stadt, Wüste und Landstraße) unterschiedlich und dient dazu, aus der Vielzahl der generierten Strecken eine möglichst schöne und passende Rennstrecke Nummer Eins zu erzeugen - schließlich werden diese normalerweise als erstes gespielt. Der Wert "seed" wird durch ein Byte dargestellt. Damit gibt es pro Umgebung 256 Rennstrecken, insgesamt also 768.

Die Strecken werden nach Auswahl der Umgebung und der Streckennummer vor jedem Rennstart neu generiert. Dabei werden zwei Techniken eingesetzt: ein Teile- und ein Funktionsbasierter Ansatz. Der Funktionsbasierte Ansatz kommt bei den geschlängelten Wüstenstrecken zum Einsatz und wird durch eine modifizierte Sinus-Funktion realisiert:
sinOffset = random()
sinAngle = columnNumber+sinOffset
sinVal = sin(sinAngle)/sinGradient
if(roadWidthUpdate){roadWidth = roadWidth + random[-1,0,+1]}
if(sinGradientUpdate){sinGradient = random[minVal..maxVal]}

Der Wert von "sinVal" bestimmt die Y-Startposition für das zeichnen der Straße für eine Spalte, der "sinGradient" wird mit einer vorgegebenen Frequenz mit Zufallswerten belegt. Die Straßenbreite "roadWidth" wird nach einigen Spalten um 8 Pixel (ein Zeichen) vergrößert oder verkleinert, dabei wird eine Mindest- und Maximalbreite eingehalten.

Bei der Wüstenumgebung erzeugt im ersten Schritt diese modifizierte Sinus-Funktion den Rennstreckenverlauf und die Wüste wird zusätzlich mit einem Muster gefüllt (siehe Wüstenbild 1). Im zweiten Schritt werden einzelne Spitzen herausgefiltert und die Kanten geglättet (Wüstenbild 2). Als Nächstes werden Hindernisse in den Wüstensand gesetzt (Wüstenbild 3). Dabei wird darauf geachtet, dass sich die Hindernisse nicht überschneiden und kein Objekt in die Fahrbahn ragt. Anschließend werden Teile der Fahrstrecke "versandet", um die Fahrt interessanter zu gestalten (Wüstenbild 3). Dies geschieht als letzter Schritt, damit keine Hindernisse versehentlich auf die vorgesehene Fahrbahn gesetzt werden und somit keine blockierten Fahrwege entstehen können.

Bei den Umgebungen "Stadt" und "Landstraße" wird ein Teilebasierter Ansatz angewendet. Dabei werde vorgefertigte Teile, also Straßenabschnitte, ausgewählt und zusammengesetzt. Die Auswahl erfolgt zufallsgesteuert, ebenso wird per Zufall bestimmt, ob das Teil horizontal gespiegelt wird oder belassen wird. Es wird darauf geachtet, dass nur Teile aneinandergefügt werden, bei welchen der Straßenverlauf nicht unterbrochen wird. Passt ein neues Teil nicht zum vorangegangenen, so wird solange zufällig ein neues Teil gewählt, bis es passt.

Für der Umgebung "Stadt" ist eine so entstandene Strecke im Stadtbild 1 dargestellt. In einem zweiten Schritt werden fehlende Straßenkanten hinzugefügt (siehe linke Kante in Stadtbild 2). Kanten können nicht immer in Teile integriert sein, da sich manchmal erst beim Zusammenfügen von Teilen entscheidet, ob eine Kante benötig wird oder nicht. Anschließend werden Häuser außerhalb der Fahrbahn eingefügt (Stadtbild 3). Um Tiefenwirkung zu erzielen erhalten dabei die Häuser im oberen Bildschirmteil eine andere Perspektive als Häuser im unteren Teil. Im letzten Schritt erhalten alle Wolkenkratzer einen Dachaufbau, der zufallsgesteuert aus einer Menge von Dachaufbauten gewählt wird. Somit entstehen mehrere optisch unterschiedliche Hochhaustypen, ohne viel zusätzlichen Speicherplatz dafür zu benötigen.

Bei der Umgebung "Landstraße" sind bereits einige Hindernisse in den vorgefertigten Teilen enthalten (siehe Landstraßenbild 1). So sollen einfache Abkürzungen vermieden werden. Im zweiten Schritt wird die gesamte Grünfläche mit einem Grasmuster gefüllt (Landstraßenbild 2). Im letzten Schritt werden wieder Hindernisse außerhalb der Fahrbahn zufallsgesteuert ergänzt (Landstraßenbild 3).

Wir sind die Roboter

"RACE+" ist ein Spiel für bis zu acht Spieler. Nach den ersten Rückmeldungen der Tester wurde schnell klar: Als Schüler traf man sich noch häufig mit Freunden oder spielte mit den Geschwistern, heute jedoch sitzt normalerweise nur ein Spieler vor dem Computer. Um den Einsatz des Spieles nicht nur auf den doch eher seltenen Party-Fall zu beschränken mussten also Roboter her. Diese können die Steuerung von bis zu sieben Fahrzeugen übernehmen.

Die Anforderungen an diese Roboter sind recht umfangreich: sie sollten ein möglichst "menschliches" Fahrverhalten zeigen, sie sollten immer eine passende Pfadberechnung vornehmen und auch bei Störungen durch andere Fahrzeuge nirgends hängenbleiben, sie müssen mit den 768 generierten Rennstrecken (Meisterschaft) sowie mit vorgefertigten Strecken (Autoschlacht) zurechtkommen, es sollten unterschiedliche Schwierigkeitsgrade einstellbar sein und das Ganze soll natürlich möglichst wenig Speicher und Rechenzeit verbrauchen.

Der Lösungsansatz von "RACE+" besteht im Wesentlichen aus zwei Konzepten: virtuelle Eingaben und Wegepunkte. Roboter erzeugen virtuelle Eingaben: links oder rechts sowie der Feuerknopf für die Fahrzeugbeschleunigung. Nach der Abfrage der Eingaben muss so prinzipiell im Programm nicht mehr zwischen menschlichen Spielern und Robotern unterscheiden werden. Für eine bessere Spielbarkeit und Fehlerbehandlung gibt es dennoch Ausnahmen, welche bereits in vorangegangenen Abschnitten beschrieben wurden.

Welche virtuellen Eingaben erzeugt werden wird durch Wegepunkte bestimmt. Jeder Roboter misst die Entfernung und den Winkel zu seinem nächsten Wegepunkt. Drei Parameter legen sein Verhalten fest: wird ein Minimalabstand zum Wegepunkt unterschritten, so wird gebremst. Dies verhindert zu schnelle Einfahrten in Kurven. Im eigentlichen Kurvenmanöver lenkt und bremst der Roboter, wenn ein maximaler Winkel zum Wegepunkt überschritten wird. Der dritte Parameter ist eine Mindestgeschwindigkeit: wird diese unterschritten, so beschleunigt das Fahrzeug wieder. Damit wird ein mögliches Stehenbleiben des Fahrzeuges in sehr engen Kurven unterbunden.

Diese drei Parameter werden abhängig vom gewählten Fahrverhalten, von den Fahrumgebungen sowie von der Roboter-Schwierigkeitsstufe gesetzt. In Summe sind dies mehr als 150 Parameter, welche für jede der möglichen Kombinationen einzeln zeitaufwändig durch Beobachtung des Roboter-Fahrverhaltens mit dazugehöriger Feineinstellung optimiert werden müssen. Erschwerend kommt hinzu, dass die Roboter-Parameter abhängig sind von den Fahrparametern der Fahrzeuge. Wird beispielsweise die Höchstgeschwindigkeit der Fahrzeuge geändert, so müssen wieder die Roboter-Parameter angepasst werden. Lohn dieser ganzen Mühen ist ein (hoffentlich) für alle Kombinationen passendes Fahrverhalten der Roboter.

Im Detail unterscheiden sich die Rennvarianten "Meisterschaft" und "Autoschlacht" deutlich. Die Roboter-Schwierigkeitsstufe bestimmt z. B. bei der Meisterschaft weitere Spieleigenschaften: die Startaufstellung (Roboter vorne oder hinten), die Wahrscheinlichkeit wie oft ein Roboter zwischen den zwei Wegepunktfolgen wechselt (diszipliniertes oder eher chaotisches Fahren), die Maximalgeschwindigkeit der Roboter, den Reibwert der Roboterfahrzeuge sowie die Stärke des Zusatzstoßes bei Kollisionen, um Roboter leichter abdrängen zu können als menschliche Spieler.

Bei der Autoschlacht gibt es keine Veränderung der Startaufstellung, dafür wird zusätzlich das Verhalten bei Unverwundbarkeit (Angriff erfolgt auch auf entfernte Fahrzeuge oder nicht), das Stoppen von Angriffen auf einen nahen Gegner nach einer bestimmten Zeit, die Fahrtneuausrichtung beim Auftauchen von Gegenständen (alle Roboter unterschiedlich oder aber in die gleiche Richtung, um Kollisionen zwischen Robotern zu vermeiden) sowie die Wahl des Weges zu einem Gegenstand (kürzer oder länger) beeinflusst.

Im Spiel gibt es zwei Wegepunktfolgen. Bei der Meisterschaft werden die Wegepunkte während der Generierung in die zwei globalen Wegepunktfolgen eingefügt. Bei der funktionsbasierten Generierung nach vorgegebenen Abständen (nicht zu kurz um keine unnötigen Bremsvorgänge zu erhalten und nicht zu weit um gute Kurvenfahrten zu erlauben) verteilt (+-1 um die Fahrbahnmitte). Bei dem Teilebasierten Ansatz sind die relativen Wegepunkte in der Teilebeschreibung enthalten und werden entsprechend den globalen Wegepunkten hinzugefügt. Im Bild zur Meisterschaft (siehe unten Beispiel Stadt) sind diese Wegepunkte - für den menschlichen Spieler normalerweise unsichtbar - sichtbar gemacht. Jeder Roboter wird einer dieser Wegepunktfolgen zugeordnet. Auf diese Weise sowie durch die unterschiedlichen Ausgangspositionen der Fahrzeuge agieren die Roboter sehr unterschiedlich im Rennen.

Die maximal mögliche Anzahl der Wegepunkte lässt sich berechnen: bei der funktionsbasierten Generierung kann die Zahl der Wegepunkte durch die vorgegebenen Abstände und die Länge der Strecke bestimmen werden. Bei der Teilebasierten Generierung erhält man eine obere Wegepunktgrenze indem man das Teil mit den meisten Wegepunkten pro Teilebreite auswählt und eine Rennstrecke bestehend nur aus diesem einen Teil berechnet. Das Maximum aus all diesen Berechnungen ist die maximal mögliche Anzahl an Wegepunkten. Im Spiel wird eine Rennstrecke mehrere Runden lang gefahren. Da die relativen Positionen der Wegepunkte in jeder Runde gleich sind, reicht es nur einmal die Wegepunkte zu speichern und dann bei der Positionsberechnung die Rundennummer zu berücksichtigen.

Die Bestimmung des nächsten gültigen Wegepunktes sollte eigentlich recht einfach sein: wird ein Wegepunkt erreicht, so wird der nächste in der Folge ausgewählt. Dieses Vorgehen hat gleich zwei Schwachstellen: zum einen wird ein Wegepunkt nicht immer erreicht, zum anderen ist der nächste Wegepunkt nicht immer der richtige. Warum ist das so?

Wie gut ein Wegepunkt getroffen wird hängt zum einen von der Fahrzeugphysik ab und zum anderen von der Roboter-Steuerung. Um einen Wegepunkt garantiert immer zu treffen muss die Roboter-Steuerung zumindest für die gewählten Fahrphysiken dies sicherstellen. Das geht aber nur, wenn der Roboter sehr langsam fährt oder aber bei verpassen eines Wegepunktes umdreht um diesen doch noch zu erreichen - beides ungewünschte Verhaltensweisen. Deshalb wurden in "RACE+" Mindestabstände gewählt: unterschreitet der Abstand eines Roboter zu einem Wegepunkt den Mindestabstand, so gilt der Wegepunkt bereits als erreicht.

Die Antwort, warum der nächste Wegepunkt eine falsche Wahl sein kann, ist recht einfach: durch eine Kollision mit einem anderen Fahrzeug oder durch den Abprall vom linken Bildschirmrand kann ein Roboter an mehreren Wegepunkten "vorbeigestoßen" werden. Dann sollte er den gegebenen Schwung auch zu seinem Vorteil nutzen und weiterfahren können statt umzudrehen um zu einem vorangegangenen Wegepunkt zurückzukehren. Je nach Positionen der anderen Fahrzeuge kann dieser alte Wegepunkt sogar schon aus dem sichtbaren Bildbereich herausgescrollt sein und damit überhaupt nicht mehr erreichbar: der Roboter würde dann immer weiter versuchen nach links zu fahren.

Eine einfache Prüfung, welcher Wegepunkt aktuell ist, könnte durch die X-Position erfolgen. Die Fahrtrichtung ist von links nach rechts: ist der Roboter weiter rechts als ein Wegepunkt, so wird solange der nächste Wegepunkt in der Liste genommen, bis ein Wegepunkt rechts vom Roboter gefunden ist. Allerding enthält die Landstraße S-Kurven, bei welchen korrekte nächste Wegepunkte links vom aktuellen Wegepunkt liegen können, also mit kleinerer X-Position. Deshalb erhalten alle Wegepunkte ein zusätzliches Attribut "orientation", welches horizontal oder vertikal sein kann. Damit kann je nach Ausrichtung des Wegepunktes eine gewisse Fahrstrecke zurück erlaubt werden. Diese darf aber auch nicht zu groß werden, da z. B. durch Scrolling der Wegepunkt evtl. auch in diesem Fall gar nicht mehr erreichbar ist und so der Roboter abermals permanent nach links fahren würde.

Zusammengefasst erhält man folgende Prüfung, ob ein Wegepunkt noch gültig ist oder nicht:

Ist ein Wegepunkt nicht mehr gültig, so wird solange der nächste in der Liste der Wegepunkte genommen, bis einer gültig ist.

Die Wegepunkte bei der Autoschlacht sind vordefiniert in den drei Arenen enthalten (Beispiel siehe unten links Bild Wüste). Hier werden die Wegepunkte abgefahren ohne Einschränkungen der Fahrt nach links. Eine besondere Situation ist das Aufsammeln von Gegenständen. Gegenstände können nur an vorgegebenen Positionen im Spiel auftauchen, die Position des nächsten Gegenstandes wird zufällig aus dieser Menge ausgewählt. Sobald ein Gegenstand im Spiel erscheint, werden alle Roboter auf die nächstgelegenen Wegepukte einer anderen Liste mit Wegepunkten gesetzt. Diese Wegepunktliste kommt nahe genug an allen möglichen Positionen von Gegenständen vorbei und ist so gestaltet, dass sie sogar für alle drei Karten identisch ist, was Speicherplatz spart (siehe Bild unten rechts Landstraße). Kommt der Roboter nahe genug an einen Gegenstand heran, so verlässt er die Wegepunktstrecke und fährt ihn direkt an. Sobald der Roboter den Gegenstand eingesammelt hat oder dieser von anderen Fahrzeuge eingesammelt wird, wird der Roboter wieder auf den nächstgelegenen Wegepunkt der Standard-Wegepunktliste gesetzt.

Bei Zweikämpfen mit anderen Autos werden ebenfalls die Wegepunkte verlassen und das gegnerische Fahrzeug als Position anvisiert. Zweikämpfe werden eingegangen, wenn ein gegnerisches Fahrzeug nahe genug ist und abgebrochen, wenn sich die Fahrzeuge wieder voneinander entfernt haben, eine gewisse Zeit überschritten wurde oder eines der Fahrzeuge bewegungsunfähig ist. Ist der Zweikampf beendet, so wird das Fahrzeug wieder auf den nächstgelegenen Wegepunkt gesetzt. Beim Schwierigkeitsgrad "C64 veteran" wird ein Zweikampf nur bei Bewegungsunfähigkeit abgebrochen. Hat ein Roboter den Gegenstand für zeitweilige Unverwundbarkeit eingesammelt, so wird bei den Schwierigkeitsgraden "C64 veteran" und "Normal" ein globaler Angriff auf einen zufälligen Spieler oder Roboter unabhängig von Wegepunkten gestartet - Kollisionen können das Fahrzeug in diesem Zustand ja nicht beschädigen. Sollte dieser Gegner besiegt sein und die Unverwundbarkeit noch aktiv, so wird der nächste zufällige Gegner ausgewählt.

Kompression von Bildern

Das Spiel enthält insgesamt acht Bilder (Flaggensequenz bestehend aus vier Bildern, Stern, Abschleppwagen, Hand und Siegerpokal). Ziel war es, diese Bilder in Zeichengrafik umzuwandeln. Damit erhält man pro Bild jeweils eine Menge von Zeichendefinitionen (Zeichensatz) und eine dazugehörige 40x25=1000 Bytes Zeichenfolge.

Der Zeichensatz sollte aus Speicherplatzgründen insgesamt 256 Zeichen nicht überschreiten. Davon gehen noch Buchstaben und Sonderzeichen für die Texte und Menüs ab (diese werden im Spiel mit den Bildern vermischt). Damit verbleiben 207 Zeichen. Die Bilder enthalten zusammengenommen allerdings 799 verschiedene Zeichen. Was tun?

Hier kommt "CSAM Super" ins Spiel - ein Werkzeug von Algorithm und es ist wirklich super :-). Das Werkzeug fasst mehrere Zeichen zu möglichst ähnlichen Zeichen zusammen. Es basiert auf evolutionären Algorithmen und ist damit nicht deterministisch - die Qualität des Ergebnisses hängt also von Zufallsprozessen ab und ist nicht reproduzierbar. Um eine möglichst gute Qualität der Kompression zu erzielen wurden daher sehr viele Berechnungen mit dem Werkzeug vorgenommen und anschließend das optisch beste Ergebnis ausgewählt. Für den Zeichensatz wird damit eine nicht-verlustfreie Kompression von 799 auf 207 erzielt, das entspricht einem Faktor von ca. 3,86.

Die Zeichenfolgen werden durch eine Abwandlung einer Standard-Lauflängenkodierung gepackt. Dabei wird ausgenutzt, dass die ersten 49 Zeichen (Buchstaben und Sonderzeichen) in den Grafiken selbst nicht vorkommen können: liegen einzelne Zeichenwerte über einer vorab berechneten optimalen Grenze, so muss die Längeninformation nicht mitkodiert werden. Die Zeichenfolgen enthalten zusammengenommen 40x25x8=8000 Bytes. Mit dieser verlustfreien Kompression werden sie auf 2478 Bytes reduziert, was einem Faktor von ca. 3,23 entspricht.

Alle Teile des Teile-basierten Ansatzes bei der prozeduralen Generierung von Rennstrecken sowie die Arenen der Autoschlacht wurden ebenfalls mit der beschriebenen Lauflängenkodierung gepackt.

Zitat von Hexworx

Nur schade, dass das hier anscheinend kaum einer zu würdigen weiß.

Na jetzt weiss ich, dass zumindest drei Leute es lesen! Danke dafür

Die Aufrufzahlen sind schon in Ordnung für so eine Sache, natürlich freuen mich direkte Rückmeldungen deutlich mehr!

Zitat von Hexworx

Vielleicht solltest du einfach weniger Text schreiben (aber nicht wegen mir). Vielleicht kommt es dann besser an .

Das stimmt wahrscheinlich. Die etwas längeren Abschnitt haben zwei Gründe: zum einen wollte ich pro Abschnitt ein abgeschlossenes Thema beleuchten, zum anderen möchte ich irgendwann auch mal damit fertig werden

Zitat von FXXS

Vier

Oha! Langsam wird es voll hier in der Box...