Autor Zpráva
KryVosa
Profil *
Mám jednoduchou mapu:
[0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ],
[0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ],
[0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ],
[0 ,0 ,0 ,0 ,-1,0 ,0 ,0 ,0 ],
[0 ,0 ,0 ,2 ,a ,0 ,0 ,1 ,0 ],
[0 ,0 ,0 ,0 ,0 ,1 ,1 ,0 ,0 ],
[0 ,0 ,0 ,0 ,2 ,0 ,0 ,0 ,0 ],
[0 ,0 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ],
[0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ]
"a" jste vy, nuly obyčejná políčka a ostatní čísla překážky. Ze začátku máte rychost 4. Můžete se pohnout na jakékoli políčko, které s vámi sousedí, ale ubere vám to jednu "rychlost", plus vám to ubere tolik "rychlosti", jaké je na políčku číslo. Výjimku tvoří číslo "-1", které znamená políčko, na které se nedá stoupnout. Na konci pohybu vám může zbýt jakékoliv množství "rychlosti". Jak zjistit, kam všude se můžete pohnout? Děkuju moc za všechny rozumné nápady, pokud máte nějaké dotazy, rád si pomůžu :)
Keeehi
Profil
Nezapadá mě nic jiného, než bruteforce.
F = nová fronta
Přidej a do fronty
While (fronta F není prázdná)
    P = vyjmi jedno pole z fronty
    // u všech polí si pamatujeme kolik bylo nejvíc energie, když jsme na něm byli, na začátku mají všechny nulu
    Projdi všechny sousedy S políčka P
        Když mám dost energie, abych se na policko přesunul
            Označím si políčko jako navštívené
            Když by mi po přesunu na políčko zbylo více energie než co si pro něj pamatují
                Zapamatuji si toto nové množství
                Přidám políčko do fronty
Snad jsem na nic nezapomněl.
KryVosa
Profil *
Děkuji moc, tedy pokud jsem to pochopil správně :)
Jen drobná otázka: "BruteForce"?
Keeehi
Profil
bruteforce je zkoušení všech možných řešení. To tedy v tomto případě není ono ale to je detail. Spíše jsem měl asi napsat naivní řešení nebo simulace možných tahů.

Myslím že to co jsem popsal je něco na způsob BFS. Je tam jen lehká optimalizace. Určitě by se dalo i něco na způsob DFS.


Jsou to ale spíš jen nástřely, žádnou hlubší analýzu jsem neprováděl.

Ta rychlost je na začátku vždy 4, nebo je to obecné N a může být vyšší i nižší?
juriad
Profil
Keeehi:
Ono optimální řešení spočívá v použití Dijkstrova algoritmu.

KryVosa:
Je ta mapa konečná? Jak se má postava chovat u kraje?
Keeehi
Profil
juriad:
Při použití prioritní fronty vlastně o Dijkstru půjde.

Kraje si asi můžeš představit jako by celá ta matice byla po obvodu rozšířená o samé -1
A kdyby ta mapa byla nekonečná, vždy ji můžeš omezit na čtverec o hraně rychlost*2+1 se startovním bodem uprostřed.
KryVosa
Profil *
Keeehi: Ano, rychlost se pak ve hře bude dát ovlivňovat npř. kouzly :)
Juriad: Mapa je konečná a předem definovaná, okraj se překročit nedá, překážky mohou být větší než jen "dvojkové";
Našel jsem si Dijkstrův algoritmus (Píšu to správně, že jo?) na netu, ale moc jsem to nepochopil.. Zkuste mi to prosím nějak načrtnout.
Keeehi
Profil
Dijkstra je algoritmus pro hledání nejkratších cest v grafu, to znamená, jak se co nejlevněji dostat z bodů a někam. Většinou se Dijkstra používá pro nalezení nejkratší cesty mezi dvěma body, ovšem při svém běhu zároveň spočítá nejkratší cesty do všech uzlů které navštíví.

Ona se ta tvoje úloha dá přeformulovat, aby to více odpovídalo hledání nejkratších cest.
Každé políčko je uzel. Dva uzly mají mezi sebou hranu, pokud se tam dá jedním tahem přesunout (jsou to sousední políčka). No a na takovémto grafu hledáš cesty délky menší než N (4). S tímto omezením už to není typický Dijkstra ale upravená verze.
Ještě jsem zapomněl napsat, že všechny hrany mají váhu 1 a do délky cesty se samozřejmě započítává i hodnota v cílovém uzlu.

Na pochopení Dijkstra jsou výborné animace nebo vysvětlující videa na YouTube.
juriad
Profil
KryVosa:
Pak by bylo dobré okraj mapy vyplnit -1, aby se nemusely testovat podmínky podle polohy.
A dobré by bylo změnit -1 na nějaké vysoké číslo, třeba 10000000, to pak znamená, že energie (budu ji používat místo rychlosti) potřebná na vstup do takového políčka je vyšší než energie, kterou hráč kdy může mít. Konstantu je nutné zvolit dostatečně velkou.
Všechna čísla na mapě by měla být alespoň 1 (abys tam neměl ten nesmysl s extra jedničkou) a hodnota měla opravdu význam ceny za vstup.
V mapě nebude vyznačená počáteční pozice, to bude další parametr funkce.

Dijkstrův algoritmus v podstatě ukládá políčka do fronty, kterou průběžně zpracovává.
Na začátky máš mapu prázdnou - všude jsou třeba -1. Protože 0 má význam, že se na dané pole hráč může dostat a zbyde mi 0 energie, musí být předvyplněná zápornými čísly.

Proměnné:
map // mapa světa s cenami za přechod na určitá políčka
e // prázdná mapa - bude obsahovat dosažitelná políčka
q // prázdná fronta
start_p // počáteční pozice
start_energy // počáteční energie

Nová podoba map (9 značí vysoké číslo, použil jsem zde pro přehlednost; ty použíješ něco v řádů miliard):
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
[9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9], 
[9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9], 
[9, 1, 1, 2, 1, 1, 1, 1, 1, 1, 9], 
[9, 1, 1, 1, 1, 9, 1, 1, 1, 1, 9], 
[9, 1, 1, 1, 3, 1, 1, 1, 2, 1, 9],
[9, 1, 1, 1, 1, 1, 2, 2, 1, 1, 9], 
[9, 1, 1, 1, 1, 3, 1, 1, 1, 1, 9], 
[9, 1, 1, 1, 1, 1, 1, 2, 1, 1, 9], 
[9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9],
[9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]]

1) Do fronty si uložíš počáteční pozici p a v mapě uložíš na pozici p počáteční energii.
q.add(start_p, start_energy);
e.update(start_p, start_energy);
2) Dokud je něco ve frontě:
while (!q.isEmpty())
3) > Odeber pozici z fronty do proměnné p
  var p = q.remove_largest();
4) > Podívej se postupně na sousedy -> s:
  var ss = map.neighbours(p);
  for (var i = 0; i < ss.length; i++)
    s = ss[i];
5) > > Pokud energie na mapě je menší než energie, se kterou jsi schopný se do něj dostat:
    var energy = e.get(p) - map.get(s);
    if (energy > e.get(s))
6) > > > Aktualizuj mapu energií
      e.update(s, energy)
8) > > > Přidej souseda s do fronty se zadanou energií (pokud už je, tak ho upraví)
      q.add(s, energy)

Výstupem je mapa e. Zajímají tě pozice, které jsou >= 0. Číslo značí zbytkovou energii.

Algoritmus funguje s libovolnou frontou, ale nejlépe s takovou, která vrací pozice s maximální energií. Tato fronta se implementuje různě, ale v tvém případě o výkon moc nejde, takže obyčejná binární halda v poli postačí.
KryVosa
Profil *
Děkuju moc, funguje bez problému. Ukazovat vám to naneštěstí nemůžu, protože to mám optimalizované zatím jen pro webkity. Zatím jsem nenašel chybu.

Jen pro informaci: Mapa doopravdy sestává z čísel značící "typ" políčka, neboli jeho obrázek, takže naštěstí nemusím předělávat desítky map, ale jen jedno pole :)

Vaše odpověď

Mohlo by se hodit

Neumíte-li správně určit příčinu chyby, vkládejte odkazy na živé ukázky.
Užíváte-li nějakou cizí knihovnu, ukažte odpovídajícím, kde jste ji vzali.

Užitečné odkazy:

Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: