Witam, mam następujący problem. Muszę znaleźć drogę z niebieskiego punktu do zielonego.

Nie zależy mi na najkrótszej, a na najszybszym sposobie. Zastanawiałem się nad przejrzeniem wszystkich kratek w obrębie niebieskiego punktu i sprawdzenie który jest najbliższy, później znowu wokól sprawdzić i znów najbliższy i tak dalej i dalej dopóki nie dojdzie, a jak siezablokuje (czyt. będzie musiał cofnąć się na kratkę), zaczac od początku wykreślając tamtą drogę.

Ma ktoś jakieś pomysły?

Jeśli to ma być najszybszy sposób, a nie najkrótsza droga, to zaproponuję Ci coś takiego (chyba w wojsku używa się podobnej metody do chodzenia po ciemku w labiryntach): kiedy tylko masz możliwość - skręcasz w prawo (tzn. idziesz ciągle dotykając wyciągniętą prawą ręką do ściany).
W ten sposób nawet jeśli nadrobisz 3 razy więcej drogi - na pewno przejdziesz przez możliwe ścieżki.

W tym wypadku może niekoniecznie jest to pomocne, bo np. punkt docelowy może nie przylegać do ściany, ale może jest to pomysł na jakiś prosty algorytm... (Sposób ma na celu znalezienie wyjścia z labiryntu)

Hmm, to będzie tak z 8000x8000 kratek mapka Może 4k, nie wiem. Można brać pod uwagę, że user kliknie i tak max 50 kratek od siebie. Dlatego potrzebuje szybkiego algorytmu, bo bedzie to musialobyc liczone w locie. Tzn. user klika na kratkę, ajaxem wysyłam prośbę o zwrot drogi i skrypt sobie tam idzie

Ja dodam, że w Tibi, program mając identycznie kratkowaną mapę, a dodatkowo wypisane prędkości pola potrafi obliczyć drogę najszybszą (czyli np. przez drogę a nie przez piasek)

Rekurencja z powrotami.

Liczysz każdy możliwy ruch, aż do momentu dojścia do wymaganego pola. Jeśli w którymś momencie się zatniesz [znaczy, wejdziesz w róg czy musiałbyś się cofnąć], robisz powrót i powtarzasz dla kolejnej pozycji.

Idziesz tak jak napisałeś. Jedynie gdy się zatnie i zauważysz, że się cofłeś (trzymasz historie zrobionych kroków) to się cofasz a miejsce z którego przyszłeś oznaczasz jako złe.

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

@up
Dzięki

Teraz w ramach dokształcania, udało mi się samemu (przed tym jak dr_bonzo podpowiedział) cosik skonstruować, tylko mam problem. Jak sprawdzic która kratka jest najbliżej celu podróży?
Załóżmy, że cel podóży to x: 7 y: 0 a ja chce porównać x:5 y:4 oraz x:4 y:5 Już nie mam siły Na 100% to banalne, a jednak nic nie przychodzi mi do głowy ;/

Banalnie proste!


PS Tak na poważnie: http://www.gamedev.pl/articles.php?x=view&id=254

Twierdzenie Pitagorasa obliczasz przeciwprostokątną, która będzie odległością między punktem docelowym, a danym punktem testowym. Wartości przyprostokątnych obliczysz w banalny sposób poprzez zwykłe odejmowanie od siebie współrzędnych X oraz Y obu punktów.

PS: aj, w sumie nie wiem czy się nie wygłupiłem mój sposób obliczy Ci odległość w linii prostej. Ale w sumie sprawdza "która kratka jest najbliżej celu podróży"

Na matmie nie miałeś układu współrzędnych ?
Najprościej kwestie mapy w grach browser-based rozwiązać właśnie układem współrzędnych.

~Phpion dzięki, tylko nie o to chodzilo. Raz jest x_celu>x a raz x_celu<x Tutaj normalna ifka i podzielenie tego jakby na ćwiartkę. Już się udało.

~Ayeo strokrotne dzięki, ładnie to gość opisał.

Samemu na razie poćwiczę :] jak nie wyjdzie przeczytam ten opis.

Wystarczyłoby wyciągnąć wartość bezwzględną z różnicy. No ale skoro i tak nie o to chodziło to nie ma tematu

Bardzo chciałbym wszystkim podziękować za pomoc, zwłaszcza ~ayeo za świetny opis. Dla mojego mózgu tyle wiedzy dużo znaczy.

PS. Tak, udało mi się:
http://hernass.pl/searchWay/

PS2. Nie nabijam postów, ten jest o czym innym i zresztą jak nabić posta w hydeparku?

<bardzo szczęśliwy> ^^

Ty, ale ten gość w tym artykule z gamedev to wszystko komplikuje, tak jakby to było mega trudne. A to jest zwykły BFS: http://pl.wikipedia.org/wiki/Przeszukiwanie_wszerz, którego można zapisać w paru linijkach:)

Artykuł tego gościa dla mnie był prostszy.



Miałem nie publikować, ale za udzieloną pomoc...
http://forum.php.pl/index.php?showtopic=107294