Полярная координатная карта Генерация

Question

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

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

Алгоритм должен генерировать «города», распространяемые по всему кругу (но только внутри круга). Каждый город должен быть связан каким-то образом.

Размер круга зависит от количества игроков.

Все должно быть случайным, то есть, если я бегу

GenerateMap() 

два раза, он не должен давать те же результаты.

Здесь картина показывает, что я хочу: img

Красные стрелки указывают на города и линии связи между городами.

Как я могу создать алгоритм на основе вышеизложенного?

Обновление: Sorry, ссылка была сломана. Починил это.

Answer 1

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

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

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

2. петля N (города) раз
3. генерировать случайные (x,y) с равномерным распределением
4. отбрасывать итерации, где (x,y) находятся вне окружности
5. Выбросьте Итерации где (x,y) находится слишком близко к уже сгенерировано

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

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

В 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.

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