Em 2017, dois cientistas, o canadense John Aycock e a britânica Tara Copplestone, publicaram uma análise do jogo clássico Entombed para o console de videogame Atari 2600 . A mecânica deste jogo, lançada em 1982, é extremamente simples: o arqueólogo, controlado pelo jogador, deve percorrer as catacumbas rolantes de baixo para cima, esquivando-se de zumbis.
O Atari 2600 tinha apenas 128 bytes de RAM; no entanto, o labirinto aparentemente interminável era novo a cada lançamento; gerado na memória. Como os programadores conseguiram isso? Aqui está um comentário de Stephen Sidley, o programador que criou este jogo há 38 anos:
- . , , . , , , , , .
A Wikipedia lista uma dúzia de algoritmos diferentes para gerar labirintos. De maior interesse para os consoles de jogos é o " algoritmo Eller ", criado no mesmo 1982 por Martin Eller da Microsoft. O algoritmo de Eller permite criar labirintos conectados linha por linha, sem loops, e gerar um labirinto de altura ilimitada, basta armazenar apenas as últimas duas linhas na memória. Parece que é exatamente isso que o Entombed precisa! Mas, infelizmente, o algoritmo de Eller é incompatível com a mecânica do jogo de um scroller vertical, porque no labirinto resultante você regularmente precisa contornar obstáculos de cima. Para demonstrar isso, modifiquei levemente o algoritmo de Eller para que o labirinto seja criado em uma matriz de "paredes" e "passagens", como em Entombed:
Algoritmos mais sofisticados usando recursão e similares não caberiam em 128 bytes de RAM. Portanto, os requisitos para o algoritmo do Entombed são:
- Geração linha por linha de labirintos de altura ilimitada;
- Os labirintos criados devem ter o menor número possível de seções desconectadas; (o jogador tem uma capacidade limitada de "romper paredes", portanto, incoerência rara não é um problema)
- Labirintos criados devem consistir principalmente em ramificações e conexões verticais - para que a passagem do labirinto não exija um movimento ascendente;
- Apenas as últimas linhas geradas devem ser usadas para gerar novas linhas do labirinto. (Como o Atari 2600 não possui um buffer de vídeo, todas as linhas do labirinto visíveis na tela devem ser armazenadas de alguma forma em 128 bytes da memória principal).
Quem e como criou esse algoritmo?
Dois cientistas que se autodenominam "arqueólogos de videogame" decidiram iniciar suas pesquisas com Entombed - um jogo sobre um arqueólogo em um labirinto. Durante a pesquisa, eles rastrearam Stephen Sidley e perguntaram qual algoritmo ele usava para gerar o labirinto. Como já mencionado, Sidley disse a eles que mesmo o autor do algoritmo não conseguia se lembrar de qual era seu algoritmo, e o próprio Sidley, ainda mais. Em seguida, os pesquisadores tentaram encontrar o "viciado" que criou esse algoritmo; a segunda metade da história foi encontrada em uma entrevista publicada em 2008:
Entombed [Duncan Muirhead] [Paul Allen Newell]. - , , , . , . , VCS [Atari 2600], . , . , , . , Towering Inferno, usando parte do nosso algoritmo lá e saia. Depois que eu saí, a empresa contratou Stephen Sidley e entregou o gerador de labirinto para ele. Ele teve que excluir uma parte significativa do meu código para abrir espaço para a mecânica do jogo. [No Atari 2600, além das severas restrições à quantidade de RAM e ROM, também é necessário que a geração de cada linha de pixels leve exatamente 76 ciclos da nota do autor ].
Sidley mencionou que o código do gerador de labirinto foi escrito no conjunto 6502 sem nenhum comentário. Isso por si só parece um feito: como observado khim, "o conjunto de comandos é tão limitado e torto que, ao escrever programas, surge a principal questão:" como você pode escrever algo sobre esse milagre? No entanto, os pesquisadores pesquisaram o código do jogo e descobriram que o labirinto é gerado da seguinte forma: para cada uma das oito células da linha gerada, cinco células já geradas são consideradas (três na parte superior e duas na esquerda) e, de acordo com a "tabela mágica", o estado da nova célula é selecionado (passagem, parede ou escolha aleatória). As duas células mais à esquerda estão sempre cheias e não são armazenadas na memória. A metade direita do labirinto é apenas uma imagem espelhada da esquerda.
Uma tabela misteriosa no coração de um algoritmo não resolvido
As propriedades do labirinto gerado dependem do estado do novo conjunto de células para cada cinco gerados anteriormente. Tabela costurada em Entombed, muitos pesquisadores intrigados: "Não notamos nenhuma lei, mesmo quando temos várias maneiras de apresentá-la na forma de um mapa de Karnaugh ". Sidley disse na mesma linha: "Para mim, continua sendo um mistério: não consegui desvendá-lo e o usei como uma caixa preta". No entanto, a ausência de regularidades na tabela é um exagero: por exemplo, no mapa de Karnot, você pode ver que quando c = 1 (a parede no canto superior esquerdo da célula atual), X = 1 (a parede na célula atual) não será gerado .
BBC em seu relatóriosobre “arqueologia digital”, ela recorreu a exageros ainda mais dramáticos: “A mesa é realmente engenhosa: toda vez que você inicia o jogo, um novo labirinto é criado, através do qual você pode ir do começo ao fim. Se os valores nesta tabela fossem ligeiramente diferentes, provavelmente o labirinto se tornaria intransitável. É simplesmente inexplicável. " O repost no hackaday.com é formulado com ainda mais confiança: "Uma mesa misteriosa sempre cria labirintos aceitáveis, mas se você alterar algum pedaço nela, o quebra-cabeça se tornará insolúvel". De fato, o labirinto nem sempre foi coerente, como pode ser visto no vídeo do jogo ; e pequenas alterações na tabela não têm um efeito perceptível nos labirintos resultantes: criei uma versão JavaScript, em que você pode brincar com a "mesa misteriosa" - mude para a direita "em movimento" e observe como o labirinto muda como resultado. Provavelmente, a garantia de conectividade do labirinto, mencionada por Paul Newell em sua entrevista, foi perdida junto com a parte excluída do código.
Arqueologia de jogos de vídeo
John Aycock comentou sobre como o Entombed se tornou o objeto de sua pesquisa: ele preparou uma tarefa de engenharia reversa para seus alunos e escolheu um jogo relativamente pouco conhecido, porque, para jogos populares, os estudantes podiam encontrar código já analisado na rede. Se uma descoberta tão marcante foi encontrada em um jogo escolhido aleatoriamente, isso significa que em quase todos os jogos da época haverá soluções de programação brilhantes, você só precisa ir mais fundo? Stephen Sidley comparou o design do Atari 2600, com seu escasso conjunto de instruções, 128 bytes de RAM e 76 relógios por linha de pixels, a "escalar o Monte Everest sem tanques de oxigênio" : as próprias limitações da plataforma forçaram os programadores a inventar algoritmos engenhosos.
Indo mais fundo não é apenas uma metáfora. A pesquisa em videogames clássicos é complicada tanto pela fragilidade da mídia em que foram gravados quanto pelo tratamento dos jogos antigos como lixo desinteressante. Em 1983, a Atari jogou 47 toneladas de cartuchos Atari 2600 em um aterro - não menos que uma dúzia de caminhões cheios! Esmagados por um rolo de asfalto e derramados com concreto, esses cartuchos permaneceram por trinta anos, até que em 2014 "arqueólogos digitais" receberam permissão para escavar e recuperar os cartuchos sobreviventes. Nenhum dos cartuchos escavados funcionou, mas pelo menos um deles foi restaurado pela soldagem dos componentes.
O comportamento de Atari, que despejou concreto em cartuchos para protegê-los de "ladrões", é muito típico dos detentores de direitos autorais que consignariam seu trabalho mais facilmente ao esquecimento eterno do que sofreriam "lucros perdidos" pelo fato de sua propriedade intelectual ser dada a alguém de graça. Mas talvez não seja tarde demais para proteger a "camada cultural virtual" do século XX, permitindo a cópia gratuita de programas que há muito perdem seu valor comercial?
