Generador De Mapas A Partir De Un Número

[Warchief]

 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.

[Sacrifai]

 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.

[Vicente]

- 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

[Zaelsius]

 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:

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.

[gdl]

 

- 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

[shephiroth]

 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 ^^

[rrc2soft]

 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.

[tamat]

 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.

[Warchief]

 @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.

[Warchief]

 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.

[shephiroth]

 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

[Pogacha]

 No entendi que pretendes.
Saludos

[Zaelsius]

 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.

[Pogacha]

 AAAAHHH....
Entonces el problema es comprimir.

[Warchief]

 

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.