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?
Und die einfachste Anwort: nimm nen Controller mit mehr Ram!! Hab ich nicht da. Und ich bin arm.
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?
Wieviel Speicher hat denn das Display, vielleicht kannst du etwas im CG-RAM o. ä. auslagern. Gruß Roland
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.
Eine Skizzierung wie man das Spielfeld darstellen kann ist in: http://www.avrfreaks.net/index.php?name=PNphpBB2&file=viewtopic&p=901101#901101 Die Schlong wird in Segmente unterteilt; jedes Segment passt locker in 1 Byte: 1 Bit für die Richtung und 7 Bits für Segmentlänge.
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 :)
Haben die Herrschaften mal daran gedacht, dass ein Display auch in gewisser Weise ein Speicher ist der ausgelesen werden kann?
Wenn der Poster die Schlange nicht selbst hinkriegt, ist das GrafikRAM des LCD-Controller jenseits der Moeglichkeiten.
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
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.