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.

[nospor]

Kiedyś uyżywalme takiego algorytmu (nie pamiętam jak się nazwyal):

Zaczynasz od punktu koncowego.Każdemu polu do któego możesz wejśc bezposrednio z punktu koncowego przypisujesz wartość 1. Następnie każdemu polu, do którego możesz wejści z pol oznaczonych jako 1, przypisujesz wartośc 1, a tamtym polom zwiekszasz wartośc na dwa. Teraz znowu wszyskim polom do których możesz wejsc z 1 przypisujesz wartośc 1, a pozostalym zwiekszasz o 1 (czyli 1 na 2, 2 na 3). robisz tak, aż natrafisz na pole poczatkowe. Teraz masz juz wyznaczoną najkrótrzą drogę. Z punktu początkowego przeskakujesz na pole o wartości 1, stamtąd na pole o wartości 2, z 2 na 3 itd az wejdziesz na koncowe.

POzdro

w efekcie koncowym powininien otrzymać taki uklad:

Kod

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

troche zamalo kratek mi sie uzupelnilo, ale mniej wiecej tak to powinno wygladac na koniec iteracji

Ten post edytował nospor 27.05.2005, 11:35:33