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]

Tja.... Djkikstry.....

Wg. mnie sposób zaproponowany przez kolegę Revana nie jest za dobry. A co bedzie, gdy po przeliczeniu całej mapy okaże się, że kwadrat jest niedostępny od danej strony? Że prościej byloby na około? Ale to miały być konstruktywne wnioski....(IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

A więc:

1. Spróbuj trzymać odległości w tzw. macierzy sąsiedztwa albo w liście sąsiedztwa
2. Do przeliczenia najkrótszej odległości użyj, zgodnie z zaleceniami kolegi matysa, algorymu Djikstry, ale to też zależy ile masz tych 'kwadratów', miast, punktów, wieszchołków.....(czy jak to nazywać). Jeśli masz bardzo dużo punktów (powiedzmy 10000 - czas wykonywania algorytmu Djiksrty jest rzędu O(m log n)) to najlepiej użyć jednego z algorytmów genetycznych. Ale jeśli tych punktów jest niewiele, to zamiast algorytmu Dikstry najlepiej użyć algorymu Floyda. W internecie jest dużo publikacji na ten temat.


Pozdrawiam serdecznie i mam nadziej, że pomogłem