algorithm - 极坐标 map 生成

Question

我目前正在为我的游戏开发某种 map 生成算法。我对我想要它做什么以及它如何生成 map 有一个基本的了解。

我想使用极坐标系。我想要一个圆形图，这样每个玩家都会在圆圈的边缘生成，均匀分布。

该算法应生成从整个圆(但仅在圆内)散开的“城市”。每个城市都应该以某种方式连接起来。

圆圈的大小应该取决于玩家的数量。

一切都应该是随机的，这意味着如果我运行

GenerateMap()

两次，它不应该给出相同的结果。

这是一张显示我想要的图片:img

红色箭头指向城市，线条是城市之间的连接。

我将如何着手根据上述内容创建算法？

更新:抱歉，链接已损坏。修复它。

Answer 1

我看到的城市是这样的:

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 程序生成 map ...

您可以在生成后重新缩放输出以更好地匹配圆形布局，只需找到边界框并重新缩放到半径 R1。

一些常量是根据经验获得的，因此请使用它们以获得最适合您目的的输出。