• Viernes 29 de Marzo de 2024, 00:28

Autor Tema:  Ayuda Laberinto De Un Robot  (Leído 1092 veces)

jimadorboy

  • Nuevo Miembro
  • *
  • Mensajes: 1
    • Ver Perfil
Ayuda Laberinto De Un Robot
« en: Jueves 28 de Junio de 2007, 02:49 »
0
HOLA QUE TAL A TODOS , ALGUIEN ME PUDIERA AYUDAR CON UN PROGRAMA EN C#, ODAR ALGUNA IDEA?  EL PROBLEMA ES EL SIG: NECESITO UN TABLERO DE 20 X 15 CASILLAS DONDE SE PONGAN ALEATORIAMENTE 40 OBSTACULOS Y ALEATORIAMENTE 2 SALIDAS EN EL CONTORNO DEL TABLERO , DONDE UN ROBOT BUSCARA LAS SALIDAS  EN TODO EL TABLERO. CUALQUIER OPINION O TIP ES BIENVENIDO .. GRACIAS

Enko

  • Miembro de PLATA
  • *****
  • Mensajes: 1562
  • Nacionalidad: 00
    • Ver Perfil
Re: Ayuda Laberinto De Un Robot
« Respuesta #1 en: Viernes 29 de Junio de 2007, 01:04 »
0
Busca informacion en Google hay de sobra.
Lo que buscas se llama PahtFinding. Existen numerosos algoritmos que hacen eso,  uno muy conocido y el "mas optimizado" es el algoritmo A* (A Star) pero es bastante dificil de implementar.

El mas sencillo que existe es este:
(esta explicado parra ActionScript pero aun asi es un buen link)
http://www.tonypa.pri.ee/tbw/tut22.html

La idea el algoritmo es:
Debes tener 2 listas de tipo pila o cola.
1)La pirmera lista es para los casillas no verificadas
2)La segunda es para las que ya se verifico.

El algoritmo funciona asi:
Te colocas en la casilla de entrada. (seria el primer elemento de la lista de celdas para verificar>)
Verificas si la casilla actual es distinta a la casilla final.
Si es igual, se encontro la salida.
Si es distinta empezamos:
   Verificas si las celdas contiguas no tienen obstaculo, las que no tienen obstaculo las agragas a la lista de celdas para verificar solo si ya no fueron verificadas. (cada vez que chequeas una celda, la agregas a la lista de celdas chequeadas)
Sacas un elemento de la lista de casillas para verificar y verificas que no sea la celda final de la meta.
    Si no es la final, la colocas en la lista de las celdas ya verificadas y agregas a la lista de las celdas para verificar todas las celdas contiguas a esa casilla salgo las que ya estan verificadas (para eso esta la lista de celdas verificadas).
Esto lo repites hasta que la casilla actual sea la final.


Basicamente, todo pasa por ir recoriendo todas las casillas salgo las que ya fueron recoridas.

Fijate en el link de Actionscript que esta muy bien explicado.