La chica de febrero

 Lleva mucha ropa porque hace frío todavía, aquí por lo menos en el hemisferio norte. Habrá que esperar a la primavera señores.

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]);
        }