Artificial Intelligence Series - Del 1: Sti Finne
12
Del
3
Del
Dette Cyber mandag Envato Tuts + Kursene vil bli redusert til bare $ 3. Ikke gå glipp av.
Denne opplæringen er den første av tre som diskuterer hvordan man skal gi noen Artificial Intelligence (AI) til spill og apps du oppretter. I denne første opplæringen skal vi lære om banen funn.
Endelig resultat Forhåndsvisning
La oss ta en titt på det endelige resultatet vi skal jobbe mot :
Klikk på et punkt, og deretter et annet punkt og AI vil finne ut en kortest mulig vei å komme mellom dem. Du kan bruke rullegardinlisten til å velge AI algoritme for å bruke
Trinn 1:. AI Series Oversikt
Denne opplæringen vil være den første av de tre som vil diskutere gi kunstig intelligens (AI) til spill og apps du oppretter. Du tenker kanskje at dette høres litt for hardt, men det er faktisk ganske enkelt! Jeg vil forklare to viktige aspekter av AI i spill og deretter lage et kult spill ved hjelp av det vi lærer. Jeg håper du liker å følge denne korte serien
Trinn 2: Innledning
I spill, er en av de viktigste aspektene for å gjøre det veldig effektivt, til å gjøre hva det har å gjøre med minimale ressurser. Det er en hel vitenskap bare for at
I denne opplæringen skal vi dekke et viktig aspekt i spillutvikling. Pathfinding. Vi vil diskutere de 2 beste metodene, hvordan de fungerer, hvordan vi gjør dem arbeide i AS3, så sist men ikke minst, når man skal bruke dem. La oss starte ..
Trinn 3: Så hva er pathfinding Om
Tenk deg at du er midt i en skog med 50 forskjellige mulige ruter foran deg, har du nesten ingen energi og trenger å finne den beste veien ut, hvordan ville du gjøre det
En mulighet vil være å følge hver av de 50 rutene; en prøve og feile metoden. Du vil sikkert få ut, men det ville ta for mye tid. Dette er ikke et nytt problem, og mange mennesker har kommet opp med ideer om hvordan å løse det. En av dem var Edsger Dijkstra som utviklet en algoritme for å få den korteste veien gitt en graf, en kilde og et mål.
Før vi kan begynne å løse problemet, må vi skape disse elementene, grafen som inneholder all informasjon, nodene som er waypoint av grafen, og kantene som forbinder nodene. Tenk på det som grafen være et kart: nodene er byene og kantene på motorveier som kobler dem
Trinn 4:. Sette opp prosjektet
Før vi begynner koding La oss først sette opp vårt arbeidsområde. Opprett en ny mappe og gi den navnet "pathfinding". Inne det oppretter en annen mappe og gi den navnet «Graph". Deretter i pathfinding mappe Opprett en ny Flash (AS3) FLA fil og kaller det "pathfinding"
Trinn 5:. Opprette Node Symbol
I "PathFinding.fla" fil, gå til Insert > New Symbol og opprette en ny MovieClip kalt Node. Velg "eksport for Actionscript" og som klassen skrive "Graph.Node"
Trinn 6: Tegning Node
Inne i Node MovieClip, opprette en ny sirkel med en radius på 25 og plassere den i midten. Deretter legger du til en ny tekstboks, gjør det dynamisk og gi den en forekomst navnet "idx_txt" og plasser den på midten av scenen
Trinn 7:. Opprette Node
Hver node består av 2 hovedelementer; en indeks for å identifisere den, og sin posisjon på grafen. Med dette i bakhodet opprette en ny klasse inne i Graph mappen /pakke og gi den navnet "Node". Gjør det forlenge sprite klassen, så bare legge til to variabler: en int for indeksen, og en Vector3D for stillingen. Også legge til deres tilsvarende sett og få metoder:
pakke Graph {import flash.display.Sprite; import flash.geom.Vector3D; public class Node strekker Sprite {private Var pos: Vector3D; private Var Indeks: int; offentlig funksjon Node (idx: int, n_Pos: Vector3D) {index = idx; pos = n_Pos; this.x = n_Pos.x; this.y = n_Pos.y; idx_txt.text = String (idx)} offentlig funksjon getIndex (): int {return index; } Offentlig funksjon setPos (n_Pos: Vector3D): void {pos = n_Pos; } Offentlig funksjon getPos (): Vector3D {return pos; }}}
Trinn 8: Opprette Edge
Kanten inneholder tre elementer: indeksene for de to noder som den kobles, og dens "pris" (eller avstanden mellom nodene Nå kan du legge to ints for nodene, og ett nummer for kostnadene, og deretter legge den tilsvarende sett og få metoder. Graph er et mer komplekst element siden det må lagre all informasjon. I Graph mappen oppretter du en ny klasse og gi den navnet «Graph". Siden det bare inneholder data, er det ingen grunn til å forlenge Sprite-klassen. Grafen vil inneholde en vektor med alle noder på grafen, en annen Vector med kantene at hver node har og en statisk int i orden for å få den neste indeks tilgjengelige for en node. På denne måten vil det være lettere å få tilgang til alle elementene i grafen, siden noden indeksen er nøkkelen til kantene vektor, noe som betyr at hvis du ønsker å få kantene på en node med indeks 3, får du tilgang til kantene vektor på posisjon 3 og du vil få de kanter for at noden Nå la oss lage disse variablene: Grafen trenger også metoder for å legge til og få noder og kanter: Så nå som vi har alle elementene som trengs, la oss gå videre og bygge en graf I pathfinding mappen opprette en ny klasse, og kaller det "Main", vil dette være vårt viktigste klassen: Nå må vi importere klassene vi bare laget siden de er i Graph-mappen. Deretter oppretter to variabler: en for grafen og en annen som er en matrise av posisjonen til nodene vi ønsker å legge til. Etter det bare legge disse nodene og kantene: Som jeg fortalte deg før det er mange metoder for å oppnå en sti mellom to noder, som DFS (Deep Første Søk? ), eller BFS (Broad First Search), men noen ganger trenger du ikke bare ønsker å få en bane som kobler nodene, du også ønsker å få den "beste" banen, som mesteparten av tiden vil bety en som tar mindre tid eller nærmeste, avhengig av hva du ønsker. I denne opplæringen vil jeg bare referere til det som den som kostnader Det er algoritmer som fungere, avhengig av kostnadene, de viktigste som er den Dijkstra Algoritme og A * (A-Star) algoritme. Lar snakke først om Dijkstra Algoritme Denne algoritmen ble opprettet av Edsger Dijkstra i 1959. Det forskudd avhengig av kostnadene som hver kant representerer, kantene med lavere kostnader vil alltid bli valgt først, slik at når du når målet, vil du være sikker på at banen er det laveste koster bane tilgjengelig Fordi denne algoritmen fungerer med kostnader, må vi ha et sted hvor vi skal lagre kostnadene ved å flytte til hver node fra kilden (utgangsnoden); kalle dette en kostnad vektor. For eksempel hvis kilden er node 0, når vi får tilgang til kostnads vektor i posisjon 3, vil dette tilbake den laveste kostnaden til nå med å gå fra 0 til 3. Vi vil også trenger en måte å lagre den korteste veien: Jeg skal forklare den korteste veien treet i neste trinn De grunnleggende trinn i algoritmen er følgende:. En animasjon vil være mer fornuftig. Her prøver vi å få fra 1 til 6: Denne algoritmen er sammensatt av ulike vektorer som vil lagre all informasjon som trengs, for eksempel Kostnadene ved nodene, eller den beste veien til nå. Jeg vil forklare dette bedre: Merk:. AS3 ikke inneholder mange datastrukturer inkludert Indeksert Priority køen, så jeg kodet en å bruke i denne opplæringen. For å få det bare laste ned kildefilene og importere utils mappen til pathfinding mappen. Klassen er utils.IndexPriorityQ Før vi begynner koding, i pathfinding mappen oppretter du en ny mappe og kaller det "algoritmer". I denne nye mappen oppretter du en ny AS3 klasse som heter "Dijkstra": La oss nå kode algoritme. Det må tre grunnleggende ting: selve grafen, kildenoden, og målet node; men vi må også skape vektorene vi bare snakket om (Cost, SPT, SF). Husk å importere Graf klasser: Når vi har satt opp i klassen, kan vi begynne å kode algoritme som vil være i "Søk" -funksjonen. Jeg vil forklare koden med kommentarer, så hvis du fortsatt har noen spørsmål tilbake til trinn 12 og 13 for å minne deg selv hvordan denne algoritmen fungerer: Når funksjonen er ferdig søker vi vil ha den bane alle messes opp på SPT, så det er opp til oss å hente den. Siden SPT har den beste kanten for å få til en node, kan vi jobbe bakover for å få den beste veien. Ta så en referanse følgende bilde som kommer fra den forrige animasjon: Hvis vi får tilgang til SPT på målet node, som i dette tilfellet er 6, vil den returnere den beste kanten for å komme dit. Det ville være den 6 - 5 kanten. Nå hvis vi fortsetter prosessen med den nye noden som kommer med kanten, 5 vi ville få den beste kanten for å komme til det node, som er 5 - 2 kanten. Gjenta denne prosessen igjen med node 2, vil gi oss den kanten 2 - 1, så vi endelig får til begynnelsen, nå begynte al disse kanter vi får den beste veien: 6 > 5 > 2 > en Som du ser har vi å jobbe bakover starter på målet og flytte til kilden for å få den beste veien Opprett en ny funksjon som vil returnere en matrise med noder av banen, kaller det "getPath": Vi er ferdig med nesten alt, vi bare nå må fylle konstruktøren og ringe søkefunksjon, slik at klassen skal se slik ut : For å se et bedre resultat av algoritmen, skrev jeg en klasse som hjelper med oppretting av grafer. Det kalles Grapher og kan bli funnet inne i utils mappe som følger med kildefilene. Denne klassen skaper et rutenett av noder fra der vi kan observere hvordan algoritmen går gjennom grafen. Med denne klassen, åpen igjen "Main.as" filen og endre det. Vi vil nå ha følgende kode: Lagre og kjøre filen, og du vil få dette resultatet: Nå la oss gå videre og utføre et søk med ny algoritme vi nettopp har gjort. Importere Dijkstra klassen, opprette en forekomst av det og kaller getPath funksjon: Lagre og kjøre filen. Du vil se kantene at algoritmen analysert som røde linjer, den beste veien fant (fra node 24 til node 35) fremstår som en svart linje: Som vi kan se, gjør Dijkstra-algoritmen finne den korteste veien mellom to noder, men som det siste bildet viser, er det en masse røde linjer. Dette betyr at alle disse kanter ble analysert, som ikke er en stor avtale, fordi vi har en liten graf, men tenk en større graf; det ville være litt for mange kanter for å analysere. . Hvis vi bare kunne finne en måte å redusere dette og gjøre algoritmen enda mer effektiv ... vel jeg presentere deg A * (A-Star) algoritme A * algoritmen er en modifisert versjon av Dijkstra. Det tar i betraktning en modifisert måte å få kostnaden for hver node med en heuristisk tilnærming. Dette betyr at vi gir litt "hjelp" for algoritmen og fortelle ham hvor du skal gå, jobber som et kompass og flytte algoritmen direkte til målet. I stedet for å beregne kostnadene for en node ved å summere kant kostnadene til den lagrede node kostnadene, er det nå beregnes ved å summere lagret node kostnader og en heuristisk kost, som er en estimering av hvor nær målet noden vi analyserer er. Denne nye kostnaden kalles F kostnadene F kostnaden er beregnet ved hjelp av følgende formel: F = G + H, hvor G er kostnaden av knutepunktet, og H er heuristisk kostnaden for den noden til målet. I denne opplæringen H kostnadene vil bli beregnet ved hjelp av euklidske avstanden mellom noden og målet, som er den rette linjen avstanden mellom de to nodene. Hva dette er at på slutten, nodene med lavere F kostnadene vil være de første testet og fordi F kostnaden vil avhenge for det meste av H kost, ved enden av algoritmen vil alltid prioritere nodene nærmest målet I Algoritmer mappen oppretter du en ny klasse som heter "Astar". Variablene inne i klassen vil være tilnærmet den samme som den Dijkstra klasse, men her vil vi ha en annen vektor for å lagre F kostnaden for hver node: Den eneste forskjellen mellom Dijkstra-algoritmen søkefunksjon og dette vil være at nodene skal sorteres (i Indeksert Priority Queue) avhengig av F Kostnaden vektor og at F kostnadene vektor vil bli gitt av den beregnede H kost og lagret G kostnad: Dette er de eneste endringene som trengs, siden getPath funksjonen er den samme for begge klasser. På slutten klassen vil være denne:
i dette tilfellet). Igjen i grafen pakke /mappe opprette en ny klasse, og kaller det "Edge"; gjøre det forlenge Sprite klassen igjen
pakke Graf {import flash.display.Sprite; import flash.geom.Vector3D; public class Edge strekker Sprite {private Var fra: int; //Indeksen til noden som denne kanten går privat Var til: int; //Indeksen til noden som denne kanten kommer private Var kostnad: Number; //Kostnadene ved krysset gjennom denne noden (dvs. avstanden) offentlig funksjon Edge (n_From: int, n_To: int, n_Cost: Number = 1,0) {fra = n_From; å = n_To; Kostnaden = n_Cost; this.z = 1; } Offentlig funksjon getFrom (): int {return fra; } Offentlig funksjon setFrom (n_From: int): void {fra = n_From; } Offentlig funksjon getto (): int {tilbake til; } Offentlig funksjon Setto (n_To: int): void {to = n_To; } Offentlig funksjon setCost (n_Cost: Number): void {pris = n_Cost; } Offentlig funksjon getCost (): Antall {return kostnad; } /* Siden kanten er bare en linje som forbinder nodene, vil vi bruke denne metoden for å trekke kanten, refererer stil til hvordan vi vil ønske kanten til å være * /public funksjon drawEdge (fromPos: Vector3D, Topos: Vector3D , stil: String = "normal") {switch (stil) {case "normal": //Hvis det er normalt, skape en grå linje this.graphics.clear (); this.graphics.lineStyle (1, 0x999999, 0,3); this.graphics.moveTo (fromPos.x, fromPos.y); this.graphics.lineTo (toPos.x, toPos.y); gå i stykker; case "banen": //Hvis det er en linje fra banen, skape en svart linje this.graphics.clear (); this.graphics.lineStyle (2, 0x000000,1); this.graphics.moveTo (fromPos.x, fromPos.y); this.graphics.lineTo (toPos.x, toPos.y); gå i stykker; case "besøkt": //Hvis det er en linje som brukes av algoritmen, lage en rød linje this.graphics.clear (); this.graphics.lineStyle (1, 0xFF0000,1); this.graphics.moveTo (fromPos.x, fromPos.y); this.graphics.lineTo (toPos.x, toPos.y); gå i stykker; }}}}
Trinn 9: Å lage grafen
pakke Graph {public class Graph {private static Var nextIndex. int = 0; private Var noder. Vector < Node >; private Var kanter: Vector < Array >;. offentlig funksjon Graph () {noder = new Vector <. Node > (); . kanter = new Vector < Array > (); }}}
pakke Graph {public class Graph {private static Var nextIndex: int = 0; private Var noder. Vector < Node >; private Var kanter: Vector < Array >;. offentlig funksjon Graph () {noder = new Vector <. Node > (); . kanter = new Vector < Array > (); } //For å få noden, vi bare be om indeksen på det, og få tilgang til noder vektor med at nøkkelen offentlig funksjon getNode (idx: int): Node {return noder [idx]; } //Å få en kant, ber vi om de to noder at det kobles, //så vi tar alle kanter av fra node og søke om en av dem //går til samme node som kanten vi er ute etter Hvis den gjør det, er at vår kant. offentlig funksjon getEdge (fra: int, til: int): Edge {var from_Edges: Array = kanter [fra] som Array; for (var en: int = 0; et < from_Edges.length, en ++) {if (from_Edges [a] .getTo () == til) {return from_Edges [a]; }} Returnere null; } //For å legge til en node i grafen, ser vi først om det allerede finnes på det, //hvis det ikke skjer, så vi legger det til noder vektor, og legge til en matrise til //kantene vektor der vi lagrer kantene av vedkommende node, til slutt øker vi //neste gyldige int index for å gi den neste tilgjengelige indeks i grafen offentlig funksjon ADDNODE (node: Node): int {if (validIndex (node.getIndex ()) ) {nodes.push (node); edges.push (ny Array ()); nextIndex ++; } Return 0; } //For å legge til en kant, må vi først se om begge nodene den kobles faktisk eksisterer, //så vi må se om denne kanten allerede finnes på grafen, endelig legger vi det //til rekken av kantene på noden hvorfra det gjelder offentlig funksjon addEdge (kant: Edge): void {if (validIndex (edge.getTo ()) & & validIndex (edge.getFrom ())) {if (getEdge (edge.getFrom (), edge.getTo ()) == null) {(kanter [edge.getFrom ()] som Array) .push (kant); }}} //For å få kantene på en node, bare returnere matrisen gitt av kantene vektor //på node-indeksen posisjons offentlig funksjon getEdges (node: int): Array {return kanter [node]; } //Denne funksjonen sjekker om noden indeksen er mellom området allerede lagt noder //som er form 0 til neste gyldig indeks over grafen offentlig funksjon validIndex (idx: int): Boolean {return (idx > = 0 & & idx < = nextIndex)} //returnerer Bare mengden av noder allerede lagt til grafen offentlig funksjon numNodes (): int {return nodes.length; } //Dette er for å tegne alle kantene på grafen for å få dem til normal stil offentlig funksjon tegne (): void {for hver (Var a_edges: Array i kantene) {for hver (var kant: Edge i a_edges) { edge.drawEdge (.. getNode (edge.getFrom ()) getPos (), getNode (edge.getTo ()) getPos ()); }}} //Denne funksjonen tilbake neste gyldig node-indeksen som skal legges public static funksjon getNextIndex (): int {return nextIndex; }}}
Trinn 10:. Bygge en graf
pakke {import flash.display.Sprite; public class Hoved strekker Sprite {offentlig funksjon main () {}}}
pakke {import flash.display.Sprite; import grafen. *; import flash.geom.Vector3D; public class Hoved strekker Sprite {var grafen: Graph = new Graf (); //Denne matrise inneholder posisjonen for de forskjellige noder i grafen (x, y) Var noder: Array = new Array ([110,20], [80,50], [300200], [180250], [380380] [500200]); //Denne rekken inneholder kanter som forbinder de forskjellige noder (fra, til) Var kanter: Array = new Array ([0,1], [0,5], [0,3], [1,2], [ ,,,0],1,0], [1,4], [2,1], [2,5], [3,1], [3,5], [4,0], [4,5], [5, 2], [5,3]); offentlig funksjon main () {//En sløyfe for å skape alle nodene for (var en: int = 0; et < nodes.length, en ++) {var node: Node = new Node (Graph.Graph.getNextIndex () , ny Vector3D (noder [a] [0], noder [a] [1])); graph.addNode (node); addChild (node); } //Annen sløyfe for å lage alle kantene mellom nodene for (VAR b: int = 0; b < edges.length; b ++) {var fra: int = kanter [b] [0]; Var i: int = kanter [b] [1]; Var kant: Edge = new Edge (fra, til, Vector3D.distance (graph.getNode (fra) .getPos (), graph.getNode (til) .getPos ())); graph.addEdge (kant); //Siden drawEdge metoden krever posisjons vektorer, får vi nodene //fra grafen med registeret sitt, og deretter få sin posisjon med getPos () edge.drawEdge (graph.getNode (fra) .getPos (), graph.getNode (til) .getPos ()); addChild (kant); }}}}
Trinn 11: Hvordan velge riktig bane
mindre å følge. (I vårt tilfelle, husk "cost" betyr avstand. I et spill, kan du ønsker å finne den minst farlige sti, eller en som bruker minst drivstoff, eller den minst synlig ...)
Trinn 12: Introduksjon til Dijkstra Algoritme
Trinn 13:. Hvordan Dijkstra Algoritme Works
Ta det nærmeste node ennå ikke analysert.
Legg til sitt beste kant til den korteste veien treet.
Hvis det er målet node, avslutte søket.
Hent alle kanter av dette node.
For hver kant beregne kostnadene ved å flytte fra kilden node til ankomst Node.
Hvis den totale kostnaden for denne kanten er mindre enn kostnadene ved ankomst node til nå, deretter oppdatere noden kostnadene med den nye.
Ta neste nærmeste node ennå ikke analysert.
Gjenta dette helt til målet er nådd, eller det ikke er flere noder tilgjengelig. Anmeldelser
Trinn 14: Algoritme hoved Elements
Den koster vektor: Her vil vi lagre den beste kost inntil nå å nå en viss node fra kilden. For eksempel hvis kildenoden er 3 og vi tilgang element 6 av kostnadene vektor, vil vi få den beste kost funnet så langt å gå fra 3, kilden node, til noden 6.
Den korteste veien treet (SPT): Denne vektoren inneholder den laveste kostnaden kanten for å få til en spesifikk node. Dette betyr at hvis vi åpne element 7 av SPT, vil den returnere den beste kant for å få tilgang til denne noden
The Search Frontier (SF). Denne vektor lagrer den beste kant for å få til en bestemt node , nesten det samme som SPT, men dette vil ha alle noder som ennå ikke er i SPT. Dette betyr at SF vil fungere som et testområde hvor vi skal teste alle kanter for én node, når alle kanter blir analysert vi vil være sikker på at SF inneholder det beste, slik at vi kan deretter legge den til i SPT.
Indeksert Priority Queue (pq): Køen En prioritet er en datastruktur som alltid holde sine elementer i en ordnet måte. Som algoritmen må først få lavest mulig kostnad node, vil denne strukturen holde noder i en avtagende orden avhengig av deres kostnad, men fordi vi ønsker å hente indeks på noden og ikke kostnadene selv, bruker vi en kø indeksert prioritet . For eksempel, hvis det første elementet i pq er node 4, vil dette bety at det er den med lavest kostnad
Trinn 15:. Lag en algoritme Folder
pakke Algoritmer {public class Dijkstra {offentlig funksjon Dijkstra () {}}}
Trinn 16: The Dijkstra algoritmen i AS3
pakken Algoritmer {import Graph.Edge; import Graph.Graph; import utils.IndexedPriorityQ; public class Dijkstra {private Var grafen: Graph //Grafen der søket skal gjøres privat Var SPT. Vector < Edge >; //Den Korteste vei treet inneholder kanter privat Var cost2Node. Vector < Number >; //The Cost vektor som inneholder tall privat Var SF. Vector < Edge >; //The Search Frontier inneholder kanter privat Var kilde: int; //Hvor vil søket bli startet private Var målet: int; //Hvor vil søket ende offentlig funksjon Dijkstra (g: Graph) {}}}
Trinn 17: Søkefunksjonen
privat funksjon søk (): void {//Dette blir indeksert prioritetskøen som vil sortere noder Var pq: IndexedPriorityQ = new IndexedPriorityQ (cost2Node) //Å starte algoritmen vi først legger kilden til pq pq.insert (kilde); //Med dette kan vi sørge for at vi vil fortsette søket til det ikke er flere noder på pq while (! Pq.isEmpty ()) {/* 1.- Ta den nærmeste noden ennå ikke analysert * ///Vi får Den neste nærmeste Node (NCN) som er det første elementet i pq Var NCN: int = pq.pop (); /* 2.-Legg sitt beste kant til den korteste veien treet (Sitt beste kanten er lagret på SF) * /SPT [NCN] = SF [NCN]; //Dette vil farge selve kanten rødt for å se hvilke kanter algoritmen har analysert if (SPT [NCN]) {SPT [NCN] .drawEdge (graph.getNode (SPT [NCN] .getFrom ()). GetPos ( ), graph.getNode (SPT [NCN] .getTo ()) getPos (), "besøkt."); } /* 3.- Hvis det er målet node, avslutte søket * /if (NCN == mål) tilbake; /* 4.- Hente alle kanter av denne noden * /var kanter: Array = graph.getEdges (NCN); //Med denne sløyfen vil vi analysere hver av de kanter av matrisen for hver (var kant: Kant i kantene) {/* 5.- For hver kant beregne kostnaden for å bevege seg fra kildenoden til ankomsten Node * ///Den totale kostnaden er beregnet ved: Kostnader til noden + Cost of kanten Var nCost: Number = cost2Node [NCN] + edge.getCost (); //Hvis ankomst node har ingen kant på SF, og deretter legge sin pris til //Cost vektor, ankomst node til pq, og legge kanten til SF if (SF [edge.getTo ()] == null) {cost2Node [edge.getTo ()] = nCost; pq.insert (edge.getTo ()); SF [edge.getTo ()] = kant; } /* 6.- Hvis kostnaden for denne kanten er mindre enn kostnadene ved ankomst node til nå, så oppdatere noden kostnadene med den nye * /else if ((nCost < cost2Node [edge.getTo ()]) & & (SPT [edge.getTo ()] == null)) {cost2Node [edge.getTo ()] = nCost; //Siden kostnadene til noden er endret, må vi omorganisere igjen pq for å gjenspeile endringene pq.reorderUp (); //Fordi denne kanten er bedre, oppdaterer vi SF med denne kanten SF [edge.getTo ()] = kant; }}}}
Trinn 18: Få Sti
Trinn 19:.. Den getPath Funksjon
offentlig funksjon getPath (): Array {var banen: Array = new Array (); if (target < 0) avkastning banen; Var nd: int = målet; path.push (nd); while (! (nd = kilde) & &! (SPT [nd] = null)). {SPT [nd] .drawEdge (graph.getNode (SPT [nd] .getFrom ()) getPos (), grafen. getNode (SPT [nd] .getTo ()) getPos (), "banen."); nd = SPT [nd] .getFrom (); path.push (nd); } Path = path.reverse (); returnere banen;}
Trinn 20: The Complete Dijkstra Class
pakke Algoritmer {import Graph.Edge; import Graph.Graph; import utils.IndexedPriorityQ; public class Dijkstra {private Var grafen: Graph private Var SPT. Vector < Edge > private Var cost2Node: Vector < Number >. private Var SF. Vector < Edge > private Var kilde: int; private Var målet: int; offentlig funksjon Dijkstra (n_graph: Graph, src: int, tjære = int) {graf = n_graph; source = src; target = tjære; SPT = new Vector. ≪ Edge > (graph.numNodes ()); cost2Node = new Vector. < Number > (graph.numNodes ()); SF = new Vector. ≪ Edge > (graph.numNodes ()); Søke(); } Private funksjon søk (): void {var pq: IndexedPriorityQ = new IndexedPriorityQ (cost2Node) pq.insert (kilde); mens {var NCN: int = pq.pop (); (pq.isEmpty ()!) SPT [NCN] = SF [NCN]; if (SPT [NCN]) {SPT [NCN] .drawEdge (graph.getNode (SPT [NCN] .getFrom ()). getPos (), graph.getNode (SPT [NCN] .getTo ()). getPos () "besøkt"); } If (NCN == mål) tilbake; Var kanter: Array = graph.getEdges (NCN); for hver (var kant: Edge i kantene) {var nCost: Number = cost2Node [NCN] + edge.getCost (); if (SF [edge.getTo ()] == null) {cost2Node [edge.getTo ()] = nCost; pq.insert (edge.getTo ()); SF [edge.getTo ()] = kant; } Else if ((nCost < cost2Node [edge.getTo ()]) & & (SPT [edge.getTo ()] == null)) {cost2Node [edge.getTo ()] = nCost; pq.reorderUp (); SF [edge.getTo ()] = kant; }}}} Offentlig funksjon getPath (): Array {var banen: Array = new Array (); if ((target < 0) || (SPT [target] == null)) tilbake banen; Var nd: int = målet; path.push (nd); while (! (nd = kilde) & &! (SPT [nd] = null)). {SPT [nd] .drawEdge (graph.getNode (SPT [nd] .getFrom ()) getPos (), grafen. getNode (SPT [nd] .getTo ()) getPos (), "banen."); nd = SPT [nd] .getFrom () path.push (nd); } Path = path.reverse (); returnere banen; }}}
Trinn 21: Opprette en ny graf
pakke {import flash.display.Sprite; import grafen. *; import utils.Grapher; public class Hoved strekker Sprite {var grafen: Graph = new Graf (); offentlig funksjon main () {//Rammene for Grapher klassen er bredden og høyden av scenen //antall kolonner og rader, og deretter grafen for lagring av data //Etter dette har vi bare legge den grapher til iscenesette og vi er ferdig. //Dette vil skape et rutenett av noder av 7 * 7 Var grapher: Grapher = new Grapher (550,400,7,7, graf); addChild (grapher); }}}
Trinn 22: Bruke Dijkstra Algoritme
pakke {import flash.display.Sprite; import grafen. *; import utils.Grapher; import Algorithms.Dijkstra; public class Hoved strekker Sprite {var grafen: Graph = new Graf (); offentlig funksjon main () {var grapher: Grapher = new Grapher (550,400,7,7, graf); addChild (grapher); //Vi skaper en ny Dijkstra søk som vil se en vei fra node 24 til node 35 Var dijkstra: Dijkstra = new Dijkstra (graf, 24,35); dijkstra.getPath (); }}}
Trinn 23: Er ikke det noe bedre?
Trinn 24: The A * algoritmen
Trinn 25: The F Cost
Trinn 26:. Den A * algoritmen i AS3
pakke Algoritmer {import Graph.Edge; import Graph.Graph; import flash.geom.Vector3D; import utils.IndexedPriorityQ; public class Astar {private Var grafen: Graph private Var SPT. Vector < Edge > private Var G_Cost: Vector < Number >. //Denne vektoren vil lagre G kostnaden for hver node private Var F_Cost. Vector < Number > //Denne vektoren vil lagre F kostnaden for hver node private Var SF. Vector < Edge > private Var kilde: int; private Var målet: int; offentlig funksjon Astar (n_graph: Graph, src: int, tjære: int) {graf = n_graph; source = src; target = tjære; SPT = new Vector. ≪ Edge > (graph.numNodes ()); Number >; G_Cost = new Vector <. (Graph.numNodes ()); Number >; F_Cost = new Vector <. (Graph.numNodes ()); SF = new Vector. ≪ Edge > (graph.numNodes ()); Søke(); }}}
Trinn 27: The New Search Class
privat funksjon søk (): void {//The pq er nå sortert avhengig av F kostnadene vektor Var pq: IndexedPriorityQ = new IndexedPriorityQ (F_Cost) pq.insert (kilde); mens {var NCN: int = pq.pop (); (pq.isEmpty ()!) SPT [NCN] = SF [NCN]; if (SPT [NCN]) {SPT [NCN] .drawEdge (graph.getNode (SPT [NCN] .getFrom ()). getPos (), graph.getNode (SPT [NCN] .getTo ()). getPos () "besøkt"); } If (NCN == mål) tilbake; Var kanter: Array = graph.getEdges (NCN); for hver (var kant: Kant i kantene) {//H kostnaden oppnås ved avstanden mellom målet node, og noden ankomsten av kanten som blir analysert Div Hcost: Nummer = Vector3D.distance (graph.getNode (kant. . getto ()) getPos (), graph.getNode (mål) .getPos ()) Var Gcost: Number = G_Cost [NCN] + edge.getCost (); Var til: int = edge.getTo (); if (SF [edge.getTo ()] == null) {F_Cost [edge.getTo ()] = Gcost + Hcost; G_Cost [edge.getTo ()] = Gcost; pq.insert (edge.getTo ()); SF [edge.getTo ()] = kant; } Else if ((Gcost < G_Cost [edge.getTo ()]) & & (SPT [edge.getTo ()] == null)) {F_Cost [edge.getTo ()] = Gcost + Hcost; G_Cost [edge.getTo ()] = Gcost; pq.reorderUp (); SF [edge.getTo ()] = kant; }}}}
Trinn 28: The Complete A * Klasse
pakke Algoritmer {import Graph.Edge; import Graph.Graph; import flash.geom.Vector3D; import utils.IndexedPriorityQ; public class Astar {private Var grafen: Graph private Var SPT. Vector < Edge > private Var G_Cost: Vector < Number >. //Denne vektoren vil lagre G kostnaden for hver node private Var F_Cost. Vector < Number > //Denne vektoren vil lagre F kostnaden for hver node private Var SF. Vector < Edge > private Var kilde: int; private Var målet: int; offentlig funksjon Astar (n_graph: Graph, src: int, tjære: int) {graf = n_graph; source = src; target = tjære; SPT = new Vector. ≪ Edge > (graph.numNodes ()); Number >; G_Cost = new Vector <. (Graph.numNodes ()); Number >; F_Cost = new Vector <. (Graph.numNodes ()); SF = new Vector. ≪ Edge > (graph.numNodes ()); Søke(); } Private funksjon søk (): void {//The pq er nå sortert avhengig av F kostnadene vektor Var pq: IndexedPriorityQ = new IndexedPriorityQ (F_Cost) pq.insert (kilde); mens {var NCN: int = pq.pop (); (pq.isEmpty ()!) SPT [NCN] = SF [NCN]; if (SPT [NCN]) {SPT [NCN] .drawEdge (graph.getNode (SPT [NCN] .getFrom ()). getPos (), graph.getNode (SPT [NCN] .getTo ()). getPos () "besøkt"); } If (NCN == mål) tilbake; Var kanter: Array = graph.getEdges (NCN);