Snake kennt ja hoffentlich jeder :)
Ich möchte dieses kleine Spiel auf einem Atmega48 mit einem 64*32
Display reaslisieren.
Das Problem: Wie mache ich das möglichst ram freundlich?
Natürlich soll man das ganze Spielfeld mit der "Schlange" füllen können.
Der Inhalt des Displays passt zwar komplett in das Ram des
Atmega48(512byte Ram, 256 byte beschreiben das Display komplett) aber
zum Snake Spiel gehören ja noch mehr Informationen. Nämlich in welcher
Reihenfolge die Elemente der Schlange liegen. Also paktisch eine
verkettete Liste.
Meine bisher ram freundlichste Idee: Startpunkt, Endpunkt und Anzahl der
Elemente in einem der 32 universal Register speichern. Dann im Ram in
jeweils 2 bit codiert die Richtung in der das nächste Element liegt.
Damit passt die Schlange komplett in 512byte Ram....aber ich brauch noch
nen bisschen Platz für den Stack und sonstiges Gedöns ;)
Hat irgendjemand ne bessere Idee?
Das ist sehr heftig kalkuliert mit 256byte fürs Display!
Ich sage nicht, dass es unmöglich ist mit 512- ABER es ist wesentlich
einfacher, wenn du einfach einen anderen Controller dir suchst^^
oder Externen Ram anschließen
Hab ich schon, aus Sichbarkeitsgründen ist ein Element 2*2 Pixel groß
(ist ein 128*64 Display)
Mit dem Rand ist natürlich eine Idee. Wobei ich mich da ja vor dem
Problem drücke und es nicht löse ;) Eine elegantere Ram Nutzung wäre mir
natürlich lieber.
Naja, es reicht eigentlich aus, wenn man jedes Feld durch ein Bit
darstellt (Schlange auf Feld/Schlange nicht auf Feld). Zusätzlich
müsstest Du die Position des Kopfes speichern und die Richtung, in die
sich dieser im nächsten Schritt bewegen wird. Dazu kommt noch das
Objekt, dass die Schlange fressen soll. Diese Informationen reichen aus.
Du musst dann nur in jedem Spielschritt die Schlange im Speicher
"entlangparsen" und dabei selbst schauen, wo sie weiterverläuft. Das ist
natürlich mit mehr Aufwand bzw. Rechenzeit verbunden, als mit deiner
2-Bit-Richtungscodierung. Spart aber eben die Hälfte beim Speichern des
Spielfeldes.
Chris schrieb:> Naja, es reicht eigentlich aus, wenn man jedes Feld durch ein Bit> darstellt (Schlange auf Feld/Schlange nicht auf Feld)
Unsinn, das reicht nicht! Man braucht auch die Reihenfolge.
@Chris:
Ich verstehe nicht ganz was du meinst. Kannst du das nochmal
anders/genauer erklären? Wo ist in deiner Speichermethode die Richtung
enthalten? Woher weiß ich, welches Element gelöscht wird (klar, das
letzte) und welches Element das neue letzte wird? Jede Bewegung besteht
ja aus dem Löschen des letzen Elements und dem Anfügen eines neuen
Elemts am Kopf. Das Futter lassen wir mal kurz außen vor...wobei das
eigentlich nur dazu führt, dass das letzte Element einmal nicht gelöscht
wird.
Also ich bekomme 5 (garantiert) bis 5,7 Pixel (Mittelwert) in ein Byte.
Damit würdest Du mit 360-410 Bytes auskommen. Ich halte die
Vorgehensweise aber für falsch.
Eigentlich müsste man eine Statistik darüber erstellen, wie lang im
Schnitt die geraden Strecken sind und danach dann eine Kodierung
festlegen. Denn ich denke es ist unwahrscheinlich, daß man jeden Pixel
'abbiegt'.
Wichtig ist also die Länge zu kodieren, nicht jeden Pixel.
Folgende Kodierung halte ich für sinnvoll:
Paketgröße 4 Bit
Zwei Bit für Strecke:
1=1 Pixel, 3=3 Pixel, 0 Pixel bewegt man sich nicht, also 0=4 Pixel
Zwei Bit für Richtung:
00 = gerade
01 = links
10 = rechts
11 = auch diese Information sollte genutzt werden und bedeutet auch
gerade, aber 4 Pixel mehr, als in Strecke angegeben. So ist eine Distanz
von bis zu 8 Pixeln machbar.
Alternativ die 16 Kombinationen auch losgelöst von den Bits benutzen:
0-4 = 1-5 Pixel und links
5-9 = 1-5 Pixel und rechts
A-F = 1-6 Pixel und gerade
Diese Art findet von selbst kein Ende. Die Länge muß an einer anderen
Stelle notiert werden.
oder:
:
A-E = 1-5 Pixel und gerade
F = Ende
Auch damit wirst Du vermutlich nicht über 6 Pixel pro Byte kommen. bei
langen, geraden Strecken schon, aber wenn Du viel und schnell abbiegst
nicht.
So ist Deine Schlange bei z.B. 100 Byte auf 200 Segmente mit jeweils
max. 5 Pixeln (mit oder ohne Knick) begrenzt. Also bis zu 1000 Pixel
lang, im Schnitt geschätzt nur ca. 60% davon.
Bei 256 Byte geschätzt bis zu 1500 Pixel.
Reicht vermutlich, das ist 3/4 des Spielfeldes.
Oooooder ...
Du benutzt 2 Bit pro Pixel direkt im FrameBuffer:
00 = Pixel leer
01 = Pixel gesetzt und Schlange biegt nach links
10 = rechts
11 = gerade
Dann sind zwar alle 512 Byte weg, dafür musst Du den Frame nicht jedes
Mal neu zeichen. (spart Code)
Stack und Interupts entfallen dann allerdings, also alles pollen :-)
Alle anderen Infos musst Du dann in den Registern und in ungenutzten
SFRs speichern.
Gruß
Jobst
Du mußt erstmal den Startpunkt und die Anzahl der Elemente speichern (4
Byte).
Und dann hast Du ein Array, wo die Richtungsänderung und die Anzahl bis
zur Richtungsänderung gespeichert wird.
Die Anzahl als 6 Bit, damit reicht ein Byte. D.h. nach 63 Elementen
erfolgt eine Dummy-Richtungsänderung.
Mehr als 256 Richtungsänderungen werden wohl kaum nötig sein.
Dann hast Du noch ein Array, wo das Futter gespeichert wird (20 Einträge
sollte reichen).
Peter
Peter Dannegger schrieb:> Du mußt erstmal den Startpunkt und die Anzahl der Elemente speichern (4> Byte).>> Und dann hast Du ein Array, wo die Richtungsänderung und die Anzahl bis> zur Richtungsänderung gespeichert wird.> Die Anzahl als 6 Bit, damit reicht ein Byte. D.h. nach 63 Elementen> erfolgt eine Dummy-Richtungsänderung.> Mehr als 256 Richtungsänderungen werden wohl kaum nötig sein.>> Dann hast Du noch ein Array, wo das Futter gespeichert wird (20 Einträge> sollte reichen).>>> Peter
Für die Richtungsänderung müsste auch 1 Bit reichen:
- Die Schlange kann nur 3 Richtungen links, geradeaus & rechts.
- kodiere man nun wie Peter vorgeschlagen hat die Länge eines Teilstücks
in 6 Bits haben ich 64 Möglichkeiten, nun hat Eumel das Spielfeld auf
64*32 begrenzt. Wenn also das Teilstück 63 lang ist, beist sich die
Schlange beim nächsten Zug selbst.
-- Also kann ich mir die Richtung geradeaus sparen und es bleiben nur
noch links & rechts übrig.
Das 7. Bit könnte man nutzen um zum Beispiel 2 kurze Teilstücke (>=6) in
einem Byte zu kodieren, so spart man wieder etwas RAM.
Ausserdem würde ich wie bei einem String das Array mit 0 terminieren,
d.h. 0 = Ende der Schlange.
Oder habe ich da noch was übersehen?
Mal ganz ehrlich, in Zeiten, wo ein AVR nur n paar Euro kostet, ist doch
sowas sehr unsinnig, wenns ein Einzeslstück ist.
Es sei denn, dich interessiert hier wirklich wie man es kleiner bekommt
und nicht wie DU es in den AVR bekommst.
Guck mal hier:
http://www.atmel.com/dyn/products/param_table.asp?category_id=163&family_id=607&subfamily_id=760
Da gibts zig AVR mit 32Pins und mehr als 512B RAM. Mega168 z.B.
Ich finde, gerade bei Neuentwicklungen sollte man bei sowas erstmal
nicht geizen, dann bleibt immer noch genug Platz für Erweitungen.
Grüße,
Ingo
Was fuer'n idiotischer Einfall. Fuer ein Stueck. Man spart die 5 Euro
fuer einen Mega644, und blaest dafuer Tage raus, um einen
RAM-Sparalgorithmus zu finden...
Ingo schrieb:> Ich finde, gerade bei Neuentwicklungen sollte man bei sowas erstmal> nicht geizen, dann bleibt immer noch genug Platz für Erweitungen.
Hehe sehe ich auch so, hab mir letztens ein Board mit ATMega2560 und
ext. RAM gemacht. Das Projekt dazu ist in der Grundform so gut wie
fertig, mit reichlich Debug-Strings gerade einmal 64K groß.
Den Rest kann ich nun für schöne Spielereien verwenden ;)
Hi,
ich hatte mal vor ~10 Jahren einen Snake Clone auf einem graphischen
Taschenrechner programmiert. 512 byte sind schon ziemlich mager.
Meine Lösung war damals:
- ein Array mit 250 Zeilen und 2 Spalten.
- eine Countervariable
- eine Variable, die die Schlangenlänge dargestellt hat.
Die Countervariable startete bei 0 und es wurde dann die x & y
Koordinaten in die Counterzeile des Arrays geschrieben.
Wenn man bei 249 angekommen war, wurde der Counter auf 0 zurück gesetzt.
Damit die Schlange eine definierte Länge hatte, wurde immer das altuelle
Pixel des Bildschirms gesetzt und dann die Koordinaten des Pixels, der
gelöscht werden muss über die Tabellenzeile Counter-Schlangenlänge
geholt und gelöscht.
Wenn der Akuelle Pixel auf deiner Frucht oder was auch immer gelandet
ist, wurde die Schlangenlängenvaribale um 2 erhöht.
Natürlichen war noch ein Ansteuerungsanteil für die Richtungen, eine
Kollisionsabfrage und ein wenig Spagetticode dabei. Auserdem musste
darauf geachtet werden, dass beim Array Überlauf das Schlangenende nicht
bei der Zeile -10 sondern bei 240 war.
Das Programm hatte den Nachteil, dass wenn die 250 Zeile verbraucht
waren, die Schlange sich fröhlich abgelöst hatte und eine neue gestartet
hatte.
Vielleicht kannst du das Array mit den Koordinaten optimieren, es gibt
ja nur 64*32 = 2048 Möglichkeiten. Also würden für die Koordinaten
theoretisch 11 Bit reichen.
Hoffendlich verständlich und ein paar interessante Infos dabei.
Gruß,
Dimpflmoser
Evtl gibt es auch noch eine Möglichkeit von der aktuellen Koordinate auf
das Schlangenende zurückrechnen zu können, in dem man bei jedem
Richungswechsel in ein Array einmal ein Bit setzt für 0=rechts 1=links
und in einem Zweiten Array die Länge des geradeausfahrens speichert.Wenn
allerdings ständig links und rechts gefahren wird, ist auch dafür ein
großes Array nötig.
erstmal vielen Dank für die tollen Vorschläge :)
Mal sehen ob mir selbst noch was einfällt, um das ganze Spielfeld mit
der Schlange zu füllen, egal wie deren Form ist. Bei einer sehr langen
und verwinkelten Schlange würden ja die vorgeschlagenen Methoden
versagen.
Vielleicht nehm ich auch einfach den lahmen Ansatz und verkleiner das
Spielfeld durch einen Rand. Wären dann 465 byte für die Schlange...47
byte für den Stack. Das sollte reichen.
Also wenn Du wirklich daran festhältst, für jeden Pixel die Richtung zu
notieren und dies auch für die komplette Füllung des Feldes vorsiehst,
dann sind das 2048 Informationen mit je drei Zuständen (3^2048). Diese
Information kannst Du in 406 Byte unterbringen (2^(406*8)).
Das sind 5,044 Pixel pro Byte.
Da wäre ich dann mit meiner Lösung, 5 Pixel in ein Byte zu bringen schon
recht dicht dran. 3^5 Bekommst Du in ein Byte.
Dann hast Du weitere 55 Byte Platz :-)
Aber bedenke, daß Du die Schlange auch malen und zum Display
transportieren musst, das 'Bild' also irgendwie zumindest in Stücken im
RAM haben musst.
Gruß
Jobst
Und ich bin so froh, dass ich nicht mehr mit jedem Bit oder Byte geizen
muss...
Es gab Zeiten, da musste ich das. Und es ergab sich auch eine gewisse
Befriedigung, scheinbar unmögliches doch möglich gemacht zu haben.
Heute ist es für mich effektiver, nahezu kostenlose Ressourcen zu nutzen
und sich die Zeit zu sparen.
Joachim, das ist mir klar. Aber ich mach das ganze ja in keinster weise
beruflich sondern nur aus privatem Vergnügen, da sei mir die Frickelei
gegönnt :)
Darf die Länge der Schlange begrenzt werden? Ich kenne zumindest eine
Version, wo die Schlange nach dem 30. Apfel nicht mehr wächst. Oder
alternativ nach dem 10. Apfel das Level gelöst ist.
Wäre dies möglich, so lässt sich die Schlange in O((n*c)/2+2) byte
kodieren:
- nach einer horizontalen ausrichtung folgt eine vertikale und vice
versa
- ein byte enthält die endkoordinate
- ein byte die länge der schlange
- die (n*c)/2 Bytes sind Eckkanten dabei muss wie ein Vorposter bereits
schon beschrieb abwechselnd nur die x und y Koordinaten geschspeichert
werden. das c kommt von der möglichen anzahl der Richtungswechsel pro
Verlängerung.
Durch diese Art der kodierung ist so auch ein Multiplexen z.B. leicht
realisierbar (organisation in Spalten und Reihen).
Bei einer Schlange mit 30 Verlängerungen und 5Pixeln "Verlängerung"
komme ich so auf 30*5/2 + 2 auf 77 Bytes für die Schlange... ähnlich
kann man dann auch die Level designen... dann ist noch genug Platz für
Scoring, Stack etc...
Desweiteren: Das Display wurde schon 2 mal angesprochen: Falls der Ram
auslesbar ist und vllt noch einen Framebuffer hat kommst du so schnell
an extra Ram...
Und nun noch meine kleine private Meinung hinsichtlich Resourcen und den
sinnigen Einsatz: im privaten Einsatz, und wenn die Resourcen eh schon
da sind ist es legitim sie zu nutzen, jedoch wenn SW weitergegeben wird
(z.b. eine Lib) sollte man penibelst darauf achten, wie man damit
umgeht... das ist mitunter die schlimmste Seuche der Informatik.
Programme sind immer mehr schichten basierend und wenn man schon in der
untersten ebene speicherplatz verschwendet und dieses in jeder iteration
zusätzlich draufgeht, so muss man sich nicht wundern, wenn ein Programm
was eine Zahl hochzählen lässt mal eben ein MB im Speicher frisst...
aber ok - das ist nicht umbeding ein µC Thema ;-)
@H.joachim Seifert: Sieh es wie Kreuzworträtsel lösen :-)
@Lehrmann Michael: Ich habe hier ausgerechnet 128x64 LCDs liegen, die
man nur optisch auslesen kann. Elektrisch kann man nur darauf schreiben.
Das DOGM128 gehört auch dazu.
Gruß
Jobst
