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?
minecraft-modding
patterns
search
David Eyk
fonte
fonte
Respostas:
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:
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
Dictionary
ouHashMap
e 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.
fonte
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.
fonte
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:
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 ''):
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):
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:
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 :
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.
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:
E execute a pesquisa como algo como:
fonte
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:
for (y) { for (x) }
).Por exemplo, digamos que temos dois ingredientes; X e Y e espaços em branco sendo *. Tome a seguinte receita:
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:
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.
fonte
Aqui está como eu fiz isso no Block Story:
fonte