JavaScript útkeresés

3. A* algoritmus

A legismertebb gráfkereső eljárás, amelyet Bertram Raphael, Nils Nilsson és Peter Hart alkotott meg 1968-ban. A legfontosabb tulajdonsága, hogy megoldás létezése esetén mindig optimális megoldást talál. Legelső változatát az első generációs Shakey robot irányításához használták. Labirintus és puzzle játékok megoldásának népszerű eszköze.

Nyomkövetés | Kattintás a sárga cellára

Bemenet: A böngésző munkaterületén kialakított játéktér falakkal és mozgási területtel, valamint az útvonal start és end pontja.

Kimenet: A start és end pozíciók közötti útvonal.

Változók: Játéktér sor és oszlop elemei, a cells tömb a cellák adatainak számításához.

Algoritmus: A start pozíciótól kezdődően folyamatosan kiszámítjuk a szomszédos cellák f(n)=g(n)+h(n) fügvényét, ahol g(n) a cellák start pozicíótól számított költsége, illetve h(n) az a heurisztikus függvény által meghatározott érték, amivel az end pozíció aktuális cellához viszonyított távolságát határozhatjuk meg. A megvizsgált cellákat egy várólistára fűzzük fel, melyből mindig a legkisebb f(n) értékő cellát helyezzük át a vizsgált listába úgy, hogy közben annak szomszédait is elemezzük. Az eljárást addig folytatjuk amíg el nem érjük az end cellát. Ha nincs megoldás, akkor az út egy üres tömb lesz, tehát nem rajzolható meg.

Eseménykezelés: Az onclick esemény bekövetkezésekor végrehajtandó metódusokat a mystep() függvényből hívjuk meg.

Az alábbiakban rendszerezzük a megoldáshoz szükséges ismereteket. A platformfüggetlen megoldás elkészítéséhez gyakorlatilag egy böngésző programra, és esetleg egy egyszerűbb editorra van szükség. A lecke mintaprogramja a böngészőben kipróbálható és módosítható. Indátásához kattintsatok a forráskód alatti "Próbáld ki! »" gombra.

1	Az algoritmus jellemzői

Az algoritmus véges számú, végrehajtható műveletek sorozatának az elnevezése. Fontos szabály még az is, hogy mindig van bemenete és legalább egy kimenete. A számítógép által értelmezhető nyelven megírt algoritmus pedig a program. Azokat a típusalgoritmusokat, amelyek egy feladat egzakt megoldását adják programozási tételeknek nevezzük. Ilyen például a sorozatszámítás, minimim-maximum választás, keresés, rendezés algoritmusa. Az algoritmusokat nem forrásnyelvi kódban szokták megadni, hanem leíróeszközök segítségével (pl. folyamatábrával, struktogrammal, Jackson ábrával vagy pszeudó kóddal) írják le, amit aztán kódolni lehet egy adott környezetben.

Hasznos leírások:

Adonyi Róbert: Adatstruktúrák és algoritmusok
Heckl István: Adatstruktúrák és algoritmusok példatár

« Előző | Lap eleje

2	Hogyan alakítsuk ki a belső adatszerkezetet?

Az algoritmus által használt értékeket változókban tároljuk. A programnyelvek egyszerű és összetett változókkal dolgoznak. A programtervezés során az adattípusok meghatározása mellet, ügyelnünk kell a belső adatszerkezet optimális kialakítása is. Egy ügyesen tervezett adatszerkezet rengeteg munkát megspórolhat a kódolásnál. A pathfinder programban többdimenziós tömb deklarálásával lehetett a legegyszerűbben kialakítani a cellák adminisztrációját, azt az apró trükköt kihasználva, hogy egy tömb eleme is lehet tömb, illetve objektumok is lehetnek tömbelemek.

  // ========== Globális változók
  var cellsize = 40;
  var nrow = 8;
  var ncell = 8;
  var cells  = new Array(nrow);
  var newrow;
  
  var wallcolor="green";
  var cellcolor="lightyellow";
  var startendcolor="orange";
  var waycolor="red";
  var start=null;
  var end=null;
  var debugenabled=false;
  
  // ========== GameArea celláinak feltöltése (DOM)
  for(var i=0;i<nrow;i++){
      newrow=document.getElementById("gamearea").insertRow(i);
      cells[i] = new Array(ncell);  // soronként új vektor, melynek elemei objektumok
      for(var j=0;j<ncell;j++){
        var cell = new Object();
        cell=newrow.insertCell(j);
        cell.id=i*ncell+j;
        cell.style.width=cellsize+"px";
        cell.style.height=cellsize+"px";
        cell.style.color="#ff3333"; // piros
		
        // === A* cellaleíró adatok deklarálása
        cell.f = 0;
        cell.g = 0;
        cell.h = 0;
        cell.visited = false;
        cell.iswall= false;
        cell.debug = "";
        cell.parent = null;
        cell.x = i;
        cell.y = j;
		
        // === Tömbösítés;
        cells[i][j] = cell;

A program futtatása közben további úgynevezett segédváltozókat is használunk, amelyekkel bizonyos vezérlőszerkezetek működést tudjuk irányítani. Ugyancsak gondoskodnunk kell a kimenő adatok tárolását biztosító adatszerkezetekről is. Ez utóbbiak lehetnek egy másik programmodul, vagy objektum bemenő adatai.

« Előző | Lap eleje

3	Hogyan működik az A* ?

Egy cellaleíró tömben tároljuk a játéksík jellemzőit. Ezen a síkon akadályok és mozgásra alkalmas területek vegyesen helyezkednek el. Ez utóbbiak közöl jelültük ki a start [A] és end [B] pozíciót. Az astar metódus paraméterként kapja meg ezeket az adatokat. Nézzük meg, milyen műveleteket kell elvégeznünk az átvett adatokkal ahhoz, hogy megkapjuk a start és end pozició közötti utat!

A start pozícióban lévő cellát felvesszük egy várólistára, ahonnan mindig a legkisebb F értékű cellát vesszük elő. Most csak a kezdő cella van a várakozási sorban, tehát az ő F értéke a legkisebb. Sorban megvizsgáljuk a körültötte lévő cellákat, ehhez a sor és oszlop azonosítókra van szükségünk. Ha járható celláról van szó, akkor kíszámítjuk az úgynevezett F értéket. Az F érték az aktuális cella start cellához mért költségének (g) és a cél cellához viszonyított távolságának (h) az összege. (Ha le akarnánk egyszerűsíteni a módszert, akkor azt is mondhatnánk, hogy kiszámoljuk a cellatávolságot mindkét irányban, majd összeadjuk az így kapott értékeket. Ugye könnyen belátható, hogyha nő az F értéke, akkor távolodunk az optimális útvonaltól.) Ezeket a számításokat minden élszomszédos cellánál elvégezzük, és a cellákat rendre felfűzzök a várólistára.

Ha egy cella minden szomszédját megvizsgáltuk akkor őt a vizsgált cellák listájára tesszük át. Az újonan listára tett négyzetek szülője mindig az aktuális cella lesz. "Ha valamelyik szomszédos négyzet már korábbról várólistán volt, megnézzük, hogy nem lenne-e jobb a jelenlegi négyzetünkről odamennünk, mint a régi útvonalát meghagyni. Ha nem jobb, ne csináljunk semmit. Ha jobb, akkor az adott négyzet szülőjének adjuk meg azt, ahol most állunk és számoljuk újra a négyzet G és F értékeit."

Ezeket a műveletek addig folytatjuk, amíg el nem értük az end cellát, vagy nem találtuk ugyan az end cellát, de már minden cellát megvizsgáltunk.

"De hogyan kapjuk meg végre azt a legrövidebb útvonalat? Egyszerűen csak haladjunk az end ponttól visszafelé, mindig a négyzetek szülei felé haladva. Így közvetlenül visszajutunk a kezdőpontunkra, tehát ez lesz az áhított útvonalunk. A-ból B-be tehát csak a már megállapított út celláinak középpontjáról középpontjára haladva juthatunk el."^[1]

Hasznos leírások:

« Előző | Lap eleje

4	Érdekel a mesterséges intelligencia?

"A mesterséges intelligencia kutatások célja olyan rendszerek (számítógépes programok, robotok) létrehozása, amelyek intelligens módon képesek feladatokat megoldani. Az utóbbi években egy új szemléletű, viselkedésalapú megközelítés van terjedőben, amely ezt a feladatot úgy fogalmazza meg, hogy kutatások, fejlesztések célja, hogy a feladatmegoldást olyan szereplőkkel, ágensekkel végeztesse el, amelyek az intelligens viselkedés bizonyos vonásaival rendelkeznek."

"Egy intelligens rendszer a problémamegoldás során megszerzett ismeretei alapján oldja meg az adott feladatot és megadja ennek eredményét. Egy ilyen viszonylag független, önálló egységet ágensnek tekintünk. Az ágens eredete a latin ago, agere szó, melynek elsődleges jelentése mozgásba hoz, elintéz, cselekszik. A szó alapjelentése szerint ágens lehet mindaz, ami bizonyos fokú önállósággal bír, valamilyen környezet veszi körül, továbbá ezt a környezetet érzékeli és szükség esetén környezetébe beavatkozik.

Ebben az értelemben ágensnek tekinthető egy ember, aki érzékszervei (pl. fül, szem, orr) segítségével érzékeli környezetét és különböző testrészei (pl. száj, kéz, láb) segítségével beavatkozik. Ágens lehet egy robot is, amely kamerái, szenzorai segítségével érzékel és motorokkal vezérelt beavatkozói (pl. robot karok) segítségével beavatkozik. Ágens lehet továbbá egy szoftver is, amelynél input és output adatok (kódolt bitsorozatok) formájában történik az érzékelés és a beavatkozás." ^[2]

Így tudod kipörgetni a Rubik-kockát 5 másodperc alatt.

Hasznos leírások:

Piglerné Lakner Rozália - Starkné Werner Ágnes: Ágens-technológia

« Előző | Lap eleje

5	Próbáld ki a megoldást!

A leckében tárgyaltak összefoglalásaként tekintsük át és próbáljuk ki az eredeti feladat megoldását. Az elkészült kód most már több mint 250 soros lett, ezért az áttekinthetőség biztosításának érdekében kommentek előzik meg a fontosabb tevékenységek utasításait. Figyeljük meg az elkészült metódusok felépítését, és fedezzük fel azok hívásának sajátosságait, a paraméterátadást, illetve a visszaadott értékek kezelését.

<!DOCTYPE html>
<html lang="hu">
<head>
 <title>Pathfinder</title>
 <meta charset="UTF-8">
 <meta name="author" content="fj">
 
 <style type="text/css" media="screen,projection,print">
  body{
    font-family: Arial, Helvetica, sans-serif;
    margin: auto;
  }
  section{
    min-width:400px;
    padding:20px;
    margin: 10px auto 10px auto;
  }
  h1,p{
    text-align:center;
  }
  h1{
    color:#1f2839;
    font-size:2.5em;
    text-shadow: 6px 6px 2px #d0d0d0;
  }
  #gamearea {
    background:orange;
    font-size:1.8em;
    text-align:center;
    margin: auto;
    border-color: orange;
    box-shadow: 10px 10px 5px #d0d0d0;
  }
 </style>
</head>
<body onload="solver()">

 <section>
  <h1>Útkeresés A* algoritmussal</h1>
  
  <table id="gamearea" border="1"></table>
  
  <p>
  <input type="checkbox" id="checkdebug" checked="checked" onclick='{debugenabled=document.getElementById("checkdebug").checked;}'>Nyomkövetés |  Következő út: Kattintás egy sárga cellára
  <!--
  <input type="button" value="Solver" onclick="solver()">
  -->
  </p>
  
  <!-- Tesztadatok kiíratása
  <p id="test"></p>
  -->
 </section>
 
 <script>
  // ========== Globális változók
  var cellsize = 40;
  var nrow = 10;
  var ncell = 10;
  var cells  = new Array(nrow);
  var newrow;
  
  var wallcolor="green";
  var cellcolor="lightyellow";
  var startendcolor="orange";
  var waycolor="red";
  var start=null;
  var end=null;
  var debugenabled=false;
  
  // ========== GameArea celláinak feltöltése (DOM)
  for(var i=0;i<nrow;i++){
      newrow=document.getElementById("gamearea").insertRow(i);
      cells[i] = new Array(ncell);  // soronként új vektor, melynek elemei objektumok
      for(var j=0;j<ncell;j++){
        var cell = new Object();
        cell=newrow.insertCell(j);
        cell.id=i*ncell+j;
        cell.style.width=cellsize+"px";
        cell.style.height=cellsize+"px";
        cell.style.color="#ff3333"; // piros
		
        // === A* cellaleíró adatok deklarálása
        cell.f = 0;
        cell.g = 0;
        cell.h = 0;
        cell.visited = false;
        cell.iswall= false;
        cell.debug = "";
        cell.parent = null;
        cell.x = i;
        cell.y = j;
		
        // ========== Fal generálása véletlenszámmal
        if (Math.floor(Math.random()*nrow*ncell)<(nrow*ncell*0.25)){
            cell.style.background=wallcolor;
            cell.iswall= true;
        }
		
        // ========== Mozgási terület szinezése
        else {
            cell.style.background=cellcolor;
            cell.onclick=function(){mystep(this);};
			
            // === Teszteléshez start és end cellák kijelölése. =====
            if (start===null && (i*j)>(nrow*ncell*0.1)) {
                start=cell;
                start.innerHTML="A";
                start.style.background=startendcolor;
            }
            if (end===null && (i*j)>(nrow*ncell*0.6)) {
                end=cell;
                end.innerHTML="B";
                end.style.background=startendcolor;
            }
            // ======================================================
        }
        // === Tömbösítés;
        cells[i][j] = cell;
      }
  }
  function mystep(obj){
    // alert("(: Kattintást a mystep függvényben dolgozd fel :)");
    // === Régi Start-End pozíciók feliratának törlése
    start.innerHTML="";
    end.innerHTML="";
	
    // === Új Start-End pozíciók beállítása
    start=end;
    start.innerHTML="A";
    start.style.background=startendcolor;

    end=obj;
    end.innerHTML="B";
    end.style.background=startendcolor;
    solver();
  }
 
  function solver(){
    document.getElementById("checkdebug").checked=debugenabled;
    var myway=astar.search(cells,start,end);
    // alert("Utvonal kirajzolás");
    for(var i=0;i<myway.length;i++){
       if (myway[i]!=end) {myway[i].style.background=waycolor;}
    }
  }	
  
// === A* algoritmus ================================================

  var astar = {
      // === Cellaleíró elemek alapállapotba állítása
      init: function(cellgrid) {
        for(var x = 0; x < cellgrid.length; x++) {
            for(var y = 0; y < cellgrid[x].length; y++) {
                cellgrid[x][y].f = 0;
                cellgrid[x][y].g = 0;
                cellgrid[x][y].h = 0;
                cellgrid[x][y].visited = false;
                cellgrid[x][y].debug = "";
                cellgrid[x][y].parent = null;
                if (!cellgrid[x][y].iswall && cellgrid[x][y]!=start && cellgrid[x][y]!=end){
                   cellgrid[x][y].style.background=cellcolor;
                   cellgrid[x][y].innerHTML="";
                }
            }   
        }
      },
      // === Cellatávolságok számítása
      manhattan: function(pos0, pos1) {
        // See list of heuristics: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
        var d1 = Math.abs (pos1.x - pos0.x);
        var d2 = Math.abs (pos1.y - pos0.y);
        return d1 + d2;
      },
      // === Szomszéd cellák meghatározása
      neighbors: function(cellgrid, node) {
        var ret = [];
        var x = node.x;
        var y = node.y;
        // === Left Right Top Bottom
        if(cellgrid[x-1] && cellgrid[x-1][y]) {
          ret.push(cellgrid[x-1][y]);
        }
        if(cellgrid[x+1] && cellgrid[x+1][y]) {
           ret.push(cellgrid[x+1][y]);
        }
        if(cellgrid[x][y-1] && cellgrid[x][y-1]) {
           ret.push(cellgrid[x][y-1]);
        }
        if(cellgrid[x][y+1] && cellgrid[x][y+1]) {
           ret.push(cellgrid[x][y+1]);
        }
        return ret;
      },
	
      // === Útvonalkeresés !!! ===
      search: function(cellgrid, start, end, heuristic) {
        astar.init(cellgrid);
        heuristic = heuristic || astar.manhattan;
		
        var closedList   = [];  // === Vizsgált lista

        var openList   = [];    // === Várólista
        openList.push(start);   // === Kezdőpont felvétele a várólistára

        while(openList.length > 0) {
            // === Legkisebb F értékű várólistás elem keresése
            var minidx=0;
            for(var i=0;i<openList.length;i++){
               if (openList[i].f<openList[minidx].f) {minidx=i;}
		    }
            // === Legkisebb F értékű elem szomszédainak feltérképezése
            var currentNode = openList[minidx];
            // === Legkisebb F értékű várólistás elem felvétele a vizsgált listára
            closedList.push(openList[minidx]);
            openList.splice(minidx,1);

            var gScore = currentNode.g + 1;
			
            // === Célcella elérésekor útvonal átadása
            if(currentNode == end) {

                var curr = currentNode;
                var ret = [];
                while(curr!=start) {
                    //alert("OpenList:"+openList.length+", id:"+curr.id+", startid:"+start.id);
                    ret.push(curr);
                    curr = curr.parent;
                }
                return ret.reverse();
            }
			
            // === Szomszédos négyzetek begyűjtése
            var neighbors = astar.neighbors(cellgrid, currentNode);
            for(var i=0; i<neighbors.length;i++) {
                var neighbor = neighbors[i];
                if(closedList.indexOf(neighbor)>-1 || neighbor.iswall) {
                  continue;
                }
                neighbor.visited = true;
                neighbor.parent = currentNode;
                neighbor.h = heuristic({x:neighbor.x,y:neighbor.y},{x:end.x,y:end.y});
                neighbor.g = gScore;
                neighbor.f = neighbor.g + neighbor.h;
				
                // === Cellaadatok kiiratása
                if (debugenabled && neighbor!=start && neighbor!=end){
                   neighbor.debug = "<div style=\"font-size:8px;color:#1f2839;margin:0;\">"+"F: " + neighbor.f + "<br />G: " + neighbor.g + "<br />H: " + neighbor.h+"</div>";

                   document.getElementById(neighbor.id).innerHTML=neighbor.debug;
                }
				
                var pos = openList.indexOf(neighbor);
                if (pos<0){
                   openList.push(neighbor);
                }
                else {
                   if (openList[pos].g>gScore){
                      openList[pos].parent = currentNode;
                      openList[pos].g = gScore;
                      openList[pos].f = openList[pos].g+openList[pos].h;
                   }
                }
            }
            // Teszteléshez
            // document.getElementById('test').innerHTML+="<br>openList.length="+openList.length+", ";
        }

        // No result was found -- empty array signifies failure to find path
        alert("Nincs eredmény!");
        return [];
    }
  }
 </script>
<!-- ========================= Hivatkozások, felhasznált ötletek:
JavaScript
http://www.w3schools.com/jsref/met_table_insertrow.asp 
http://www.w3schools.com/js/js_htmldom_events.asp
http://stackoverflow.com/questions/4825295/javascript-onclick-to-get-the-id-of-the-clicked-button
http://mercator.elte.hu/~saman/hu/okt/tilitoli/ 

A* algoritmus
http://jatekfejlesztes.hu/page.php?&id=116 (+)
http://www.briangrinstead.com/files/astar/
http://www.briangrinstead.com/files/astar/astar.js
http://www.briangrinstead.com/files/astar/graph.js
http://www.briangrinstead.com/files/astar/demo.js
============================= -->
</body>
</html>

« Előző | Lap eleje

6	Oldd meg a feladatokat!

Kedves Bakonyi Bitfaragó Jelöltek!

Elérkeztünk az erőgyűjtés szakaszának a végéhez. Az itt szerzett ismereteket fogjátok majd alkalmazni az összemérés fordulójában. A következő erőpróbáig azonban még meg kellene oldani néhány izgalmas feladatot.

A karácsonyi online játékpiacon töretlen népszerűségnek örvendenek a labirintus és kirakós játékok. Reméljük az idén sem lesz ez másképp. Készítsétek el az alábbi játékprogramokat, és a biztos siker érdekében tűzdeljétek meg a felsorolt ötletekkel. A kódoláshoz bátran használjátok fel a most bemutatott programot is. Az igényes megoldásokkal értékes pontokat szerezhettek a versenyben, amivel ismét megerősíthetitek a megszerzett pozíciótokat.

Beküldhető feladatok:

Mike a Shanta Claus család reménysége titokban szeretné a karácsonyfa alá becsempészni az ajándékait, ám Steve Dark a Hacker klán legifjabb csemetéje változó intenzítással mindent elkövet, hogy ebben megakadályozza.
- Tervezzétek meg a játék labirintusát!
- Helyezzetek el valamelyik cellában egy virtuális karácsonyfát!
- Tegyétek pályára Mike-ot, és Steve-t!
- Az egér- vagy billentyű-eseményekkel irányítsátok Mike mozgását!
- A most megismert útkereső algoritmusra hagyatkozva indítsátok el Steve-t. Ne feledjétek, ő sztochasztikus intenzítással különböző irányba mozog.
- Nehezítsétek a pályát akadályok elhelyezésével!
- Kezeljétek le az esetleges ütközésket!
- Használjátok fel ez előző fordulóban megírt kattintás-számláló, óra és naplozó metódusokat!
1000 0000|₂ pont
A 8-as kirakójátéknak 9!/2=181 440 elérhető állapota van, és így a játék viszonylag könnyen megoldható. Valósítsátok meg a 8-as puzzle kirakását az A* algoritmus felhasználásával.
HELP Számoljátok ki a puzzle celláinak célállapothoz viszonyított F értékét minden egyes cellánál, majd összesítsétek a kapott értékeket. Tegyétek várakozási sorba az elmozdítható cellákat a következő állapotra kiszámított F értékekkel, ezután válasszátok ki a legkisebb F értékűt, és mozdítsátok el a játéksíkon. Ismételjétek a fenti műveleteket addig, amíg az aktuális F érték nem egyezik a célállapot értékével.
1000 0000|₂ pont

Lazításként oldjátok meg, majd töltsétek fel az alábbi gondolatébresztő feladatokat is. Lehet, hogy éppen az itt szerzett bitpoint-ok vezetnek el benneteket egyenesen a döntőig.

Beküldhető feladatok:

Az (x₁,y₁), (x₂,y₂),…,(x_n,y_n) valós értékpárok egy síkbeli, n csúcspontú konvex sokszög csúcspontjainak az óramutató járásával ellenkező irányú körüljárási sorrendben megadott koordinátái.
- Számítsátok ki a sokszög kerületét!
- Határozzátok meg a sokszög területét!
  Útmutató: Feltételezzük, hogy a sokszog az origot körbefogja. Az origót összekötve a csúcsokkal háromszögeket kapunk. Egy háromszög területét – ha az oldalakat a, b, c jelöli – a már megismert Heron képlettel számolhatjuk ki: T=Math.sqrt(s*(s-a)*(s-b)*(s-c)), ahol s=0,5*(a+b+c).
10 0000|₂ pont
Számítsátok ki egy szám négyzetgyökét Newton módszerrel. A beolvasott szám legyen A. X₁=A/2, X_n+1=(X_n+A/X_n)/2 ha n>=1. A számítást addig folytassátok, amíg |X_n+1-X_n|<0,0001. Az eredményt négy tizedes jeggyel jelenítsétek meg!
1 0000|₂ pont

« Előző | Lap eleje

3. A* algoritmus

Az algoritmus jellemzői

Hasznos leírások:

Hogyan alakítsuk ki a belső adatszerkezetet?

Hogyan működik az A* ?

Hasznos leírások:

Érdekel a mesterséges intelligencia?

Hasznos leírások:

Próbáld ki a megoldást!

Oldd meg a feladatokat!

Kedves Bakonyi Bitfaragó Jelöltek!

Beküldhető feladatok:

Beküldhető feladatok:

Hivatkozások, felhasznált források