Erschienen in 64'er Magazin, Ausgabe 11/1993 · Originaldatei: BESTENLI.TXT

Hinweis: Dies ist das an die Redaktion eingereichte Manuskript, nicht der gedruckte Endtext. Layout, Bildunterschriften, Korrekturen und Kürzungen der Redaktion können in der veröffentlichten Fassung abweichen.

Basic-Corner

Bestenlisten

Diesmal zeigen wir Ihnen, wie man die »Bestenlisten« in Spielen programmiert. Sie lernen einiges über Strings sowie Arten des Dateizugriffs. Wie immer verraten wir dabei auch einige sehr interessante Tricks.

Nikolaus M. Heusler

In dieser Folge wollen wir ein Programm entwickeln, das sich ausgiebig auf Stringverarbeitungen stützt und außerdem Einblick gewährt, wie die in vielen kommerziellen Spielen eingebauten »Bestenlisten« funktionieren. Wie immer werden wir das Programm Stück für Stück entwickeln, wobei die einzelnen Teile im Prinzip für sich funktionsfähig sind. Bitte verwenden Sie für Ihre Experimente die von uns vorgegebenen Zeilennummern!
Die Bestenlisten - englisch »High Score« genannt - enthalten die besten Ergebnisse, die in einem Spiel erzielt wurden. Dabei gibt es drei prinzipielle Unterschiede:
- die ewige Bestenliste
- die persönliche Bestenliste
- die Tages-Bestenliste
Die ewige Bestenliste beruht darauf, daß der jeweils letzte Stand am Ende eines Spieldurchgangs auf Diskette gespeichert wird. Zu Beginn einer neuen Runde wird er geladen und steht dann zur Verfügung. Die persönliche Bestenliste unterscheidet sich von der ewigen Bestenliste nur darin, daß hier jeder Spieler nur einmal erfaßt ist - natürlich mit seinem persönlichen besten Ergebnis. Die Tages-Bestenliste ist eigentliche eine ewige Bestenliste, sie wird jedoch nicht auf Diskette gespeichert, sondern enthält nur das Ergebnis einer »Session«.
In unserem Fall werden wir nur die ersten beiden Typen betrachten. Möchten Sie eine Tages-Bestenliste realisieren, lassen Sie einfach die Programmteile für den Diskettenzugriff weg. Sehen wir uns erst einmal eine ewige Bestenliste als Beispiel an:

EWIGE BESTENLISTE

1. HEINZ 678
2. HEINZ 567
3. HEINZ 503
4. NICKI 445
5. KATJA 440
6. NICKI 390
7. HEINZ 377
8. PETER 50
9. KATJA 33
10. AXEL 9

PERSÖNLICHE BESTENLISTE

1. HEINZ 678
2. NICKI 445
3. KATJA 440
4. PETER 50
5. AXEL 9

Heinz ist also eindeutig der Beste, vielleicht weil er häufig spielt. In der ewigen Liste hält er die ersten drei Plätze. Auch Katja hat gute Ergebnisse und steht zweimal in der Liste. In der persönlichen Liste dagegen ist jeder nur einmal vertreten, natürlich mit seinem besten Ergebnis. Damit liegen die Sortiervorschriften eigentlich schon fest.

Sortiervorschriften

Ewige Bestenliste: Ein neues Ergebnis wird mit der ersten Eintragung der Liste verglichen. Ist es größer, kommt es an dessen Position, die restlichen Werte rücken um einen Platz nach hinten, und der Vorgang wiederholt sich mit dem nächsten Wert der Liste. Ist es gleich oder kleiner, dann wird sofort der nächste Listenplatz zum Vergleich verwendet. Ist das Ergebnis kleiner oder gleich als der unterste (letzte) Eintrag, so erscheint beispielsweise die Meldung »dieses Mal hat es leider nicht für einen Highscore gereicht«. Der Name des Spielers, der dieses Ergebnis erzielt hat, wird sonst an die selbe Position der Liste gebracht, unabhängig davon, wie oft er schon in der Liste steht. Damit kann ein einziger Spieler die komplette Bestenliste belegen.
Bei der persönlichen Bestenliste prüfen wir erst einmal, ob dieser Spieler schon einmal in der Liste steht. Wenn nein, wird sein Wert wie oben beschrieben der Größe nach einsortiert. Gibt es jedoch schon einen Eintrag für diesen Spieler, testen wir jetzt, ob er sich selbst übertroffen hat. Wenn nein (altes Ergebnis größer oder gleich dem neuen Resultat), geben wir die Meldung aus »Leider waren Sie schon einmal besser!«, und verzichten auf den Eintrag. Hat sich der Spieler jedoch verbessert, löschen wir den alten Eintrag und rücken die verbleibenden Werte in der Liste um eins nach oben nach. Sodann wird das neue Ergebnis wie gehabt der Größe nach einsortiert.
Aus diesen Vorschriften, aber auch beim Betrachten der beiden Listen wird deutlich, daß wir uns für das Problem der Zuordnung von Namen, Platznummern und Ergebnissen etwas einfallen lassen müssen. Allein der Name »Heinz« belegt vier Plätze in der Liste mit vier unterschiedlichen Ergebnissen. Das klingt aber schlimmer als es ist.
Das erste Beispielprogramm (Listing 1) realisiert eine ewige Bestenliste mit 15 Einträgen. Das Ablaufdiagramm (Bild) verdeutlicht die Vorgänge nochmals. Die besonders gekennzeichneten Bereiche werden nur für die persönliche Bestenliste benötigt. Die Bestenliste soll als Feld (Array, indizierte Variable) gespeichert werden. In Zeile 210 reservieren wir für 15 Namen und 15 Ergebnisse zwei Variablenfelder: NA$(I) für den Namen von Platz I und PU(I) für die Punkte zu Platz I (I von 1 bis 15). »I«, also die Nummer der Variablen, die wir ansprechen wollen, heißt der »Index« in das Feld. Hier wird auch der Bildschirm gelöscht (Code 147). Damit die Liste zu Beginn des Programms definiert ist, weisen wir ihr in Zeile 220 spezielle Werte zu. Alle Namen werden auf »(LEER)« gesetzt, die Punkte vergeben wir von 30 bis 2 im Zweierschritt (Platz 1: 30 Punkte, Platz 2: 28 Punkte, Platz 3: 26 Punkte und so weiter bis Platz 15: 2 Punkte).

Verwenden einer alten Liste

Jetzt wird die Frage gestellt, ob eine auf Diskette gespeicherte alte Liste geladen werden soll: Gerade das ist ja die besondere Eigenschaft einer »ewigen« Liste. Gibt der Anwender N ein, geht es sofort im Hauptteil (Zeile 310) mit der Ausgabe der Bestenliste weiter. Sonst eröffnen wir eine sequentielle Datei mit dem Namen »BESTENLISTE« (bitte nennen Sie daher das Programm anders, falls Sie es auf der selben Diskette speichern möchten!) zum Lesen geöffnet. Die Schleife in Zeile 280 liest alle 15 Einträge ein. Hier findet keine Prüfung statt, ob die Liste auf Diskette existiert.
Ab Zeile 310 soll die Highscore-Liste auf dem Bildschirm ausgegeben werden. Eine FOR..NEXT-Schleife klappert die Plätze 1 bis 15 der Reihe nach ab. Zeile 330 druckt vor dem Namen des Spielers auf diesem Platz die Platznummer rechtsbündig (Einer unter Einer, Zehner unter Zehner) aus. Durch die RIGHT$-Funktion stellt man sicher, daß die Länge der Platznummer immer zwei Zeichen beträgt. Bei Nummern über 10 schneidet diese Funktion nämlich das führende Leerzeichen, welches die STR$-Funktion einfügt, ab. Aus »(SPACE)14« wird »14«. Zeile 340 gibt abhängig von der Länge des Namens so viele Punkte aus, daß alle Punktwerte untereinander stehen. Die Scores geben wir in Zeile 350 formatiert (rechtsbündig) aus.
Jetzt beginnt die Eingabe des Namens und des Ergebnisses, das dieser Spieler erzielt hat (in Punkten). Wird als Name der Text »STOP« eingegeben, springt das Programm in Zeile 440 in die Zeile 810. Dort kann, falls der Anwender dies wünscht, vor Beendigung des Programms die Bestenliste noch auf Diskette gespeichert werden. Die alte Datei wird dabei in Zeile 860 gelöscht.
Anstelle eines Spieles simulieren wir die erreichte Punktezahl per INPUT. Bekanntlich wird der Text in Gänsefüßchen hinter INPUT vor der Eingabe am Bildschirm ausgegeben. In Zeile 450 gibt der Anwender die erreichte Punktezahl ein. Damit nicht, falls ohne Eingabe nur RETURN gedrückt wird, der alte Wert des letzten Spielers übernommen wird, setzen wir die Variable PU vorher auf Null.
Der Zeilenbereich 500 bis 590 fehlt, hier werden wir später die Ergänzung einbauen, die aus der ewigen Bestenliste eine pesönliche Bestenliste macht. Daher geht es mit Zeile 610 weiter. Die Liste wird komplett durchsucht, wo der erste Eintrag steht, der kleiner ist als das aktuelle Ergebnis. Damit wäre dann der Platz bekannt, wo der neue Eintrag stehen soll. Gibt es keinen Eintrag, der kleiner ist als das aktuelle Ergebnis, dann »reicht« es leider nicht für einen Highscore, nach einer entsprechenden Meldung in Zeile 640 geht es dann mit der Ausgabe der Bestenliste von vorn los.

Georg schafft 400

Nehmen wir einmal an, Georg hat gespielt und 400 Punkte erhalten. Betrachten Sie die obige Beispiel-Liste: Georg ist nicht so gut wie Katja mit 440 Punkten, aber besser als Nickis 390 Punkte. Georg sollte also auf Platz 6 eingetragen werden. Die Variable I (Zeile 620) enthält in diesem Beispiel den Wert 6. Die alten Plätze 6 bis 10 (oder im Programm 15) rücken also um eins nach unten. Der unterste Eintrag (Platz 15) fällt aus der Liste weg.
Schaffen wir also ab Eintrag I Platz für Georgs Ergebnis. Wir fangen unten an (Zeile 710: K=15) und tasten und Schritt für Schritt nach oben, bis wir bei Platz I angelangt sind. In Zeile 730 wird der Eintrag an der ehemaligen Position K-1 um eins nach hinten verschoben (Stelle K), und zwar sowohl der Name NA$(K) wie auch die Punktezahl PU(K). Beim freigewordenen Eintrag setzen wir in Zeile 740 das neue Ergebnis ein, wieder Namen und Punktezahl. Damit ist die Bestenliste auf dem neuesten Stand, und kann nach einer entsprechenden Meldung (Zeile 750) wieder gezeigt werden.
Eigentlich ist es nicht mehr, was Sie brauchen, um eine Bestenliste zu programmieren. Das Programm ist damit komplett. Einige Hinweise vielleicht noch: Wie man sieht, werden die neuen Einträge einfach in die Liste einsortiert. Es findet also keine Sortierung der gesamten Liste statt. Wenn Sie beispielsweise aufgrund eines Programmier- oder Ladefehlers eine Liste haben, in der die Einträge nicht schon der Größe nach stehen, werden beim Neueintrag mit Sicherheit Störungen auftreten. Als kleine Anregung sollten Sie einmal versuchen, das Programm so zu modifizieren, daß nicht eine hohe, sondern eine niedrige Punktezahl ein gutes Ergebnis bedeutet. Wenn also die Einträge nicht beispielsweise für die Anzahl der Punkte stehen, die Sie in einem Spiel errungen haben, sondern etwa für die Zeit, die Sie benötigten, das Spiel zu schaffen, und es darauf ankommt, möglichst schnell zu sein, müssen Sie dafür sorgen, daß die Liste in anderer Reihenfolge sortiert wird. Leicht ist es auch möglich, die Anzahl der Einträge (momentan 15) zu verändern. Dazu ersetzen Sie nur überall im Programm (in den Zeilen 210, 220, 280, 320, 610, 710, 880) die Konstante 15 durch einen anderen Wert ersetzen.

Die persönliche Bestenliste

Kommen wir nun zur zweiten Variante, der persönlichen Liste. Hier ist jeder Spieler nur einmal vertreten, natürlich mit seinem persönlichen Bestergebnis. Aus der ewigen Bestenliste läßt sich sehr einfach die persönliche Bestenliste gewinnen. Dazu arbeiten wir uns Schritt für Schritt in der ewigen Liste vor und geben einen Eintrag nur dann aus, falls dieser Name nicht schon an einem höheren Listenplatz ausgegeben wurde. Die folgende Routine, die Sie, wenn Sie möchten, an Listing 1 anhängen und mit GOTO 1000 aufrufen können, erledigt diese Umrechnung sehr elegant. Im Speicher steht allerdings immer noch nur die ewige Highscore-Liste.
Wir tasten uns also von Platz 1 bis Platz 15 in der ewigen Bestenliste voran. Dazu braucht man eine FOR..NEXT-Schleife:

1000 PRINT "PERSOENLICHE BESTENLISTE:"
1010 FOR I = 1 TO 15
1100 NEXT I
1110 END

Bitte lassen Sie das I hinter NEXT nicht weg. Der erste Platz der ewigen Liste soll immer ausgegeben werden, ein besseres Ergebnis kann es auch in der persönlichen Liste nicht geben. Die Prüfung, ob eine Ausgabe erfolgen darf, können wir uns für I=1 also sparen:

1020 IF I=1 THEN 1060

Ab Zeile 1060 geben wir den Score für den Eintrag Nummer I aus. Dazu kopieren wir die Programmzeilen 330 bis 350:

1060 A$=RIGHT$(STR$(I),2)
1070 PRINT "PLATZ "A$": "NA$(I);
1080 PRINT LEFT$(" {21 PUNKTE}",23-LEN(NA$(I)));
1090 PRINT RIGHT$("{5 SPACES}"+STR$(PU(I)),6)

In Zeile 1100 geht es wie gesehen mit NEXT weiter. Wenn Sie das Programm mit RUN starten, einige Highscores eingeben, dann während der Ausgabe der ewigen Bestenliste (!) mit der Taste RUN STOP unterbrechen, können Sie mit GOTO 1000 die neue Liste ausgeben. Da der Teil zur Prüfung auf Namenswiederholung noch fehlt, wird zunächst einfach nichts anderes als die bekannte ewige Bestenliste gedruckt. Also prüfen wir bei I>1 jetzt, ob dieser Name schon vorher ausgegeben wurde. Falls also NA$(I) an einem Platz kleiner I auftaucht, überspringen wir die Ausgabe und machen direkt mit NEXT weiter. Es läuft auf eine weitere FOR..NEXT-Schleife hinaus:

1030 FOR K=1 TO (I-1)
1040 IF NA$(K) = NA$(I) THEN 1100
1050 NEXT K

Damit die beiden verschachtelten Schleifen korrekt ausgeführt werden, ist es wichtig, daß sowohl in 1050 wie auch in 1100 hinter NEXT der jeweilige Kennbuchstabe (K bzw. I) steht.
Probieren Sie jetzt einmal, aus dem Hauptprogramm auszusteigen und dann mit GOTO 1000 eine Liste auszugeben. Sie werden bemerken, daß jeder Name nur noch einmal ausgegeben wird. Ein kleiner Schönheitsfehler tritt noch auf: Die Plätze sind noch entsprechend der alten Liste numeriert. Eine neue Variable N, die bei jeder Ausgabe um eine hochgezählt und anstelle der Platznummer I gedruckt wird, löst das Problem:

1005 N=0
1060 N=N+1 : A$=RIGHT$(STR$(N),2)

Jetzt können wir aus unserer ewigen Bestenliste eine persönliche Bestenliste machen. Es geht aber auch auf dem direkten Weg. Löschen Sie zunächst die Zeilen 1000 bis 1100 wieder. Wir wollen jetzt das Hauptprogramm so modifizieren, daß es von sich aus eine persönliche Bestenliste verwaltet. Dazu geben Sie - während Listing 1 im Speicher steht - zusätzlich (!) dazu die Programmzeilen von Listing 2, welches alleine nicht funktionsfähig ist, ein. Damit es zu keinen Datenkollisionen auf Diskette kommt, spendieren wir der neuen Liste einen anderen Namen: »BESTENLISTE/P« für »persönlich«. In den Zeilen 270, 860 und 870 wird der neue Name eingetragen.
Überlegen wir, was zu tun ist. Nachdem ein Name und die dazugehörige Punktzahl eingegeben wurde, soll der Eintrag in der persönlichen Highscoreliste nur unter der Bedingung erfolgen, daß dieser Spieler sich selbst verbessert oder noch nie gespielt hat. Zunächst prüft man also, ob es ein »alter Bekannter« in der Liste ist. Zeilen 510 bis 530 testen, ob der gerade eingegebene Name schon einmal in der Liste enthalten ist. Wenn nein, geht es weiter bei Zeile 610, dann wird der Score, falls noch Platz vorhanden ist, ganz normal in die Liste einsortiert. In diesem Fall hat der Spieler zum ersten Mal gespielt.
Wurde jedoch ein Eintrag dieses Namens gefunden, verzweigt das Programm nach Zeile 540. Dort testen wir, ob der bisher in der Liste eingetragene Punktestand, der ja den bisher besten Score dieses Spielers darstellt, kleiner (also schlechter) ist als das neue Ergebnis. Wenn ja, machen wir in 565 weiter. Sonst hat sich der Spieler nicht verbessert, und die Liste darf nicht verändert werden (»Sie waren schon einmal besser«).
Ab Zeile 565 löschen wir den alten Eintrag dieses Spielers aus der Liste. Falls der Spieler beispielsweise zuvor auf Platz 5 stand, wird jetzt Name und Punktezahl von Platz 6 nach Platz 5 kopiert (Zeile 580), dann I um eins erhöht, sodann der Eintrag von Platz 7 nach Platz 6 kopiert, dann Platz 8 nach Platz 7 und so weiter, so lange, bis Platz 15 nach Platz 14 kopiert wurde. I hat jetzt den Wert 15, dadurch verläßt das Programm in Zeile 570 diese Zeile und schreibt - nur zur Sicherheit - in Zeile 590 einen Leertext und den Vermerk »Null Punkte« in den letzten Listenplatz (I = 15).
Der Spieler wurde jetzt mit seinem alten, schlechteren Ergebnis aus der Liste gestrichen, und es kann wie gehabt mit dem neuen Eintrab ab Zeile 610 weitergehen.
Damit wären wir am Ende unseres kleinen Kurses in die weite Welt der Bestenlisten angelangt. Lassen Sie sich von unseren Programmen ruhig dazu anregen, ein wenig mit dieser Thematik zu experimentieren. Vielleicht finden Sie bei Ihren Versuchen weitere interessante, möglicherweise bessere Verfahren, die wir in späteren Ausgaben vorstellen können. Auch für Kritik und Verbesserungsvorschläge finden Sie bei uns immer ein offenes Ohr. Interessant wäre eine Realisierung in Maschinensprache, die man in der »Assembler-Corner« vorstellen könnte.
(hb)