Como implementar algo como a grade de criação do Minecraft?

55

O sistema de criação no Minecraft usa uma grade 2x2 ou 3x3. Você coloca os ingredientes na grade e, se você colocar os ingredientes certos no padrão certo, ele ativará a receita.

Alguns pontos interessantes sobre o design:

  • Algumas receitas podem trocar certos ingredientes por outras. Por exemplo, uma palheta usa palitos para o cabo e pode usar pranchas de madeira, paralelepípedos, lingotes de ferro, lingotes de ouro ou gemas de diamante para a cabeça.
  • A posição relativa dentro do padrão é o que importa, não a posição absoluta na grade. Ou seja, você pode criar uma tocha colocando o bastão e o carvão (ou carvão) no padrão correto em qualquer uma das seis posições na grade 3x3.
  • Os padrões podem ser invertidos horizontalmente.

Posso estar pensando demais, mas isso parece ser um problema interessante de pesquisa / redução de conjuntos. Então, como (ou poderia) isso funcionar, falando algoritmicamente?

David Eyk
fonte
6
Incrível pergunta! Eu estou muito interessado! Eu já tenho algumas idéias, mas as compartilharei assim que chegar em casa.
Jcora #
Na verdade, estou tentando escrever uma cópia do Minecraft "o mais próximo possível". Já escrevi todas as coisas sobre inventário e gerente de receitas e devo dizer que está funcionando muito bem. Estou satisfeito com o código limpo. No entanto, não foi fácil escrevê-lo. Escrevi cerca de 10 aulas para que tudo funcionasse bem nas receitas, grades, inventário etc. Quando encontrar algum tempo, escreverei uma resposta.
Martijn Courteaux
Você deve ver como o minecraft codifica suas receitas de artesanato.
precisa saber é o seguinte

Respostas:

14

Outra solução é usar uma árvore um tanto complicada. Os nós de ramificação da sua árvore seriam criados repetindo a receita (usando novamente for (y) { for (x) }); essa é a sua estrutura em árvore padrão de estoque. Seu nó final conteria uma estrutura adicional ( Dictionary/ HashMap) que mapeia as dimensões para as receitas.

Essencialmente, o que você está buscando é o seguinte:

Árvore de receita

Os nós pretos são seus ramos que indicam o tipo de item - os vermelhos são suas folhas (terminadores) que permitem diferenciar tamanho / orientação.

Para pesquisar nessa árvore, você primeiro encontraria a caixa delimitadora (conforme descrito na minha primeira resposta ) e, em seguida, iteraria sobre os nós na mesma ordem que atravessava a árvore à medida que avança. Finalmente, você simplesmente procuraria a dimensão no seu Dictionaryou HashMape obteria o resultado da receita.

Apenas por diversão, eu implementei isso - o que provavelmente esclarecerá minha resposta. Além disso : sei que essa é uma resposta diferente - e com razão: é uma solução diferente.

Jonathan Dickinson
fonte
Muito simples. Eu gosto disso.
David Eyk
Aceito este porque gosto de árvores, hashes e diagramas que cortam o cerne da questão. Uma olhada no diagrama e entendi seu algoritmo quase que imediatamente.
precisa saber é o seguinte
23

Você deve se lembrar que o Minecraft usa apenas um conjunto muito pequeno de receitas possíveis, portanto, não há necessidade de algo tão inteligente.

Dito isto, o que eu faria é encontrar a menor grade que se encaixe (por exemplo, ignore linhas e colunas vazias para descobrir se é um 2x2 ou 3x3 ou 2x3 (porta)). Em seguida, percorra a lista de receitas com esse tamanho, simplesmente verificando se o tipo de item é o mesmo (ou seja, no máximo 9 comparações inteiras no minecraft, pois ele usa um ID de tipo inteiro para itens e blocos) e pare quando encontrar uma correspondência.

Dessa forma, também torna irrelevante a posição relativa dos itens (você pode colocar uma tocha em qualquer lugar da grade de fabricação e ela funcionará porque a vê como uma caixa 1x2, não como uma caixa 3x3 que está quase vazia).

Se você tiver uma quantidade enorme de receitas para que a busca linear pelas possíveis correspondências demore muito, seria possível classificar a lista e fazer uma pesquisa binária (O (log (N)) vs O (N)). Isso causaria algum trabalho extra na criação da lista, mas isso pode ser feito na inicialização uma vez e mantido na memória posteriormente.

Também uma última coisa, permitir virar a receita horizontalmente mais simples seria apenas adicionar a versão espelhada à lista.

Se você quiser fazê-lo sem adicionar uma segunda receita, poderá verificar se a receita de entrada possui um item em [0,0] com ID maior que em [0,2] (ou [0,1] para 2x2, não é necessária verificação para 1x2 e, se for o caso, espelhe-o, se não continuar, verifique a próxima linha até chegar ao final.Usando isso, você também deve garantir que as receitas sejam adicionadas na rotação correta.

Elva
fonte
11
Gostaria de saber se o pequeno número de receitas no Minecraft pode não se prestar a uma pesquisa linear.
David Eyk
11
É, e é basicamente o que escrevi acima (com possível otimização da pesquisa binária). No entanto, isso deixa algumas opções para criar tochas, que você pode instalar basicamente em qualquer lugar. Ao obter o tamanho da receita, você não precisa adicionar 6 receitas para tochas e limitar sua pesquisa apenas às do tamanho correto em uma única etapa. - Então, basicamente, as opções para o seu ponto 2 são agrupadas por tamanho, mova a receita para um canto ou adicione mais receitas duplicadas.
Elva
15

Ver se uma determinada configuração da grade corresponde a uma determinada receita é simples se você codificar a grade 3x3 como uma sequência e usar uma correspondência de expressão regular . Acelerar a pesquisa é um assunto diferente, sobre o qual falarei no final. Continue lendo para obter mais informações.

Etapa 1) Codificar grade como String

Simplesmente forneça um ID de caractere para cada tipo de célula e concatene tudo lado a lado nesta ordem:

123
456 => 123456789
789

E, como exemplo mais concreto, considere a receita do palito, em que W significa madeira e E é uma célula vazia (você pode simplesmente usar um caractere vazio ''):

EEE
WEE => EEEWEEWEE
WEE

Etapa 2) Corresponder Receita usando Expressão Regular (ou String. Contém um pouco de processamento nos dados)

Continuando no exemplo acima, mesmo se movermos a formação, ainda há um padrão na string (WEEW preenchido por E nos dois lados):

EEW
EEW => EEWEEWEEE
EEE

Portanto, não importa para onde você mova o manche, ele ainda corresponderá à seguinte expressão regular: /^E*WEEWE*$/

Expressões regulares também permitem executar o comportamento condicional que você mencionou. Por exemplo (receita confeccionada), se você quiser uma picareta de ferro ou pedra para obter o mesmo resultado, ou seja:

III    SSS
EWE or EWE
EWE    EWE

Você pode combinar os dois na expressão regular: /^(III)|(SSS)EWEEWE$/

Os movimentos horizontais também podem ser adicionados com a mesma facilidade (usando também o operador |).

Edit: Enfim, a parte regex não é estritamente necessária. É apenas uma maneira de encapsular o problema em uma única expressão. Mas, para o problema de localização variável, você também pode aparar a cadeia de grade de qualquer espaço de preenchimento (ou E neste exemplo) e executar um String.Contains (). E para o problema de vários ingredientes ou as receitas espelhadas, você pode lidar com todos eles como várias receitas (separadas) com a mesma saída.

Etapa 3) Acelerando a pesquisa

Quanto à redução da pesquisa, você precisará criar alguma estrutura de dados para agrupar as receitas e ajudar na pesquisa. Tratar a grade como string também tem algumas vantagens aqui :

  1. Você pode definir o "comprimento" de uma receita como sendo a distância entre o primeiro caractere não vazio e o último caractere não vazio. Um simples Trim().Length()lhe daria essa informação. As receitas podem ser agrupadas por tamanho e armazenadas em um dicionário.

    ou

    Uma definição alternativa de "comprimento" pode ser o número de caracteres não vazios. Nada mais muda. Você também pode agrupar receitas por esse critério.

  2. Se o ponto número 1 não for suficiente, as receitas também poderão ser agrupadas de acordo com o tipo do primeiro ingrediente que aparece na receita. Isso seria tão simples quanto fazer Trim().CharAt(0)(e proteger contra Trim resultando em uma sequência vazia).

Por exemplo, você armazenaria receitas em:

Dictionary<int, Dictionary<char, List<string>>> _recipes;

E execute a pesquisa como algo como:

// A string encode of your current grid configuration 
string grid;

// Get length and first char in our grid
string trim = grid.Trim();
int length = trim.Length();
char firstChar = length==0 ? ' ' : trim[0];

foreach(string recipe in _recipes[length][firstChar])
{
    // Check for a match with the recipe
    if(Regex.Match(grid, recipe))
    {
        // We found a matching recipe, do something with it
    }
}
David Gouveia
fonte
3
Isso é ... muito, muito inteligente.
Raveline
18
Você tem um problema e deseja resolvê-lo usando expressões regulares? Agora você tem 2 problemas :)
Kromster diz suporte Monica
2
@ Krom eu acho que você provavelmente está apenas brincando, mas algum raciocínio por trás desse comentário? O uso de uma expressão regular é apenas uma maneira concisa (coincidir grade com receita com uma única linha de código) e flexível (atende a todos os requisitos deste problema) para realizar a correspondência em um conjunto de dados (o conteúdo da grade). Não vejo desvantagens significativas em relação ao lançamento do seu próprio algoritmo de correspondência e isso simplifica todo o processo.
David Gouveia
2
@DavidGouveia, isso é apenas uma frase para pessoas que não estão muito confortáveis ​​com o Regex. Se eles decidem resolver um problema com regex, agora têm dois problemas: (1) o problema real que desejam resolver (2) escrevendo o padrão de regex para resolver esse problema
iamserious
2
Voltando ao 'agora você tem dois problemas' - o Regex terá problemas assim que você tiver mais itens do que o intervalo imprimível ASCII, a menos que seu processador regex suporte unicode e você possa garantir que certas combinações não desarmarão o compilador regex NFA acima. Você pode criar seu próprio DFA (com muita facilidade) para corresponder aos padrões; mas regex seria o melhor caminho a percorrer durante a criação de protótipos.
Jonathan Dickinson
3

Não sei dizer como o Minecraft funciona - embora tenha certeza de que, se você olhou para o MCP (se você possui uma cópia legal do Minecraft), pode descobrir.

Eu implementaria isso da seguinte maneira:

  1. Tenha algum dicionário / hashmap baseado em disco ( B + Tree / SQL-Light ) - o valor seria o ID do item do resultado da receita.
  2. Quando um usuário está criando algo, simplesmente encontre a primeira linha / coluna com um item INDEPENDENTEMENTE ; combine-os em um deslocamento.
  3. Encontre a última linha / coluna com um item, novamente, independentemente.
  4. Calcule a largura e a altura dos itens e adicione-a à chave.
  5. Faça um loop no intervalo da caixa delimitadora que você acabou de computar e anexe o ID de cada item (usando o seu habitual for (y) { for (x) }).
  6. Procure a chave no banco de dados.

Por exemplo, digamos que temos dois ingredientes; X e Y e espaços em branco sendo *. Tome a seguinte receita:

**X
**Y
**Y

Primeiro trabalhamos a caixa delimitadora, cedendo (2,0)-(2,2). Portanto, nossa chave ficaria assim [1][3](1 largura, 3 altura). Em seguida, fazemos um loop sobre cada item dentro da caixa delimitadora e anexamos o ID, assim a chave se torna [1][3][X][Y][Y]- você então pesquisa isso no seu dicionário / banco de dados e obtém o resultado dessa receita.

Para explicar a independência na etapa 2 mais claramente, considere a seguinte receita:

*XX
XXX
XX*

A parte superior / esquerda está claramente em 0,0 - no entanto, o primeiro item que você normalmente encontraria seria 0,1 ou 1,0 (dependendo do seu loop). No entanto, se encontrar a primeira coluna não vazia e a primeira linha não vazia e combinar essas coordenadas, você obterá 0,0 - o mesmo princípio se aplica à parte inferior / direita da caixa delimitadora.

Jonathan Dickinson
fonte
O repositório Bukkit não tem qualquer código Minecraft, você precisa de MCP (e uma cópia do Minecraft)
BlueRaja - Danny Pflughoeft
Isso não é apenas o inverso de sua outra resposta?
David Eyk
@DavidEyk (Esta é minha primeira resposta) não, na verdade, é mais dependente de uma estrutura de hashmap (seja do tipo bigtable ou na memória). A razão pela qual respondi novamente é porque estava preocupado com colisões de hash que levavam a um desempenho ruim - pelo menos em um mapa de hash na memória. Minha outra resposta funcionaria melhor para mais itens e uma estrutura na memória - onde isso funcionaria melhor se estivesse no SQL / etc.
Jonathan Dickinson