Algoritmo de resolución de pantallas?
Acabo de terminar de programar este jueguecito en flash:
http://www.piensaenpixels.com/renacuajos/renacuajos.htm
Como veis es muy sencillo, pero ahora tengo un problema, me gustaría hacer bastantes pantallas (por ahora solo hay 4), pero por supuesto no todas las combinaciones de renacuajos y obstaculos tienen solución. Mi idea es hacer un pequeño programilla que me haga pantallas con solución o bien que me indique si una combinación dada de obstaculos y renacuajos la tiene.
¿El problema? bien, que no tengo ni idea de por donde empezar, no soy programadora ni he hecho informatica y no tengo muy claro por donde atacar esto.
Necesitaria que me dierais alguna idea de por donde empezar o si conoceis algún problema similar cuya resolución este descrita. Hartum me comentó nosequé de un "Problema del Automata" pero no se acuerda muy bien como era y no sé si es lo que necesito o no.
hartum
¿como atacar el problema?
A ver aunque no puedo darte la solucion exacta, creo que por lo menos puedo orientarte, la cosa seria la siguiente:
-tienes una escenario conunas medidas, la podrias cuadricular(de forma esquematica, o mental).
-cada interseccion de la cuadricula es un nodo, y en principio podrias viajar de nodo a nodo, de forma libre(como si fuese un array, o un registro de punteros(luego me explico mejor).
-hay unas reglas universales de desplazamiento, estas reglas son que los espermatoxoides-rana, solo pueden viajar de nodo a nodo, en direccion vertical u horizontal, y que no se detendran hasta que encuentren un obstaculo.
-cuando consigas hacer eso(que ya lo tienes), es cuando empiezas a poner condiciones(obstaculos, flechas, etc...)
-En cada nodo puedes definir unas reglas, si el nodo esta vacio, sigue adelante, si tiene una flecha cambia la direccion, si es una piedra detente, si el nodo esta ocupado por otro espermato-rana, detente, etc...
-cada vez que viajas de nodo a nodo, tienes que hacer una
comprobacion, cogiendo la informacion del nodo destino,
Esto tiene una pinta de tipico algorimto de resolucion, por nodos, hay varios algoritmos por ahi que te encuentran el camino mas optimo, el que tiene solucion etc... realmente lo que tiene miga es poder pasar lo expuesto a una estructura de nodos, a ver si alguno de mis colegas conserva los apuntes, y se lo pido.
Y Preguntale a fumarmata, que el se hizo un neredaor para su juego.
granatta Profesor Plus
HARTUM
Y Preguntale a fumarmata, que el se hizo un neredaor para su juego
sí, pero ese muchacho se hizo en flash 5 toda la drawin' api que trae flash mx
vamos, que está pallá, por eso lo digo :P
eso sí, el web de Blank le está quedando de vicio :)
d+g.
orange
Hartum
"Esto tiene una pinta de tipico algorimto de resolucion por nodos"
Anda coño!!! ¡¡¿cómo no se nos había ocurrido?!!
..................
O_O -> Jimena (y un servidor) al leer eso
:P
PD: Marc es un puto crack !!
Looup
Y digo yo... ¿no te valdría el famoso algoritmo del laberinto? Como bien dice Hartum, lo suyo es dividir el espacio en una cuadrícula, y allí vas poniendo los obstáculos y las salidas.
Con este algoritmo resuelves todos los caminos posibles (si quieres claro) y te indica si hay o no solución. Voy a ver si lo encuentro por ahi. o si no te lo copio de mi libro de fundamentos de programación.
Si no lo ves claro, acuérdate de tu camiseta del pac-man, la teoría es la misma jejej
(joer, ahora me ha entrao la neura por cambiarme el nick)
cadrilo
Hola
Precisamente hoy en la web de sephiroth se habla del tema con un ejemplo muy gráfico.
El tutorial que explica todo lo puedes encontrar aqui
Espero que te sea de gran ayuda
Keroak
Pues yo lo veo todo clarisísimo, de hecho supongo que será más sencillo incluso de lo que plantean, ya que las reglas de movimiento implican que los renacuajos no se mueven a los nodos adyacentes sino al último nodo antes de encontrar un obstaculo reduciendo las posibilidades.
Lo malo es que el nº de escenarios con solución será muy bajo si los escenarios se generan al azar. A lo mejor deberías pensar en qué requisitos cumple un escenario para ser jugable.
Yo lo que haría es disponer los renavujos y obstaculos al azar y utilizar el algoritmo para saber hasta donde pueden llegar y en cuanto tiempo y colocar los nidos después en función de ese resultado.
------------------------
De paso saludo al resto de ¿domestikadores?, nos sequiremos viendo por aqui
:D
hartum
en prolog estaria chupao , poruqe solo defines el escenario el te explora todos los caminos posibles y te devuelve las soluciones en caso de haberlas, pero claro, ¿quien coño se pone ahora a repasar los apuntes de prolog y de haskell?