Wyznaczanie najkrótszej drogi poruszając się odcinkami

Witam szukam odpowiedniego algorytmu do mojego problemu.
Mam mapę w stylu:

Czerwona kropka to gracz który chce się dostać do punktu zielonego.
Białe kratki to pola po których można chodzić, brązowe pola to przeszkody na które nie można wejść. Przeszkód na mapie jest niewiele ok 10% brązowych kratek w stosunku do białych. Odcinek nie może się przecinać z brązową kratką.
Mapa ma bardzo dużą granulację tzn. każdy "kafelek" ma 32x32 piksele a gracz może poruszać się z dokładnością co do piksela z tym, że odcinkami o promieniu dajmy na to 20 pikseli w każdym kierunku (pierwszy krok można zrobić na dowolny pkt. pokazanego okręgu) fioletowe pkt. to miejsca w których jest zrobiony krok w stronę "mety" (długość ostatniego odcinka może być krótsza).

Szukam algorytmu, który może nie wytyczy mi idealnej najkrótszej drogi, ale zależy mi na szybkości jej wyznaczenia no i przede wszystkim aby gracz dotarł do wyznaczonego punktu. Jakby tego było mało po każdym kroku pkt. docelowy może okazjonalnie zmienić swoją pozycję też o jakiś odcinek. Nie mam pojęcia jak do tego podejść, które algorytmy wykluczyć od razu a które wziąć pod uwagę. Jeśli ktoś ma jakieś doświadczenie z tego typu problemami będę wdzięczny za każdą wskazówkę.

W tym przypadku proponuje A* z prostą herustyką bazującą na kierunku w którym powinieneś iść.
http://upload.wikimedia.org/wikipedia/commons/8/85/Weighted_A_star_with_eps_5.gif
Tu masz gifa który pokazuje jak to będzie wyglądać.

Możesz też liczyć zwykłego Dijkstrę albo BFSa, ale będzie wolniej (chociaż wtedy masz pewność że ruch jest optymalny, w przypadku A* niekoniecznie, chociaż zwykle tak).

Ale jeśli chodzi o to że cel moze się przemieszczać to możesz po każdym kroku puszczać pełną A*/Dijkstrę, wtedy masz pewność że zachłannie poruszasz się najlepiej jak się da w każdym kroku, ale to znów jest kosztowne. Oczywiście nowe obliczanie trasy warto puszczać tylko jeśli cel zmienił położenie ;)
Alternatywnie możesz po zmianie położenia przez cel policzyć tylko odcinek trasy pomiędzy starym położeniem celu a nowym położeniem i zastosować prostą kompresję ścieżki (tzn sprawdzić czy czasem cel nie przesunął się na któreś pole które już było wcześniej na trasie ;) )

Oświeciło mnie w międzyczasie i wpadłem na pomysł, że może rozłożyć etap poszukiwania ścieżki na wytyczenie jej najpierw na tych dużych kafelkach i później uszczegóławiać drogę celując kątem pod jakim ma być zrobiony krok aby dojść do celu tylko boje się że postać będzie się poruszać jak pijana "wężykiem".
Ten A* wygląda fajnie bo od razu kieruje się w miejsce optymalne, przy dijkstrze za bardzo rozchodzi się to jakoś na boki. Po twoim nakierowaniu na A* trafiłem jeszcze na to http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/ co wydaje się pasować do mojego problemu i to chyba jakaś odmiana A* sądząc po obrazkach, ale przeczytanie tego zostawię sobie na jutro.
Zastanawiam się też nad sposobem łączenia wierzchołków wytyczonej wcześniej trasy tymi odcinkami bo "połowy" odcinka od tak sobie zrobić nie mogę niestety, ale to wydaje się mniejszym problemem.
Cel porusza się tak średnio 3 kroki na moje 10 i to w randomowych kierunkach (za daleko od pierwotnego położenia nie ucieknie) więc chyba tak jak piszesz przed końcowymi kilkoma krokami będę sprawdzał ponownie zamiast za każdym razem a ile to już doświadczalnie dobiorę w ostateczności postać mogła by dochodzić do starego miejsca i szukać celu ponownie, ale to wygląda sztucznie.