Polar Coordinate Map Generation

Question

I am currently work some sort of map generation algorithm for my game. I have a basic understanding on what I want it to do and how it would generate the map.

I want to use the Polar Coordinate system. I want a circular graph so that each player would spawn on the edge of the circle, evenly spread out.

The algorithm should generate "cities" spread out from across the circle (but only inside the circle). Each city should be connected some form of way.

The size of the circle should depends on the number of players.

Everything should be random, meaning if I run

GenerateMap()

two times, it should not give the same results.

Here is a picture showing what I want: img

The red arrows are pointing to the cities and the lines are the connections between the cities.

How would I go about creating an algorithm based on the above?

Update: Sorry the link was broken. Fixed it.

Answer 1

I see the cities like this:

1. compute sizes and constants from N

   as your cities should have constant average density then the radius can be computed from it directly. as it scales linearly with average or min city distance.

2. loop N (cities) times

3. generate random (x,y) with uniform distribution

4. throw away iterations where (x,y) is outside circle

5. throw away iterations where (x,y) is too near to already generated city

The paths are similar just generate all possible paths (non random) and throw away:

• paths much longer then average or min distance between cities (connects jutst neighbors)
• paths that intersect already generated path

In C++ code it could look like this:

//---------------------------------------------------------------------------
// 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++;
        }
    }
//---------------------------------------------------------------------------

Here overview of generated layout:

And Growth of N:

The blue circles are the cities, the gray area is the target circle and Lines are the paths. The cnt is just watch dog to avoid infinite loop if constants are wrong. Set the _max value properly so it is high enough for your N or use dynamic allocation instead. There is much more paths than cities so they could have separate _max value to preserve memory (was too lazy to add it).

You can use the RandSeed to have procedural generated maps ...

You can rescale output to better match circle layout after the generation simply by finding bounding box and rescale to radius R1.

Some constants are obtained empirically so play with them to achieve best output for your purpose.