Algorytm A*

Kiedyś postawiono pewien problem. Jak odnaleźć najlepszą drogę z punktu A do punktu B? W taki sposób powstał algorytm A*, czyli algorytm wyszukujący najlepsze możliwe rozwiązanie. To była absolutna rewolucja. Zaczęły wychodzić gry w których postacie same wyszukiwały drogę z punktu w którym są do wyznaczonego i same ją pokonywały. Jest to absolutna klasyka informatyki.

Algorytm szuka pól. One są odpowiednio oznaczone. Są pola wolne i zajęte. Algorytm omija pola zajęte i wybiera najbardziej optymalne pola wolne. Jak np. idziemy ulicą i na parkingu stoi samochód to omijamy go idąc parę metrów od samochodów. Jest to optymalne rozwiązanie. Nieoptymalne rozwiązanie to ominięcie samochodu mijając go np. paręset metrów.

W implementacji używa się tablic, które mają odpowiednie oznaczenia liczbowe. 0 w tablicy może oznaczać wolne pole, 1 zajęte. Algorytm przeszukuje wszystkie 0 i dobiera odpowiednią trasę. Trzeba wziąć to pod uwagę, że tablica może zmieniać się w czasie.