I'm quite new to programming games and I'm currently working on a group project in university on creating one. In the game we've got a set of squares (cities, other entities) which are placed on the real plane. We'd like to start the game with a few squares in the center of the map and, as time goes, randomly place new ones around them, growing the whole network like that. I couldn't figure out how to elegantly do this and I found a lot of map generation algorithms, but they're mostly for surfaces and similar things, whereas my problem is more discrete. Any ideas?

I've added a picture in response to a comment - so our game might start off with the three red squares and as time goes we might add additional three squares (greens), after a while we can add two more squares again and so on. enter image description here

  • 1
    \$\begingroup\$ As worded, this seems pretty broad - for instance, there's many different ways to randomly place new nodes. A specific example (even just something hand drawn) would help clarify what your goal is. Also, initially, you mention the real plane, but at the end, you say discrete - this is a bit confusing as they are opposing ideas. \$\endgroup\$ – Pikalek Apr 9 '18 at 20:54
  • \$\begingroup\$ Thanks for the comment, I've added a bit more explanation and changed from nodes to squares. Yes, the coordinates are real, but the set of squares is finite. That's what I meant by "more discrete" than the surfaces.:) \$\endgroup\$ – Andrius Ovsianas Apr 9 '18 at 21:23
  • \$\begingroup\$ Are you saying the initial squares are the parents and new squares are place around these? \$\endgroup\$ – ErnieDingo Apr 9 '18 at 21:45
  • \$\begingroup\$ No, the squares themselves don't have any parent/child relationship. We just want to add squares randomly, not somewhere on the corner of the map and not too far away from those that we've already got. \$\endgroup\$ – Andrius Ovsianas Apr 9 '18 at 21:47

I find that a very elegant way of random placement is the use of Halton sequences.

Compare the random with Halton, here:

halton and noise

As you can see, the Halton-2,3 distribution is much more orderly, in that all points have their neighbours at a reasonable distance. Also, it progressively densifies, so the first samples are all widely spaced apart.

Now, in your specific application, you want to grow outwards. You could achieve this with filtering the sequence based on proximity to centre.

Do you ever want your cities to show 'infill?' If not, you could simply sort the sequence on distance to centre, and create them in that order.

If you do want occasional infill, I would push them outward, with increasing distance for each city. The extends will grow, yet, spaces in the interiour will get filled every now and then.

You could also reject outliers based on a radius, with a growing radius as the city grows.

The code to reject samples would look like this:

    i = 0
    while numaccepted < numv:
            x = -1 + 2 * halton( i, 2 )
            y = -1 + 2 * halton( i, 3 )
            allowed_radius = 0.1 + 0.9 * numaccepted / float(numv)
            if pt_in_circle( x, y, allowed_radius ) :
                    accepted.append( (x,y) )
                    numaccepted += 1
            i += 1

As you generate samples, you slowly grow the accepted distance from centre from 0.1 to 1.0 units.

And to generate the halton numbers, I used:

def halton(idx, base) :
        result = 0
        f = 1.0 / base
        i = idx
        while ( i > 0 ) :
                result += f * ( i % base )
                i = i / base
                f = f / base
        return result

Which results in the follow growth animation of 200 samples that survived the rejection test. To get them, a total of 2791 samples were tested, by the way.

rejections sampling

Because so many samples are rejected, the final result is not as nicely distributed as straight up Halton-2,3. You would get a nicer distribution by sorting the Halton samples, at the detriment of never seeing new samples in the interiour: they will always grow at the outskirts.

This is what it looks like if you generate 200 Halton samples that fall with in the unit circle, and then sort them by distance to the origin:

sorted samples

| improve this answer | |
  • \$\begingroup\$ occasional infill - sometimes place squares closer to the centre than the current squares are? If so, then that would be preferable. I can't see what you mean by "I would push them outward, with increasing distance for each city" though. \$\endgroup\$ – Andrius Ovsianas Apr 9 '18 at 22:16
  • \$\begingroup\$ Never mind about the pushing outward: I tried it, the results are not as good as rejecting samples. I'll add some (pseudo) code. \$\endgroup\$ – Bram Apr 10 '18 at 1:54
  • \$\begingroup\$ Ah, thanks for more explanation, an elegant solution indeed.:) I've altered your version of rejection approach by adding some personal space for each point and ended up with this. How would you add randomness though? Just pick different bases? \$\endgroup\$ – Andrius Ovsianas Apr 10 '18 at 9:23
  • \$\begingroup\$ Looks good! To have different runs, I add an offset when indexing the Halton set. So instead of using samples 0..200, I use 200..400 instead. \$\endgroup\$ – Bram Apr 10 '18 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.