Sprinkfield pálya nehézség

Posted by | · · · · | Cégélet · Webstar Works | Nincs hozzászólás a(z) Sprinkfield pálya nehézség bejegyzéshez

Arról már írtunk, hogy egy pályán megkeresni a legjobb megoldást nem egyszerű feladat. Miután kiderült, hogy meg tudunk oldani egy pályát automatizálva is és el tudjuk róla dönteni, hogy megoldható-e, felmerült bennünk az igény, hogy generáljunk pályákat egy program segítségével. A pálya generálása több paraméter alapján történik, a pálya nagysága, a kövek, a száraz és trágyázott területek száma, a pálya nehézsége stb.
A pálya nehézsége kapcsán, első lépésként összeállítottunk egy képletet, de a béta tesztelés során kiderült, hogy a képletünk nem elég pontos, ezért átalakítottuk. Ebben a posztban bemutatom, hogy mi volt a tapasztaltunk a béta tesztelés során a nehézséggel kapcsolatban, illetve hogyan változott meg a képlet.

nehezseg-3

Mitől nehéz egy pálya ?

Erre a szubjektív kérdésre csak a saját játékélményünk alapján tudunk válaszolni. Szedjük össze mégis azokat az objektív szempontokat, amik  fontosnak lehetnek a  játék nehézség szempontjából.

  • Ha sok lehetséges kezdő lépés van egy pályán, akkor kisebb az esélye, hogy jó lépéssel kezdünk.
  • Minél több lépésből áll a megoldás (locsolók száma), annál nehezebb megtalálni a megoldást.
  • Azt is megfigyeltük, hogy a megoldás nagyon nehézzé válik, ha a megoldásnak nem része a pályán letehető legnagyobb lépés. (A játékosok szeretik kitölteni a teret, szeretik lerakni a legnagyobb lépést.)
  • Azt is nehezítő tényezőnek éreztük, hogy egy mezőt hány lépés érinthet. Ha sok lépés tehető le egy pályán, akkor sok a variáció (a pályának ilyen leképzését hívjuk histogramnak)

Minél kisebb értéket adott ez a képlet, annál nehezebb volt a pálya. Kód szinten ez így nézett ki:

(4.0 * moves.size()) / (1.0 * bestKnownSolution.size() *
(1 + largestPossibleMove - largestMadeMove) * histogram);

Béta teszt

Egy pálya nehézségére jó mérőszám még a pályán eltöltött idő. A tesztelés során erre a következő eredményeket kaptuk:

difficulity

Az x tengelyen a pályák találhatók (1-20 a puzzle mód ingyenes pályái), y tengelyen a pályán eltöltött idők másodpercben (a színek a különböző tesztelők).

Látszik, hogy voltak olyan tesztelők, akik már a négyes pályán elakadtak, azután a 12-13 pálya okozott fenn akadást, és a végén az utolsó pályák. A végső pályákat nehézre szerettük volna, ami sikerült is, de kicsit túlzásba estünk.
Több tanulság is volt a nehézséggel kapcsolatban:

  • emberenként változik a pálya nehézség
  • véletlenen is múlik, ha a játékos beragad egy rossz kezdésbe (mintába) akkor nagyon nehezen tud abból kilépni

A béta teszt tanulságai alapján az első 20 pályát átalakítottuk.

Új verzió, új pályákkal

Szerettünk volna kiadni egy frissítést a játékhoz, egy új “easy” pálya csomaggal, de a régi képletünk nem volt megfelelő arra, hogy egyformán könnyű pályákat generáljunk.
Szinte lehetetlen volt súlyozni a különböző paramétereket, és bővíteni sem tudtuk a képletet, így hát újra gondoltuk. Olyan képletet találtunk ki, ahol 1 és 100 közé esik a nehézség (minél nehezebb egy pálya, annál nagyobb ez a szám), a képlet bővíthető és az egyes paraméterek súlyozását is könnyen állíthatjuk.
Minden paraméternél meghatároztunk egy alsó és felső határértéket, így a végső számot 0 és 1 közé tudtuk szorítani.
nehezseg-2
Azt gondoljuk, hogy a következő paraméterektől függ a nehézség:

  • a locsolók száma (azaz a legkevesebb lépés, amiből van megoldása a pályának)
  • nem izolált területre eső madárijesztők száma, plusz hány lépésben tettük le az összes disznót, plusz hány madárijesztőnek van maximum 1 oldal szomszédja, ami nem léphető terület (azaz köves vagy pálya széle)
  • a megoldás minden lépésénél megvizsgáljuk, hogy az adott pontban a letehető legnagyobb lépéshez képest mekkora lépést tettünk le (a legnagyobb különbséggel számolunk)
  • az alapterület (ez általában a földes terület) típusától eltérő területlapok száma, azaz minél több objektum (kő, száraz terület stb…) van egy pályán annál nehezebb
  • a legjobb megoldást a megoldó a gráfban hány visszalépés után találja meg, mivel a megoldó “okosan” oldja meg a pályákat így a sok visszalépés nehezebb pályára utal
  • megoldások száma – ez kiemelt paraméter, minden egyéb felett áll

Kódrészlet a képletről:

final double solutionLengthScore = (Math.max(2.0, Math.min(10.0, bestKnownSolution.moves.size())) - 2) / 8.0;
final double freeScarecrowScore = (Math.min(11.0, 1.0 * (scarecrows - isolatedAreas) + pigMoves + cornerScarecrows)) / 11.0;
final double moveSizeDifferenceScore = (Math.min(3.0, 1.0 * largestMoveDifference)) / 3.0;
final double areaScore = (Math.max(3.0, Math.min(10.0, rocks + groundArea + dryArea + pigFreeWater - Math.max(Math.max(Math.max(rocks, groundArea), dryArea), pigFreeWater))) - 3) / 7.0;
final double backtrackScore = -1/(0.032 * (nodes - bestKnownSolution.moves.size()) + 1) + 1;

final double solutionCountScore = 9.0 / (1.0 * numberOfSolutions + 8.0);

return (
 (0.3 * solutionLengthScore + 0.25 * freeScarecrowScore + 0.125 * moveSizeDifferenceScore + 0.175 * areaScore + 0.15 * backtrackScore)
* Math.pow(solutionCountScore, 0.25) ) * 100.0;

Eddigi tapasztalataink pozitívak, a paraméterek súlyozásán kellett csak állítanunk.


No Comments

Leave a comment