IA de JavaScript para un rompecabezas de mosaicos deslizantes HTML

 

 

 

  • Patrones de diseño de interfaces inteligentes, vídeo de 10h + formación UX
  • Taller de diseño conductual, con Susan y Guthrie Weinschenk

  • Índice
    1. Disposición
    2. Inteligencia artificial
      1. ¿Qué hará la búsqueda A*?
      2. Misplaced Tiles

    Ingrese al asombroso mundo de los agentes racionales, el aprendizaje supervisado y el aprendizaje no supervisado. Comience a desarrollar algoritmos que puedan resolver problemas de la vida diaria simulando el pensamiento de la mente humana. En este artículo, Arnaldo Pérez Castaño describirá una inteligencia artificial mediante un algoritmo de búsqueda A* para el rompecabezas de fichas deslizantes. ¡Podrás competir con amigos y crear inteligencias artificiales para este y muchos otros rompecabezas y juegos!

     

    Sam Loyd (1841-1911), ajedrecista y creador de rompecabezas estadounidense, creó el rompecabezas de fichas deslizantes en la década de 1870. El rompecabezas está representado por una cuadrícula de m × n , donde m es el número de columnas y n es el número de filas, y cada celda puede tener cualquier valor imaginable (número, letra, imagen, etc.).

    El propósito del rompecabezas es reorganizar la configuración inicial de las fichas para que coincida con otra configuración conocida como configuración de objetivo . La tarea de reorganización se logra intercambiando la ficha vacía por otra ficha en todas las direcciones posibles (arriba, abajo, izquierda y derecha).

    Se supone que la ficha vacía no se puede sacar del tablero: por lo tanto, si se ubica en la primera columna, la ficha vacía no puede ir a la izquierda; y si se ubica en la columna de más a la derecha, no puede ir hacia la derecha; Lo mismo se aplica a las filas que consideran movimientos hacia arriba o hacia abajo. La solución al rompecabezas anterior la obtendrás en los siguientes pasos.

    …y finalmente:

    Verifique que las configuraciones inicial y objetivo ahora sean las mismas; esto significa que hemos completado el rompecabezas.

    Este artículo se dividirá en dos partes. Primero, proporcionaremos una breve descripción de cómo crear y desarrollar un rompecabezas de mosaicos deslizantes usando HTML, CSS para los aspectos visuales y JavaScript para mover (mediante animación) los mosaicos en el tablero. (Necesitaremos esto para ilustrar la última parte de este artículo).

    En segundo lugar, desarrollaremos una inteligencia artificial mediante un algoritmo de búsqueda A* capaz de encontrar una solución con el mínimo número de movimientos hasta la configuración objetivo, proporcionando así una solución óptima. Las diversas heurísticas asociadas con el algoritmo A* ayudarán a guiar la búsqueda y cuanto más inteligente sea la heurística, antes se encontrará la solución óptima. Cada una de las heurísticas descritas se presentará en orden de inteligencia; por lo tanto, la última heurística presentada será la más poderosa.

     

    Disposición

    Comenzaremos creando el archivo slide_tiles_puzzle.html correspondiente que contendrá el juego; También crearemos los siguientes archivos vacíos:

    • estilos.css
    • stpuzzle.js

    Además, será necesario añadir jquery.js ya que lo utilizaremos para hacernos la vida más fácil y conseguir un código mucho más elegante y legible.

    El encabezado debería terminar luciendo así:

    head meta name="viewport" content="width=device-width, initial-scale=1.0" meta http-equiv="Content-Type" content="text/html; charset=UTF-8" / link href="css/styles.css" rel="stylesheet" media="screen" type="text/css" titleSliding Tiles Puzzle/title/head

    Para mayor eficiencia, agregaremos enlaces a cada secuencia de comandos en la parte inferior de la página. Esta es una práctica común, ya que las páginas se representan de arriba a abajo y normalmente queremos que la página se cargue lo más rápido posible; Dejamos que los scripts funcionales se carguen al final, después de que todos los elementos visuales se hayan cargado correctamente.

     script type="text/javascript" src="js/jquery.js"/script script type="text/javascript" src="js/priority-queue.js"/script script type="text/javascript" src="js/hashtable.js"/script script type="text/javascript" src="js/hashset.js"/script script type="text/javascript" src="js/stpuzzle.js"/script /body/html

    Priority -queue.js , hashtable.js y hashset.js se utilizarán en el componente de inteligencia artificial para brindar eficiencia a nuestro agente racional; representan respectivamente colas de prioridad, tablas hash y estructuras de datos de conjuntos hash.

    Ahora comenzaremos a crear el diseño de la página. Al principio, nuestro diseño se verá así.

    body div /div div /div

    La containerclase, ubicada en el archivo estilos.css , aparece como en el siguiente bloque de estilos.

    /* Developed by Arnaldo Perez [email protected]*/.container { width:1024px; margin-left: auto; margin-right: auto; min-height:380px;}

    El panel es simplemente un registro que usaremos para imprimir o mostrar los resultados asociados al componente de inteligencia artificial. En este panel estaremos imprimiendo la solución óptima obtenida por la IA.

    #panel { width:100%; background-color: rgb(180,180,180); min-height:1000px; color:white; font-weight: bold; padding:5px; font-family: Arial;}

    Como queremos que el contenedor global esté en el centro de la página, configuramos un ancho fijo, propiedades margin-lefty margin-rightautomático; esto lo ubicará justo en el medio. Ahora agregamos el grid-containerdiv que, como su nombre indica, es básicamente el div que contendrá inmediatamente la cuadrícula que representa el tablero.

     

    div div h2 Initial Config /h2 /div/div

    La grid-containerclase y los selectores que la involucran se ilustran en los siguientes bloques.

    .grid-container { float: left; width:210px; height:250px; text-align: center; width:50%;}.grid-container h2 { font-family: Tahoma;}

    Estamos flotando hacia la izquierda del contenedor del grid ya que pondremos dos de estos en la misma línea: uno para cada configuración (inicial y objetivo). Finalmente, agregamos el grid div.

    div h2 Initial Config /h2 div div div data-pos="0,0"span6/span/div div data-pos="0,1"span4/span/div div data-pos="0,2"span7/span/div /div div div data-pos="1,0"span8/span/div div data-pos="1,1"span5/span/div div data-pos="1,2"/div /div div div data-pos="2,0"span3/span/div div data-pos="2,1"span2/span/div div data-pos="2,2"span1/span/div /div /div/div

    La cuadrícula del rompecabezas de fichas deslizantes consta de tres filas, cada una con tres celdas; esto básicamente constituye toda la cuadrícula. Con el diseño propuesto conseguimos una forma muy intuitiva de representar la cuadrícula. La cuadrícula contiene tres hijos; cada hijo es una fila (elemento div); una fila contiene tres hijos; y cada niño representa una celda (también un elemento div).

    Para cuestiones relacionadas con la programación agregamos el data-posatributo a cada celda, para indicar la posición de cada celda en el tablero. Lo mismo ocurre con la startclase. Necesitamos diferenciar la configuración inicial de la configuración objetivo ya que esta última no recibirá información del usuario. La startclase nos ayudará a lograrlo. La definición de las clases anteriores se enumera en las siguientes líneas.

    .grid { background-color: rgb(248,248,248); border: solid 5px rgb(249, 90, 0); width:210px; height:210px; margin-left: auto; margin-right: auto; border-radius: 3px; box-shadow: 5px 5px #d8d8d8, 5px 5px #d8d8d8; overflow: auto;}.row { height:33.3%;}.cell { width:32.3%; height:100%; float: left; text-align: center; font-size:150%; font-family: Arial; font-weight: bold; position:relative;}.cell:hover { background-color: rgb(221,221,221);}.cell span { display: block; transform: translateY(70%);}

    El resultado final es una cuadrícula completa de 3×3 con los números del 1 al 9.

    Para obtener la configuración del objetivo en la página, simplemente copiamos el grid div y todo su contenido y cambiamos el nombre de la startclase a goal.

    div h2 Goal Config /h2 div div divspan1/span/div divspan2/span/div divspan3/span/div /div div divspan4/span/div divspan5/span/div divspan6/span/div /div div divspan7/span/div divspan8/span/div div/div /div /div/div

    Para concluir, agregamos los botones Resolver y Mostrar paso al primer contenedor de cuadrícula.

     

    button Solve /buttonbutton Show Step /button

    El primer botón activará al agente racional; en otras palabras, el algoritmo de búsqueda A*. El segundo mostrará visualmente un paso de la solución obtenida por el primero. Por lo tanto, al presionar el botón Mostrar paso n veces, donde n es la longitud de la solución, sabremos cómo resolver el rompecabezas en el mínimo número de pasos.

    Ahora que tenemos algo de competencia visual, comencemos a desarrollar alguna competencia funcional. Necesitamos hacer que el juego funcione; básicamente, eso se traduce en permitir que la ficha vacía se mueva por todo el tablero. Para completar esta pieza de desarrollo usaremos JavaScript. Las primeras líneas del archivo stpuzzle.js se verán así

    /* Developed by Arnaldo Perez Castano [email protected]*/var emptytilePosRow = 1;var emptytilePosCol = 2;var cellDisplacement = "69px";

    El emptytilePosRowy emptytilePosColnos indicará dónde está el mosaico vacío en cada momento. Se actualizará con cada movimiento realizado.

    La cellDisplacementvariable indicará el valor de desplazamiento a aplicar a una celda cuando se esté realizando una animación. Observe cómo la cellclase tiene el positionatributo establecido en relativo. Queremos mover libremente las celdas en el tablero usando las propiedades topy righten las animaciones. El cellDisplacementvalor indicará los nuevos valores de las propiedades topy right, moviendo así las celdas.

    La función que se encarga de los movimientos en el tablero comienza así:

    function moveTile() { // Gets the position of the current element var pos = $(this).attr('data-pos'); var posRow = parseInt(pos.split(',')[0]); var posCol = parseInt(pos.split(',')[1]);

    Observe cómo ya estamos usando jQuery para seleccionar todas las celdas de la cuadrícula inicial. Tenga en cuenta también el uso de la startclase. Queremos mantener el tablero de objetivos como de solo lectura, por lo tanto seleccionamos todas las celdas que pertenecen a la cuadrícula de inicio, y solo a la cuadrícula de inicio. A continuación, obtenemos la posición de la celda que se está seleccionando. Recuerde, las posiciones se almacenan como ' x , y ': obtenemos los índices de filas y columnas en las variables posRowy posCol.

    El resto de la función está dedicada a ejecutar el movimiento correcto.

    // Move Up if (posRow + 1 == emptytilePosRow posCol == emptytilePosCol) { $(this).animate({ 'top' : "+=" + cellDisplacement //moves up }); $('#empty').animate({ 'top' : "-=" + cellDisplacement //moves down }); emptytilePosRow-=1; $(this).attr('data-pos',(posRow+1) + "," + posCol); } // Move Down if (posRow - 1 == emptytilePosRow posCol == emptytilePosCol) { $(this).animate({ 'top' : "-=" + cellDisplacement //moves down }); $('#empty').animate({ 'top' : "+=" + cellDisplacement //moves up }); emptytilePosRow+=1; $(this).attr('data-pos',(posRow-1) + "," + posCol); } // Move Left if (posRow == emptytilePosRow posCol + 1 == emptytilePosCol) { $(this).animate({ 'right' : "-=" + cellDisplacement //moves right }); $('#empty').animate({ 'right' : "+=" + cellDisplacement //moves left }); emptytilePosCol -= 1; $(this).attr('data-pos',posRow + "," + (posCol+1)); } // Move Right if (posRow == emptytilePosRow posCol - 1 == emptytilePosCol) { $(this).animate({ 'right' : "+=" + cellDisplacement //moves left }); $('#empty').animate({ 'right' : "-=" + cellDisplacement //moves right }); emptytilePosCol += 1; $(this).attr('data-pos',posRow + "," + (posCol-1)); } // Update empty position $('#empty').attr('data-pos',emptytilePosRow + "," + emptytilePosCol);}

    Cada una de las cuatro ifdeclaraciones representa un movimiento diferente para la ficha vacía. Comparten similitudes ya que sus principales diferencias residen en las condiciones, signos y actualización de las variables. El movimiento hacia la derecha, por ejemplo, comienza comprobando si el mosaico vacío está a la izquierda de la celda actual mediante la condición: posRow == emptytilePosRow(lo mismo que decir que están en la misma fila) y posCol - 1 == emptytilePosCol(lo mismo que decir que el mosaico vacío está a la izquierda de la celda actual).

     

    Si se cumple la condición entonces, usando la animación de JQuery, cambiamos el valor de la rightpropiedad para desplazar la celda actual hacia la izquierda y crear la ilusión de haber intercambiado los elementos. La ifdeclaración termina actualizando la emptytilePosColvariable (agregando 1) a medida que se movió hacia la derecha y actualizando la posición de la celda que se movió hacia la izquierda (restando 1 de su posición en la columna). Al final, actualizamos la posición del mosaico vacío.

    Inteligencia artificial

    La búsqueda informada A* (Hart et al, 1968) representa el agente racional no vivo que desarrollaremos para resolver el rompecabezas de las baldosas deslizantes. Un agente racional es una entidad que, siendo parte de un entorno y sujeta a determinadas reglas, es capaz de percibir en ese entorno y actuar racionalmente ante dichas percepciones. La racionalidad estaría dada por la adecuada toma de decisiones por parte del agente, considerada apropiada si está orientada a maximizar algún resultado deseado. La inteligencia artificial es el agente mismo. Noticias del cadiz

    Los humanos somos agentes vivos racionales (la mayor parte de las veces) ya que pertenecemos a un entorno (el universo) y estamos sujetos a ciertas reglas ambientales (no podemos vivir bajo temperaturas extremadamente frías, por ejemplo); obtenemos percepciones del entorno (sentimos frío) y reaccionamos racionalmente (de nuevo, la mayor parte del tiempo) a estas percepciones (llevamos abrigos).

    En el contexto del rompecabezas de fichas deslizantes, el entorno está representado por el tablero, las reglas o restricciones por las posibles direcciones en las que se puede mover la ficha vacía (arriba, abajo, izquierda, derecha) y por el hecho de que ejecutas un movimiento válido cuando intercambias la ficha vacía con cualquiera de sus fichas adyacentes. Una percepción corresponde al estado actual de la configuración y la reacción racional a esta percepción corresponde al movimiento ejecutado. Si es racional, este movimiento debería estar orientado a conseguir una configuración que coincida con la configuración objetivo.

     

    ¿Qué hará la búsqueda A*?

    La búsqueda A*, como sugiere el nombre, es un algoritmo de búsqueda, cuyo propósito es buscar inteligentemente el estado del espacio (conjunto de todas las configuraciones de la placa) y encontrar una ruta desde la configuración inicial hasta la configuración objetivo. La inteligencia de la búsqueda viene dada por el número de estados que visita: cuanto menor sea el número de estados visitados, más inteligente será y antes proporcionará una solución. Para navegar por el estado espacial, modelamos el problema como un gráfico. De esta manera, consideramos que el estado B es hijo del estado A si B se obtiene moviendo la ficha vacía en alguna dirección válida en A. En este sentido, un nodo en el gráfico puede tener como máximo cuatro hijos, uno para cada dirección posible.

    La búsqueda A* se informa ya que utiliza el conocimiento del entorno para seleccionar el siguiente paso para continuar la búsqueda. Este conocimiento está representado por un valor numérico asociado a cada estado ( s ) y conocido como f(s) , de ahí que en general:

    f(s) = g(s) + h(s)

    donde g(s) es el costo de alcanzar el estado s desde el estado inicial y h(s) es el costo estimado de alcanzar el estado objetivo desde el estado o configuración actual. Esta relación se representa en la siguiente figura.

    Para guiar la búsqueda a través del inmenso estado espacial utilizamos heurísticas. Una heurística es la forma en que adherimos nuestro conocimiento empírico y específico del entorno al agente racional, en este caso la búsqueda A*. Se supone que la información proporcionada por la heurística ayuda a encontrar un camino corto y factible hacia la configuración del objetivo.

    Dado que estamos modelando el problema como un gráfico, el esqueleto básico de la búsqueda A* corresponde al de una búsqueda en amplitud (BFS), un algoritmo de búsqueda de gráficos clásico. La diferencia entre la búsqueda A* y BFS es que los nodos o estados en la búsqueda A* están asociados con algún valor f(s) y el nodo seleccionado para la siguiente iteración es el que tiene el mínimo f(s) . En BFS, todos los nodos tienen el mismo valor (1), por lo que no es realmente importante cuál viene primero, solo que se seleccionen en el orden en que se agregaron a la cola (FIFO: primero en entrar, primero en salir).

    Al desarrollar una heurística, es importante asegurarse de que cumpla los criterios de admisibilidad. Una heurística se considera admisible si no sobreestima el costo mínimo de alcanzar la configuración objetivo a partir de la configuración actual. Si es admisible, el algoritmo de búsqueda A* siempre encontrará una solución óptima.

    Como se mencionó anteriormente, estamos codificando la inteligencia artificial en JavaScript. Algunos pueden pensar que este es un enfoque imprudente, pero demostraremos que JavaScript puede ofrecer todo lo que necesitamos para obtener un agente racional eficiente. Comenzaremos creando el Nodeobjeto que se muestra en el siguiente código.

    function Node(value, state, emptyRow, emptyCol, depth) { this.value = value this.state = state this.emptyCol = emptyCol this.emptyRow = emptyRow this.depth = depth this.strRepresentation = "" this.path = "" // String representation of the state in CSV format for (var i = 0; i state.length; i++) { // We assume the state is a square if (state[i].length != state.length) { alert('Number of rows differs from number of columns') return false } for (var j = 0; j state[i].length; j++) this.strRepresentation += state[i][j] + ","; } this.size = this.state.length}

    A continuación se incluye una descripción de cada variable.

     

    • value: representa el valor de f(s) .
    • state: representa el estado del tablero como una matriz bidimensional.
    • emptyCol: indica la columna en la que se encuentra el mosaico vacío.
    • emptyRow: indica la fila en la que se encuentra el mosaico vacío.
    • depth: indica el número de movimientos ejecutados desde la configuración inicial hasta la configuración de este nodo, el valor g(s) .
    • strRepresentation: representación en cadena del tablero en formato CSV. Para la configuración del objetivo, la representación de la cadena sería "1,2,3,4,5,6,7,8,0". El rompecabezas de fichas deslizantes es un rompecabezas cíclico: desde una configuración s y después de una secuencia de movimientos podemos volver a s , por lo tanto almacenaremos la representación de cada nodo expandido para evitar estos ciclos. Para ello utilizamos el HashSet.
    • path: almacena cada movimiento en una cadena (“DLRU”), por lo que esta cadena representa la secuencia de movimientos realizados desde la configuración inicial hasta el nodo actual.
    • size: el tamaño del tablero. Observe que asumimos que el tablero tiene dimensiones n , m donde n = m .

    Ahora que hemos presentado el objeto Nodo, ilustremos la ejecución del algoritmo A* mediante un ejemplo. Para este ejemplo, consideraremos la heurística de fichas fuera de lugar , probablemente la heurística más simple y común para este rompecabezas. La heurística de mosaicos fuera de lugar devuelve el número de mosaicos que están fuera de lugar; es decir, en una posición incorrecta en comparación con la configuración de la meta. Es admisible ya que el número devuelto no sobreestima el número mínimo de movimientos necesarios para llegar al estado objetivo. Tienes que mover cada ficha fuera de lugar al menos una vez para poder llevarlas a su posición objetivo; por tanto, es admisible.

    Para implementar el algoritmo A* crearemos un AStarobjeto con el siguiente esquema:

    function AStar(initial, goal, empty) { this.initial = initial this.goal = goal this.empty = empty this.queue = new PriorityQueue({ comparator: function(a, b) { if (a.value b.value) return 1 if (a.value b.value) return -1 return 0 }}); this.queue.queue(initial); this.visited = new HashSet();}

    Observe cómo ya estamos usando las estructuras de datos contenidas en los archivos de script que agregamos al principio. Para la cola de prioridad, definimos una función de comparación que necesitaremos para ordenar los elementos o nodos en orden ascendente. El HashSet visitado almacenará las strRepresentationconfiguraciones visitadas. De esta forma evitamos ciclos.

    Para mejorar el AStarobjeto, usaremos prototipos para agregar métodos y propiedades. A prototypees un método o propiedad que pasa a formar parte de cada nuevo objeto creado después de que el método o propiedad se ha relacionado con el objeto en cuestión. Por ejemplo, la executefunción estará disponible para cada AStarobjeto declarado después de este código.

     

    AStar.prototype.execute = function () { // Add current state to visited list this.visited.add(this.initial.strRepresentation) while (this.queue.length 0) { var current = this.queue.dequeue() if (current.strRepresentation == this.goal.strRepresentation) return current this.expandNode(current) }}

    El executeesqueleto se parece al del BFS:

    • Hay un bucle que finalizará cuando la cola de prioridad esté vacía.
    • La variable actual contendrá el nodo contenido en la cola con el valor mínimo.
    • Si el estado de este nodo coincide con el estado objetivo, entonces habríamos completado la tarea.
    • De lo contrario ampliamos el nodo actual. La expansión se traduce en mover el mosaico vacío en todas las direcciones posibles, generando así nuevos nodos que se incorporarán a la cola.

    El bloque de declaraciones del método de expansión se presenta en el siguiente código:

    AStar.prototype.expandNode = function (node) { var temp = ’ var newState = ’ var col = node.emptyCol var row = node.emptyRow var newNode = ’ // Up if (row 0) { newState = node.state.clone(); temp = newState[row - 1][col] newState[row - 1][col] = this.empty newState[row][col] = temp newNode = new Node(0, newState, row - 1, col, node.depth + 1) if (!this.visited.contains(newNode.strRepresentation)) { newNode.value = newNode.depth + this.heuristic(newNode) newNode.path = node.path + "U" this.queue.queue(newNode) this.visited.add(newNode.strRepresentation) } } // Down if (row node.size - 1) { newState = node.state.clone(); temp = newState[row + 1][col] newState[row + 1][col] = this.empty newState[row][col] = temp newNode = new Node(0, newState, row + 1, col, node.depth + 1) if (!this.visited.contains(newNode.strRepresentation)) { newNode.value = newNode.depth + this.heuristic(newNode) newNode.path = node.path + "D" this.queue.queue(newNode) this.visited.add(newNode.strRepresentation) } } // Left if (col 0) { newState = node.state.clone(); temp = newState[row][col - 1] newState[row][col - 1] = this.empty newState[row][col] = temp newNode = new Node(0, newState, row, col - 1, node.depth + 1) if (!this.visited.contains(newNode.strRepresentation)) { newNode.value = newNode.depth + this.heuristic(newNode) newNode.path = node.path + "L" this.queue.queue(newNode) this.visited.add(newNode.strRepresentation) } } // Right if (col node.size - 1) { newState = node.state.clone(); temp = newState[row][col + 1] newState[row][col + 1] = this.empty newState[row][col] = temp newNode = new Node(0, newState, row, col + 1, node.depth + 1) if (!this.visited.contains(newNode.strRepresentation)) { newNode.value = newNode.depth + this.heuristic(newNode) newNode.path = node.path + "R" this.queue.queue(newNode) this.visited.add(newNode.strRepresentation) } }}

    Todas las ifdeclaraciones son muy similares; cada uno está dedicado a uno de los posibles movimientos. Primero verificamos una condición para ver si el movimiento en cuestión es posible. El movimiento correcto, por ejemplo, sólo será posible si la columna de fichas vacía es menor que el tamaño del tablero. Si el movimiento es posible, creamos un newStateclonando el estado actual (la clonación se vuelve necesaria ya que las matrices son tipos de referencia). Intercambiamos el mosaico vacío con el elemento correspondiente, creamos un newNodey finalmente lo ponemos en cola si, y solo si, el estado del nodo no está en el HashSet visitado. También calculamos el valor del nodo como se explicó anteriormente ( f = g + h ) y sumamos la dirección correspondiente a la pathvariable.

     

    Array.prototype.clone = function() { return JSON.parse(JSON.stringify(this))}

    Por último, pero no menos importante, la función heurística.

    AStar.prototype.heuristic = function (node){ return this.manhattanDistance(node);}

    From this point on we’ll start presenting and comparing results provided by the A* when accompanied by different heuristics. We’ll see how the heuristic turns out to be an essential component during the search and how its cleverness can drastically reduce the time complexity of the algorithm.

    Misplaced Tiles

    Before we dive into the interesting field of heuristics, let’s point out an important note when calculating any heuristic: we never take into account the empty tile. If we do, then we could be overestimating the real cost of the shortest path to the goal state, thereby making the heuristic non-admissible. To illustrate this note, consider the following node:

    If we take into account the empty tile, then h=2, an overestimation of the shortest path to the goal configuration, which could be obtained just by moving the empty tile down. Thus the length of the shortest path to the goal configuration is 1 and we are overestimating.

    To test our heuristics we’ll be using one of the worst configurations for this puzzle – it requires 31 moves to be completed.

    The A* algorithm will be executed when the Solve button is pressed. The onclick event associated with this button will trigger the start function whose body is up next.

    function start() { var init = new Node(0, [[6,4,7],[8,5,0],[3,2,1]], 1, 2, 0) var goal = new Node(0, [[1,2,3],[4,5,6],[7,8,0]], 2, 2, 0) var astar = new AStar(init, goal, 0) // To measure time taken by the algorithm var startTime = new Date() // Execute AStar var result = astar.execute() // To measure time taken by the algorithm var endTime = new Date() alert('Completed in: ' + (endTime - startTime) + ' milliseconds') var panel = document.getElementById('panel') panel.innerHTML = 'Solution: ' + result.path + ' Total steps: ' + result.path.length + '' solution = result.path}

    Note that we are going to measure the time taken by the algorithm in milliseconds. This is how we’ll compare the various heuristics developed. The code of the misplaced tiles heuristic is very simple.

    AStar.prototype.misplacedTiles = function (node) { var result = 0; for (var i = 0; i node.state.length; i++) { for (var j = 0; j node.state[i].length; j++) if (node.state[i][j] != this.goal.state[i][j] node.state[i][j] != this.empty) result++; } return result;}

    The result is the following

    The algor






    Tal vez te puede interesar:

    1. ¿Deberían abrirse los enlaces en ventanas nuevas?
    2. 24 excelentes tutoriales de AJAX
    3. 70 técnicas nuevas y útiles de AJAX y JavaScript
    4. Más de 45 excelentes recursos y repositorios de fragmentos de código

    IA de JavaScript para un rompecabezas de mosaicos deslizantes HTML

    IA de JavaScript para un rompecabezas de mosaicos deslizantes HTML

    Patrones de diseño de interfaces inteligentes, vídeo de 10h + formación UX Taller de diseño conductual, con Susan y Guthrie Weinschenk Índice

    programar

    es

    https://aprendeprogramando.es/static/images/programar-ia-de-javascript-para-un-rompecabezas-de-mosaicos-deslizantes-html-884-0.jpg

    2024-05-20

     

    IA de JavaScript para un rompecabezas de mosaicos deslizantes HTML
    IA de JavaScript para un rompecabezas de mosaicos deslizantes HTML

    Si crees que alguno de los contenidos (texto, imagenes o multimedia) en esta página infringe tus derechos relativos a propiedad intelectual, marcas registradas o cualquier otro de tus derechos, por favor ponte en contacto con nosotros en el mail [email protected] y retiraremos este contenido inmediatamente

     

     

    Top 20