Создание карты полярных координат

Я вижу такие города:

1. вычислять размеры и константы из N

   так как ваши города должны иметь постоянную среднюю плотность, радиус можно рассчитать напрямую из нее. так как он линейно масштабируется со средним или минимальным расстоянием до города.

2. цикл N (города) раз

3. генерировать случайный (x,y) с равномерным распределением

4. выбросить итерации, в которых (x,y) находится за пределами круга

5. выбросить итерации, в которых (x,y) находится слишком близко к уже созданному городу

Пути похожи, просто сгенерируйте все возможные пути (не случайные) и выбросьте:

• пути намного длиннее среднего или минимального расстояния между городами (соединяет только соседей)
• пути, которые пересекают уже созданный путь

В коде C ++ это может выглядеть так:

//---------------------------------------------------------------------------
// some globals first
const int _max=128;         // just max limit for cities and paths
const int R0=10;            // city radius
const int RR=R0*R0*9;       // min distance^2 between cities
      int N=20;             // number of cities
      int R1=100;           // map radius

struct _city { int x,y; };  // all the data you need for city
_city city[_max];           // list of cities
struct _path { int i0,i1; };// index of cities to join with path
_path path[_max];           // list of paths
int M=0;                    // number of paths in the list
//---------------------------------------------------------------------------
bool LinesIntersect(float X1,float Y1,float X2,float Y2,float X3,float Y3,float X4,float Y4)
    {
    if (fabs(X2-X3)+fabs(Y2-Y3)<1e-3) return false;
    if (fabs(X1-X4)+fabs(Y1-Y4)<1e-3) return false;
    float dx1,dy1,dx2,dy2;
    dx1 = X2 - X1;
    dy1 = Y2 - Y1;
    dx2 = X4 - X3;
    dy2 = Y4 - Y3;
    float s,t,ax,ay,b;
    ax=X1-X3;
    ay=Y1-Y3;
    b=(-(dx2*dy1)+(dx1*dy2)); if (fabs(b)>1e-3) b=1.0/b; else b=0.0;
    s = (-(dy1*ax)+(dx1*ay))*b;
    t = ( (dx2*ay)-(dy2*ax))*b;
    if ((s>=0)&&(s<=1)&&(t>=0)&&(t<=1)) return true;
    return false; // No collision
    }
//---------------------------------------------------------------------------
// here generate n cities into circle at x0,y0
// compute R1,N from R0,RR,n
void genere(int x0,int y0,int n)
    {
    _city c;
    _path p,*q;
    int i,j,cnt,x,y,rr;
    Randomize();            // init pseudo random generator
    // [generate cities]
    R1=(sqrt(RR*n)*8)/10;
    rr=R1-R0; rr*=rr;
    for (cnt=50*n,i=0;i<n;) // loop until all cities are generated
        {
        // watchdog
        cnt--; if (cnt<=0) break;
        // pseudo random position
        c.x=Random(R1+R1)-R1;   // <-r,+r>
        c.y=Random(R1+R1)-R1;   // <-r,+r>
        // ignore cities outside R1 radius
        if ((c.x*c.x)+(c.y*c.y)>rr) continue;
        c.x+=x0;            // position to center
        c.y+=y0;
        // ignore city if closer to any other then RR
        for (j=0;j<i;j++)
            {
            x=c.x-city[j].x;
            y=c.y-city[j].y;
            if ((x*x)+(y*y)<=RR) { j=-1; break; }
            }
        if (j<0) continue;
        // add new city to list
        city[i]=c; i++;
        }
    N=i; // just in case watch dog kiks in
    // [generate paths]
    for (M=0,p.i0=0;p.i0<N;p.i0++)
     for (p.i1=p.i0+1;p.i1<N;p.i1++)
        {
        // ignore too long path
        x=city[p.i1].x-city[p.i0].x;
        y=city[p.i1].y-city[p.i0].y;
        if ((x*x)+(y*y)>5*RR) continue; // this constant determine the path density per city
        // ignore intersecting path
        for (q=path,i=0;i<M;i++,q++)
         if ((q->i0!=p.i0)&&(q->i0!=p.i1)&&(q->i1!=p.i0)&&(q->i1!=p.i1))
          if (LinesIntersect(
            city[p.i0].x,city[p.i0].y,city[p.i1].x,city[p.i1].y,
            city[q->i0].x,city[q->i0].y,city[q->i1].x,city[q->i1].y
            )) { i=-1; break; }
        if (i<0) continue;
        // add path to list
        if (M>=_max) break;
        path[M]=p; M++;
        }
    }
//---------------------------------------------------------------------------

Вот обзор сгенерированного макета:

И рост N:

Синие круги - это города, серая область - это целевой круг, а линии - это пути. cnt - это просто сторожевой пес, чтобы избежать бесконечного цикла, если константы неверны. Установите значение _max правильно, чтобы оно было достаточно высоким для вашего N, или используйте вместо него динамическое размещение. Путей намного больше, чем городов, поэтому они могут иметь отдельное значение _max для сохранения памяти (было лень его добавлять).

Вы можете использовать RandSeed для процедурно сгенерированных карт ...

Вы можете изменить масштаб вывода для лучшего соответствия компоновке круга после создания, просто найдя ограничивающую рамку и изменив масштаб до радиуса R1.

Некоторые константы получены эмпирическим путем, так что поиграйте с ними, чтобы добиться наилучшего результата для ваших целей.