Share
Ce projet décrit les bases de la recherche de chemin dans le SDK Corona via l'algorithme de recherche de chemin A *, un élément essentiel dans l'industrie du jeu depuis 1970 environ. Cette application vous permet d'ajouter des obstacles à une grille 10x10 et d'afficher le chemin déterminé par A *..
A * utilise deux fonctions pour déterminer le chemin du "moindre coût" vers la cible. La première fonction, souvent appelée g (x), est le coût de déplacement entre deux carrés adjacents. Ceci est utile lorsque votre jeu comporte des terrains variés tels que des marécages et des routes pavées pouvant avoir des effets de mouvement différents. La deuxième fonction, h (x), est une estimation de la distance entre le carré actuel et le carré cible le long du trajet idéal. Il existe différentes manières de calculer cette distance, mais pour ce programme, nous utiliserons une approche relativement simple en ajoutant la distance restante dans la direction y à la distance restante dans la direction x..
Nous allons utiliser les deux fonctions lua suivantes pour trouver le chemin. La fonction est appelée comme suit, CalcPath (CalcMoves (board, startX, startY, targetX, targetY)). La fonction CalcPath renvoie une table des coordonnées de la cible, ou nil si aucun chemin ne peut être trouvé. Ce comportement sera utile pour déterminer la validité du placement d'obstacles.
Si vous n'êtes pas intéressé par les aspects cachés de l'algorithme, n'hésitez pas à copier et coller les fonctions de la source complète en haut de la page. Sinon, attachez vos ceintures: cela risque d’être beaucoup au début.
Jetons d'abord un coup d'œil à CalcMoves.
local openlist = --Possible Moves local closedlist = --Vérifié Carrés local listk = 1 - compteur d'openlist local closedk = 0 - compteur de listes fermées local tempH = math.abs (startX-targetX) + math.abs ( startY-targetY) --h (x) tempG local = 0
Ici, nous déclarons la plupart des variables utilisées dans la méthode.
openlist [1] = x = startX, y = startY, g = 0, h = tempH, f = 0 + tempH, par = 1 local xsize = table.getn (tableau [1]) local ysize = table.getn (board) local curSquare = local curSquareIndex = 1 - Index de la base actuelle
En plongeant dans le bloc suivant, nous commençons par définir le premier carré de la liste ouverte sur le carré de départ. Ensuite, nous créons des variables pour la largeur et la hauteur du tableau, déclarons une table pour le carré en cours de vérification dans la liste ouverte et créons une variable pour l'index dans la liste ouverte du carré en cours. Au cas où vous vous le demanderiez, "Par" contient l'index du parent du carré. Cela permet une reconstruction facile du chemin.
tandis que listk> 0 est le plus bas local = openlist [listk] .f curSquareIndex = listk pour k = listk, 1, -1 faire si openlist [k] .f < lowestF then lowestF = openlist[k].f curSquareIndex = k end end…
Cette méthode est en quelque sorte renversée. Il parcourt, en parcourant d’abord la liste ouverte, puis en développant la liste ouverte jusqu’à atteindre la dernière case. La première boucle imbriquée parcourt la liste ouverte pour trouver le carré avec la valeur F la plus basse. La valeur f est similaire à la valeur h, à la différence que la valeur f est le coût du plus court chemin du début à la fin passant par le carré actuel. L'index de ce carré est stocké dans une variable. Remarque: si la liste ouverte devient jamais vide (c’est-à-dire qu’il n’y avait plus d’espaces pouvant être déplacés), un chemin ne pouvait pas être déterminé et la fonction ne renvoyait rien. Cette possibilité est cochée dans la boucle while.
closedk = closedk + 1 table.insert (liste fermée, ferméek, openlist [curSquareIndex]) curSquare = liste fermée [closedk]
Ici, nous incrémentons le compteur de liste fermée, insérons le carré avec le score f le plus bas dans la liste fermée et définissons ce carré comme le carré actuel. Les lignes suivantes détermineront si les carrés adjacents au nouveau carré actuel sont éligibles pour le mouvement..
local rightOK = true local leftOK = true - Des booléens définissant s'ils sont corrects d'ajouter local downOK = true - (doivent être réinitialisés pour chaque boucle while) local upOK = true - Parcourez la liste fermée. S'assure que le chemin ne double pas si closedk> 0 alors pour k = 1, closedk si liste fermée [k] .x == curSquare.x + 1 et liste fermée [k] .y == curSquare.y alors rightOK = fausse fin si liste fermée [k] .x == curSquare.x-1 et liste fermée [k] .y == curSquare.y puis leftOK = fausse fin si liste fermée [k] .x == curSquare.x et liste fermée [k ] .y == curSquare.y + 1 alors downOK = false fin si liste fermée [k] .x == curSquare.x et liste fermée [k] .y == curSquare.y - 1 puis upOK = false fin fin fin
Tout d’abord, nous vérifions s’ils figurent déjà dans la liste fermée:
si curSquare.x + 1> xsize alors rightOK = false, fin si curSquare.x - 1 < 1 then leftOK = false end if curSquare.y + 1 > ysize then downOK = false end si curSquare.y - 1 < 1 then upOK = false end
Deuxièmement, cela garantit que les cases adjacentes sont dans les limites du plateau:
si curSquare.x + 1 <= xsize and board[curSquare.x+1][curSquare.y].isObstacle ~= 0 then rightOK = false end if curSquare.x - 1 >= 1 et bord [curSquare.x-1] [curSquare.y] .isObstacle ~ = 0 puis leftOK = false end si curSquare.y + 1 <= ysize and board[curSquare.x][curSquare.y+1].isObstacle ~= 0 then downOK = false end if curSquare.y - 1 >= 1 et conseil [curSquare.x] [curSquare.y-1] .isObstacle ~ = 0 alors upOK = fausse fin
Troisièmement, nous vérifions si les carrés adjacents contiennent des obstacles:
-- vérifie si le déplacement de la base actuelle est plus court que de l'ancien parrent tempG = curSquare.g + 1 pour k = 1, listk do si rightOK et openlist [k] .x == curSquare.x + 1 et openlist [k] .y == curSquare.y et openlist [k] .g> tempG puis tempH = math.abs ((curSquare.x + 1) -targetX) + math.abs (curSquare.y-targetY) table.insert (openlist, k, x = curSquare.x + 1, y = curSquare.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk) rightOK = fausse fin si leftOK et openlist [k] .x = = curSquare.x-1 et openlist [k] .y == curSquare.y et openlist [k] .g> tempG alors tempH = math.abs ((curSquare.x-1) -targetX) + math.abs (curSquare .y-targetY) table.insert (openlist, k, x = curSquare.x-1, y = curSquare.y, g = tempG, h = tempH, f = tempG + tempH, par = fermék) leftOK = false end if downOK et openlist [k] .x == curSquare.x et openlist [k] .y == curSquare.y + 1 et openlist [k] .g> tempG alors tempH = math.abs ((curSquare.x) -targetX) + math.abs (curSquare.y + 1-targetY) table.insert (openlist, k, x = curSquare.x, y = curSquare.y + 1, g = tempG, h = tempH, f = tempG + tempH, par = closedk) downOK = false termine si upOK et openlist [k] .x == curSquare.x et openlist [k] .y == curSquare.y-1 et openlist [k] .g> tempG alors tempH = math.abs ((curSquare.x) -targetX) + math.abs (curSquare.y-1-targetY) table.insert (openlist, k, x = curSquare.x, y = curSquare.y-1, g = tempG, h = tempH, f = tempG + tempH, par = closedk) upOK = faux fin fin
Enfin, l'algorithme vérifie qu'il est "moins cher" de passer du carré actuel au carré suivant que de passer du carré parent au carré suivant. Cela garantit que le chemin choisi est bien le chemin le moins cher possible et qu'aucun raccourci évident n'a été oublié..
-- Ajoutez un point à droite du point actuel si rightOK alors 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 = fermék) end - Ajoute un point à gauche du point actuel si leftOK est affiché, puis 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 - Ajoutez un point en haut du point actuel si downOK, puis listk = listk + 1 tempH = math.abs (curSquare. x-targetX) + math.abs ((curSquare.y + 1) -targetY) table.insert (openlist, listk, x = curSquare.x, y = curSquare.y + 1, g = tempG, h = tempH, f = tempG + tempH, par = closedk) end - Ajoute un point au bas du point actuel si upOK puis listk = listk + 1 tempH = math.abs (curSquare.x-targetX) + math.abs ((curSquare. y-1) -targetY) table.insert (openlist, listk, x = curSquare.x, y = curSquare.y-1, g = tempG, h = tempH, f = tempG + tempH, par = clos edk) end
Cet avant-dernier segment est l'endroit où nous avons finalement élargi la liste ouverte après tous ces tests ardus. Si une case adjacente à la case actuelle a réussi à résister à nos conditions rigoureuses, elle gagne une place sur la liste ouverte, où elle peut être choisie comme prochaine case actuelle en fonction de sa valeur F.
… Table.remove (openlist, curSquareIndex) listk = listk-1 si closedlist [closedk] .x == targetX et closedlist [closedk] .y == targetY puis renvoie returnlist end end return nil end
Nous arrivons enfin à la fin de la longue fonction. Nous supprimons d’abord le carré actuel de la liste ouverte. Nous vérifions ensuite si les positions x et y du carré actuel sont égales à celles du carré cible. Si oui, nous passons la liste fermée à la méthode CalcPath où les données sont raffinées.
function CalcPath (liste fermée) si liste fermée == nil puis renvoie nil fin chemin local = pathIndex local = local last = table.getn (liste fermée) table.insert (pathIndex, 1, dernier) i = 1 tant que pathIndex [ i]> 1 do i = i + 1 table.insert (pathIndex, i, liste fermée [pathIndex [i-1]]. par) fin pour n = table.getn (pathIndex), 1, -1 do table.insert ( chemin, x = liste fermée [cheminIndex [n]]. x, y = liste fermée [cheminIndex [n]] .y) fin liste fermée = nil retour chemin fin
C'est tout en descente d'ici! Cette fonction réduit la liste fermée pour garantir que seul le chemin correct est renvoyé. Sans cela, si l'algorithme traversait un chemin, restait bloqué et rayait dans un nouveau chemin, la table renvoyée contiendrait les coordonnées du chemin correct ainsi que de la tentative infructueuse. Tout ce qu'il fait est de commencer à la fin de la liste fermée et de reconstruire le chemin au début via la propriété parent ajoutée précédemment. Après avoir obtenu notre liste de coordonnées correctes, nous pouvons utiliser ces informations pour créer un chemin complet dans la deuxième boucle. C'est tout ce qu'il y a dans l'algorithme A *. Ensuite, nous examinons comment nous pouvons l’utiliser dans un programme..
Ouf! C'était beaucoup de nouvelles informations. Heureusement, le reste de cette application est très facile à construire avec même une compréhension de base de l'API Corona. La première chose à faire est de créer votre fichier main.lua et de le placer dans un nouveau répertoire. C'est tout ce que Corona nécessite en termes de configuration! Ensuite, nous allons créer la table qui contiendra notre grille 10x10 et pendant que nous y sommes, nous pouvons nous débarrasser de cette barre d'état inesthétique en haut de l'écran..
display.setStatusBar (display.HiddenStatusBar) board = --Créez une table vide pour contenir le tableau - Remplit la table pour i = 1, 10 do board [i] = pour j = 1, 10 do board [ i] [j] = tableau [i] [j] .square = display.newRect ((i-1) * 32, (j-1) * 32, 32, 32) tableau [i] [j]. square: carte setFillColor (255, 255, 255) [i] [j] .isObstacle = 0 end end
Il n'y a rien de révolutionnaire ici. Nous avons simplement masqué la barre d'état et créé un tableau en trois dimensions pour contenir la grille. Dans les boucles for, nous définissons la longueur des côtés de nos carrés à 32 pixels et nous les positionnons avec une multiplication astucieuse. Remarque: veillez à utiliser les clés .square et .isObstacle au lieu de simplement dire conseil [2] [3].
L'ajout d'obstacles est une tâche simple. Pour ce didacticiel, les espaces éligibles au déplacement seront en blanc, les obstacles en noir et les balises indiquant le chemin seront en rouge. Regardez la fonction suivante:
Accentsconagua
addObstacle = fonction (événement) si event.phase == "terminé" et event.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) Notez que la fonction est un écouteur d'événements au moment de l'exécution. Les événements d'exécution sont envoyés à tous les écouteurs et ne s'appliquent pas à un objet spécifique. C'est le comportement souhaité pour cette implémentation. La fonction addObstacle commence par vérifier si l'utilisateur a levé son doigt. L'oubli de cette étape est certain de causer beaucoup de frustration chez l'utilisateur car le bouton pourrait être appuyé par un balayage accidentel et non par un mouvement délibéré du doigt vers le haut et le bas. Les utilisateurs sont habitués à ces nuances, il est donc important de les surveiller autant que possible. Cette même condition garantit également que seuls les événements tactiles qui se produisent dans la grille de 320 pixels de haut sont envoyés à cette méthode. Cela les empêche d'interférer avec nos boutons.
En outre, cette fonction utilise des notions de base en mathématiques pour déterminer quelle case a été touchée à l'aide de event.y et event.x. Elle appelle également la fonction de recherche de chemin pour s'assurer que l'utilisateur laisse un chemin. En fonction de vos besoins, cela peut être souhaitable ou non, mais il est bon de savoir que vous avez la capacité de prendre ces décisions..
Par souci de brièveté, ce didacticiel économisera des animations et placera simplement des marqueurs le long du chemin déterminé par A *..
placeMarkers = fonction (événement) chemin = CalcPath (CalcMoves (tableau, 1, 1, 10, 10)) pour i = 1, table.getn (chemin) do local newX = chemin [i] .x local newY = chemin [i ] .y marqueur local = display.newCircle ((newX * 32 - 16), (newY * 32 - 16), 8) marqueur: setFillColor (255, 0, 0) end end
C'est tout le code qui est nécessaire. Nous plaçons simplement les coordonnées dans une table nommée path et parcourons l'intégralité de la table, en plaçant un marqueur de rayon de huit pixels à chaque ensemble de coordonnées. Les choses peuvent devenir un peu poilues lorsque vous essayez d'utiliser des animations en même temps, mais cela ne devrait pas être trop grave tant que vous gardez une trace de l'index de votre coordonnée actuelle et l'incrémentez après un certain intervalle de temps..
Dans l'état actuel des choses, la fonction animate ne fera absolument rien car elle n'est jamais appelée. L'utilisation d'un événement d'exécution n'est vraiment pas appropriée dans ce cas, nous allons donc utiliser une image avec un écouteur d'événement.
local goButton = display.newImage ("PlaceMarkers.png", -200, 350) goButton: addEventListener ("touch", placeMarkers) Voila! Avec deux lignes de code, nous sommes prêts à aller.
Si vous exécutez le programme maintenant, vous remarquerez certainement que les marqueurs ne disparaissent pas lorsque vous exécutez à nouveau le programme. La solution consiste à placer les boucles for imbriquées qui ont initialement rempli la table dans une méthode que nous pouvons appeler chaque fois que nous avons besoin d'une table rase. Le début du programme devrait maintenant ressembler à ceci:
setup = function () counter = 1 board = --Peupler la table pour i = 1, 10 faire board [i] = pour j = 1, 10 faire board [i] [j] = board [ i] [j] .square = display.newRect ((i-1) * 32, (j-1) * 32, 32, 32) carte [i] [j] .square: setFillColor (255, 255, 255) tableau [i] [j] .isObstacle = 0 fin fin fin
Plus que deux lignes et notre programme sera complet! J'ai pris la liberté d'ajouter une palette de couleurs plus attrayante au programme. Je vous encourage à jouer avec ce projet. Voyez si vous pouvez vous en débarrasser. Si vous vous sentez courageux, essayez de modifier la fonction h (x) et voyez ce qui se passe.!
local resetButton = display.newImage ("Reset.png", 300, 350) resetButton: addEventListener ("touch", configuration) Ce tutoriel couvre beaucoup de terrain! La viande en était l'algorithme de recherche de chemin. A * est un outil très puissant, et sa version était assez simple. Vous avez peut-être remarqué que cela ne tenait pas compte du mouvement en diagonale et reposait sur des carrés. En réalité, vous pouvez modifier l’algorithme pour s’adapter à n’importe quelle forme, et vous pouvez modifier h (x) pour obtenir un mouvement diagonal. L'avantage est que, même si votre code d'algorithme peut devenir complexe, le code pour l'interface utilisateur et le reste de l'application restera simple et rapide à écrire grâce à la puissance et à la simplicité du SDK Corona. Il vous fournit une capacité sans précédent dans deux dimensions sans la complexité d'Objective-C.
