Share
Dit project doorloopt de basisprincipes van padvinden in de Corona SDK via het A * -padvindingsalgoritme, een nietje in de game-industrie sinds ongeveer 1970. Met deze app kun je obstakels toevoegen aan een raster van 10x10 en het pad bekijken dat wordt bepaald door A *.
A * gebruikt twee functies om het pad van 'least cost' naar het doel te bepalen. De eerste functie, vaak g (x) genoemd, is de kosten van het verplaatsen tussen twee aangrenzende vierkanten. Dit is handig als je spel verschillende terreinen heeft, zoals moerassen en verharde wegen die verschillende bewegingseffecten kunnen hebben. De tweede functie, h (x), is een schatting van de afstand van het huidige vierkant tot het doelvierkant langs het ideale pad. Er zijn veel verschillende manieren om deze afstand te berekenen, maar voor dit programma gebruiken we een relatief eenvoudige benadering door de resterende afstand in de y-richting toe te voegen aan de resterende afstand in de x-richting.
We zullen de volgende twee lua-functies gebruiken om het pad te vinden. De functie wordt als volgt aangeroepen, CalcPath (CalcMoves (bord, startX, startY, targetX, targetY)). De CalcPath-functie retourneert een tabel van de coördinaten naar het doel, of nul als er geen pad kon worden gevonden. Dit gedrag zal van pas komen bij het bepalen van de geldigheid van plaatsing van obstakels.
Als u geen interesse hebt in de aspecten achter de schermen van het algoritme, hoeft u alleen maar de functies van de volledige bron bovenaan de pagina te kopiëren en te plakken. Anders zet u uw veiligheidsgordels vast: dit kan in eerste instantie veel zijn om in te nemen.
Laten we eerst naar CalcMoves kijken.
lokale openlist = - Mogelijke verplaatsingen lokale closedlist = - gecontroleerde vierkanten lokale listk = 1 - openlistteller lokale closedk = 0 - closedlistteller lokale tempH = math.abs (startX-targetX) + math.abs ( startY-targetY) --h (x) local tempG = 0
Hier verklaren we de meeste variabelen die in de methode worden gebruikt.
openlist [1] = x = startX, y = startY, g = 0, h = tempH, f = 0 + tempH, par = 1 local xsize = table.getn (board [1]) local ysize = table.getn (board) local curSquare = local curSquareIndex = 1 - Index van huidige basis
Duik in het volgende deel, we beginnen met het instellen van de eerste sqare in de open lijst naar het startveld. Vervolgens maken we variabelen voor de breedte en hoogte van het bord, verklaren een tabel voor het huidige vierkant dat wordt gecontroleerd in de open lijst en maken een variabele voor de index in de open lijst van het huidige vierkant. In het geval dat je je afvroeg, bevat "Par" de index van de ouder van het vierkant. Dit maakt gemakkelijke reconstructie van het pad mogelijk.
while listk> 0 do local lowestF = openlist [listk] .f curSquareIndex = listk voor k = listk, 1, -1 do als openlist [k] .f < lowestF then lowestF = openlist[k].f curSquareIndex = k end end…
Deze methode is een beetje op zijn kop gezet. Het loopt door, eerst itereert door de open lijst en tweede breidt de open lijst uit tot het het laatste vierkant bereikt. De eerste geneste lus itereert door de open lijst om het vierkant met de laagste F-waarde te vinden. De f-waarde is vergelijkbaar met de h-waarde, behalve dat de f-waarde de prijs is van het kortste pad van begin tot eind dat door het huidige vierkant loopt. De index van dit vierkant wordt opgeslagen in een variabele. Opmerking: als de open lijst ooit leeg wordt (dat wil zeggen: er waren geen spaties meer die in aanmerking komen voor verplaatsing), kon een pad niet worden bepaald en keerde de functie nul terug. Deze mogelijkheid wordt gecontroleerd in de while-lus.
closedk = closedk + 1 table.insert (closedlist, closedk, openlist [curSquareIndex]) curSquare = closedlist [closedk]
Hier verhogen we de gesloten-lijst-teller, voegen het vierkant met de laagste f-score in de gesloten lijst in en stellen dat vierkant in als het huidige vierkant. De volgende regels bepalen of de vierkanten naast het nieuwe huidige vierkant in aanmerking komen voor verplaatsing.
local rightOK = true local leftOK = true - Booleans bepalen of ze OK lokaal kunnen toevoegen downOK = true - (moet worden gereset voor elke while-lus) local upOK = true - Kijk door gesloten lijst. Zorgt ervoor dat het pad niet dubbel teruggaat als closedk> 0 en dan voor k = 1, closedk doe als closedlist [k] .x == curSquare.x + 1 en closedlist [k] .y == curSquare.y then rightOK = false end if closedlist [k] .x == curSquare.x-1 en closedlist [k] .y == curSquare.y then leftOK = false end if closedlist [k] .x == curSquare.x en closedlist [k ] .y == curSquare.y + 1 then downOK = false end if closedlist [k] .x == curSquare.x en closedlist [k] .y == curSquare.y - 1 then upOK = false end end end
Eerst controleren we of ze al in de gesloten lijst staan:
als curSquare.x + 1> xsize en rightOK = false end als 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
Ten tweede zorgt het ervoor dat de aangrenzende vierkanten zich binnen de grenzen van het bord bevinden:
als curSquare.x + 1 <= xsize and board[curSquare.x+1][curSquare.y].isObstacle ~= 0 then rightOK = false end if curSquare.x - 1 >= 1 en bord [curSquare.x-1] [curSquare.y] .isObstacle ~ = 0 then 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 en bord [curSquare.x] [curSquare.y-1] .isObstacle ~ = 0 then upOK = false end
Ten derde controleren we of de aangrenzende pleinen obstakels bevatten:
-- controleer of de verplaatsing van de huidige basis korter is dan van de voormalige parrent tempG = curSquare.g + 1 voor k = 1, listk do als rightOK en openlist [k] .x == curSquare.x + 1 en openlist [k] .y == curSquare.y en 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) rightOK = false end if leftOK en openlist [k] .x = = curSquare.x-1 en openlist [k] .y == curSquare.y en 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 = false einde als downOK en openlist [k] .x == curSquare.x en openlist [k] .y == curSquare.y + 1 en 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 einde als upOK en openlist [k] .x == curSquare.x en openlist [k] .y == curSquare.y-1 en 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 = valse end-end
Ten slotte controleert het algoritme of het "goedkoper" is om van het huidige vierkant naar het volgende vierkant te gaan dan van het oudervierkant naar het volgende vierkant te gaan. Dit zorgt ervoor dat het gekozen pad inderdaad het goedkoopste pad is dat mogelijk is en dat er geen duidelijke snelkoppelingen zijn die zijn gemist.
-- Voeg een punt toe rechts van het huidige punt als rightOK dan 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 - Voeg punt links van huidig punt toe als leftOK then 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 - Voeg punt toe bovenaan het huidige punt als downOK dan 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 - Voeg punt toe onderaan het huidige punt als upOK dan 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) einde
Dit tweede tot en met het laatste deel is waar we eindelijk de open lijst uitbreiden na al die zware testen. Als een vierkant naast het huidige vierkant in staat is om door onze rigoureuze omstandigheden te overleven, verdient het een plek op de open lijst, waar het kan worden gekozen als het volgende huidige vierkant, afhankelijk van zijn F-waarde.
... table.remove (openlist, curSquareIndex) listk = listk-1 if closedlist [closedk] .x == targetX en closedlist [closedk] .y == targetY en retourneer vervolgens closedlist end end return nil end
Eindelijk komen we aan het einde van de lange functie. Eerst verwijderen we het huidige vierkant uit de open lijst. We controleren vervolgens of de x- en y-posities van het huidige vierkant gelijk zijn aan die van het doelvak. Als dat het geval is, geven we de gesloten lijst door aan de CalcPath-methode, waar de gegevens worden verfijnd.
function CalcPath (closedlist) als closedlist == nul en return 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 voor n = table.getn (pathIndex), 1, -1 do table.insert ( pad, x = closedlist [pathIndex [n]]. x, y = closedlist [pathIndex [n]]. y) end closedlist = nil retourpad einde
Het is allemaal bergafwaarts vanaf hier! Deze functie vermindert de gesloten lijst om ervoor te zorgen dat alleen het juiste pad wordt geretourneerd. Zonder dit als het algoritme een pad zou passeren, vast zou lopen en een nieuw pad zou raken, zou de teruggestuurde tabel coördinaten bevatten voor zowel het juiste pad als de mislukte poging. Het enige dat het doet is beginnen aan het einde van de gesloten lijst en het pad naar het begin reconstrueren via de eerder toegevoegde oudereigenschap. Nadat we onze lijst met correcte coördinaten hebben verkregen, kunnen we die informatie gebruiken om een voltooid pad in de tweede lus te maken. Dat is alles wat er is met het A * -algoritme. Vervolgens bekijken we hoe we het in een programma kunnen gebruiken.
Oef! Dat was veel nieuwe informatie. Gelukkig is de rest van deze app heel eenvoudig te bouwen met zelfs een basiskennis van de Corona API. Het eerste dat u moet doen, is uw main.lua-bestand maken en dit in een nieuwe map plaatsen. Dat is alles wat Corona nodig heeft op het gebied van setup! Vervolgens gaan we de tabel maken die ons 10x10 raster zal bevatten, en terwijl we bezig zijn, kunnen we van die lelijke statusbalk aan de bovenkant van het scherm afkomen.
display.setStatusBar (display.HiddenStatusBar) board = - Maak een lege tabel om het bord vast te houden - Bepaal de tabel voor i = 1, 10 do board [i] = voor j = 1, 10 do board [ i] [j] = bord [i] [j] .square = display.newRect ((i-1) * 32, (j-1) * 32, 32, 32) bord [i] [j]. square: setFillColor (255, 255, 255) bord [i] [j] .isObstacle = 0 end end
Er is hier niets revolutionairs. Alles wat we deden was de statusbalk verbergen en een driedimensionale array maken om het raster vast te houden. In de for-loops hebben we de lengte van de zijkanten van onze vierkanten ingesteld op 32 pixels en gepositioneerd met een handige vermenigvuldiging. Opmerking: zorg ervoor dat u de .square- en .isObstacle-sleutels gebruikt in plaats van alleen maar board [2] [3] te zeggen.
Het toevoegen van obstakels is een eenvoudige taak. Voor deze zelfstudie zijn spaties die in aanmerking komen voor beweging wit, zijn obstakels zwart en zijn de markeringen die het pad aangeven rood. Bekijk de volgende functie:
Accentsconagua
addObstacle = function (event) als event.phase == "ended" en 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) Merk op dat de functie een runtime-gebeurtenislistener is. Runtime-evenementen worden verzonden naar alle luisteraars en zijn niet van toepassing op een specifiek object. Dit is het gewenste gedrag voor deze implementatie. De addObstacle-functie begint met het controleren of de gebruiker zijn vinger heeft opgetild. Het vergeten van deze stap zal ongetwijfeld veel frustratie veroorzaken bij de gebruiker, omdat de knop kan worden ingedrukt door een toevallige veegbeweging en niet een opzettelijke beweging van de vinger. Gebruikers zijn aan deze nuances gewend, dus het is belangrijk om daar waar mogelijk aandacht aan te schenken. Deze zelfde voorwaardelijke zorgt er ook voor dat alleen aanraakgebeurtenissen die plaatsvinden binnen het 320px hoge raster naar deze methode worden verzonden. Dit voorkomt dat ze onze knoppen verstoren.
Daarnaast maakt deze functie gebruik van basisberekeningen om te achterhalen welk vierkant is aangeraakt met behulp van event.y en event.x en wordt de padzoekfunctie opgeroepen om ervoor te zorgen dat de gebruiker een pad verlaat. Afhankelijk van je behoeften is dit misschien wel of niet wenselijk, maar het is leuk om te weten dat je de mogelijkheid hebt om deze beslissingen te nemen.
Kortheidshalve zal deze tutorial skimp animaties bevatten, en markeringen plaatsen langs het pad bepaald door A *.
placeMarkers = functie (event) pad = CalcPath (CalcMoves (board, 1, 1, 10, 10)) voor i = 1, table.getn (pad) do local newX = pad [i] .x local newY = path [i ] .y local marker = display.newCircle ((newX * 32 - 16), (newY * 32 - 16), 8) marker: setFillColor (255, 0, 0) end end
Dit is alle code die nodig is. We plaatsen simpelweg de coördinaten in een tabel met de naam pad en doorlopen de hele tabel, waarbij een marker met een straal van acht pixels op elke set coördinaten wordt geplaatst. Dingen kunnen een beetje harig worden als je probeert om animaties in combinatie hiermee te gebruiken, maar het zou niet zo slecht mogen zijn zolang je de index van je huidige coördinaat bijhoudt, en het na een bepaald tijdsinterval verhoogt.
Zoals het er nu uitziet, zal de animatiefunctie absoluut niets doen omdat het nooit wordt aangeroepen. Het gebruik van een runtime-evenement is in dit geval niet geschikt, dus we gebruiken een afbeelding met een gebeurtenislistener.
local goButton = display.newImage ("PlaceMarkers.png", -200, 350) goButton: addEventListener ("touch", placeMarkers) Voila! Met twee regels code zijn we klaar om te gaan.
Als u het programma nu uitvoert, zult u ongetwijfeld merken dat de markeringen niet verdwijnen wanneer u het programma opnieuw uitvoert. De oplossing is om de geneste for-lussen die aanvankelijk de tafel bevolkten, in een methode te plaatsen die we kunnen oproepen wanneer we een schone lei nodig hebben. Het begin van het programma zou er nu als volgt uit moeten zien:
setup = functie () counter = 1 board = --Populate the Table voor i = 1, 10 do board [i] = voor j = 1, 10 do board [i] [j] = board [ i] [j] .square = display.newRect ((i-1) * 32, (j-1) * 32, 32, 32) bord [i] [j] .square: setFillColor (255, 255, 255) board [i] [j] .isObstacle = 0 end end end
Nog twee regels en ons programma is compleet! Ik nam de vrijheid om een mooier kleurenschema aan het programma toe te voegen. Ik moedig je aan om met dit project te spelen. Kijk of je het kunt stropen. Als je je moedig voelt, probeer dan de functie h (x) te wijzigen en kijk wat er gebeurt!
local resetButton = display.newImage ("Reset.png", 300, 350) resetButton: addEventListener ("touch", setup) Deze tutorial bestrijkt heel wat terrein! Het vlees ervan was het padvindende algoritme. A * is een zeer krachtig hulpmiddel en dit was een vrij eenvoudige versie ervan. Je hebt misschien gemerkt dat het geen diagonale beweging was en was gebaseerd op vierkanten. De waarheid is dat je het algoritme kunt aanpassen aan elke vormentegel en je kunt h (x) aanpassen om diagonale bewegingen te bereiken. Het mooie is dat, terwijl je algoritmecode complex kan worden, de code voor de gebruikersinterface en de rest van de toepassing eenvoudig en snel te schrijven blijft dankzij de kracht en eenvoud van de Corona SDK. Het biedt je ongekende mogelijkheden in twee dimensies zonder de complexiteit van Objective-C.
