¿Cómo podría implementar algo como la cuadrícula de artesanía de Minecraft?

55

El sistema de fabricación en Minecraft utiliza una cuadrícula de 2x2 o 3x3. Coloca los ingredientes en la cuadrícula, y si coloca los ingredientes correctos en el patrón correcto, se activará la receta.

Algunos puntos interesantes sobre el diseño:

  • Algunas recetas pueden intercambiar ciertos ingredientes por otros. Por ejemplo, un pico usa palos para el mango y puede usar tablas de madera, adoquines, lingotes de hierro, lingotes de oro o gemas de diamantes para la cabeza.
  • La posición relativa dentro del patrón es lo que importa, no la posición absoluta en la cuadrícula. Es decir, puede crear una antorcha colocando el palo y el carbón (o carbón) en el patrón correcto en cualquiera de las seis posiciones en la cuadrícula de 3x3.
  • Los patrones pueden voltearse horizontalmente.

Puede que esté pensando demasiado, pero esto parece un problema interesante de búsqueda / reducción de conjuntos. Entonces, ¿cómo funciona (o podría) funcionar esto, algorítmicamente hablando?

David Eyk
fuente
66
Impresionante pregunta! ¡Estoy muy interesado! Ya tengo algunas ideas, pero las compartiré tan pronto como llegue a casa.
jcora
Realmente estoy tratando de escribir una copia de Minecraft "lo más cerca posible". Ya escribí todo el inventario y el administrador de recetas y tengo que decir que está funcionando muy bien. Estoy satisfecho con el código limpio. Sin embargo, no fue fácil escribirlo. Escribí alrededor de 10 clases para que todo funcione bien las recetas, cuadrículas, inventario, etc. Cuando encuentre algo de tiempo, escribiré una respuesta.
Martijn Courteaux
Debes ver cómo Minecraft codifica sus recetas de elaboración.
Bradman175

Respuestas:

14

Otra solución es usar un árbol algo complicado. Los nodos de rama en su árbol se crearían iterando sobre la receta (una vez más usando for (y) { for (x) }); Esta es su estructura de árbol estándar estándar. Su nodo final contendría una estructura adicional ( Dictionary/ HashMap) que asigna dimensiones a recetas.

Esencialmente, lo que busca es esto:

Árbol de recetas

Los nodos negros son sus ramas que indican el tipo de elemento; los rojos son sus hojas (terminadores) que le permiten diferenciar el tamaño / orientación.

Para buscar sobre este árbol, primero encontrará el cuadro delimitador (como se describe en mi primera respuesta ) y luego iterará sobre los nodos en el mismo orden que atraviesa el árbol a medida que avanza. Finalmente, simplemente buscaría la dimensión en su Dictionaryo HashMapy obtendría el resultado de la receta.

Solo por diversión fui e implementé esto , lo que probablemente aclarará mi respuesta. Además : me doy cuenta de que esta es una respuesta diferente, y con razón: es una solución diferente.

Jonathan Dickinson
fuente
Muy sencillo Me gusta.
David Eyk
Aceptaré este, porque me gustan los árboles, los hash y los diagramas que cortan el meollo del asunto. Una mirada al diagrama, y ​​entendí tu algoritmo casi de inmediato.
David Eyk
23

Debe recordar que Minecraft solo usa un conjunto muy pequeño de posibles recetas, por lo que no hay necesidad de nada tan inteligente.

Dicho esto, lo que haría es encontrar la cuadrícula más pequeña que se ajuste (es decir, ignorar las filas y columnas vacías para averiguar si es una 2x2 o 3x3, o 2x3 (puerta)). Luego recorra la lista de recetas con ese tamaño, simplemente verificando si el tipo de elemento es el mismo (es decir, en el peor de los casos, 9 comparaciones enteras en Minecraft, ya que usa una identificación de tipo entero para elementos y bloques) y deténgase cuando encuentre una coincidencia.

De esta manera también hace que la posición relativa de los elementos sea irrelevante (puede colocar una antorcha en cualquier lugar de la cuadrícula de fabricación y funcionará porque lo ve como una caja de 1x2, no una caja de 3x3 que está principalmente vacía).

Si tiene una gran cantidad de recetas, por lo que hacer una búsqueda lineal a través de las posibles coincidencias lleva mucho tiempo, sería posible ordenar la lista y hacer una búsqueda binaria (O (log (N)) vs O (N)). Esto ocasionaría un trabajo adicional en la creación de la lista, pero esto se puede hacer al inicio una vez y mantenerse en la memoria después.

También una última cosa, para permitir voltear la receta horizontalmente más simple sería simplemente agregar la versión reflejada a la lista.

Si desea hacerlo sin agregar una segunda receta, puede verificar si la receta de entrada tiene un elemento en [0,0] con una identificación más alta que en [0,2] (o [0,1] para 2x2, no es necesario verificarlo) para 1x2 y, de ser así, duplíquelo, si no, continúe verificando la siguiente fila hasta llegar al final. Con esto también debe asegurarse de que las recetas se agreguen en la rotación correcta.

Elva
fuente
1
Me preguntaba si la pequeña cantidad de recetas en Minecraft podría no prestarse a una búsqueda lineal.
David Eyk
1
Lo hace, y es básicamente lo que escribí anteriormente (con posible optimización de búsqueda binaria). Sin embargo, eso deja algunas opciones para la fabricación de antorchas que puedes colocar básicamente en cualquier lugar. Al obtener primero el tamaño de la receta, no necesita agregar 6 recetas para antorchas y limita su búsqueda solo a las del tamaño correcto en un solo paso. - Básicamente, las opciones para su punto 2 son agrupar por tamaño, mover la receta a una esquina o agregar más recetas duplicadas.
Elva
15

Ver si una determinada configuración de cuadrícula coincide con una determinada receta es simple si codifica la cuadrícula de 3x3 como una cadena y utiliza una coincidencia de expresión regular . Acelerar la búsqueda es un asunto diferente, del que hablaré al final. Siga leyendo para obtener más información.

Paso 1) Codificar la cuadrícula como cadena

Simplemente asigne una identificación de carácter a cada tipo de celda y concatene todo lado a lado en este orden:

123
456 => 123456789
789

Y como un ejemplo más concreto, considere la receta del palo, donde W representa madera y E es una celda vacía (simplemente podría usar un carbón vacío ''):

EEE
WEE => EEEWEEWEE
WEE

Paso 2) Haga coincidir la receta con expresión regular (o cadena. Contiene un poco de procesamiento en los datos)

Continuando con el ejemplo anterior, incluso si movemos la formación, todavía hay un patrón en la cadena (WEEW rellenado por E en ambos lados):

EEW
EEW => EEWEEWEEE
EEE

Entonces, no importa dónde mueva el palo, seguirá coincidiendo con la siguiente expresión regular: /^E*WEEWE*$/

Las expresiones regulares también le permiten realizar el comportamiento condicional que mencionó. Por ejemplo (receta inventada), si desea un pico hecho de hierro o piedra para dar el mismo resultado, es decir:

III    SSS
EWE or EWE
EWE    EWE

Puede combinar ambos en la expresión regular: /^(III)|(SSS)EWEEWE$/

Los volteos horizontales también se pueden agregar con la misma facilidad (utilizando también el operador |).

Editar: De todos modos, la parte regex no es estrictamente necesaria. Es solo una forma de encapsular el problema en una sola expresión. Pero para el problema de ubicación variable, también podría recortar la cadena de la cuadrícula de cualquier espacio de relleno (o E en este ejemplo) y hacer un String.Contains (). Y para el problema de ingredientes múltiples o las recetas duplicadas, puede manejarlas todas como recetas múltiples (es decir, separadas) con el mismo resultado.

Paso 3) Acelerar la búsqueda

En cuanto a la reducción de la búsqueda, deberá crear una estructura de datos para agrupar las recetas y ayudar con la búsqueda. Tratar la cuadrícula como una cadena tiene algunas ventajas aquí también :

  1. Podría definir la "longitud" de una receta como la distancia entre el primer carácter no vacío y el último carácter no vacío. Un simple Trim().Length()le daría esta información. Las recetas pueden agruparse por longitud y almacenarse en un diccionario.

    o

    Una definición alternativa de "longitud" podría ser el número de caracteres no vacíos. Nada más cambia. También podría agrupar recetas por este criterio.

  2. Si el punto número 1 no es suficiente, las recetas también se pueden agrupar por el tipo del primer ingrediente que aparece en la receta. Esto sería tan simple como hacerlo Trim().CharAt(0)(y evitar que Trim resulte en una cadena vacía).

Entonces, por ejemplo, almacenaría recetas en:

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

Y realice la búsqueda como algo así 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
fuente
3
Esto es ... muy muy inteligente.
Raveline
18
¿Tienes un problema y quieres resolverlo usando expresiones regulares? Ahora tienes 2 problemas :)
Kromster dice que apoya a Mónica el
2
@Krom Supongo que probablemente solo bromeas, pero ¿hay algún razonamiento detrás de ese comentario? El uso de una expresión regular es solo una forma concisa (hacer coincidir la cuadrícula con la receta con una sola línea de código) y flexible (se ajusta a todos los requisitos de este problema) para realizar la coincidencia en un conjunto de datos (el contenido de la cuadrícula). No veo desventajas significativas sobre la implementación de su propio algoritmo de coincidencia, y simplifica todo el proceso.
David Gouveia
2
@DavidGouveia, esa es solo una frase para las personas que no se sienten muy cómodas con Regex. Si deciden resolver un problema con la expresión regular, ahora tienen dos problemas: (1) el problema real que quieren resolver (2) escribir el patrón de expresión regular para resolver ese problema
iamserious
2
Volviendo al 'ahora tiene dos problemas': Regex tendrá problemas tan pronto como tenga más elementos que el rango imprimible ASCII, a menos que su procesador de expresiones regulares admita unicode y pueda garantizar que ciertas combinaciones no dispararán el compilador NFA de expresiones regulares. arriba. Podría reunir su propio DFA (bastante fácil en realidad) para que coincida con los patrones; pero regex sería la mejor manera de hacer prototipos.
Jonathan Dickinson
3

No puedo decirte cómo funciona el Minecraft, aunque estoy seguro de que si miraste MCP (si tienes una copia legal de Minecraft) podrías averiguarlo.

Implementaría esto de la siguiente manera:

  1. Tenga un diccionario / hashmap basado en disco ( B + Tree / SQL-Light ): el valor sería el ID del elemento del resultado de la receta.
  2. Cuando un usuario está elaborando algo, simplemente encuentre la primera fila / columna con un elemento INDEPENDIENTEMENTE ; combinarlos en un desplazamiento.
  3. Encuentre la última fila / columna con un elemento, nuevamente, de forma independiente.
  4. Calcule el ancho y el alto de los elementos y agréguelo a la clave.
  5. Recorra el rango del cuadro delimitador que acaba de calcular y agregue la ID de cada elemento (usando su habitual for (y) { for (x) }).
  6. Busque la clave en la base de datos.

Entonces, por ejemplo, digamos que tenemos dos ingredientes; X e Y y espacios en blanco son *. Toma la siguiente receta:

**X
**Y
**Y

Primero resolvemos el cuadro delimitador, cediendo (2,0)-(2,2). Por lo tanto, nuestra clave se vería así [1][3](1 ancho, 3 alto). A continuación, recorremos cada elemento dentro del cuadro delimitador y agregamos la ID, por lo que la clave se convierte [1][3][X][Y][Y]; luego, busque esto en su diccionario / DB y obtendrá el resultado de esa receta.

Para explicar la independencia en el paso 2 más claramente, considere la siguiente receta:

*XX
XXX
XX*

La parte superior / izquierda está claramente en 0,0, sin embargo, el primer elemento que normalmente encontraría sería 0,1 o 1,0 (dependiendo de su ciclo). Sin embargo, si encuentra la primera columna no vacía, así como la primera fila no vacía y combina esas coordenadas, obtendrá 0,0: el mismo principio se aplica a la parte inferior / derecha del cuadro delimitador.

Jonathan Dickinson
fuente
El repositorio de Bukkit no tiene ningún código de Minecraft, necesitarías MCP (y una copia de Minecraft)
BlueRaja - Danny Pflughoeft
¿No es esto lo contrario de tu otra respuesta?
David Eyk
@DavidEyk (Esta es mi primera respuesta) no realmente, es más dependiente de una estructura de hashmap (ya sea en forma de tabla grande o en memoria). La razón por la que respondí nuevamente es porque estaba preocupado por las colisiones de hash que conducen a un bajo rendimiento, al menos en un hashmap en memoria. Mi otra respuesta funcionaría mejor para más elementos y una estructura en memoria, donde esto funcionaría mejor si fuera en SQL / etc.
Jonathan Dickinson