Warum ist die Blockgröße oft eine Zweierpotenz?

15

Es gibt viele Minecraft-Klone und ich arbeite an meiner eigenen Implementierung. Ein Prinzip des Terrain-Renderings besteht darin, die ganze Welt in Blöcken fester Größe zu kacheln, um den Aufwand für lokalisierte Änderungen zu verringern.

In Minecraft ist die Chunk-Größe 16 x 16 x 256 so weit wie ich jetzt. Und in Klonen habe ich auch immer Brockengrößen einer Potenz der Zahl 2 gesehen.

Gibt es einen Grund dafür, vielleicht in Bezug auf Leistung oder Gedächtnis? Ich weiß, dass Zweierpotenzen bei Binärcomputern eine besondere Rolle spielen, aber was hat das mit der Blockgröße zu tun?

danijar
quelle
1
Es ist schön, dass Sie es durch zwei teilen und gerade Zahlen zurückbekommen können. (Keine vollständige Antwort, aber etwas Nützliches bei der Verwendung einer Zahl wie 2^n)
ashes999

Antworten:

27

Dies hängt vom Spiel und der für die Blöcke verwendeten Indexierungsstruktur ab. Obwohl es auf einem so hohen Niveau nicht allzu wahrscheinlich ist, dass es viel mit dem Speicher oder einer bestimmten Leistungssteigerung zu tun hat. Höchstwahrscheinlich ist es eine willkürliche Entscheidung, die Größe von Stücken auf vorhersehbare Weise zu bestimmen. Es erlaubt einige Zähl- und Indizierungs-Tricks mit Bit-Verschiebung, die mit Zahlen, die keine Zweierpotenzen sind, nicht möglich wären.

Zum Beispiel ist das Zählen in Zweierpotenzen so einfach wie das Verschieben eines Bits in Binärform:

Dec =  Bin
1   =  000001
2   =  000010
4   =  000100
8   =  001000
16  =  010000
32  =  100000

Wo diese Verknüpfungen verwendet werden, hängt vom Entwickler und dem zu lösenden Problem ab.

Wenn Sie sich für die Größe der Stücke entscheiden und es in keiner Weise darauf ankommt, können Sie auch etwas verwenden, das Ihnen vertraut ist und Vorteile bietet, an die Sie gewöhnt sind.

MichaelHouse
quelle
15

Erstens ist das Multiplizieren mit Zweierpotenzen viel billiger als das Multiplizieren mit einer beliebigen Zahl, da Sie dies durch Bitverschiebung tun können . Meistens kann der Compiler dies für Sie tun. Wenn Sie also "* 16" in Ihren Code schreiben, verschiebt sich der Compiler tatsächlich um vier, und Sie müssen sich keine Gedanken darüber machen - Sie müssen nur die geben Compiler die Möglichkeit, indem Sie Ihre Datenstrukturen auf diese Weise gestalten.

Zweitens, da Cache-Zeilen, Speicherbusse und andere Datenautobahnen in Ihrem Computer in der Regel ebenfalls auf Zweierpotenzen ausgelegt sind, können Sie auf diese Weise insgesamt eine bessere Leistung erzielen.

Drittens sind wir alten Geeks einfach daran gewöhnt, mit Zweierpotenzen herumzuspielen, also ist es eine Gewohnheit.

(Viertens mögen auch andere alte Geeks, die Ihre Hardware und Ihre Compiler entwickeln, Potenzen von zwei, so dass sich dies in Kürze nicht ändern wird.)

Jari Komppa
quelle
2
+1 "Drittens sind wir alten Freaks einfach daran gewöhnt, mit Zweierpotenzen herumzuspielen, also ist es eine Gewohnheit." Dies ist wahrscheinlich der Hauptgrund.
Laurent Couvidou
9

Die eigentliche Antwort lautet: Auf einem Binärcomputer sind Zweierpotenzen schöne runde Zahlen.

Wenn eine normale Person aus irgendeinem Grund eine willkürliche Zahl wählen muss, wählt sie normalerweise nette runde Zahlen in dem Zahlensystem, mit dem sie vertraut ist (Basis 10). Sie wählen also 10, 100, 1000 usw., weil sie einfach und leicht und erfordern nicht viel Nachdenken und der genaue Wert war für sie nicht wirklich wichtig, sie zielten nur auf eine allgemeine Größenordnung.

Wenn wir als Programmierer aus irgendeinem Grund eine willkürliche Zahl auswählen müssen, wählen wir normalerweise schöne runde Zahlen in dem Zahlensystem, das Computer verwenden, Basis 2. Also wählen wir 2, 4, 8 usw. aus, weil sie einfach und unkompliziert sind einfach und erfordern nicht viel Nachdenken und der genaue Wert war uns nicht wirklich wichtig, wir strebten nur eine allgemeine Größenordnung an.

Es ist wirklich nicht komplizierter. Das sind nur schöne runde Zahlen.

Trevor Powell
quelle
6

Ein in anderen Antworten nicht genannter Grund ist, dass Potenzen von zwei Zahlen bei Bedarf immer halbiert werden können, ohne dass Rundungsprobleme auftreten. Dies ist wahrscheinlich kein Grund für Minecraft-Klone, ist aber in einigen anderen Fällen wie bei Texturen mit Mipmaps der Fall .

msell
quelle
2

Ein weiterer möglicher Grund wäre, dass Sie damit Informationen zu jedem Chunk in einer 3D-Textur kodieren können. Wenn Ihre Zielhardware 3D-Texturen unterstützt, aber keine vollständig robuste und allgemeine Nicht-Zweierpotenz-Texturunterstützung bietet (für die Sie zugegebenermaßen ziemlich wenig fotografieren möchten), ist es nicht sinnvoll, die Zweierpotenzen Ihrer Chunk-Größen zu erreichen einfach ideal - es ist wichtig.

Maximus Minimus
quelle