Share
Questo progetto illustra le basi della ricerca del percorso nel Corona SDK tramite l'algoritmo di individuazione dei percorsi A *, un punto fermo nell'industria del gioco dal 1970 circa. Questa app consente di aggiungere ostacoli a una griglia 10x10 e visualizzare il percorso determinato da A *.
A * utilizza due funzioni per determinare il percorso di "costo minimo" per l'obiettivo. La prima funzione, spesso chiamata g (x), è il costo del movimento tra due quadrati adiacenti. Questo è utile quando il tuo gioco ha diversi terreni come paludi e strade asfaltate che possono avere effetti di movimento diversi. La seconda funzione, h (x), è una stima della distanza dal quadrato corrente al quadrato bersaglio lungo il percorso ideale. Esistono molti modi per calcolare questa distanza, ma per questo programma utilizzeremo un approccio relativamente semplice aggiungendo la distanza rimanente nella direzione y alla distanza rimanente nella direzione x.
Utilizzeremo le seguenti due funzioni lua per trovare il percorso. La funzione è chiamata come segue, CalcPath (CalcMoves (board, startX, startY, targetX, targetY)). La funzione CalcPath restituisce una tabella delle coordinate sull'obiettivo o nulla se non è possibile trovare alcun percorso. Questo comportamento si rivelerà utile nel determinare la validità del posizionamento degli ostacoli.
Se non sei interessato agli aspetti dietro le quinte dell'algoritmo, sentiti libero di copiare e incollare le funzioni dall'origine completa nella parte superiore della pagina. Altrimenti, allacciate le cinture di sicurezza: all'inizio potrebbe trattarsi di molto.
Diamo prima un'occhiata a CalcMoves.
local openlist = --Possible Moves local closedlist = --Checked Squares local listk = 1 - contatore di openlist locale closedk = 0 - contatore di closedlist local tempH = math.abs (startX-targetX) + math.abs ( startY-targetY) --h (x) local tempG = 0
Qui dichiariamo la maggior parte delle variabili usate nel metodo.
openlist [1] = x = startX, y = startY, g = 0, h = tempH, f = 0 + tempH, par = 1 local xsize = table.getn (scheda [1]) local ysize = table.getn (board) local curSquare = local curSquareIndex = 1 - Indice della base attuale
Immergiti nel prossimo blocco, iniziamo impostando il primo sqare nella lista aperta sul quadrato iniziale. Quindi creiamo le variabili per la larghezza e l'altezza della tavola, dichiariamo una tabella per il quadrato corrente che viene controllato nell'elenco aperto e creiamo una variabile per l'indice nella lista aperta del quadrato corrente. Nel caso ti stavi chiedendo, "Par" contiene l'indice del genitore del quadrato. Ciò consente una facile ricostruzione del percorso.
while listk> 0 fa local lowestF = openlist [listk] .f curSquareIndex = listk per k = listk, 1, -1 do se openlist [k] .f < lowestF then lowestF = openlist[k].f curSquareIndex = k end end…
Questo metodo è un po 'rovesciato. Passa attraverso, prima ripetendo l'elenco aperto, e poi espandendo l'elenco aperto fino a raggiungere il quadrato finale. Il primo ciclo annidato scorre l'elenco aperto per trovare il quadrato con il valore F più basso. Il valore f è simile al valore h, tranne per il fatto che il valore f è il costo del percorso più breve dall'inizio alla fine che passa attraverso il quadrato corrente. L'indice di questo quadrato è memorizzato in una variabile. Nota: se la lista aperta diventa mai vuota (cioè non ci sono più spazi idonei per il movimento) non è possibile determinare un percorso e la funzione restituisce zero. Questa possibilità viene controllata nel ciclo while.
closedk = closedk + 1 table.insert (closedlist, closedk, openlist [curSquareIndex]) curSquare = closedlist [closedk]
Qui incrementiamo il contatore dell'elenco chiuso, inseriamo il quadrato con il punteggio f più basso nella lista chiusa e impostiamo quel quadrato come il quadrato corrente. Le linee successive determineranno se i quadrati adiacenti al nuovo quadrato corrente sono idonei per il movimento.
locale rightOK = true local leftOK = true - Booleans che definiscono se sono OK per aggiungere local downOK = true - (deve essere ripristinato per ogni ciclo while) local upOK = true - Guarda attraverso la closedlist. Fa in modo che il percorso non ritorni indietro se closedk> 0 quindi per k = 1, closedk do if closedlist [k] .x == curSquare.x + 1 e closedlist [k] .y == curSquare.y quindi rightOK = false end if closedlist [k] .x == curSquare.x-1 e closedlist [k] .y == curSquare.y quindi leftOK = false end se closedlist [k] .x == curSquare.x e closedlist [k ] .y == curSquare.y + 1 then downOK = false end se closedlist [k] .x == curSquare.x e closedlist [k] .y == curSquare.y - 1 then upOK = false end end end
Per prima cosa, controlliamo se sono già nella lista chiusa:
se curSquare.x + 1> xsize poi rightOK = false end se curSquare.x - 1 < 1 then leftOK = false end if curSquare.y + 1 > ysize then downOK = false end if curSquare.y - 1 < 1 then upOK = false end
Secondo, assicura che i quadrati adiacenti si trovino entro i limiti del tabellone:
se curSquare.x + 1 <= xsize and board[curSquare.x+1][curSquare.y].isObstacle ~= 0 then rightOK = false end if curSquare.x - 1 >= 1 e board [curSquare.x-1] [curSquare.y] .isObstacle ~ = 0 quindi leftOK = false end if curSquare.y + 1 <= ysize and board[curSquare.x][curSquare.y+1].isObstacle ~= 0 then downOK = false end if curSquare.y - 1 >= 1 e board [curSquare.x] [curSquare.y-1] .isObstacle ~ = 0 then upOK = false end
Terzo, controlliamo se i quadrati adiacenti contengono ostacoli:
-- controlla se il movimento dalla base corrente è più breve rispetto all'ex parrent tempG = curSquare.g + 1 per k = 1, listk do se rightOK e openlist [k] .x == curSquare.x + 1 e openlist [k] .y == curSquare.y e openlist [k] .g> tempG then tempH = math.abs ((curSquare.x + 1) -targetX) + math.abs (curSquare.y-targetY) table.insert (lista aperta, k, x = curSquare.x + 1, y = curSquare.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk) rightOK = false end se leftOK e openlist [k] .x = = curSquare.x-1 e openlist [k] .y == curSquare.y e openlist [k] .g> tempG then 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) leftOK = falso end if downOK e openlist [k] .x == curSquare.x e openlist [k] .y == curSquare.y + 1 e openlist [k] .g> tempG then 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 end if upOK e openlist [k] .x == curSquare.x e openlist [k] .y == curSquare.y-1 e openlist [k] .g> tempG then 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 = false end end
Infine, l'algoritmo controlla che sia "più economico" spostarsi dal quadrato corrente al quadrato successivo rispetto a quello che sarebbe stato spostarsi dal quadrato padre al quadrato successivo. Questo assicura che il percorso scelto sia effettivamente il percorso più economico possibile e non ci sono scorciatoie ovvie che non sono state rispettate.
-- Aggiungi punto a destra del punto corrente se rightOK quindi listk = listk + 1 tempH = math.abs ((curSquare.x + 1) -targetX) + math.abs (curSquare.y-targetY) table.insert (lista aperta, listk , x = curSquare.x + 1, y = curSquare.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk) end - Aggiungi punto a sinistra del punto corrente se lasciatoOK quindi listk = listk + 1 tempH = math.abs ((curSquare.x-1) -targetX) + math.abs (curSquare.y-targetY) table.insert (lista aperta, listk, x = curSquare.x-1, y = curSquare.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk) end - Aggiungi punto nella parte superiore del punto corrente se downOK quindi 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 - Aggiungi punto nella parte inferiore del punto corrente se upOK quindi 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) fine
Questo penultimo pezzo è dove finalmente espandiamo la lista aperta dopo tutti questi ardui test. Se un quadrato adiacente al quadrato corrente è stato in grado di perservare attraverso le nostre condizioni rigorose, guadagna un posto nella lista aperta, dove può essere scelto come il quadrato corrente successivo a seconda del suo valore F.
... table.remove (openlist, curSquareIndex) listk = listk-1 se closedlist [closedk] .x == targetX e closedlist [closedk] .y == targetY, quindi restituisce la lista chiusa end end return nil end
Finalmente arriviamo alla fine della lunga funzione. Per prima cosa rimuoviamo il quadrato corrente dalla lista aperta. Verifichiamo quindi se le posizioni xey del quadrato corrente sono uguali a quelle del quadrato obiettivo. Se è così, passiamo la lista chiusa al metodo CalcPath in cui i dati sono raffinati.
function CalcPath (closedlist) se closedlist == nil quindi restituisce 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 per n = table.getn (pathIndex), 1, -1 do table.insert ( path, x = closedlist [pathIndex [n]]. x, y = closedlist [pathIndex [n]]. y) end closedlist = nil return path end
È tutto in discesa da qui! Questa funzione riduce l'elenco chiuso per garantire che venga restituito solo il percorso corretto. Senza questo se l'algoritmo ha attraversato un percorso, si è bloccato e ha colpito un nuovo percorso, la tabella restituita conterrà le coordinate per il percorso corretto e il tentativo fallito. Tutto ciò che fa è iniziare alla fine dell'elenco chiuso e ricostruire il percorso all'inizio tramite la proprietà genitore aggiunta in precedenza. Dopo aver ottenuto il nostro elenco di coordinate corrette, possiamo usare quell'informazione per creare un percorso finito nel secondo ciclo. Questo è tutto ciò che c'è nell'algoritmo A *. Di seguito vediamo come possiamo usarlo in un programma.
Meno male! C'erano molte nuove informazioni. Fortunatamente il resto di questa app è molto semplice da costruire anche con una conoscenza di base della Corona API. La prima cosa da fare è creare il file main.lua e inserirlo in una nuova directory. Questo è tutto ciò che Corona richiede in termini di configurazione! Ora creeremo il tavolo che terrà la nostra griglia 10x10 e, mentre ci siamo, possiamo sbarazzarci di quella barra di stato sgradevole nella parte superiore dello schermo.
display.setStatusBar (display.HiddenStatusBar) board = --Crea una tabella vuota per contenere la tavola --Popola la tabella per i = 1, 10 fai board [i] = per j = 1, 10 fai board [ i] [j] = scheda [i] [j] .square = display.newRect ((i-1) * 32, (j-1) * 32, 32, 32) scheda [i] [j]. square: setFillColor (255, 255, 255) board [i] [j] .isObstacle = 0 end end
Non c'è nulla di rivoluzionario qui. Tutto ciò che abbiamo fatto è stato nascondere la barra di stato e creare una matrice tridimensionale per contenere la griglia. Nei loop for, abbiamo impostato la lunghezza laterale dei nostri quadrati a 32 pixel e li abbiamo posizionati con una certa moltiplicazione. Nota: assicurati di utilizzare i tasti .square e .isObstacle invece di dire solo board [2] [3].
Aggiungere ostacoli è un compito semplice. Per questo tutorial, gli spazi idonei per il movimento saranno bianchi, gli ostacoli saranno neri e gli indicatori che indicano il percorso saranno rossi. Guarda la seguente funzione:
Accentsconagua
addObstacle = function (event) if event.phase == "ended" ed 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) Si noti che la funzione è un listener di eventi di runtime. Gli eventi di runtime vengono inviati a tutti gli ascoltatori e non si applicano a un oggetto specifico. Questo è il comportamento desiderato per questa implementazione. La funzione addObstacle inizia controllando se l'utente ha alzato il dito. Dimenticare questo passaggio causerà sicuramente molta frustrazione da parte dell'utente, poiché il pulsante potrebbe essere premuto da uno sfioramento accidentale e non da un movimento intenzionale verso il basso e verso l'alto del dito. Gli utenti sono abituati a queste sfumature, quindi è importante prestare attenzione a loro ogni volta che è possibile. Questo stesso condizionale assicura anche che solo gli eventi di tocco che si verificano all'interno della griglia alta 320 px vengano inviati a questo metodo. Questo impedisce loro di interferire con i nostri pulsanti.
Oltre a ciò, questa funzione utilizza una matematica di base per capire quale quadrato è stato toccato usando event.y ed event.x, e chiama la funzione di ricerca del percorso per garantire che l'utente lasci un percorso. A seconda delle esigenze, questo può o non può essere desiderabile, ma è bello sapere che hai la possibilità di fare queste determinazioni.
Per ragioni di brevità, questo tutorial non lesinerà le animazioni e posizionerà semplicemente degli indicatori lungo il percorso determinato da A *.
placeMarkers = function (event) path = CalcPath (CalcMoves (board, 1, 1, 10, 10)) per i = 1, table.getn (percorso) do local newX = percorso [i] .x local newY = percorso [i ] .y local marker = display.newCircle ((newX * 32 - 16), (newY * 32 - 16), 8) marker: setFillColor (255, 0, 0) end end
Questo è tutto il codice necessario. Semplicemente inseriamo le coordinate in una tabella denominata path e iteriamo attraverso l'intera tabella, posizionando un marker con un raggio di otto pixel per ogni set di coordinate. Le cose possono diventare un po 'pelose quando si tenta di utilizzare animazioni insieme a questo, ma non dovrebbe essere un problema se si tiene traccia dell'indice della coordinata corrente e lo si incrementa dopo un certo intervallo di tempo.
Allo stato attuale, la funzione animata non farà assolutamente nulla perché non viene mai chiamata. L'utilizzo di un evento di runtime non è davvero appropriato in questa istanza, quindi utilizzeremo un'immagine con un listener di eventi.
local goButton = display.newImage ("PlaceMarkers.png", -200, 350) goButton: addEventListener ("touch", placeMarkers) Ecco! Con due linee di codice, siamo pronti per partire.
Se si esegue il programma ora, si noterà senza dubbio che i marcatori non scompaiono quando si esegue nuovamente il programma. La soluzione è mettere i loop nidificati che inizialmente popolavano la tabella in un metodo che possiamo chiamare ogni volta che abbiamo bisogno di una lavagna pulita. L'inizio del programma dovrebbe ora assomigliare a questo:
setup = function () counter = 1 board = --Popola la tabella per i = 1, 10 fa board [i] = per j = 1, 10 fa 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
Solo altre due righe e il nostro programma sarà completo! Mi sono preso la libertà di aggiungere una combinazione di colori di aspetto migliore al programma. Ti incoraggio a giocare con questo progetto. Vedi se riesci a fermarlo. Se ti senti coraggioso, prova a modificare la funzione h (x) e guarda cosa succede!
local resetButton = display.newImage ("Reset.png", 300, 350) resetButton: addEventListener ("touch", setup) Questo tutorial copre molto terreno! La carne di esso era l'algoritmo di ricerca del percorso. A * è uno strumento molto potente, e questa era una versione abbastanza semplice di esso. Potresti aver notato che non ha tenuto conto del movimento diagonale ed era basato sui quadrati. La verità è che puoi modificare l'algoritmo per adattarlo a qualsiasi tessera di forma e puoi modificare h (x) per ottenere il movimento diagonale. Il bello è che, mentre il codice dell'algoritmo può diventare complesso, il codice per l'interfaccia utente e il resto dell'applicazione rimarrà semplice e veloce da scrivere grazie alla potenza e alla semplicità di Corona SDK. Offre capacità senza precedenti in due dimensioni senza la complessità di Objective-C.
