Generowanie dróg / rzek na 2d mapie sieci

To pytanie dla początkujących, ale oto:

Moja mapa to siatka 2d i chcę generować drogi i rzeki. Trasa od punktu początkowego do końcowego nie może być optymalną drogą pod względem liczby płytek. Zamiast tego powinny mieć pewien poziom losowości (tury).

Czy istnieje standardowy algorytm dla tego rodzaju rzeczy?

Twoje zdrowie!

AKTUALIZACJA:

Jest to wynik zabawy z wagami na siatce i zastosowania algorytmu najkrótszej ścieżki (Bellman-Ford) przy użyciu biblioteki jgrapht. W końcu poszedłem z odpowiedzią Donutza.

http://pastebin.com/AGQGK5ik

Możesz wygenerować optymalną ścieżkę za pomocą A *, a następnie zniekształcić ją z przesunięciem punktu środkowego.

Zapewni to osiągnięcie punktów końcowych i pozwoli w dużym stopniu kontrolować losowość. Na przykład nie losowałbym dróg tak często jak rzek. Jakakolwiek inteligencja buduje drogi, zwykle stara się być optymalna.

Uważaj, aby upewnić się, że jeśli na mapie znajdują się przeszkody, po każdej iteracji sprawdzasz, czy nie przekraczasz tych przeszkód.

Inną metodą byłoby wygenerowanie szumu Perlina po znalezieniu optymalnej ścieżki, a następnie przesunięcie punktów w oparciu o wygenerowany hałas. Na przykład za pomocą tego hałasu:

Następnie pokaż z optymalną ścieżką na czerwono i przesuniętą ścieżką na niebiesko:

Zauważ, jak przesunięta ścieżka „osiadła” w ciemniejszych obszarach hałasu. W ten sam sposób rzeka może przepłynąć przez dolinę.

Jedną z zalet wyboru hałasu Perlin jest to, że możesz uwzględnić przeszkody i unikać ich w ramach algorytmu.

Algorytm A * pozwala również przypisywać wartości do kafelków, wskazując ich przydatność. Na przykład, możesz przypisać najniższe koszty do niskich gruntów dla rzek, do płaskich gruntów (ale nie bagien) dla dróg i generować na ich podstawie. Nie zapewnia to najkrótszej trasy, ale zapewnia najbardziej efektywną trasę. Zastosuj trochę losowości do swoich wartości kafelków, aby uzyskać kilka nieoptymalnych tras.

A kiedy wysokość jest czynnikiem? Mogę wykonać mapę wysokości z algorytmem kwadratu diamentowego. Myślałem o dodaniu losowej wody do każdego kafelka, a następnie iteracji i przemieszczaniu wody na niższe poziomy, aż wszystko się uspokoi, ale to spowolni i prawdopodobnie stworzy jeziora, a nie rzeki.

Zastanawiałem się też nad normami dla każdej płytki. Jeśli 2 normalne wskazują na siebie, to musi to być dolina. Woda zbierałaby się w dolinie. Jeśli skierują się w tym samym kierunku lub od siebie, woda nie zbierze się. Byłoby to prawdopodobnie szybsze niż metoda iteracji, ale może nie tworzyć jezior, tylko rzeki. Musiałbym się z tym bawić, aby nie zamieniać każdego przypadku płytek skierowanych ku sobie w rzekę.