Por que o tamanho do pedaço geralmente é uma potência de dois?

15

Existem muitos clones do Minecraft por aí e estou trabalhando na minha própria implementação. Um princípio de renderização do terreno é agrupar o mundo inteiro em pedaços de tamanho fixo para reduzir o esforço de alterações localizadas.

No Minecraft, o tamanho do pedaço é 16 x 16 x 256, tanto quanto eu agora. E nos clones, também sempre vi tamanhos de pedaços de uma potência do número 2.

Existe alguma razão para isso, talvez desempenho ou memória relacionada? Eu sei que os poderes de 2 desempenham um papel especial em computadores binários, mas o que isso tem a ver com o tamanho do bloco?

danijar
fonte
11
É bom que você possa dividi-lo por dois e obter números pares de volta. (Não é uma resposta completa, mas algo útil sobre como usar um número como 2^n)
ashes999

Respostas:

27

Isso dependeria do jogo e da estrutura de indexação usada para os pedaços. Embora, em um nível tão alto, não seja muito provável que tenha muito a ver com memória ou um aprimoramento de desempenho específico. Muito provavelmente, é uma decisão arbitrária para dimensionar pedaços de maneira previsível. Ele permite alguns truques de contagem e indexação usando deslocamento de bits que não seria possível com números que não são dois.

Por exemplo, contar em potências de dois é tão fácil quanto mudar um pouco em binário:

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

O local em que esses atalhos serão usados ​​dependerá do desenvolvedor e de qual problema ele está tentando resolver.

Se você está tomando uma decisão sobre qual tamanho criar os pedaços, e isso não importa em nenhum outro aspecto, você também pode usar algo familiar e com benefícios que está acostumado a usar.

MichaelHouse
fonte
15

Primeiro, multiplicar por potências de dois é muito mais barato do que multiplicar por um número arbitrário, pois você pode fazer isso mudando pouco . Na maioria das vezes, o compilador pode fazer isso por você; portanto, sempre que você escreve "* 16" em seu código, o compilador na verdade faz uma troca de quatro e você não precisa se preocupar com isso - basta fornecer o compile a oportunidade projetando suas estruturas de dados dessa maneira.

Segundo, como as linhas de cache, barramentos de memória e outras estradas de informações em seu computador também tendem a ser projetadas para usar potências de dois, é possível obter um desempenho geral melhor dessa maneira.

Terceiro, nós, velhos geeks, estamos acostumados a brincar com poderes de dois, então é um hábito.

(Quarto, outros geeks antigos que projetam seu hardware e seus compiladores também gostam de potências de dois, então isso não vai mudar tão cedo).

Jari Komppa
fonte
2
+1 "Terceiro, nós, velhos geeks, estamos acostumados a brincar com poderes de dois, então é um hábito." Esta é provavelmente a principal razão.
precisa saber é o seguinte
9

A resposta real é apenas esta: em um computador binário, potências de dois são números redondos agradáveis.

Quando uma pessoa normal precisa escolher um número arbitrário para algum propósito, geralmente escolhe números agradáveis ​​no sistema numérico com o qual se sente confortável, base 10. Portanto, escolhe 10, 100, 1000 etc. simples e fácil e não exigem muita reflexão e o valor exato não era realmente importante para eles, eles estavam apenas visando uma escala geral de magnitude.

Como programadores, quando precisamos escolher um número arbitrário para alguma finalidade, geralmente escolhemos números redondos agradáveis ​​no sistema de números que os computadores usam, base 2. Portanto, escolheremos 2, 4, 8 etc. Porque são simples e fácil e não exige muita reflexão e o valor exato não era realmente importante para nós, estávamos apenas visando uma escala geral de magnitude.

Realmente não é mais complicado do que isso. Eles são apenas bons números redondos.

Trevor Powell
fonte
6

Uma razão não mencionada em outras respostas é que, se necessário, potências de dois números sempre podem ser reduzidas pela metade sem problemas de arredondamento. Provavelmente, essa não é uma razão nos clones do Minecraft, mas em alguns outros casos, como nas texturas com mipmaps .

msell
fonte
2

Outro motivo potencial seria o fato de permitir codificar informações sobre cada pedaço em uma textura 3D. Se o seu hardware de destino suporta texturas 3D, mas não possui um suporte de textura totalmente robusto e sem potência de duas (que eu admito que você gostaria de fotografar bastante baixo), então fazer com que o tamanho das suas partes seja de duas ideal - é essencial.

Maximus Minimus
fonte