Summary of the A* Method

Okay, now that you have gone through the explanation, let's lay out the step-by-step method all in one place:
Add the starting square to the open list.
Repeat the following:
a) Look for the lowest F cost square on the open list. We refer to this as the current square.
Switch it to the closed list.
c) For each of the 8 squares adjacent to this current square …
If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
If it isn't on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.
If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

d) Stop when you
Add the target square to the open list, in which case the path has been found, or
Fail to find the target square, and the open list is empty. In this case, there is no path.
Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.

Jo!
Mam taka mape, ktora jest podzielona na kwadraty:

Teraz, zalozmy ze chce przejsc z kwadratu 2,2 (p) do 4,5 (k) z tym ze pola oznaczone x sa nie do przejscia. Tak jak tu:

Pomyslalem zeby zrobic petle. Kazda iteracja petli to jeden ruch. Przewiduje mozliwosc na skos. No i w kazdej sytuacji najprostrza droga bedzie wlasnie na ukos. No i zeby tak przejsc musimy przejsc przez pola 2,3 , 3,3 , 3,4 i 4,4. Na poczatek zastanawiam sie czy w ogole jest to mozliwe do obliczenia przez php. No, ale dajmy na to ze tak. Pierwsza iteracja - sprawdzamy czy mozemy wejsc na pole 2,3. Jezeli tak - idziemy do drugiej iteracji, jezeli nie - sprawdzamy czy sasiednie pola (zaczynajac od tych najblizej punktu docelowego) sa puste. Jezeli mozna wejsc na jakies pole, wchodzimy na nie, konczymy petle i wchodzimy do nowej, gdzie nastepuje ponowne liczenie sciezki, ale juz od nowego pukntu.
Dobrze mysle, i czy da to sie wykonac? Potrafil bym napisac takie cos, ale nie uwzgledniajac chodzenia na skos. Prosze o jakies sugestie, jak to rozwiazac.

Widze, ze slabo znacie sie na algorytmach ;-).

Ktos wspominal algorytm Dijkstry. Tak - moznaby go w tym wypadku uzyc, ale nie ma takiej potrzeby. Dijkstry uzywa sie w przypadku kiedy odleglosci miedzy polami bylyby rozne [wagi krawedzi w grafie o roznych wartosciach].

Algorytm do rozwiazania tego problemu jest prosty.

Implementujesz sobie prosta kolejke FIFO do przechowywania pol [czyli wartosci X i Y]. Nastepnie wsadzasz na stos pole startowe i robisz tak:
1. kolejka jest pusta? -> nie znaleziono drogi, koncz dzialanie skryptu
2. pobierz z kolejki pole P, zaznacz jako przegladniete
3. jesli pole P jest polem koncowym -> znaleziono droge
3. sprawdz kazde pole sasiednie pola P [czyli pola na ktore mozna przejsc] -> jesli nie sa odwiedzone i nie sa oznaczone jako X to wsadz je do kolejki, dla kazdego wsadzanego R pola ustaw jako poprzednik jako P

Jest to algorytm przeszukiwania wszerz.
Zlozonosc tego algorytmu to O(N+8N)=O(N), gdzie N to liczba pol na szachownicy.
W momencie dojscia do pola koncowego aby wyznaczyc sciezke po ktorej nalezy sie poruszac robimy to cofajac sie po poprzednikach. Jest to dosc ogolnie opisany algorytm wiec jak masz jakies pytania to pisz, ew. szukaj na googlach "przeszukiwanie grafu wszerz"

Kogo masz na myśli?

A kto Ci takich bajek naopowiadał? Niby czemu tutaj go nie można użyć. Fakt, że nie jest zbyt wydajny, ale jest JEDNYM Z MOŻLIWYCH rozwiązań i w sieci można znaleźć bardzo wiele publikaci na jego temat.

Dla jednych jest, dla innych nie....


Dobre, też dobre rozwiązanie, można by nawet powiedzieć, że najlepsze....



No nie koniecznie wszerz, można też wstecz....

Ogólnie, zgadzam się z kolegą Radkiem - poczytaj o grafach, to naprawde poteżne narzędzie i na pewno Ci się przyda w tej sytuacji.