Forum PHP.pl

Witam, mam mały problem.

Załóżmy, że mamy mape 9x9 pól.

- 1 2 3 4 5 6 7 8 9
1 1 0 1 1 1 0 1 1 1
2 1 0 0 0 0 0 1 1 1
3 1 0 1 1 1 0 1 1 1
4 1 0 0 0 0 0 1 1 1
5 1 0 1 1 1 0 0 0 1
6 1 0 0 0 0 0 1 1 1
7 1 0 1 1 1 0 1 1 1
8 1 0 1 1 1 0 1 1 1
9 1 0 0 0 0 0 0 0 0

1 - to pole zablokowane
0 - pole po którym możemy się poruszac.

Jak napsiać skrypt, który wyznacz mi najkrótsza trasę do pola 8x5. Jakieś pomysły?

http://en.wikipedia.org/wiki/A*_search_algorithm

Myślę, że najlepiej się sprawdzi tutaj "zalewanie wodą": http://pl.wikipedia.org/wiki/Algorytm_Bellmana-Forda
, czy lepiej wyjaśnione: http://www.forbot.pl/forum/topics20/microm...yntu-vt2246.htm -> METODA PROPAGACJI FALI (uproszczony algorytm BELLMANA-FORDA)

Ten post edytował kamil4u 30.04.2013, 17:28:38

Ja podzieliłbym na kratki to wszystko (jak w krzyżówkach - 1 litera - 1 kratka).

[PHP] pobierz, plaintext 
while(1){ 
    if(można_skręcić_w_prawo)             //* 
        skrec_w_prawo();                  //* 
    else if(można_jechać_prosto) 
        ;   // nie rób nic 
    else if(można_skręcić_w_lewo)        //** 
        skrec_w_lewo();                  //** 
    else 
        zawróć(); 
jedz_jeden_segment_do_przodu(); 
}
[PHP] pobierz, plaintext 

Coś takiego.

@Dominator Jest szansa, że nigdy nie dojdziesz do wyznaczonego pola

Wiem o tym, algorytm ten trzeba lekko zmodyfikować (IMG:style_emoticons/default/smile.gif)

Dominator ładnie kopiujesz algorytmy (IMG:style_emoticons/default/smile.gif)

Taki skrypcik to już mam zapisany, i niestety nie zawsze dochodzę do miejsca... dlatego szukam nowego rozwiązania.
Próbuje strawić algrytm nr jeden, opornie mi to idzie, ale spróbuje go przetworzyć.