Saludos,
estoy tratando de encontrar una solución interesante para generar a partir de un número. Pondré un ejemplo: el "Freecell" de Windows. En el FC puedes poner el número X y en función de ese número sale una combinación de las cartas. Esto permite que un jugador recuerde el número de combinación que no pudo superar y vuelva a intentarlo sin tener que guardar el estado inicial de todas las combinaciones.
Quiero aplicar esta funcionalidad al jueguecillo que estoy haciendo. La cuestión es:
- Pensemos en un mapa 2D lleno de casillas (llamémosle... tablero vulgar).
- Cada una de sus casillas puede tener 5 estados distintos (agua, montaña, ... típicos)
- Aún no he fijado un límite para las casillas, en principio pensé un límite máximo de 100x100, (luego consideré otros valores según iba pensando la generación para que se ajustaran mejor al cálculo).
Soy tranquilamente incapaz de encontrar una solución agradable. Las dos que se ocurren nada más verlo son:
- Codificar los mapas (supongo que es lo que hace el FreeCell). El problema es que son 5 posibilidades por pongámosle 10000 casillas -> VR5,10000 = 5^10K (lo que me plantea serios problemas para salvaguardar el principio de que el jugador debe memorizar el mapa XD, aún codificando a letras).
- Generar el mapa aleatoriamente gracias a la semilla. Semilla 0 genera un mapa (=mapa 0), semilla 1 genera un mapa (=mapa1), etc, etc, etc. El problema aquí es que no veo posibilidad de encontrar función inversa (dado un mapa obtener su número) a menos que me construya yo un generador y sepa cómo lo calcula (y aún así creo que puede ser "problemático").
¿Sabéis de algún método que me permita hacer estas cosas?
¿Recomendáis lo del generador propio?
Ya he notado que hay un "fallo" en esto que he comentado, y es que parece que quiero generar mapas del tipo:
(siendo Llano = 1 Agua = 2 Montaña = 3..... lo que sean los demás)
1 2 3 1 2 3 1 2 3 1 2 3
1 2 3 1 2 3 1 2 3 1 2 3
1 2 3 1 2 3 1 2 3 1 2 3
1 2 3 1 2 3 1 2 3 1 2 3
que realmente no son unos mapas muy apetecibles. Pero en realidad, sí que me interesa ser capaz de generar estos mapas tan extraños para el jugador, que para investigar con la IA me vienen bien.
Gracias por los comentarios.
Yo creo que lo mejor esque por ejemplo si es un tablero de 100x100, le pidas al usuario una pequeña tabla de numeros de 5x5 o algo así. Despues buscas formulas y vas generando el terrenos, no aleatoriamente, sino tomando como referencia esos 25 numeritos, por ejemplo.
Cita de: "Warchief"- Generar el mapa aleatoriamente gracias a la semilla. Semilla 0 genera un mapa (=mapa 0), semilla 1 genera un mapa (=mapa1), etc, etc, etc. El problema aquí es que no veo posibilidad de encontrar función inversa (dado un mapa obtener su número) a menos que me construya yo un generador y sepa cómo lo calcula (y aún así creo que puede ser "problemático").
Hola,
a lo mejor para calcular el inverso te sirve una funcion hash (como un hash md5 por ejemplo). Tu haces con la semilla 0 el mapa 0, y aplicas el hash sobre el mapa, y el resultado que te salga lo guardas en una tabla. Luego para invertir simplemente cuando te den un mapa calculas su hash y miras en la tabla cual era. A lo mejor te sirve como solución...
Un saludo!
Vicente
Si no te he entendido mal, lo que quieres es poder almacenar el desarrollo de una partida de un juego de tablero en un sólo número, ¿verdad?
Puedes codificar una secuencia de números en otro número
único, usando un "número de Gödel". Es un método muy general... demasiado general para este caso me parece pero ahí va..
Ejemplo:
Citar
El número de Gödel de la secuencia (1,4,5,1) es
[1, 4, 5, 1] = 2^1 * 3^4 * 5^5 * 7^1 = 3543750
Es una secuencia de números primos(2,3,5,7), donde cada factor está elevado a los números que queremos codificar(1,4,5,1). La función inversa es la descomposición en factores primos.
Lo malo es que salen números muy grandes cuando tienes muchos factores...
:( es por eso que seguramente no te sirva este método, pero bueno lo mismo te da ideas.
Citar- Codificar los mapas (supongo que es lo que hace el FreeCell). El problema es que son 5 posibilidades por pongámosle 10000 casillas -> VR5,10000 = 5^10K (lo que me plantea serios problemas para salvaguardar el principio de que el jugador debe memorizar el mapa XD, aún codificando a letras).
No estás calculando el tamaño del tablero, estás calculando las combinaciones posibles que el mapa puede tener. Hay que calcular el logartimo en base dos para saber los bits que vas a necesitar.
De todas las maneras, sale un número gordote: 10K log 5 más o menos 30K bits, más o menos 3KB (Una página de letras).
Yo te aconsejaría que no guardases las 10000 casillas. Sólo, por ejemplo, 100 (una de cada 10x10) y luego te inventases las de en medio (interpolación) para que todo quede suavemente encajado.
Con 100 casillas, necesitas unas 30 letras.
En fin, sea como fuere, está la cosa chunga para que el jugador pueda usar esa clave para guardar las partidas.
Un saludo
Muy buenas.
He estado leyendo y en principio no pensaba responder, pero al leer la ultima respuesta me hizo pensar. Si se guardan 100 casillas son 30 letras, y las de enmedio por interpolacion............en vez de una interpolacion se podría utilizar un truco digamos un poco sucio, chapucero y largo de codificar (pero que puede resultar eficaz).
Pongamos un ejemplo que esa interpolacion son de 2 casillas en vez de 9 (sino puede ser eterno). Puedes establecer serie de cambios. Pongamos el ejemplo que los 3 primeros terrenos sean 3-4-5, guardarías el primer terreno q es un 3, y luego para codificar los siguiente sabemos que es +1 +1. Tener una tabla con las series establecidas, y sabemos que la serie +1 +1 le corresponde el numero 37, pues solo guardaríamos el 3 y el 37. Ahora vayamonos al caso de 9, el numero de series podría ser enorme, pero solo guardarías la primera posicion y el numero de serie.
Si se quiere trenzar aun mas la cosa se podría guardar solo el primer mapa y el resto serían todo numero de series, puesto que se podrían establecer series entre las "100" casillas que se guardaban
Como digo es muy tarde y no pensé mucho. Aunque habría que sopesar cual sería el nº de mapas para las series, para que no salga un numero demasiado exagerado y sea posible manejarlo todo
SALUDOS ^^
Hmmm... el numero podria utilizarse como "seed" de una funcion random, y a partir de ahi podrias utilizar algoritmos de generacion de mapas aleatorios como
este de aqui (archivo powerpoint) del heroes of might and magic 3. Si quieres buscar un documento mas detallado, creo que en los archivos de la
GDC hay algo.
Pues yo creo que un perlin noise iria de coña ya que genera el mismo ruido si le pasas el mismo parametro, y dicho parametro podría ser el numero de partida que mencionas.
@sacrifai
Sí, ya estuve pensando divisiones, pero eso no me resuelve el problema de grandes números
(aunque es cierto que dado el número de combinaciones no es posible que el código de
identificación sea pequeño).
@vicente
La tabla hash es interesante, pero para eso necesito generar antes todos los mapas. La idea
es poder tener un editor de mapas. Creas un mapa, y el resultado en vez de ser un archivo de
mapa es un número (no suena estúpido, ¿no?)
@zaelsius
¿Ese "número de Gödel" me recuerda a los algoritmos genéticos? El resultado efectivamente es
un número muy grande que tendría que codificar igualmente para que fuera más manejable.
@gdl
Ya había tenido en cuenta el log, sí, por eso puse lo de la codificación a letras pensando que
un mapa podría ser "EN UN LUGAR DE LA MANCHA DE CUYO NOMBRE..", pero cuando hice los cálculos
para 5^10K <= 27^X ...
Respecto a la interpolación, como dije originalmente, los mapas que no son usuales (como el que
puse de ejemplo
1 2 3 1 2 3
1 2 3 1 2 3 (donde 1, 2 y 3 son terrenos distintos)
1 2 3 1 2 3
1 2 3 1 2 3
1 2 3 1 2 3
también me interesan (en principio). Si no queda más remedio tendré que usar algo así y perder
esos mapas.
@shephiroth
Interesante cuestión. Ahora pensaré en ello numéricamente, porque me temo que el número de series
a codificar también tiene su problema. Puede ser interante hacer cálculos.
@rrc2soft
Un documento interesante, lo he mirado por encima. (Posiblemente la función inversa sea un problema
que no resuelve ni la máquina de Turing?). Voy a estudiar la posibilidad.
@tamat
Ahora me miro el enlace que se puso hace poco sobre el perlin, a ver cómo funciona. Lo que no sé
(ya que no he mirado nada) es si será posible obtener una función inversa.
@TODOS
Gracias a todos por tantas ideas, se ve que tenéis la mente fresquita en Noviembre (ole). Estudiaré
lo que me habéis propuesto y volveré con otra batería de restricciones o con una solución.
(Sigo abierto a sugerencias).
Gracias.
Matizo:
no pretendo hacer un generador de mapas aleatorios. El tema es:
todos recordamos los "passwords" de los mapas de juegos de consolas antiguas que te permitían empezar en el nivel X. (Una serie de 20 objetos rombo + cuadrado + circulo + corazon + ...). La idea es hacer algo parecido pero para todos los mapas que se pueden generar en un tablero de NxM donde cada casilla puede tener 5 valores.
Wenas.
Me he releido todo el post sabiendo ya todas las ideas a ver si por encima para ver si se podrían mezclar. No se si el resultado final saldría aceptable (como tu dices hay q hacer calculos) pero se podría hacer una mezcla entre los números de Gödel de Zaelsius y mi idea.
El principal problema es que a la hora de codificar la cantidad de series puede ser enorme. Se puede utilizar el numero de gödel para codificar la serie en un numero, en vez de un numero que llame a una tabla para saber q serie es. En vez de decir la serie +1 +2 -1 le corresponde el numero10 de serie, podemos aplicarle el numero de gödel.
Esto tiene una pega pero facil solucion. Los numeros negativos. La forma de hacerlo seria reservar X bites para los signos, 0 negativo 1 positivo.
De esta forma el archivo constaria de "Mapa inicial"+"Xbites de signos"+"Numero gödel de la serie"
Pero como siempre, hay que echar mano de calculos, porque no tengo mucha idea pero si lo empiezo a pensar me da dolor de cabeza xDD
SALUDOS ^^
EDIT:
Ahora q lo pienso, para minimizar los mapas a guardar, te podrías elaborar una tabla de repeticiones tipo gif (cuando el 3 y el 4 van seguidos les llamo 6, etc.......)aunque quiza es rizar el rizo xDD
No entendi que pretendes.
Saludos
Pues yo creo que no hay solución adecuada para tablas de cierto tamaño, siempre va a salir un número o secuencia demasiado larga como para memorizarla fácilmente... :( .
Hay unas fórmulas relacionadas con la "teoría de la información" que son capaces de deducir la longitud mínima(o algo equivalente) con la que se puede expresar cierta información. Yo no las he estudiado nunca pero si alguien las manejase, podria decir si lo que quieres hacer se puede hacer o no.
Es que en los juegos de antaño no habian tantas variables a codificar.. guardabas nivel, vidas, munición y poco más en una cadena de símbolos. Eso resulta en una cadena relativamente corta.. pero quizá para un tablero con cientos de piezas sea demasiado.
Ahora me vienen a la cabeza las cadenas del Wonder Boy III: "nosequé" de Mega-Drive. Tenia toques de rol, ya que guardabas armadura, dinero, espadas, items, etc.. y las cadenas para guardar/cargar eran bastante largas, yo diria que de unos 20 caracteres por lo menos.
Edit: Pogacha, lo que Warchief pretende es ser capaz de codificar el estado actual de un juego de tablero de NxN elementos en un sólo número o cadena de corta longitud memorizable por una persona.
AAAAHHH....
Entonces el problema es comprimir.
Citar
Edit: Pogacha, lo que Warchief pretende es ser capaz de codificar el estado actual de un juego de tablero de NxN elementos en un sólo número o cadena de corta longitud memorizable por una persona.
No exactamente. El estado de las partidas se guardaría en un fichero como se hace usualmente. Quiero aplicar el código a la generación de un mapa, pero SÓLO el terreno, sin unidades ni objetos. Es decir,
si yo pongo 1 (o símbolos, o lo que sea) se genera un mapa N1, (tablero con 5 tipos de terreno)
si yo pongo 2 se genera un mapa N2,...
de forma que si quiero jugar en otro ordenador al mismo mapa sólo tengo que acordarme del número de mapa (jugando desde el principio, sin unidades ni nada), y así no tengo que llevarme ficheros de partidas y darle "reiniciar". Quiero ser capaz de generar cualquier mapa, y no solo unos pocos que pueda yo crear en un editor.
Ah sólo el terreno.. ok.. entonces creo que la solución que ha propuesto Tamat(la del Perlin Noise) es la más idónea, es decir, usar un valor númerico o cadena como semilla para la generación de la textura de ruido.
Bien, entonses lo que quieres crear es mapa a partir de una semilla, Matizo te proponina esto con pseudo-azar, si usas la misma semilla se generara el mismo mapa en cualquier ordenador y cada vez.
Como generar un mapa con una semilla ... eso depende de las reglas del juego, tienes que usar un sistema como por ejemplo:
randomize(Semilla); // incicializa el generador de numeros pseudo-aleatoreos (no se como se escribe ) !Mars!!!!
for x
for y
{
tile[x][y]=(random() % 5); // de 0 a 4 el codigo del textura
if(x < XMAX-1 && tile[x+1][y]==tile[x][y]) tile[x][y]++; // por ejemplo para que no halla dos casillas continuas iguales.
}
Entonces generas con pseudo-azar y despues corriges en el mismo o en otro bucle o con una funcion rara segun las reglas de mapas validos.
No se me ocurre algo mas rebuscado a tu pregunta.
saludos
Saludos, apunto de terminar la fase de diseño sigo con el problema (que por otro lado me parece un poco más cercano a implementación).
Por partes:
Los números de Gödel no me terminan de convencer. Debe de ser que no los entiendo (nooo) . El caso es que me puse a pensar y resulta que sólo me sirven como transformación de números grandes a pequeños (en el ejemplo de Zaelsius 1451 <-> 3543750). Sin embargo, me he dado cuenta que esto no soluciona el problema, ya que los números generados por las secuencias de 0 a 1450 son exactamente 1451 números. Esto quiere decir que sigo teniendo 1451 mapas, no 3543750 como había yo pensado en un principio.
El tema de las series también me parecía interesante, pero el número de casillas a considerar (grupos de casillas codificadas en series) era demasiado grande respecto al número de combinaciones (series) codificadas.
Finalmente, hacer el documento de diseño mientras trabajaba esta situación de los mapas me ha revelado que 100x100 es una locura! Necesito un juego rápido, que prefieras jugar muchas partidas a jugar 1 partida de 2 días de duración. Joerz que el ajedrez es 8x8 y da un juego increíble (se juega desde hace siglos XDD). El Battle Masters, origen de mi juego, tenía un tablero de 12 x 12 y se hacía eterno! Así que he optado por reducir y reducir y reducir las casillas hasta quedarme con sólo 16x16. (Siempre se puede ampliar y generar los mapas de otra forma, versión 2.0 :rolleyes: ).
El caso es que si codifico los mapas con letras(26) + números(10) + caracteres ,;.:-_@#$% (10) el problema se me queda en:
VR 46,n >= VR 5, 256 donde
VR = Variaciones con repetición
n = caracteres necesarios para codificar
46 = letras + nums + cars
5 = tipos de terreno (pensé reducirlos a 4)
256 = 16x16
----->
--> 46^n >= 5^256
--> n log 46 >= 256 log 5
--> n >= 256 (log5/log46) ~= 107.62
--> n = 163 caracteres !!
He desestimado la opción del generador de números aleatorios, ya que la semilla debería ser del tamaño de 5^256, que según windows calc ™ 5^256 = 8,6361685550944446253863518628004e+178. Así que, bueno, sigo estrujándome la cabeza, pero creo que esta característica del juego se va a tener que quedar en el borrador. Aún así, creo que generaré los mapas con esos 163 caracteres. Creo que no es posible hacer que el jugador recuerde eso, ni siquiera inventandome "n" dibujitos (n >>> 46), uhm, que creo que es la única idea que me queda.
Algún invento se podría hacer como por ejemplo
semilla(num1)
semilla(rand*num2)
semilla(rand*num3)
rand...
Creo que desvarío.
Aún no he podido mirarme lo del perlin, ya que la opción de encontrar una función inversa la olvido completamente y el perlin puede serme útil. El problema es que luego no sabré cómo generar un mapa concreto, y tendré que jugar mapas llenos de áreas rarararaarraarararraas XDD
Te juro por dios que no te entiendo!!! (nooo)
Quieres generar un mapa al azar o comprimir un mapa editable?
Hablo de mapa como un Tablero de 16 x 16 con 5 valores posibles o
sea 256 *3 bits (0..8) = 738 bytes comprimidos con suerte seran 30 bytes lo cual es imposible de memorizar.
A no ser que tengas reglas claras de mapas validos y no validos.
Los mejores compresores genericos hacen 4 a 1 los que conocen casi todo y con perdidas logran 10 a 1 así que es casi imposible que lo reduzcas a 8 caracteres que es lo maximo que alguien anotaria en un papel.
Po otro lado:
Citarla semilla debería ser del tamaño de 5^256
Por que? :blink:
CitarEl problema es que luego no sabré cómo generar un mapa concreto, y tendré que jugar mapas llenos de áreas rarararaarraarararraas
No !!, generas al azar y luego arreglas el mapa segun siertas reglas como por ejemplo : nunca dos montañas juntas o cosas así.
Saludos
Una sugerencia....
Y por que en vez de memorizar un número, memorizas una serie de caracteres. Con los calculos de Pogacha 30 bytes es un numero muuuuy largo dificil de memorizar. Pero una cadena de 6 caracteres (letras y numeros ) a razon de 5 bytes por caracter (5^2= 32 = 22 letras y 10 numeros) es mucho más comodo. Incluso puedes subir la información guardada a 50 bytes o más...
rafa
Jeje, a ver si me explico.
No quiero generar mapas aleatorios. Quiero generar todo el espacio de mapas generables para el tablero de NxM con 5 tipos de terreno por casilla. Es decir, que si las dimensiones fueran de 3x1 con 2 tipos de terreno (A y B), querría los mapas:
AAA AAB ABA BAA ABB BAB BBA BBB
Las combinaciones totales de mapa resultan de la forma: VR j,k donde VR = variaciones con repetición, j és el número de tipos de terreno, k es el número de casillas. Para el ejemplo VR2,3 = 2^3 = 8.
Cuando mis dimensiones son 16x16 = 256 casillas, y 5 tipos de terreno -> VR 5,256 = 5^256. Que no importa si están codificados en bits o como sea, pero es el número de mapas generables.
Sin embargo, es cierto que con este cálculo se numeran los mapas, que me parecía al principio una gran opción. Al ver la idea de Pogacha de los bits y mezcándola con la idea de sheph de las series , se me ha ocurrido una idea bastante interesante:
Para cada casilla:
0 Si no varía con respecto al anterior
1 Si varía
Al encontrar un 1, se pone entonces el código de la variación (2 bits)
De forma que el código de variación depende del tipo actual
Llano Camino Bosque Montaña Agua
X 00 01 10 11
00 X 01 10 11
00 01 X ... etc.
En el mejor de los casos (cuando todas las casillas son iguales) el número de bits necesarios será de 256 + 2 bits (si no es llano) o 256 (si es llano).
En el peor de los casos (cuando cada casilla es distinta de la anterior) el número de bits necesarios será de 768 (3 bits por casilla).
De esta forma, además, se premia los mapas que tienen filas de casillas del mismo tipo.
Estoy pensando alguna mejora, como que se tenga en cuenta las casillas Norte y Oeste, en vez de sólo la Oeste, pero creo que es quebrarme ya demasiado. Al fin y al cabo, los mapas los voy a querer yo utilizar para entrenar la IA. Creo que voy a tirar por este lugar.
Alguien tiene alguna megaidea o ve problemas a este planteamiento?
Gracias por dedicarle unos minutos a pensar conmigo (ole)
NOTA:
En el Freecell hay 52 cartas. En este caso el número de combinaciones es de P52 = V52,52 = 52! y sin embargo sólo te deja escoger del 1 al 1 millón. Supongo que se cargaron algunas combinaciones.
Creo que no entiendes el concepto de compresion:
Si hay 5 ^ 256 mapas distintos no hay forma alguna de que ocupes menos de 5 ^ 256 codigos distintos en describirlos ( regla del trabajo y energia, se estudia en fisica pero se aplica de la misma manera aquí :P ), pero lo que puedes hacer es, asignar codigos pequeños a los mapas mas probables y codigos grandes a los menos problables, de esta manera tendras longitud de codigos variables y para mapas sencillos tendras de cadenas de caracteres cortas y para los que no deberian ocurrir serán los mapas de codigos de mayor extension, esto se puede optimizar como hace el huffman, pero se hace dificil encontrar el algoritmo de encriptación, lo que se suele hacer es una euristica como se me puede ocurrir: una biblioteca de tabals de 4x4 con las 256 formas mas comunes para cada lugar y de esta manera reduces la tabla de 16x16 a 16 numeros de 0-255, mas las diferencias que pueda tener con el original, estas diferencias seran comprimidas con run code lenght, de esta manera tendras una compresion aceptable, quisas de 20 o 30 caracteres para los mapas mas comunes y de 10^256 para los mas raros.
Entonces el algoritmo de compresion se vuelve:
Para cada fragmento de la entrada
Salida[0..3][0..3] = buscar el mas parecido()
Por cada casilla
Diferencia[numero de diferencias++] = Bibliotecas[fragmento, Salida[0..3][0..3]] - original[Casilla]
Comprimir Diferencia con run code lenght
Encriptar la salida y el diferencias en un numero
y el de descompresion seria
Desencriptar el codigo de entrada en tabla de entrada y diferencias;
Expandir diferencias
Crear final con las bibliotecas segun tabla de entrada.
Agregar diferencias.
Ejemplo de las tablas:
0:
MMMA
AMAA
AAAA
CCCC
1:
MMMA
AMAA
AMAA
MMMM
2:
CCCC
CRRR
CRRR
CCCC
3:
AAAA
AAAA
CCCC
CCCC
Que al final se necesitan 5^256 códigos esta claro, de ahí que no fuera capaz de pensar en un generador de números pseudoaletorios con semilla tan grande.
| QUOTE ("pogacha") |
lo que puedes hacer es, asignar codigos pequeños a los mapas mas probables y codigos grandes a los menos problables, de esta manera tendras longitud de codigos variables y para mapas sencillos tendras de cadenas de caracteres cortas
[/quote]
Esa era la idea del código que puse en el mensaje anterior. Una mejora un poco menos ambiciosa que lo que me has propuesto.
Hoy he estado hablando del tema con mi tutor del proyecto, y al final hemos decido descartar la opción del código. Finalmente la solución pasará por un txt donde se dibuje el mapa en ascii, como siempre (la decisión se puede tomar ahora que hemos decidido 16x16, porque con dimensiones mayores sería un poco costoso :D).
LLLLLLLL
LLLBBBLL
LLLBBLLL
LLLBLLLL
etc.
Así puedo añadir otra información al mapa como los "centros de mando" colocados en algún lugar concreto, etc.
Siempre tendré tiempo de volver a retomar estos cálculos para hacer un editor de mapas que guarde los mapas en un formato comprimido no legible.
Gracias por vuestros comentarios, la idea del código recordable no era factible me temo (aunque sigo pensando que la idea de hacer miles de dibujitos cambiando a palabras podría tener futuro, por ejemplo: perro-gato-despertador-mechero-alfombra sería bastante fácil de recordar y da pie a tener miles de palabras).
--> Para 10K palabras (sacadas del drae)
--> 10000^n >= 5^256
--> n log 10000 >= 256 log 5
--> n >= 256 (log5/log10000) ~= 44.73
--> n = sólo 45 palabras !! (ole)
La otra cuestión es hacer como el Freecell, que sólo ofrece 1M combinaciones de las 52! que hay. Pero bueno, eso es ya otra historia.
En fin, olvidemos lo del código. Gracias por las ideas.
|