diario rck: algoritmo A * en javascript (A star)

<html>
    <head>
        <script type="text/javascript" src="http://code.jquery.com/jquery-3.2.1.min.js"></script>  
    
        <style>
        .casilla{
            width: 13px; 
            height: 13px;
            font-size: 10px;
            border:1px solid green;
        }
        </style>


    </head>
    <body>
    Alogritmo A*<br>

    <label for="escenarios">Escenarios:</label>
    <select id="escenarios" onchange="TABLERO.cambiarEscenario(this)">
        <option value="elegir">Elegir</option>
        <option value="escenario_1">Escenario 1</option>
        <option value="escenario_2">Escenario 2</option>
        <option value="escenario_3">Escenario 3</option>
 
      </select>
    <!-- <br> -->
    <!-- <input type="button" value="Eliminar Jugadas" id="eliminar_jugadas"> -->
    <br>
    <span>Posicion Inicial <span id="pos_inicial">(3,1)</span></span>
    <span>Posicion Final <span id="pos_final">(3,5)</span></span>

    <table style="width:150px;" id="tablero">
        <tr>
          <td class="casilla" id="casilla_0_0">1</td>
          <td class="casilla" id="casilla_1_0">2</td> 
          <td class="casilla" id="casilla_2_0">3</td>
          <td class="casilla" id="casilla_3_0">4</td>
          <td class="casilla" id="casilla_4_0">5</td>
          <td class="casilla" id="casilla_5_0">6</td>
          <td class="casilla" id="casilla_6_0">7</td>
          <td class="casilla" id="casilla_7_0">8</td>
        </tr>
      </table>

    <br>
    <input type="button" value="buscar solucion A Star" id="btn_2">
    
    <br>
    <div id="mensaje"></div>
  
    
        <script>

        var NADA = 0;

        //los movimientos posibles
        var filas = [ 0, 0, 1, -1 ,1,1,-1,-1]; 
        var columnas = [ 1, -1, 0, 0,1,-1,1,-1 ];
  
        var puntoInicio = {i:3,j:1}
        var puntoFinal = {i:3,j:5}

        //8x8
        var tablero =[
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0],
            [0,0,0,1,0,0,0,0],
            [0,0,0,1,0,0,0,0],
            [0,0,0,1,0,0,0,0],
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0]
        ];


var ESCENARIOS = {
    //8 es inicio, 9 es el final
    escenario_1 : {
        ini: {i:3,j:1},
        fin:  {i:3,j:5},
        tablero: [
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0],
            [0,0,0,1,0,0,0,0],
            [0,0,0,1,0,0,0,0],
            [0,0,0,1,0,0,0,0],
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0]
        ]
    },
    escenario_2 : {
        ini: {i:1,j:2},
        fin:  {i:3,j:5},
        tablero: [
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0],
            [0,0,1,1,1,1,1,0],
            [0,0,0,0,0,0,1,0],
            [0,0,1,1,1,1,1,0],
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0]
        ]
    },
    escenario_3 : {
        ini: {i:1,j:0},
        fin:  {i:2,j:4},
        tablero: [
            [0,0,0,0,0,0,0,0],
            [0,0,1,1,1,1,0,0],
            [0,0,1,0,0,1,1,0],
            [0,0,1,0,1,1,0,0],
            [0,0,1,0,1,1,0,0],
            [0,0,1,1,0,1,0,0],
            [0,0,0,0,1,0,1,0],
            [0,0,0,0,0,0,0,0]
        ]
    },
}

var TABLERO = {

    cambiarEscenario: function(obj){
        // console.log("escenario_1")

        if(obj.value == "escenario_1"){
            tablero = ESCENARIOS.escenario_1.tablero;

            puntoInicio = ESCENARIOS.escenario_1.ini;
            puntoFinal = ESCENARIOS.escenario_1.fin;
            Sistema.dibujarTableroVisible(tablero)
            console.log("escenario_1")
      
        }

        if(obj.value == "escenario_2"){
            tablero = ESCENARIOS.escenario_2.tablero;

            puntoInicio = ESCENARIOS.escenario_2.ini;
            puntoFinal = ESCENARIOS.escenario_2.fin;
            Sistema.dibujarTableroVisible(tablero)
            console.log("escenario_2")
        }

        if(obj.value == "escenario_3"){
            tablero = ESCENARIOS.escenario_3.tablero;

            puntoInicio = ESCENARIOS.escenario_3.ini;
            puntoFinal = ESCENARIOS.escenario_3.fin;
            Sistema.dibujarTableroVisible(tablero)
            console.log("escenario_3")
        }

        $("#pos_inicial").html("(" + puntoInicio.i + "," + puntoInicio.j + ")")
        $("#pos_final").html("(" + puntoFinal.i + "," + puntoFinal.j + ")")
    }

}



function NodoSolucion(fila, columna, papi = null, fin = null) {

        this.f;
        this.c;

        this.F = 0; 
        this.G = 0; 
        this.H = 0;

        this.papa = null;  //es recursivo
        this.camino = null; //PARA EVITAR APILAR Y DESAPILAR

        this.f = fila;
        this.c = columna;
        if( papi != null ) this.papa = papi;
        
        if( fin != null ){
            this.H = (dif(this.f,fin.f) + dif(this.c,fin.c)) * 10;  //distancia q queda
        } 
        
        if( this.papa != null ){
            this.G = dist(this.f, this.c, this.papa.f, this.papa.c) * 10;  //costo x pasar x aca
        }
        if (this.G > 10) { this.G = 14; }
        //es un movimiento diaogonal q da 20 pero es 14    
        this.F = this.G + this.H;


        this.GetF_TotalHastaAca= function()
        {      
            var acum = this.F;
            var ptr = this.papa;
            while (ptr != null)
            {
                acum += ptr.F;
                ptr = ptr.papa;
            }

            return acum;
        }

        this.GetG_TotalHastaAca= function()
        {
            var ptr;
            var acum = this.G;

            ptr = this.papa;
            while (ptr != null)
            {
                acum += ptr.G;
                ptr = ptr.papa;
            }

            return acum;
        }    
        
        var este = this
 
        this.getArrSolucion = function(){
      
            var ptr = este;
            var arrSolucion = []

            while (ptr != null)
            {
                arrSolucion.push({i:ptr.f, j:ptr.c})
                ptr = ptr.papa 
            }

            return arrSolucion;
        }


        /*Metodos Privados*/

        function cuadrado(x) { return x * x; }
        function dif(a, b) { if (a >= b)return a - b; return b - a; }
        function dist(xi, yi, xf, yf)
        {
            var a, b;
            a = cuadrado(dif(xf, xi));
            b = cuadrado(dif(yf, yi));
            return a + b;
        }
 }

// var testNodos = []
// var nodo = new NodoSolucion(3,1)
// testNodos.push(nodo)
// testNodos.push(new NodoSolucion(3,2))
// testNodos.push(new NodoSolucion(3,3))
// console.log(testNodos)
// testNodos.sort(CompararPorF);
// console.log(testNodos)


function buscar_solucion_astar(){

    var res = AStar(tablero, puntoInicio.i, puntoInicio.j)
    if (res == 0){
        console.log("AStar: No puedo!!! ");
    }else{
        // console.log("solucion", res)
        res = res.reverse();
        for(var pos=1; pos<res.length-1; pos++){   
            var element = res[pos]
            $("#casilla_" + element.i +'_'+ element.j ).html("" + pos)
        };
    }
}


function AStar(T, yi, xi)
        {

            var f, c, yAct, xAct, pos;
            var yf = puntoFinal.i;
            var xf = puntoFinal.j;

            var caminosPorExplorar = []
            var camino = []

            var ini = new NodoSolucion(yi, xi);
            var fin = new NodoSolucion(yf, xf);

            caminosPorExplorar.push(ini);                      //lo agrego a la cola
  
            var ptr;

            while (caminosPorExplorar.length > 0 )
            {
                ptr = caminosPorExplorar.shift(); 
           
                yAct = ptr.f;
                xAct = ptr.c;

                //llegue entonces marcar el camino volviendo para atras
                if (yAct == yf && xAct == xf) {           
                    camino.push(ptr);              
                    var arrSol = ptr.getArrSolucion();                     
                    return arrSol; 
                }

                // debugger;
                // #region AgregoAdyacentes

                for (var jug = 0; jug < 8; jug++)
                {
                    f = yAct + filas[jug];
                    c = xAct + columnas[jug];

                    // estoy adentro del tablero ? y no esta jugadoo no es pared?
                    if ((0 <= f) && (f < 8) && (0 <= c) && (c < 8) && (T[f] [c] == NADA))      
                    {
                        var nd = new NodoSolucion(f, c, ptr, fin);                 
                        //(casilla actual o nueva ,ultima casilla o anterior o papa , casilla fin o destino)
                        //papa usado para calculo de G y destino para calculo de H
                        fil = f;
                        colum = c;

                        if ((pos = caminosPorExplorar.findIndex((element => (element.f == fil && element.c == colum) )) ) >= 0) // con array function -1 si no esta
                        {//si esta
                            //comparo sus G totales                          
                            if (nd.GetG_TotalHastaAca() < caminosPorExplorar[pos].GetG_TotalHastaAca())
                            {
                                caminosPorExplorar.splice(pos, 1);                               
                                caminosPorExplorar.push(nd);
                            }//else nd.Dispose();

                        }
                        else 
                        {//si no esta en caminos x ezplorar ni tampoco en camino entonces lo agrego                    
                            if (!camino.find((element => (element.f == fil && element.c == colum) )) )
                            {
                                caminosPorExplorar.push(nd);
                            }//else nd.Dispose();                        
                        
                        }

     
                    }else{
                        // console.error("jugada no valida", f,c)
                    }
                }
                // #endregion
                camino.push(ptr);    //los hijos de este padre ya estan ligados          
                caminosPorExplorar.sort(CompararPorF);
            }
            
            return 0;
        }

// -----------------------------------------------------------------------------------------------------------------
        //predicado para el sort   
        function CompararPorF( n1, n2) 
        {
            if (n1.F < n2.F) return -1;
            if (n1.F == n2.F) return 0;
            return 1;
        }
// -----------------------------------------------------------------------------------------------------------------

function resetTablero(){
    for (var i = 0; i < 8; i++) {
        for (var j = 0; j < 8; j++) {      
          tablero[i][j] = 0;

        }
    }
}


var Sistema ={

    crearTableroVisible : function(){
        var casilla = 1
        var str = ""
        for (var i = 0; i < 8; i++) {
            str += "<tr>"
            for (var j = 0; j < 8; j++) {      
            str += '<td class="casilla" id="casilla_'+ i +'_'+ j +'">' + casilla++ + '</td>'

            }
            str += "</tr>"
        }

        $("#tablero").html(str)
    },

    resetTableroVisible : function(){
        // var casilla = 1
        var str = ""
        for (var i = 0; i < 8; i++) {
            str += "<tr>"
            for (var j = 0; j < 8; j++) {      
            str += '<td class="casilla" id="casilla_'+ i +'_'+ j +'">' + 0 + '</td>'

            }
            str += "</tr>"
        }

        $("#tablero").html(str)
        
    },

    dibujarTableroVisible : function(tablero){
        // var casilla = 1
        var str = ""
        for (var i = 0; i < 8; i++) {
            str += "<tr>"
            for (var j = 0; j < 8; j++) {                
                if(tablero[i][j] == 0){
                    str += '<td class="casilla" id="casilla_'+ i +'_'+ j +'">' + ' ' + '</td>'
                }    
                if(tablero[i][j] == 1){
                    str += '<td class="casilla" id="casilla_'+ i +'_'+ j +'">' + '&#9608;' + '</td>'
                }    
               
            }
            str += "</tr>"
        }

        // puntoInicio
        //
        // $("#casilla_" + puntoInicio.i +'_'+ puntoInicio.j ).css('color', 'red')
        // (function(){ 
        //     $("#casilla_1_5").css("color","red")
        // })();
            
        setTimeout(function(){
            $("#casilla_" + puntoInicio.i +'_'+ puntoInicio.j ).html("i")
            $("#casilla_" + puntoInicio.i +'_'+ puntoInicio.j ).css("color","red") 

            $("#casilla_" + puntoFinal.i +'_'+ puntoFinal.j ).html("f")
            $("#casilla_" + puntoFinal.i +'_'+ puntoFinal.j ).css("color","blue") 


            // $("#casilla_1_5").css("color","red") 
        }, 50);
        
        // console.log(puntoInicio)

        $("#tablero").html(str)
    }

}

$( document ).ready(function() {

    Sistema.crearTableroVisible()

    $(".casilla").click(function(){    
        console.log(this.id)
    })

    $("#reset_tablero").click(function(){    
        Sistema.resetTableroVisible()       
        $("#mensaje").text("")
    })

    $("#btn_1").click(function(){    
        Sistema.resetTableroVisible()
        resetTablero() //el interno
        pasos_limite_caballo = parseInt( $("#pasos_limite_caballo").val() )
        buscar_solucion()
    })

    $("#btn_2").click(function(){    
        // Sistema.resetTableroVisible()
        // resetTablero() //el interno
        // pasos_limite_caballo = parseInt( $("#pasos_limite_caballo").val() )
        console.log("iniciando..")
        buscar_solucion_astar()
    })

    // Sistema.dibujarTableroVisible(tablero)

});

    
        </script>
    </body>
    </html>
diario rck

miércoles, 15 de abril de 2020

algoritmo A * en javascript (A star)

1 comentario:

Datos personales

Archivo del blog

Seguidores
