Monstro Errante: como se livrar de problemas no mapa

Já no processo de criação de The Witness se tornou um dos meus jogos favoritos. Comecei a tocá-lo a partir do momento em que Jonathan Blow começou a desenvolvê-lo, e mal podia esperar pelo seu lançamento.

Ao contrário do jogo anterior de John Braid , a escala de recursos e programação do The Witness estava muito mais próxima dos projetos AAA do que dos jogos independentes. Todo mundo que trabalha nesses projetos sabe que a quantidade de trabalho na escolha desse caminho aumenta significativamente. Havia muito mais pessoas trabalhando no The Witness do que Braid , mas, como em qualquer projeto desse nível, há muitos aspectos que requerem mais atenção do que o gerenciamento de projetos pode proporcionar.

Portanto, eu sempre quis encontrar tempo livre para ajudar a criar a The Witness no lançamento do jogo. Então, um dia, dia de ação de graças, John e eu nos sentamos e examinamos a lista de coisas na base de código que se beneficiariam de esforços adicionais de outro programador. Tendo decidido a importância relativa dos itens da lista, decidimos que a jogabilidade será mais beneficiada se fizermos melhorias no código de movimento do jogador.

Walkmonster na parede

No contexto de The Witness , o objetivo do código de movimento de um jogador é ser o mais discreto possível. O jogador deve mergulhar completamente em uma realidade alternativa, e nesta experiência de jogo todos os detalhes são importantes. A última coisa que queríamos era que o jogador notasse que ele estava sentado no computador e movendo a câmera virtual.

Portanto, o código de movimento do jogador deve ser absolutamente confiável. Se um jogador se agarra a cantos, fica preso em paredes, cai no chão, desce de uma colina sem a capacidade de voltar etc., isso destrói instantaneamente a ilusão de imersão e lembra ao jogador que ele está dentro de um processo artificial de jogo que é interferido por um sistema não confiável deslocamentos. Em algumas circunstâncias, isso pode levar a conseqüências desastrosas para o jogador, se ele não tiver a oportunidade de resolver o problema reiniciando o jogo ou recarregando a (provavelmente muito antiga) “defesa”. Se você costuma jogar, deve ter encontrado problemas desse tipo e sabe o que quero dizer.

Após nossa discussão, comecei a trabalhar nessa tarefa. Antes de tudo, decidi escrever ferramentas integradas para trabalhar com o código de movimento do jogador, para que possamos analisá-lo e observar seu comportamento atual. Depois de abrir o projeto, me deparei com um problema sério já conhecido por mim: como devo nomear o primeiro arquivo de código-fonte? Essa é sempre a parte mais importante de qualquer projeto ( como Bob Pollard disse uma vez sobre os nomes de grupos musicais e álbuns ). Se você der um nome adequado ao arquivo de origem, os trabalhos futuros serão claros e suaves. Escolha o errado - você pode destruir todo o projeto.

Mas qual é o nome do sistema para garantir a qualidade do código de movimento do jogador? Eu nunca tive que escrever um código como esse antes. Quando pensei nisso, percebi que pessoalmente vi um exemplo desse código apenas uma vez: ao jogar a versão beta inicial do Quake . Ele continha bugs com a localização dos monstros, e na janela do console você podia ver mensagens de erro informando que os monstros, em vez de criar na superfície da Terra, são criados, parcialmente se cruzando com a geometria dos níveis. Cada mensagem de depuração começou com a frase "walkmonster in wall at ..."

Bingo! É difícil encontrar um nome melhor para o arquivo de código do que "walk_monster.cpp". E eu tinha quase certeza de que a partir de agora o código seria criado sem problemas.

Movimento ao ponto

Quando você deseja testar o sistema, o mais importante é realmente testá-lo . Embora essa regra pareça simples, as pessoas que escrevem testes geralmente não cumprem.

No nosso caso particular, é muito fácil imaginar que estamos testando o código de movimento de um jogador sem realmente testá-lo. Aqui está um exemplo: você pode analisar o volume de colisões e superfícies nas quais pode se mover no jogo, procurar pequenas superfícies, lacunas, etc. Tendo eliminado todos esses problemas, podemos dizer que agora o jogador pode se mover e caminhar com segurança pelo mundo.

Mas, na verdade, testamos os dados, não o código. É muito provável que haja erros no código de movimento que levem a um comportamento ruim, mesmo com dados de alta qualidade.

Para evitar essa armadilha, eu queria que o sistema de testes estivesse o mais próximo possível do comportamento da pessoa que realmente controla o movimento do personagem no jogo. Comecei escrevendo dois procedimentos que se tornariam os alicerces de tais testes.

O primeiro procedimento é o mais próximo das ações humanas reais. Esta é uma chamada de atualização que se conecta ao sistema de processamento de entrada do The Witness e transmite os eventos de teclado e mouse sintetizados para ele. É capaz de coisas simples que uma pessoa pode fazer: olhar em volta, ir em direção a um ponto, olhar para um ponto e assim por diante. O procedimento executa essas ações simplesmente simulando a interação do usuário com o teclado e o mouse, então eu tinha certeza de que, ao processar a entrada do The Witness, tudo será feito exatamente como foi durante o teste. Nos artigos a seguir, falarei mais sobre esse sistema e seu uso.

O segundo procedimento é uma etapa que não é usada neste nível. Essa é uma função chamada DriveTowardPoint , que recebe dois pontos no mundo e, causando um sistema de colisão existente de um jogador, tenta se mover perfeitamente de um ponto para outro. Realizando o retorno, ela transmite informações sobre a tentativa: quais obstáculos encontrou no caminho e se conseguiu chegar ao ponto final.

Essa função não é tão confiável quanto um método de teste com entrada sintetizada, porque elimina parte do sistema de movimento do jogador dos testes. Por exemplo, qualquer estado incorreto associado à localização do jogador em caso de problemas com o sistema de colisão não afetará o teste usando esta função. No entanto, considerei esse nível de teste valioso, porque ele pode testar vastas áreas muito mais rapidamente, porque não requer a execução de todo o ciclo do jogo, ou seja, pode ser usado com muito mais frequência em todo o mundo, e não apenas em testes separados .

Também é importante notar que esta função não transmite dados de entrada físicos; por exemplo, as velocidades não são indicadas para o ponto de partida. Isso ocorre porque The Witness não é um jogo de ação, portanto o jogador tem poucas propriedades físicas significativas. Os jogadores não podem pular, correr nas paredes, ativar o tempo da bala. Você pode suportar esses comportamentos usando sistemas que descreverei mais adiante, mas eles adicionam níveis de complexidade que não eram necessários em nosso projeto.

Seja como for, depois de implementar o DriveTowardPoint, eu poderia começar a resolver a primeira tarefa do sistema: determinar para onde o jogador pode se mudar para The Witness Island.

Exploração rápida de árvores aleatórias

Para onde os jogadores podem ir? Parece uma pergunta simples, mas você ficará surpreso ao descobrir quantos jogos foram lançados quando a equipe de desenvolvimento não sabia a resposta real. Se isso for possível, eu queria que o The Witness fosse um daqueles poucos jogos em que os desenvolvedores antes do lançamento sabiam exatamente onde o jogador poderia ou não conseguir - sem surpresas.

Isso torna a declaração do problema (mas provavelmente não a solução) muito simples: se houver uma função DriveTowardPoint que determine com segurança se o jogador pode se mover em uma linha reta entre dois pontos, crie um mapa de cobertura mostrando onde o jogador pode estar.

Por alguma razão, sem escrever uma única linha de código, por alguma razão, pensei que seria melhor usar a Árvore aleatória de exploração rápida . Para aqueles que não estão familiarizados com esse algoritmo, explicarei: esse é um processo muito simples no qual registramos todos os pontos que visitamos com referência ao ponto de onde viemos. Para adicionar um ponto à árvore, pegamos um ponto de destino aleatório em qualquer lugar do mundo, selecionamos o ponto mais próximo, já na árvore, e tentamos ir desse ponto ao alvo. O local onde acabamos se torna o próximo ponto de amostragem.

Normalmente, esse algoritmo é usado para procurar caminhos: alternadamente, para pontos aleatórios, sempre selecionamos o mesmo ponto que o alvo. Isso inclina a exploração do espaço em direção ao ponto alvo, e é isso que é necessário quando nossa única tarefa é atingir a meta. Mas, neste caso, eu queria criar um mapa completo dos lugares em que o jogador pudesse se encaixar, então eu uso apenas amostras aleatórias.

Depois de implementar esse algoritmo (felizmente, é muito simples e não exigiu muito tempo), vi que ele executou um bom trabalho explorando o espaço (os caminhos mostrados são mostrados por caminhos brancos e as linhas vermelhas verticais indicam os locais onde o algoritmo colidiu com um obstáculo) :


No entanto, depois de observar seu comportamento, percebi que, na verdade, não precisava desse algoritmo. Por exemplo, mesmo após muitas iterações, ele mal consegue explorar as salas semelhantes às mostradas abaixo, apesar da densa cobertura das áreas externas. Isso ocorre porque ele simplesmente não é capaz de selecionar pontos aleatórios o suficiente dentro das salas:


Se eu pensasse nisso antes de começar o trabalho, entenderia que a vantagem de algoritmos como o Rapidly Exploring Random Tree é que eles exploram efetivamente espaços de alta dimensão. De fato, essa é geralmente a principal razão de seu uso. Mas a testemunha não tem espaços de alta dimensão. Temos um espaço bidimensional (sim, distribuído por uma variedade complexa, mas ainda é um espaço bidimensional).

Neste espaço de baixa dimensão, as vantagens da Rapidly Exploring Random Tree são fracas e sua desvantagem é criticamente importante para a minha tarefa: o algoritmo é projetado para a pesquisa mais eficiente de caminhos para pares de pontos conectados no espaço, e não para a pesquisa eficiente de todos os pontos alcançáveis ​​desse espaço. Se você tiver essa tarefa, na verdade, a Árvore aleatória de exploração rápida levará uma quantidade enorme de tempo para resolvê-la.

Então, rapidamente percebi que precisava procurar um algoritmo que cobrisse efetivamente completamente os espaços de baixa dimensão.

Enchimento 3D

Quando realmente pensei em escolher um algoritmo, ficou óbvio que, de fato, eu precisava de algo como o bom e velho preenchimento bidimensional, usado para preencher áreas do bitmap. Para qualquer ponto de partida, eu apenas tive que preencher todo o espaço, verificando exaustivamente todas as formas possíveis. Infelizmente, por muitas razões, a solução para o The Witness será muito mais complicada do que para um bitmap bidimensional.

Primeiro, não temos um conceito claro da conexão finita de um ponto. Todo o espaço é contínuo. Isto é para um pixel, podemos listar facilmente 4 locais possíveis que podem ser alcançados a partir de um determinado ponto e verificar cada um deles por vez.

Em segundo lugar, não há tamanho fixo de posição no espaço, como um pixel em um bitmap. As superfícies nas quais o jogador está se movendo e os obstáculos podem estar em qualquer lugar, eles não têm um tamanho topológico máximo ou mínimo, além de não serem vinculados a nenhuma grade externa.

Em terceiro lugar, embora o movimento através do espaço The Witness possa ser considerado localmente como se movendo ao longo de um avião, o próprio espaço é na verdade um coletor profundamente interconectado e mutável, no qual as áreas passíveis de caminhar do jogador estão diretamente acima de outras áreas (às vezes pode haver vários níveis localizados um acima do outro) . Além disso, existem conexões que variam de acordo com as condições do mundo (portas abertas / fechadas, elevadores que sobem / descem, etc.).

Dadas as dificuldades descritas, é muito simples criar sua própria opção de implementação para preenchimento, que, como resultado, será preenchida com áreas que se cruzam, falta de rotas importantes, informações erradas sobre conexões em locais complexos da variedade. No final, o algoritmo será muito complicado de usar, porque, para levar em conta as mudanças no estado do mundo, ele deve ser executado novamente.

Como não achei uma boa solução imediatamente, decidi começar com experimentos simples. Usando o código Rapidly Exploring Random Tree que escrevi, mudei a seleção dos pontos de destino de aleatório para muito controlado. Cada vez que um novo ponto foi adicionado à árvore, eu indiquei que os pontos estão a uma distância unitária ao longo das direções principais a partir do ponto que será considerado o futuro alvo, como acontece em um simples preenchimento bidimensional.

Mas é claro que, se não for cuidadoso, isso criará um ciclo de amostragem inútil. O ponto se ramificará nos 8 pontos vizinhos ao redor, mas esses 8 pontos tentarão novamente retornar ao ponto de partida, e isso continuará para sempre. Portanto, além da seleção controlada de pontos-alvo, preciso de uma restrição simples: qualquer ponto-alvo que não esteja a uma certa distância útil mínima de um ponto-alvo existente não será levado em consideração. Para minha surpresa, essas duas regras simples criam um preenchimento bem-sucedido:


Nada mal para um experimento bastante simples. Mas o algoritmo sofre do que chamo de "eco de fronteira". Esse efeito pode ser visto na seguinte captura de tela feita durante o estudo do mapa:


Em áreas sem obstáculos, o algoritmo funciona bem por amostragem a distâncias relativamente iguais. Mas quando a interseção atinge a borda, eles criam pontos "fora da grade", ou seja, não são alinhados de acordo com o padrão de amostras, segundo o qual o algoritmo preenche a área aberta vizinha. A razão pela qual os pontos "na grade" não criam mosaico excessivamente denso é porque cada novo ponto que tenta retornar a um dos anteriores encontra o ponto anterior e se recusa a recontá-lo novamente. Mas, ao criar novos pontos na borda, eles ficam completamente desalinhados, de modo que nada pode impedi-los de retornar ao espaço já explorado. Isso leva à criação de uma onda de amostras tendenciosas, que continua até atingir uma linha aleatória de pontos em algum outro lugar próximo o suficiente para que o algoritmo possa encontrá-lo coincidindo com a frente móvel dos pontos.

Embora isso não pareça ser um problema sério, é realmente crítico. O objetivo de tais algoritmos é concentrar as amostras nas áreas em que é mais provável que produzam resultados produtivos. Quanto mais tempo gastamos amostrando e realizando a amostragem de vastas áreas abertas, menos tempo gastamos marcando as próprias faces dessa área, que são as informações de que precisamos. Como estamos lidando com espaço contínuo e apenas um número infinito de amostras pode descrever sua forma real, a proporção de amostras significativas para amostras insignificantes é literalmente uma medida da eficácia do algoritmo na criação de uma superfície aceitável para um jogador.

No entanto, existe uma solução simples para esse problema em particular: você precisa expandir a distância na qual os dois pontos são considerados "bastante próximos". Ao fazer isso, reduziremos a densidade de amostragem em locais que não são importantes para nós, mas também perderemos a densidade de amostragem em locais que são importantes para nós, por exemplo, as áreas ao redor das fronteiras que queremos verificar cuidadosamente quanto à presença de "buracos".

Amostragem direcional localizada

Provavelmente porque comecei com a Árvore Aleatória Rapidamente Exploradora, meu cérebro suplantou todas as outras idéias, exceto a de proximidade. Todos os algoritmos anteriores usavam proximidade para sua tarefa, por exemplo, para determinar um novo ponto que precisa ser considerado a seguir ou para selecionar um ponto a partir do qual começar a chegar a um novo ponto de destino.

Mas, depois de pensar sobre a tarefa por algum tempo, cheguei à conclusão de que tudo está se tornando mais lógico, se pensarmos não apenas na proximidade, mas também na direção . Então fica óbvio, mas se você trabalhou em tarefas semelhantes, sabe que é fácil cair na armadilha do pensamento tacanho e não ver o quadro geral, mesmo que isso seja mais simples. Foi exatamente o que aconteceu comigo.

Quando mudei minha visão das coisas, a abordagem correta da amostragem parecia óbvia. Cada vez que eu queria expandir minha exploração do espaço a partir de um ponto, solicitava a existência de pontos próximos no ambiente local. No entanto, em vez de usar a distância desses pontos para a pesquisa, os classificarei de acordo com suas instruções (antes disso, usei apenas oito direções principais, mas queria experimentar outros kernels).

Em qualquer direção em que não "vejo" o ponto, percorro a distância especificada e adiciono um ponto em qualquer lugar em que parei (independentemente de ter encontrado algo ou não). Se eu vir um ponto em uma das direções, estou indo para lá e verificando se consigo chegar lá. Se eu puder, basta adicionar uma aresta visível para que o usuário possa ver facilmente que os pontos estão conectados. Se não puder, adiciono um novo ponto no ponto de colisão, definindo o limite do obstáculo.

Esse método de amostragem funcionou bem. Ele nos permite controlar com muita precisão a amostragem usando parâmetros personalizáveis ​​convenientes, salvar todos os pontos necessários e evitar mosaicos desnecessários, o que leva a um preenchimento muito rápido do espaço:


Como o algoritmo realiza uma pesquisa ao longo das direções, e não apenas usa a proximidade, ele é protegido contra ecos de limites e limita a amostragem excessiva apenas aos limites de que precisamos:


Além disso, o algoritmo não é afetado por transições de estado ou problemas com variedades complexas. Ele lida apenas com pontos, e esses pontos podem estar em qualquer lugar, e novos podem ser adicionados a qualquer momento. Se você já desenhou um mapa da área com a porta fechada, depois de abrir a porta, basta colocar o único ponto de pesquisa do outro lado da porta e ordenar que o algoritmo continue expandindo esse mapa, após o qual ele se conectará corretamente e examinará corretamente toda a área fora da porta.

Além disso, a qualquer momento, você pode alterar os parâmetros básicos e o sistema continuará funcionando. Deseja que a amostragem de área seja feita com maior densidade? Apenas abaixe a distância padrão. Isso já pode ser feito no processo de construção do mapa, e o algoritmo começará a amostrar com uma densidade mais alta sem a necessidade de redefinir os resultados anteriores (o que pode levar algum tempo).

Verificação rudimentar de arestas

O algoritmo padrão já faz amostras de bordas com muito cuidado, porque as interseções criam pontos adicionais que não estão incluídos no padrão de amostragem, mas não necessariamente os verifica com os cuidados necessários, porque não executa nenhuma ação especial ao encontrar obstáculos. Percebi que, como sabia quais pontos foram criados durante as colisões, os dois pontos de colisão detectados são conectados por uma aresta e podemos solicitar amostragem adicional para tentar encontrar mais pontos de fronteira na vizinhança.

Não pesquisei ativamente essa abordagem, mas criei um método rudimentar para testar essa teoria, que me pareceu promissora. Tendo tomado dois pontos de colisão conectados por uma aresta, mudo para o ponto médio da aresta e tento desenhar a perpendicular externa à aresta. Se ele não cruzar a borda a uma distância muito curta, suponho que a borda seja mais complexa e adicione um novo ponto de destino para continuar a pesquisa nessa área.

Mesmo esse esquema simples cria uma amostragem densa e de alta qualidade ao longo da fronteira sem amostrar desnecessariamente áreas abertas vizinhas. Aqui está uma área com várias bordas, mas sem verificar as bordas:


E aqui está a mesma área com arestas de verificação:


Por mais que eu estivesse satisfeito com esse resultado, fiquei surpreso com a falta de algoritmos significativamente melhores para amostragem de borda e tentarei escolher mais alguns métodos no futuro.

Vitórias rápidas

Mesmo tendo investido apenas um pouco de tempo no desenvolvimento e criando um código bastante simples, certifiquei-me de que o Walk Monster já esteja criando uma saída bastante adequada que possa detectar problemas reais no jogo. Aqui estão exemplos de problemas que eu encontrei durante o desenvolvimento do algoritmo:


As encostas nas laterais desta plataforma não devem ser transitáveis, mas o jogador pode andar sobre elas. Isso aconteceu porque no código de movimento do jogador há uma maneira patológica de processar geometria oblíqua. Agora eu sei que ele está lá, e eu o corrigirei quando se trata de garantir sua confiabilidade.


A Testemunha deveria ser um jogo contemplativo, mas se perguntando por que parece que existe uma pedra, embora não seja, não era um dos seus koans. Como você pode imaginar, esse problema surgiu porque alguém deixou a quantidade de colisão no jogo após remover a geometria que o designava. Isso pode acontecer facilmente, e é muito bom que tenhamos uma ferramenta que possa reconhecer rapidamente esses erros, para que as pessoas não precisem.



Esses objetos deveriam ser rochas intransitáveis, mas o Walk Monster descobriu que isso não aconteceu. Pior, o Walk Monster descobriu que, por algum motivo, o caminho é apenas de um caminho (da captura de tela da esquerda para a direita), mas não deve ser assim. Eu me certifiquei de que o jogador realmente pudesse fazer isso (eu consegui). É muito interessante observar a ocorrência de tais erros!

Perguntas abertas

Quando você vê bons resultados que podem ser desenvolvidos, isso é inspirador. Como eu disse, se você escolher um nome adequado para os arquivos de origem, tudo será como um relógio! Mas todo esse trabalho foi concluído em apenas alguns dias, por isso está longe de ser exaustivo e muito foi feito completamente improvisado. Se eu tiver tempo suficiente para o desenvolvimento posterior desses sistemas, vale a pena responder a várias perguntas.

Primeiro, que pós-processamento precisa ser feito com os dados para facilitar a visualização? Será difícil para as pessoas descobrir uma rede não processada de pontos e arestas, mas se você melhorar a descrição dos dados, isso provavelmente dificultará a avaliação de áreas transitáveis ​​difíceis à primeira vista.

Segundo, como os padrões de amostragem em torno das bordas podem ser aprimorados para garantir que o número máximo de “furos” seja encontrado? Existem boas maneiras de caracterizar a redução de números em uma treliça e existem esquemas de mosaico de alta qualidade que maximizam a probabilidade de cruzar e passar por esses números?

Terceiro, quais padrões de amostragem são melhores para preencher espaços - regulares ou aleatórios? Posso alterar facilmente os critérios para escolher pontos de destino para criar mais padrões aleatórios, mas não está muito claro se vale a pena fazer e, nesse caso, que tipos de padrões aleatórios serão melhores.

Quarto, que outras informações queremos obter dos mapas de áreas transitáveis ​​se já aprendemos a construí-las? Por exemplo, é muito simples expandir um sistema existente com funções como procurar caminhos ou mapas de distância, para que o usuário possa selecionar um ponto e solicitar o caminho mais curto entre ele e algum outro ponto, ou visualizar um mapa de calor da distância entre um ponto e outros pontos do mapa. Essas consultas serão úteis? Que outras consultas posso usar?

No momento, as visualizações de áreas transitáveis ​​do Monster Walk são mais que suficientes para mostrar que o código de movimento do jogador é muito ruim. Planejei passar à criação de um sistema para cartões de teste noturnos usando o método de simulação de entrada do usuário, mas é óbvio que já temos problemas suficientes para resolver sem essa etapa. Portanto, o próximo passo será aumentar a confiabilidade do código de movimento do jogador. E enquanto estou trabalhando nisso, gostaria de verificar se é possível aumentar a velocidade de execução em uma ou duas ordens de magnitude, porque enquanto o trabalho do Walk Monster é muito mais lento pelo sistema de freios de colisões.