15 respuestas en este tema

[cram]

Quiero agregar un desafío pero me temo que éste debe estar muy bien definido antes de comenzar, ya que se presta a muchas confusiones. Se trata de resolver caminos en un laberinto para poder alcanzar a un objetivo que puede estar en movimiento cuyas coordenadas son conocidas y pueden utilizarse para que nuestro sprite se acerque.

 

Intentaré definir el tipo de laberintos primero.

 

1) tiene caminos delimitados por muros

2) los muros son como mínimo del ancho de los caminos en grosor

3) los caminos son del ancho de los sprites.

4) debe existir caminos fluidos para que los "sprites" circulen por el laberinto, aunque es posible que haya caminos sin salida (trampas) en forma de U.

 

Los sprites de ahora en adelante escribiré sin estilo, tienen coordenadas conocidas y son como lo dije antes del tamaño correcto como para caber en los caminos.

 

Dado que hacer la programación como para dibujar el laberinto, mostrar los sprites y moverlos es avanzado, el desafío se limita al uso de funciones y procedimientos para comprobar y mover. Las funciones son las siguientes:

 

1) Camino_libre(direccion: byte): boolean; comprueba si es posible mover en la dirección especificada

2) Caminar(direccion: byte); mueve el sprite un paso en la dirección indicada

 

Las coordenadas del sprite perseguido son XP y YP, mientras que las coordenadas de nuestro sprite son X y Y.

Otras variables necesarias pueden ser creadas libremente (pues de otra manera sería algo complicado).

 

XXXXXXXXXXXXXXX

X     X X   X X

X XXX X X XXX X

X X   X     X X

X X XXXXXXX X X

X X   X       X

X XXX XX XXXX X

X        X    X

XXXXXXXXXXXXXXX

 

Esta muestra con X es algo extremadamente pequeño, pero apenas pueda subiré una imagen clara sobre el caso, claro que siempre y cuando le interese a alguien.

 

También en breve subo un algoritmo inicial como para que se entienda mejor.

 

Una comprobación típica es IF (X<XP), que comprueba si la ordenada horizontal de nuestro spritre es menor que la del sprite perseguido. Es decir, si será necesario moverse en dirección de la derecha.

 

Por último para facilitar la comprensión dejo la codificación de las direcciones:

 

1. Arriba

3. Derecha

5. Abajo

7. Izquierda

 

Los pares están reservados para su uso en una función, por ejemplo para comprobar si será necesario tomar la dirección abajo y derecha, que será 4. Claro que el sprite no podrá moverse en diagonal.

 

Los códigos de direcciones siguen así:

 

2. arriba y derecha

4. abajo y derecha

6. abajo e izquierda

8. arriba e izquierda

 

Aclaro una vez más, los sprites no pueden moverse en diagonal.

 

Espero que les sea de agrado.

 

Saludos

 

[enecumene]

Donde subiste el algoritmo?

[cram]

Donde subiste el algoritmo?

 

Aún no lo subí. Es que nadie se "prendió".

Pero como alguien al menos escribió, lo subo apenas pueda. No son nada complejos, por el contrario tienen muchos inconvenientes para ciertos laberintos, por esta razón tuve que hacer especificaciones para su creación.

 

Saludos

[cram]

Es que se trata de un desafío Enecumene. Por eso no quería subir antes que alguien muestre una posible solución.

 

Para adelantar algo, puedo decir que mi solución comienza por la división en dos clases de resoluciones:

1) Choque y nuevo rumbo, es decir que el perseguidor debe hallar un muro en frente para cambiar de rumbo.

2) El perseguidor puede cambiar de rumbo apenas encuentre un camino perpendicular

 

Evité que vuelva tras sus pasos, por razones algo sin sentido para ser explicadas.

 

En mi algoritmo de resolución inicial los muros en forma de U (o C), es decir que forman un lugar con solo una escapatoria (que es volver) dejaba sin salida al perseguidor.

Otro caso que lo dejaba fuera de combate era lo que denominé cárcel, pero prefiero llamarle actualmente rotonda cerrada, y es el caso de una especie de golfo con una isla en el medio, en el cual el preseguidor queda dando vueltas sin poder salir.

 

Cuando implementé los tres o cuatro diferentes algoritmos en el mismo programa haciendo que varios persecutores persigan al jugador, puedo decir que había pocas posibilidades de escapatoria. De esto ya hace demasiado, pues lo hice cuando tenía dieciséis (iba a la secundaria) en una Talent DPC-200 con MSX-Basic (Sprites servidos en bandeja).

También desafié a mi hijo de trece, a ver si lo resuelve con Scratch, pero el muy "cara dura" , me djo que prefiere implementarlo en otro lenguaje (como no sabe otro, significa no me interesa, prefiero seguir en modo zombie con Minecraft ).

Se me ocurrió reflotar el caso para implementarlo en Delphi o Lazarus y de ahí me surgió la idea de ponerlo en desafíos.

 

Mis persecutores se llamaban en aquel entonces: Lama, Axón, Forgot y Zilug (supongo que Zilug era por el Zilug Z-80, procesador de la Talent).

Uno perseguía, otro más o menos y Forgot solo andaba al azar.

Cuando me planteé soluciones más importantes empecé a estudiar en la facultad, y los abandoné.

 

Subiré el algoritmo de Lama, apenas lo encuentre ( ).

Saludos

[egostar]

Hola
 
Me ha recordado un poco al asunto del hilo "Nuevo algoritmo de inteligencia artificial increible" de nuestro amigo Sergio.

¿Será que se puede tomar algo de eso para desarrollar el laberinto?

Saludos

[Delphius]

Si fuera porque tengo trabajo, le entro al reto.

A mi lo que me mareaba es que no es un laberinto para encontrar salida, porque de entrada en lo primero que pensaba era implementar el Algoritmo de Thremos. Y ya como mejora, el algoritmo (cuyo nombre no recuerdo) que consiste en generar tantas "copias fantasmas" como opciones de ruta encuentra en su camino hasta cierta distancia definida. Aquella que más "cerca" está de la salida se toma como el camino elegido. y se repite el proceso desde ese mismo punto.

 

Que yo sepa son los únicos algoritmos de resolución propuestos para laberintos.

El que sea para atrapar a un objetivo que también tiene libertad de movimiento me rompe los esquemas. Pero la estrategia de movimiento en principio que considero más efectiva es la de forzar en lo posible a que el objetivo quede encerrado... siempre y cuando la IA del objetivo sea muy pobre y reducida. Ahora bien si la IA del objetivo es tanto o igual de avanzada que la que pudiera pensar una persona la cosa ahí si que se pone interesante.

 

Saludos,

[cram]

No, nada de eso de IA. La cosa es simple, es más, quise interesar a personas más nuevas en la programación con este tema que a los "maestros de siempre".

Por eso les comentaba que lo solucioné hace mucho. Eso no lleva muchas líneas de código, ni nada parecido.

No se trata de resolver el laberinto, para eso existe un método que recorre los muros pegado a la pared siempre a un lado, hasta hallar una salida, recordando aquellos caminos que no conducen a la salida, etc. SUpongo que eso es el algoritmo de Thremos.

 

Lamentablemente, no encuentro mis apuntes (transcriptos) algo viejos. Pero la cosa es algo así.

 

Fijar XP, YP, X, Y, Direccion a valores iniciales.

Repetir

  si XP<X entonces si camino_libre(derecha) entonces direccion :=derecha;

  si [análogo a izquierda]

  ...

  mover(Direccion)

hasta (XP = X) y (YP = Y)

 

Claro que esto solo aclara el modo en que pensaba lo encararían.

En realidad una vez que se logra el movimiento fluido del perseguidor hay que lograr que no quede dando vueltas interminables en algún lugar o encerrado en otro, etc. Y de esto se trata el desafío.

 

Saludos.

[Delphius]

No, nada de eso de IA. La cosa es simple, es más, quise interesar a personas más nuevas en la programación con este tema que a los "maestros de siempre".

Por eso les comentaba que lo solucioné hace mucho. Eso no lleva muchas líneas de código, ni nada parecido.

No se trata de resolver el laberinto, para eso existe un método que recorre los muros pegado a la pared siempre a un lado, hasta hallar una salida, recordando aquellos caminos que no conducen a la salida, etc. SUpongo que eso es el algoritmo de Thremos.

 

Lamentablemente, no encuentro mis apuntes (transcriptos) algo viejos. Pero la cosa es algo así.

 

Fijar XP, YP, X, Y, Direccion a valores iniciales.

Repetir

  si XP<X entonces si camino_libre(derecha) entonces direccion :=derecha;

  si [análogo a izquierda]

  ...

  mover(Direccion)

hasta (XP = X) y (YP = Y)

 

Claro que esto solo aclara el modo en que pensaba lo encararían.

En realidad una vez que se logra el movimiento fluido del perseguidor hay que lograr que no quede dando vueltas interminables en algún lugar o encerrado en otro, etc. Y de esto se trata el desafío.

 

Saludos.

 

Efectivamente, ese es el algoritmo de Thremos, o también conocido como el algoritmo de la mano derecha.

 

La verdad es que no me dediqué a estudiarlo como para ver si es tan simple como dices, que no hace falta el enfoque IA. Aunque se pondría interesante si el perseguido y/o el perseguidor tuviera una implementación más "inteligente".

 

Saludos,

[poliburro]

Yo no me había animado a participar por que de entrada no se qué es un sprite...

[ELKurgan]

Yo no me había animado a participar por que de entrada no se qué es un sprite...

 

http://es.wikipedia....e_(videojuegos)

 

Saludos

[poliburro]

http://es.wikipedia....e_(videojuegos)

 

Saludos

 

Mmmm interesante... Sería genial iniciar un juego usando sprites en moviles...

[genriquez]

Alguna vez implementé una solución a este problema, no para laberintos sino en una central de distribución eléctrica, para conocer la ruta de la energía, ya que en las centrales de distribución existen muchos caminos redundantes e interruptores para poder administrar la energía.

 

Efectivamente apliqué el Algoritmo de Tremaux  implementado con un grafo.

 

Adaptandolo a este problema, pienso que cada esquina donde cruza el laberinto puede ser un nodo, el link entre los nodos tendría el PESO o distancia y la posición donde está el objetivo otro nodo, en cada "jugada"  se buscarán las posibles rutas hasta el nodo objetivo, midiendo el peso de cada paso, así se podría ubicar el objetivo con la ruta más corta.

 

Lamentablemente no tengo tiempo, pero sería bien interesante implementarlo.

 

Saludos.

[cram]

Alguna vez implementé una solución a este problema, no para laberintos sino en una central de distribución eléctrica, para conocer la ruta de la energía, ya que en las centrales de distribución existen muchos caminos redundantes e interruptores para poder administrar la energía.

 

Efectivamente apliqué el Algoritmo de Tremaux  implementado con un grafo.

 

Adaptandolo a este problema, pienso que cada esquina donde cruza el laberinto puede ser un nodo, el link entre los nodos tendría el PESO o distancia y la posición donde está el objetivo otro nodo, en cada "jugada"  se buscarán las posibles rutas hasta el nodo objetivo, midiendo el peso de cada paso, así se podría ubicar el objetivo con la ruta más corta.

 

Lamentablemente no tengo tiempo, pero sería bien interesante implementarlo.

 

Saludos.

 

El caso de los nodos conocido como "problema del viajante" es sí, un caso de inteligencia artificial.

 

El asunto es que como lo dije antes es más sencillo.

Un caso muy conocido es del famoso Pac-Man, juego desarrollado con una tecnología poco conocida para un mundo que también era bastante nuevo (el mundo de los vídeo-juegos).

El caso es que los cuatro fantasmas que persiguen Mrs Pac-Man son Inky, Dinky, Pinky y Blue, donde:

Inky: persigue al Mrs. Pac-Man

Dinky: persigue a Inky.

Pinky: huye de -creo- Inky

Blue: se mueve al azar,

 

pero todos resuelven los caminos evitando los muros.

 

Digo que es más simple, porque el problema se reduce a la detección de los muros, es decir reconocimiento de los posibles caminos y para cambiar de rumbo, se debe reconocer aquellos caminos abiertos (ausencia de muros) a los costados, ya que luego de un avance el paso hacia atrás es verdadero y no requiere comprobación.

Los giros solo se hacen a derecha o izquierda y el movimiento es de tipo paso a paso, es decir que se debe cumplir una distancia para poder dar un nuevo paso o decidir si cambiar de rumbo.

Para decidir que rumbo tomar, se debe tener en cuenta las coordenadas del sprite perseguido.

Y eso es todo.

 

Po eso cuando planteé el problema (desafío) a la comunidad lo aclaré, no tener en cuenta a los sprites, ni en general a la parte gráfica. El problema es de tipo algorítmico, es decir que se puede resolver con pseudocódigo o diagramas de flujo.

 

Saludos.

[FerCastro]

El laberinto fue un proyecto de fin de semestre de estructura de datos en la universidad. Interesante el reto, y el chiste era que por medio de un heap indicaramos un camino cerrado.

 

Lo hice en pascal hace unos... 1995.

[cram]

Al fin pude encontrar (en realidad sacar mi cuaderno de cierto lugar), y les muestro las decisiones más simples para perseguir a una coordenada dentro de un laberinto sin partes complejas, como lo había explicado arriba (laberintos de tipo PacMan).

 

S:= 1

case S on

  1: si camino_libre(1) entonces caminar(1) caso contrario si (X > XP) entonces si camino_libre(7) entonces S:= 7 caso contrario si camino_libre(3) entonces S:= 3;

  3. si camino_libre(3) entonces caminar(3) caso contrario si (Y > YP) entonces si camino_libre(1) entonces S:= 1 caso contrario si camino_libre(5) entonces S:= 5;

  5: si camino_libre(5) entonces caminar(5) caso contrario si (X < XP) entonces si camino_libre(3) entonces S:= 3 caso contrario si camino_libre(7) entonces S:= 7;

  7: si camino_libre(7) entonces caminar(7) caso contrario si (Y < YP) entonces si camino_libre(5) entonces S:= 5 caso contrario si camino_libre(1) entonces S:= 1;

end;

 

1. Arriba

3. Derecha

5. Abajo

7. Izquierda

 

Aún así, esta pequeña orden de decisiones no puede solucionar dos casos en los que 1: queda sin poder moverse y 2: queda dando vueltas en círculo

Al agregar al final de las decisiones caso contrario S:= 5, 7, 1 y 3 respectivamente, se soluciona el primer error.

 

El algoritmo en MSX BASIC, fue algo así:

Como el tamaño de los sprites era de 8x8 pixels, los saltos debían ser de 8 en 8 y las celdas que formaban los muros también. En definitiva, era una matriz de cuadritos de 8x8 pixeles.

 

10 S = 1

20 ON S GOTO 30, 40, 50, 60

30 IF POINT (X+4, Y-1) <> C THEN Y = Y - 8: GOTO 70 ELSE 80

40 IF POINT (X+9, Y+4) <> C THEN X = X + 8: GOTO 70 ELSE 90

50 IF POINT (X+4, Y+9) <> C THEN Y = Y + 8: GOTO 70 ELSE 80

60 IF POINT (X-1, Y+4) <> C THEN x = X - 8: ELSE 90

70 PUT SPRITE 0, (X, Y), 15, 0: GOTO 20

80 IF X > A THEN 100 ELSE 120

90 IF Y > B THEN 110 ELSE 130

100 IF POINT(X-1, Y+4) <> C THEN S = 7: GOTO 20 ELSE 120

110 IF POINT(X+4, Y-1) <> C THEN S = 1: GOTO 20 ELSE 130

120 IF POINT(X+9, Y+4) <> C THEN S = 3: GOTO 20 ELSE 100

130 IF POINT(X+4, Y+9) <> C THEN S = 5: GOTO 20 ELSE 110

 

Bueno, les dejo el original en BASIC, ya que fue lo que encontré entre mis "apuntes del recuerdo" (año 1988).

Puede tener errores, pero para mover la cabeza un poco, sobre todo aquellos recién iniciados en la programación que cuentan con bastante tiempo para los ensayos.

 

Saludos

Editado por cram, 17 febrero 2016 - 03:05 .

[poliburro]

El laberinto fue un proyecto de fin de semestre de estructura de datos en la universidad. Interesante el reto, y el chiste era que por medio de un heap indicaramos un camino cerrado.

 

Lo hice en pascal hace unos... 1995.

 

Comparte el código...