Soko pálya editor?

Kell írni egy "solvert" a játékodhoz, ami mindenképpen megtalálja a megoldást, ha létezik. Ha nem túl bonyolult a játékod, akkor ez akár egy egyszerü gráfkeresés is lehet:

A gráf csúcsai a játék pillanatnyi állapota: hol vannak a dobozok, hol áll a karakter, ilyesmik.

A gráf élei inputok az usertöl.

Egy példa:

- tegyük fel, hogy a játékod egy 3x3-as mapon játszódik, ahol van egy játékos karakter, egy doboz, meg egy cél, ahova a dobozt be kell juttatni.

Ekkor a játék pillanatnyi állapota leírható három koordinátapárral:

- Játékos(x,y)

- Doboz (x,y)

- Cél (x,y)

Ebböl az állapotból 4 él vezet(a 4 irány):

Minden él abba a gráfcsúcsba vezet, ami azt az állapotot írja le, amibe a játék kerül, ha az user megnyomja az adott gombot.

A kezdö állapot legyen ez (0,0 a bal felsö sarok, lefelé és jobbra vannak a pozitív koordináták):

- J(0,0), D(1,1), C(2,2)

A gombok pedig a w,a,s,d

- J(0,0), D(1,1), C(2,2) * w -> J(0,0), D(1,1), C(2,2) (nem történik semmi, hisz fent állunk, nem tudunk feljebb menni)

- J(0,0), D(1,1), C(2,2) * a -> J(0,0), D(1,1), C(2,2) (nem történik semmi, hisz nem tudunk balra menni menni)

- J(0,0), D(1,1), C(2,2) * s -> J(0,1), D(1,1), C(2,2) (a játékos egy mezövel lejjeb ment)

- J(0,0), D(1,1), C(2,2) * d -> J(1,0), D(1,1), C(2,2) (a játékos egy mezövel jobbra ment)

Egy ilyen gráfon kell keresgélned. Elindulsz a kezdö állapotból(ahogy a pálya kinéz a játék elején) és addig keresel a gráfban, amíg

a) Nem találsz egy olyan állapotot, amivel a játékos megnyeri a játékot(a fenti példában ez akkor lenne, ha a doboz és a cél koordinátái megegyeznek). Ekkor a pálya megoldható

b) Kimeríted az összes állapotot anélkül, hogy találtál volna nyerö állapotot(ilyenkor a pálya nem megoldható)