Mapa, wspolrzedne, obliczanie sciezki Opcje

[Revan]

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

Kod

|--1--|--2--|--3--|--4--|--5--|
1     |     |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
2     |     |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
3     |     |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
4     |     |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
5     |     |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|

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:

Kod

|--1--|--2--|--3--|--4--|--5--|
1     |     |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
2     |  p  |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
3     |     |  x  |  x  |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
4     |     |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
5     |     |     |  k  |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|

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.

[TomASS]

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

Kogo masz na myśli?

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].

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.

Algorytm do rozwiazania tego problemu jest prosty.

Dla jednych jest, dla innych nie....

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

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

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"

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.