Share
Este proyecto recorre los conceptos básicos de búsqueda de ruta en el SDK de Corona a través del algoritmo de búsqueda de ruta A *, un elemento básico en la industria de los juegos desde 1970. Esta aplicación le permite agregar obstáculos a una cuadrícula de 10x10 y ver la ruta determinada por A *.
A * usa dos funciones para determinar la ruta de "menor costo" al objetivo. La primera función, a menudo llamada g (x), es el costo de moverse entre dos cuadrados adyacentes. Esto es útil cuando su juego tiene diferentes terrenos como pantanos y caminos pavimentados que pueden tener diferentes efectos de movimiento. La segunda función, h (x), es una estimación de la distancia desde el cuadrado actual al cuadrado objetivo a lo largo del camino ideal. Hay muchas formas diferentes de calcular esta distancia, pero para este programa, utilizaremos un enfoque relativamente simple al agregar la distancia restante en la dirección y a la distancia restante en la dirección x.
Usaremos las siguientes dos funciones de lua para encontrar la ruta. La función se llama de la siguiente manera, CalcPath (CalcMoves (board, startX, startY, targetX, targetY)). La función CalcPath devuelve una tabla de las coordenadas al objetivo, o nil si no se pudo encontrar una ruta. Este comportamiento será útil para determinar la validez de la colocación de obstáculos.
Si no tiene interés en los aspectos detrás del escenario del algoritmo, no dude en copiar y pegar las funciones desde la fuente completa en la parte superior de la página. De lo contrario, abroche los cinturones de seguridad: esto puede ser mucho para tomar al principio.
Echemos un vistazo a CalcMoves primero.
local openlist = - Movimientos posibles local closedlist = - Squecked Squares local listk = 1 - contador de listas abiertas local closedk = 0 - closedlist counter local tempH = math.abs (startX-targetX) + math.abs ( startY-targetY) --h (x) tempG local = 0
Aquí declaramos la mayoría de las variables utilizadas en el método..
openlist [1] = x = startX, y = startY, g = 0, h = tempH, f = 0 + tempH, par = 1 xsize local = table.getn (board [1]) ysize local = table.getn (tablero) local curSquare = local curSquareIndex = 1 - Índice de la base actual
Al sumergirnos en el siguiente fragmento, comenzamos por establecer el primer cuadrado en la lista abierta al cuadrado inicial. Luego creamos variables para el ancho y el alto del tablero, declaramos una tabla para el cuadrado actual que se está verificando en la lista abierta y creamos una variable para el índice en la lista abierta del cuadrado actual. En caso de que te lo preguntes, "Par" contiene el índice de la matriz del cuadrado. Esto permite una fácil reconstrucción del camino..
mientras que listk> 0 do local lowestF = openlist [listk] .f curSquareIndex = listk para k = listk, 1, -1 do si openlist [k] .f < lowestF then lowestF = openlist[k].f curSquareIndex = k end end…
Este método es una especie de giro en su cabeza. Recorre, primero iterando a través de la lista abierta, y segundo expandiendo la lista abierta hasta que llega a la casilla final. El primer bucle anidado recorre la lista abierta para encontrar el cuadrado con el valor F más bajo. El valor de f es similar al valor de h, excepto que el valor de f es el costo de la ruta más corta de principio a fin pasando por el cuadrado actual. El índice de este cuadrado se almacena en una variable. Nota: si la lista abierta alguna vez se vacía (es decir, no había más espacios elegibles para el movimiento), no se pudo determinar una ruta y la función devuelve nula. Esta posibilidad se comprueba en el bucle while.
closedk = closedk + 1 table.insert (closedlist, closedk, openlist [curSquareIndex]) curSquare = closedlist [closedk]
Aquí incrementamos el contador de la lista cerrada, insertamos el cuadrado con la puntuación f más baja en la lista cerrada y configuramos ese cuadrado como el cuadrado actual. Las siguientes líneas determinarán si los cuadrados adyacentes al nuevo cuadrado actual son elegibles para el movimiento.
local rightOK = true local leftOK = true - Booleanos que definen si están bien para agregar local downOK = true - (debe restablecerse para cada ciclo) local upOK = true - Mira a través de la lista cerrada. Se asegura de que la ruta no se doble hacia atrás si closedk> 0 entonces para k = 1, closedk do si closedlist [k] .x == curSquare.x + 1 y closedlist [k] .y == curSquare.y luego a la derechaOK = final falso si closedlist [k] .x == curSquare.x-1 y closedlist [k] .y == curSquare.y luego leftOK = false final si closedlist [k] .x == curSquare.x y closedlist [k ] .y == curSquare.y + 1 luego downOKOK = falso final si closedlist [k] .x == curSquare.x y closedlist [k] .y == curSquare.y - 1 entonces upOK = false end end end
Primero, verificamos si ya están en la lista cerrada:
si curSquare.x + 1> xsize entonces rightOK = false end si curSquare.x - 1 < 1 then leftOK = false end if curSquare.y + 1 > ysize entonces downOK = false final si curSquare.y - 1 < 1 then upOK = false end
Segundo, asegura que los cuadrados adyacentes estén dentro de los límites del tablero:
si curSquare.x + 1 <= xsize and board[curSquare.x+1][curSquare.y].isObstacle ~= 0 then rightOK = false end if curSquare.x - 1 >= 1 y placa [curSquare.x-1] [curSquare.y] .isObstacle ~ = 0 luego leftOK = falso final si curSquare.y + 1 <= ysize and board[curSquare.x][curSquare.y+1].isObstacle ~= 0 then downOK = false end if curSquare.y - 1 >= 1 y tablero [curSquare.x] [curSquare.y-1] .isObstacle ~ = 0 luego arribaOK = falso final
En tercer lugar, comprobamos si los cuadrados adyacentes contienen obstáculos:
-- compruebe si el movimiento desde la base actual es más corto que el anterior tempr = curSquare.g + 1 para k = 1, listk do if rightOK y openlist [k] .x == curSquare.x + 1 y openlist [k] .y == curSquare.y y la lista abierta [k] .g> tempG luego tempH = math.abs ((curSquare.x + 1) -targetX) + math.abs (curSquare.y-targetY) table.insert (lista abierta, k, x = curSquare.x + 1, y = curSquare.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk) rightOK = false end si leftOKOK y lista abierta [k] .x = = curSquare.x-1 y lista abierta [k] .y == curSquare.y y lista abierta [k] .g> tempG entonces tempH = math.abs ((curSquare.x-1) -targetX) + math.abs (curSquare .y-targetY) table.insert (lista abierta, k, x = curSquare.x-1, y = curSquare.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk) leftOK = false termine si está abajoAceptar y abrir lista [k] .x == curSquare.x y lista abierta [k] .y == curSquare.y + 1 y abrir lista [k] .g> tempG entonces tempH = math.abs ((curSquare.x) -targetX) + math.abs (curSquare.y + 1-targetY) table.insert (lista abierta, k, x = curSquare.x, y = curSquare.y + 1, g = tempG, h = tempH, f = tempG + tempH, par = closedk) downOK = false termina si upOK y lista abierta [k] .x == curSquare.x y lista abierta [k] .y == curSquare.y-1 y lista abierta [k] .g> tempG entonces tempH = math.abs ((curSquare.x) -targetX) + math.abs (curSquare.y-1-targetY) table.insert (lista abierta, k, x = curSquare.x, y = curSquare.y-1, g = tempG, h = tempH, f = tempG + tempH, par = closedk) upOK = final falso
Finalmente, el algoritmo comprueba para asegurarse de que es "más barato" moverse desde el cuadro actual al siguiente cuadrado de lo que sería pasar del cuadro principal al siguiente. Esto garantiza que la ruta elegida sea, de hecho, la ruta más barata posible y que no haya ningún atajo obvio que se haya perdido..
-- Agregue un punto a la derecha del punto actual si tiene el derechoHasta entonces listk = listk + 1 tempH = math.abs ((curSquare.x + 1) -targetX) + math.abs (curSquare.y-targetY) table.insert (lista abierta, listk , x = curSquare.x + 1, y = curSquare.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk) fin - Agregar punto a la izquierda del punto actual si se deja en Aceptar, luego en listk = listk + 1 tempH = math.abs ((curSquare.x-1) -targetX) + math.abs (curSquare.y-targetY) table.insert (openlist, listk, x = curSquare.x-1, y = curSquare.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk) end - Agregar punto en la parte superior del punto actual si está abajoOK A continuación, listk = listk + 1 tempH = math.abs (curSquare. x-targetX) + math.abs ((curSquare.y + 1) -targetY) table.insert (lista abierta, listk, x = curSquare.x, y = curSquare.y + 1, g = tempG, h = tempH, f = tempG + tempH, par = closedk) fin - Agregar punto en la parte inferior del punto actual si está arribaAceptar entonces listk = listk + 1 tempH = math.abs (curSquare.x-targetX) + math.abs ((curSquare. y-1) -targetY) table.insert (lista abierta, listk, x = curSquare.x, y = curSquare.y-1, g = tempG, h = tempH, f = tempG + tempH, par = clos edk) fin
Este segundo a último trozo es donde finalmente expandimos la lista abierta después de todas esas arduas pruebas. Si un cuadrado adyacente al cuadrado actual pudo perseverar a través de nuestras condiciones rigurosas, se gana un lugar en la lista abierta, donde se puede elegir como el siguiente cuadrado actual en función de su valor F.
… Table.remove (openlist, curSquareIndex) listk = listk-1 si closedlist [closedk] .x == targetX y closedlist [closedk] .y == targetY luego return closedlist end end end return nil end
Por fin llegamos al final de la larga función. Primero eliminamos el cuadrado actual de la lista abierta. Luego verificamos si las posiciones x e y del cuadrado actual son iguales a las del cuadrado objetivo. Si es así, pasamos la lista cerrada al método CalcPath donde se refinan los datos.
función CalcPath (closedlist) si closedlist == nil devuelve nil end local path = local pathIndex = local last = table.getn (closedlist) table.insert (pathIndex, 1, last) local i = 1 while pathIndex [ i]> 1 do i = i + 1 table.insert (pathIndex, i, closedlist [pathIndex [i-1]] par) end para n = table.getn (pathIndex), 1, -1 do table.insert ( ruta, x = lista cerrada [pathIndex [n]]. x, y = lista cerrada [pathIndex [n]]. y) final closedlist = nil return ruta final
¡Es todo cuesta abajo desde aquí! Esta función reduce la lista cerrada para garantizar que solo se devuelva la ruta correcta. Sin esto, si el algoritmo atravesaba una ruta, se atasca y se ponía en una ruta nueva, la tabla que se devolvía contendría las coordenadas de la ruta correcta y el intento fallido. Todo lo que hace es comenzar al final de la lista cerrada y reconstruir la ruta al principio a través de la propiedad principal agregada anteriormente. Una vez que hayamos obtenido nuestra lista de coordenadas correctas, podemos usar esa información para crear una ruta terminada en el segundo bucle. Eso es todo lo que hay para el algoritmo A *. A continuación veremos cómo podemos usarlo en un programa..
¡Uf! Eso fue mucha información nueva. Afortunadamente, el resto de esta aplicación es muy fácil de construir, incluso con una comprensión básica de la API de Corona. Lo primero que debes hacer es crear tu archivo main.lua y colocarlo en un nuevo directorio. ¡Eso es todo lo que Corona requiere en la forma de configuración! A continuación, vamos a crear la tabla que contendrá nuestra cuadrícula de 10x10, y mientras estamos en eso, podemos eliminar esa barra de estado antiestética en la parte superior de la pantalla..
display.setStatusBar (display.HiddenStatusBar) board = --Crear una tabla vacía para sostener el tablero --Popular la tabla para i = 1, 10 do board [i] = para j = 1, 10 do board [ i] [j] = board [i] [j] .square = display.newRect ((i-1) * 32, (j-1) * 32, 32, 32) board [i] [j]. cuadrado: placa setFillColor (255, 255, 255) [i] [j] .isObstacle = 0 end end
No hay nada revolucionario aquí. Todo lo que hicimos fue ocultar la barra de estado y crear una matriz tridimensional para mantener la cuadrícula. En los bucles for, establecemos la longitud del lado de nuestros cuadrados a 32 píxeles y los posicionamos con una multiplicación astuta. Nota: asegúrese de usar las teclas .square y .isObstacle en lugar de solo decir board [2] [3].
Agregar obstáculos es una tarea simple. Para este tutorial, los espacios que son elegibles para el movimiento serán blancos, los obstáculos serán negros y los marcadores que indican la ruta serán rojos. Mira la siguiente función:
Accentsconagua
addObstacle = función (evento) if event.phase == "terminó" y evento.y < 320 then --Use event.x and event.y to calculate the coordinate in terms of the 10x10 grid x = math.ceil(event.x/32) y = math.ceil(event.y/32) board[x][y].isObstacle = 1 if CalcPath(CalcMoves(board, 1, 1, 10, 10)) then board[x][y].square:setFillColor(0, 0, 0) else board[x][y].isObstacle = 0 end end return true end Runtime:addEventListener("touch", addObstacle) Observe que la función es un detector de eventos en tiempo de ejecución. Los eventos de tiempo de ejecución se envían a todos los oyentes y no se aplican a un objeto específico. Este es el comportamiento deseado para esta implementación. La función addObstacle comienza verificando si el usuario ha levantado su dedo. Olvidar este paso es seguro que causará mucha frustración en la parte del usuario, ya que se podría presionar el botón con un golpe accidental y no con un movimiento hacia arriba y hacia abajo deliberado del dedo. Los usuarios están acostumbrados a estos matices, por lo que es importante prestarles atención siempre que sea posible. Este mismo condicional también se asegura de que solo los eventos táctiles que ocurren dentro de la cuadrícula de 320px se envíen a este método. Esto evita que interfieran con nuestros botones..
Además de eso, esta función usa algunas matemáticas básicas para averiguar qué casilla se tocó usando event.y y event.x, y llama a la función de búsqueda de ruta para asegurar que el usuario deja una ruta. Dependiendo de sus necesidades, esto puede o no ser deseable, pero es bueno saber que tiene la capacidad de tomar estas decisiones..
En aras de la brevedad, este tutorial escatimará las animaciones y solo colocará marcadores a lo largo del camino determinado por A *.
placeMarkers = function (event) path = CalcPath (CalcMoves (board, 1, 1, 10, 10)) para i = 1, table.getn (path) do local newX = path [i] .x local newY = path [i ] .y marcador local = display.newCircle ((newX * 32 - 16), (newY * 32 - 16), 8) marcador: setFillColor (255, 0, 0) end end
Este es todo el código que es necesario. Simplemente colocamos las coordenadas en una tabla llamada ruta, e iteramos la totalidad de la tabla, colocando un marcador con un radio de ocho píxeles en cada conjunto de coordenadas. Las cosas pueden volverse un poco complicadas cuando intentas usar animaciones junto con esto, pero no debería ser tan malo siempre que mantengas un registro del índice de tu coordenada actual y lo incrementes después de un cierto intervalo de tiempo..
Tal como está actualmente, la función animada no hará absolutamente nada porque nunca se llama. El uso de un evento de tiempo de ejecución realmente no es apropiado en esta instancia, así que usaremos una imagen con un detector de eventos.
local goButton = display.newImage ("PlaceMarkers.png", -200, 350) goButton: addEventListener ("touch", placeMarkers) Voila! Con dos líneas de código estamos listos para ir.
Si ejecuta el programa ahora, sin duda notará que los marcadores no desaparecerán cuando vuelva a ejecutar el programa. La solución es colocar los bucles anidados para los que inicialmente rellenaron la tabla en un método al que podemos llamar siempre que necesitemos una pizarra limpia. El comienzo del programa ahora debería verse así:
setup = function () counter = 1 board = --Popular la tabla para i = 1, 10 do board [i] = para j = 1, 10 do board [i] [j] = board [ i] [j] .square = display.newRect ((i-1) * 32, (j-1) * 32, 32, 32) board [i] [j] .square: setFillColor (255, 255, 255) board [i] [j] .isObstacle = 0 end end end end
¡Solo dos líneas más y nuestro programa estará completo! Me tomé la libertad de agregar un esquema de colores de mejor aspecto al programa. Te animo a que juegues un poco con este proyecto. A ver si puedes tentarlo. Si te sientes valiente, intenta modificar la función h (x) y ver qué pasa!
local resetButton = display.newImage ("Reset.png", 300, 350) resetButton: addEventListener ("touch", configuración) Este tutorial cubre mucho terreno! La carne de eso fue el algoritmo de encontrar el camino. A * es una herramienta muy poderosa, y esta era una versión bastante simple de la misma. Es posible que haya notado que no tuvo en cuenta el movimiento diagonal y que se basó en cuadrados. La verdad es que puede modificar el algoritmo para acomodar cualquier forma de mosaico y puede modificar h (x) para lograr un movimiento diagonal. Lo mejor es que, si bien el código de su algoritmo puede volverse complejo, el código para la interfaz de usuario y el resto de la aplicación seguirán siendo simples y rápidos de escribir gracias a la potencia y simplicidad del Corona SDK. Le proporciona una capacidad sin precedentes en dos dimensiones sin la complejidad de Objective-C.
