Wybór algorytmu najkrótszej ścieżki Opcje

[SlimShady]

Hej, od pewnego czasu wertuje strony gugla w poszukiwaniu ciekawego algorytmu na odnajdywanie najkrótszej ścieżki w "grafie". Mój przysłowiowy graf jest dość nie typowy, ponieważ nie ma w nim czegoś takiego jak długość krawędzi, bowiem jest ona stała dla każdego elementu, a więc i ich wynik nie ma znaczenia. Również możliwość poruszania się "po skosach" jest mi zbędna, a więc algorytmy takie jak dijkstra czy a-star skreśliłem po krótkim czasie namysłu. Może dla uzmysłowienia mojego "grafu" przedstawie jego techniczny wygląd: http://imageshack.us/a/img18/551/howalgo.png
ma on posłużyć jako prosta mapa 2D, w której za pomocą kliknięcia przechodzimy na następne pola tej mapy. wielkość pól mapy (krawędzi "grafu") jest stała - jak już wspomniałem - a także skosy są nie potrzebne. jak widać na obrazku, celem algorytmu ma być dostanie się z punktu A do punktu B najszybszą ściężką (polami) zważając przy tym na zaistniałe przeszkody (tak, to te ciemne czerwone kwadraciki). uznałem dijkstrę za zbyt przesadną, nie potrzebuję kombajna tylko ekonomicznej kosiarki, która błyskawicznie obliczy mi ścieżke bez innych bajerów. natrafiłem na dość dużo informacji o przeróżnych algorytmach z implementacjami do PHP, jednak jest ich tyle, a moje pojęcie na temat grafów (i matematyki) nie budzi podziwu, więc potrzebuję solidnej porady, który z algo okaże się dla mnie najlepszy? liczę na Wasze ciepłe sugestię i refleksję dotyczące każdej z metod ; ]
pozdrawiam, Shady.

Powód edycji: [Spawnm]:

[Pawel_W]

w tym temacie był poruszany identyczny problem http://forum.php.pl/index.php?showtopic=107294&hl= jak poszukasz w dalszych postach to była wersja bez chodzenia po skosie

[SlimShady]

dzięki, jednak przeglądałem ten wątek już dawno temu i przedstawiony tam algorytm nie jest mi na rękę, poza tym jego wykonanie nie wydaje się być najlepsze, a ja szukam łatwego, a wydajnego "wzorca", który sam mógłbym zaimplementować. myślałem nad takimi algorytmami jak Bellmana-Forda, Floyda-Warshalla, Johnsona, czy nawet użycia algo przeszukiwania wszerz. jednak nie mam pojęcia, który z nich będzie najodpowiedniejszy dla mojego celu, a jego stworzenie ogarnę sam. jakieś inne sugestię osób mocno w temacie grafów?

boli mnie, że odkąd śledzę tę forum - a robię to już dość długo - to gdy są pytania od osób początkujących w odpowiedziach znajdują się: było.., poszukaj.., banalne.. a gdy ktoś zada pytanie na innym poziomie to nikt nic nie napiszę


@refresh..

[Spawnm]

Z tego co piszesz wynika że na forum nikt od kilku lat nie dostał pomocy

Skoro jest to macierz to puść pętlę która sprawdza wszystkie pola stykające się z A, każde pole na które da się wejść(nie przeszkoda) dajesz ten sam algorytm sprawdzania wszystkich stykających się pól, aż dojdziesz do celu. Ten wektor który jako pierwszy natrafi na punkt B jest najkrótszą drogą.

Łatwiej już się chyba nie da.

[kamil4u]

Polecam: http://en.wikipedia.org/wiki/Flood_fill

To podobne rozwiązanie co podał Spawnm - opisane i nazwane.

[SlimShady]

oo, dziękuje Panowie, a jednak doczekałem się odpowiedzi
pewnego dnia - gdy mój mózg wykazał się niecodzienną ambicją twórczą - wykombinowałem coś podobnego i napisałem od zera algorytm, który wyszukiwał mi ścieżkę, jednak miał problemy, gdy "zakrętów" było więcej.
mam wątpliwości, czy aby flood fill nie zajechał mojego serwera, ale przyjrzę się mu i może na jego podstawię zrozumię i 'opatentuje' coś własnego, wydajniejszego