Znajdowanie drogi

Witam
Potrzebuje rozwiazac nastepujacy problem:
Mam pewien obszar 10 na 10 podzielony na kwadraty. Chodzi o to aby znaleŹĆ droge z punktu A do B, ale wystepuja pewne utrudnienia:

• sa pewne pola przez ktore w drodze do punktu B musimy przejsc
• wystepuja rowniez przeszkody, czyli pola przez ktore nie mozna przejsc

Samo znalezienie drogi od A do B nie jest trudne. Natomiast problem napotkałem juz przy omijaniu przeszkody.
Moze ktos spotkał sie juz z takim lub chociaz podobnym problemem. Ogolnie byłbym wdzieczny za wszelkie podpowiedzi.

ma byc dowolna droga, czy najkrotsza?

Zakładam, że można przechodzić tylko z kwadratu na kwadrat. Jeżeli nie mamy ograniczenia, że ma to być najkrótsza, to można rozłożyć problem na przechodzenie pomiędzy polami na których musi stanąć.
Można do tego wykorzystać pierwszy z brzegu algorytm do wyszukiwania drogi w grafie dając dla pól, przez które nie można przejść, koszt dążący do nieskończoności.

Ale nie sądzę, by to było tak banalne. Napisz dokładnie jakie są ograniczenia.

Poruszac mozna sie tylko z kwadratu na kwadrat, po lini prostej ( nie mozna chodzic na skos). Powiedzmy na razie, ze szukamy dowolnej drogii, mozesz podac nazwe algorytmu ktory mazna by w takim przypadku zastosowac ?

Po co się tak rozwodzić...

Istnieje wiele metod znajdowania drogi (google -> pathfinding)
Najlepszym istniejącym algorytmem jest A* (czyt. 'a star') - uwzględnia przeszkody, można założyć mu karę np. za skręty dzięki czemu droga będzie prostsza, kary mogą też być za różne rejony planszy (np. wchodzenie pod górę) etc etc.

A* gwarantuje znalezienie optymalnej (czyli najlepszej wg zadanych kryteriów) drogi jeśli tylko jest jakakolwiek droga od A do B.

Jego implementację znajdziesz na setkach stron poprzez google.