Mam pewien problem, z którym nie potrafię sobie poradzić. Chcę wygenerować losowo mapę galaktyki (przykład z takich gier jak Endless Space czy FreeOrion) tylko nie wiem jak się za to zabrać. Na mapie mają być punkty (gwiazdy) połączone ze sobą ścieżkami. Graficznie wiem jak to zrobić za pomocą canvas, rysuję z tablicy kolejne punkty następnie nanoszę połączenia na mapę i gotowe. Nie wiem tylko jak stworzyć losową tablicę takiej mapy.

Wypisałem sobie różne parametry mapy dwa podstawowe z nich to wielkość i kształt.

Wielkość: 5x5, 10x10, 15x15
Kształt: pierścieniowa, spiralna itp.

Mam pomysł aby trzymać w plikach php tablicę wielkości dla danego kształtu. Tzn. mamy kształ pierścieniowy, i wielkość małą. Nazwa pliku to RingSmall.php a w tym pliku tablica:

[PHP] pobierz, plaintext 
$array = array(
 0, 1, 1, 1, 0,
 1, 0, 0, 0, 1,
 1, 0, 1, 0, 1,
 1, 0, 0, 0, 1,
 0, 1, 1, 1, 0
);
[PHP] pobierz, plaintext 

0 = miejsce gdzie gwiazda nie może wystąpić,
1 = miejsce gdzie może wystąpić

Kolejny parametr to ilość gwiazd: mała, średnia i duża. Teraz np. dla małej galaktyki mała ilość gwiazd to 5, dla średniej już 10, a dla dużej 15.

Losowo bez problemu uzupełnię taką tablicę miejscami gdzie są gwiazdy, problem pojawia się w połączeniach między nimi. Chciałbym zrobić to tak aby po 1 nie było gwiazdy bez połączenia, po 2 aby połączenia były realizowane do najbliższej gwiazdy.

Są może jakieś gotowe algorymty na tego typu problem? Kiedyś na anglojęzycznym forum trafiłem na gościa który opisywał krok po kroku jak generuje takie mapy jego program z listingami i wszystkimi klasami, ale nie mogę tego znaleźć :/.