sábado, 3 de febrero de 2018

Algoritmo de búsqueda

 Buenas. Pues nada el otro día pensando que cosas meter en este blog que me puedan ser útiles para mi o para otras personas, ya que no tengo discípulos, me acordé de un algoritmo que recientemente implementé pero que fue desarrollado hace long time ago (más de una década), a poco de comenzar en DarKBasic (un engine para crear juegos en Basic). Dicho algoritmo es simplemente comprender la idea, apenas mostraré código, quizás si porque ya lo tengo implementado pero sólo basicamente y con lo de basicamente me refiero a no una forma compleja a la que puede llegar. El algoritmo en si no solamente sirve para hacer búsquedas, mientras lo desarrollaba con boli y papel (así es como se crean los algoritmos) me di cuenta que puede usarse para rellenar un polígono (dentro de una matriz dimensional) entre otros posibles propósitos. 

 Cuando hablo de búsquedas me refiero a completar una ruta desde un punto A a otro punto B. No me refiero a las consultas desde luego, eso no tiene mérito ninguno aunque se de alguien muy entendido en base de datos que me diría que las consultas de datos son algo pero que muy complejo, cosa que no estoy de acuerdo pues desde mi punto de vista lo complejo es para quienes no comprenden como funciona algo. Comprender tampoco es que necesariamente tengas que aprenderte de puntillas (de la A a la Z) todo el proceso, todos los pasos, los nombres, fechas o hitos históricos, algo que normalmente es como funciona la educación o los métodos educativos ¿Por qué esta énfasis en lo de comprender? Porque a pesar de que usted, lector de esta publicación, pierda el código fuente o nunca pueda recuperar esta página para consultar el algoritmo, típico en los pica-códigos (tranquilo yo también empecé así), siempre que comprenda como funciona podrá desarrollar el algoritmo, tal como me ha pasado.


La teoría del buscarutas

 Cuando desarrollé el algoritmo lo llamé buscarutas porque principalmente ese era su propósito. Su deber era trazar una ruta desde un punto A hasta otro punto B, en su recorrido podría encontrarse con lugares no ya restringidos sino también casi cerrados (o cerrados, no hay ruta posible). Así es como me vino a la cabeza, aunque fue algo visual. Me vino como conseguiría llegar a otro punto que estuviera fuera de un vaso o con forma de vaso. Pensé en el agua, el agua cuando llena el vaso se desborda. Si el problema solamente fuera ese, llenar el vaso... Y así fue como empecé, el algoritmo primigenio inundaba la matriz con unos datos que se comportaría como el agua hasta que esta tocara el otro punto.

 Para inundar la matriz simplemente se comienza desde un punto y se comprueba si hay salida a las celdas próximas, de estar estas vacías o no encontrarse un obstáculo se llena la celda con un dato. En principio se usaba un dato que significaba que estaba ocupado llena esa celda pero luego se optó por un método numérico.

 Este proceso, el de inundar se hace recursivamente. Esto significa que cada celda comprobará a su vez que sus celdas próximas estén vacías y de no estarlo las rellenará indiferentemente de si esas celdas se alejan del destino o el origen, ya que es necesario inundar la superficie para tener claro los límites, salidas o caminos posibles. Dese cuenta querido lector que el algoritmo está diseñado para que afronte con éxito una ruta que lo saque del laberinto más enrevesado, y esto es literal, no hablo metafóricamente.

 Si en el desarrollo optamos por una depuración visual de la matriz (dimensional) podríamos ver un resultado así:


 Llegado a este punto, tenemos algo que de alguna forma llega hasta el otro punto, valga la redundancia. Pero lo que nos interesa es que aparte de encontrar el camino lo genere porque así a priori lo que tenemos es un sistema que nos puede indicar que existe un camino o que también podríamos usar para rellenar polígonos, por ejemplo. Para resolver el siguiente punto me tomó varios días, pensando y garabateando sobre el papel hasta llegar a la conclusión de que era necesario un índice, algo que indicara además que después de un número iba otro número, pero ¿Bajo que regla o reglas? ¿La distancia? La verdad es que el sistema apareció de una forma que no recuerdo bien, pero es cierto que empezó como un índice. El código usado consistía en lo siguiente, se trataba de valores numéricos que ascendían, se incrementaban según se inundaba la superficie, los valores crecían y crecían y por alguna razón, no me acuerdo sinceramente porque llegué a esta conclusión o si lo sabía os juro que no recuerdo en este instante (más de diez años de eso), decidí tomar el valor más grande para trazar la ruta o camino y luego buscar el valor más pequeño que me señalaría al origen (siempre de mayor a menor).


 Y así amigos fue como conseguí algo tan crucial como crear un mapa 3D y que una entidad 3D llegara al objetivo aunque este cambiara su posición en el mapa, sin atorarse o quedándose caminando infinitamente hacia la pared como un gilipollas. El algoritmo originalmente trabajaba con desplazamiento diagonal pero para un trabajo reciente se me pedía que el desplazamiento solo fuera en cruz, como el movimiento de la torre en ajedrez y la verdad no me supuso ningún problema adaptarlo. Por eso si domináis bien esta técnica no es que paséis a cinturón negro de programación pero podréis resolver montón de problemas, incluso quien sabe, redes neuronales (ahora tan de moda).

Aplicación práctica (ejemplo)

Aquí una porción de una aplicación desarrollada en VanillaScript. La porción recoge como primero se encuentra el camino, la inundación, y la segunda parte más pequeña la que genera el camino y lo guarda en un array. En ambos caso se usan bucles indeterminados, aunque no falta decir que para evitar el cuelgue o la aplicación no responde etc... usar un contador para impedir que se quede en un bucle infinito. Cuando este contador llegue a cero se podría interpretar que no hay caminos posibles.

        var ruta=[];
        // creamos caminos
        movimientos=0;
        ruta[0]=[hastaX, hastaY,0];
        this.mapa=replaceAt(this.mapa, hastaY*this.anchoMapa+hastaX,movimientos); 
        this.mapa=replaceAt(this.mapa, desdeY*this.anchoMapa+desdeX," "); 
        var bucle=100;
        while(encontrado!=true && bucle>0){
            bucle--;
            for (var i in ruta){
                var punto=ruta[i];
              
                if (punto[2]==0){
                    ruta[i]=[punto[0],punto[1],1];
                    
                    if (this.mapa[punto[1]*this.anchoMapa+(punto[0]-1)]==" ") { 
                        movimientos++;
                        ruta[movimientos]=[punto[0]-1, punto[1],0];
                        this.mapa=replaceAt(this.mapa, punto[1]*this.anchoMapa+(punto[0]-1),"*");                   
                        if (ruta[movimientos][0]==desdeX && ruta[movimientos][1]==desdeY){
                            encontrado=true;
                            break;
                        }
                    }
                    if (this.mapa[(punto[1]-1)*this.anchoMapa+punto[0]]==" ") { 
                        movimientos++;
                        ruta[movimientos]=[punto[0], punto[1]-1,0];
                        this.mapa=replaceAt(this.mapa, (punto[1]-1)*this.anchoMapa+punto[0],"*");                  
                        if (ruta[movimientos][0]==desdeX && ruta[movimientos][1]==desdeY){
                            encontrado=true;
                            break;
                        }
                    }
                    if (this.mapa[punto[1]*this.anchoMapa+(punto[0]+1)]==" ") { 
                        movimientos++;
                        ruta[movimientos]=[punto[0]+1, punto[1],0];
                        this.mapa=replaceAt(this.mapa, punto[1]*this.anchoMapa+(punto[0]+1),"*");
                        if (ruta[movimientos][0]==desdeX && ruta[movimientos][1]==desdeY){
                            encontrado=true;
                            break;
                        }
                    }
                    if (this.mapa[(punto[1]+1)*this.anchoMapa+punto[0]]==" ") { 
                        movimientos++;
                        ruta[movimientos]=[punto[0], punto[1]+1,0];
                        this.mapa=replaceAt(this.mapa, (punto[1]+1)*this.anchoMapa+punto[0],"*");
                        if (ruta[movimientos][0]==desdeX && ruta[movimientos][1]==desdeY){
                            encontrado=true;
                            break;
                        }
                    } 
                }               
            }
        }
        
        var ruta_final=[];
        if (bucle!=0) { // generamos ruta o camino
            for (var i=movimientos;anterior!=i;){
                var punto=ruta[i], anterior=i;
                for (var ii=i-1;ii>0;ii--){
                    var siguiente=ruta[ii];
                    if ((Math.abs(punto[0]-siguiente[0])==1 && Math.abs(punto[1]-siguiente[1])==0) ||
                        (Math.abs(punto[0]-siguiente[0])==0 && Math.abs(punto[1]-siguiente[1])==1)){
                        i=ii;
                        ruta_final.push(ruta[i]);
                        break;
                    } 
                }
            
            }
            ruta_final.push(ruta[0]);
        }


6 comentarios:

  1. Hola, srwhiteskull, soy crazykenny, del foro de elhacker.net.

    Veras, acabo de leer tu articulo sobre tu codigo de DarkBasic, y, bueno, quisiera preguntarte una cosa, si no es molestia, claro esta: ¿estuviste registrado en el foro de gamedevelopers, administrado por xuri?.

    Y, bueno, se que el administrador del foro lo cerro hace ya bastante tiempo, pero yo fui un usuario casual de ese foro y recuerdo que se uno de los usuarios publico el mismo programa (y en el mismo lenguaje) de tu articulo, y me preguntaba si tu eras el mismo que habia publicado el programa en aquel entonces.

    Saludos.

    ResponderEliminar
    Respuestas
    1. Estuve tanto en el foro inglés como en uno no oficial en español también de DarkBasic. No recuerdo bien si lo llegué a publicar en el foro inglés, creo que no, fue hace muchos años. Se que aparte de mi hubo otros usuarios que crearon su propio algoritmo, y nos pusimos a picarnos a ver quien hacía la búsqueda más rápida. El mío era rápido en algunos escenarios pero la resolución era buena, siempre encontraba una ruta y en un tiempo(la media) que yo pienso es bueno. Es más el algoritmo luego lo porté a C (originalmente hecho en DarkBasic) y lo convertí en una DLL para importarlo en DarkBasic y el tiempo de búsqueda mejoró muchísimo más. En el vídeo que muestro más adelante uso el algortimo, pero solo realiza la búsqueda cuando le daba a la tecla de espacio que a su vez ponía en funcionamiento la animación de saltar. Si te fijas cuando hace la animación de saltar el personaje de dios egipcio (lo saqué de un pack) comienza a caminar hasta la chica. Algunas veces se quedaba trabado pero por el sistema de colisión que tenía poca resolución. https://www.youtube.com/watch?v=Dq35srQqIZ8

      Eliminar
    2. Ya veo, y gracias por responder tan rapido.

      Y, bueno, me alegra ver a otro usuario que tambien participo en los foros de darkbasic, aunque yo solo estuve en el foro español. :)

      Eliminar
    3. Por cierto, casi se me olvida una cosa.

      Habia un moderador de una web y foro de darkbasic que se llamaba battlin (o, almenos, creo que este era su nick) que, si no recuerdo mal, siguio colaborando en la seccion de darkbasic en el foro que he comentado al principio (la web creo que era "portalxuri.dydns.org").

      Entonces, lo que quisiera comentarte es si conocias algo de este usuario, ya que creo dejo el foro (o, almenos, por el tema de actividad y publicar) y, bueno, aunque surgio el tema en el foro, creo no llegue a saber porque lo dejo, y quisiera preguntar si sabias porque lo habia dejado.

      Saludos.

      Eliminar
    4. No me suena, pero desconozco el paradero de los pocos que conocía. Además había un colega quien me introdujo en el mundo de DarkBasic (creo que su nick era Chafariz), de quien aprendí muchas cosas del mundo 3D incluso a modelar/animar con aplicaciones de modelado y render, y del cual tampoco se donde anda y eso que vivimos en la misma ciudad. Me imagino que fue como una moda pasajera, nada perdura eternamente y hoy estás aquí y mañana allá XD
      Saludos.

      Eliminar
    5. Entiendo, y, bueno, muchas gracias por responder, Pedro RG. :)

      Saludos.

      Eliminar