4

I am trying to code a game which currently uses a matrix ( that I am calling a map). On this map are islands which can be generated n times. The purpose of the algorithm is to distribute the islands across the map in a way that makes use of the space to ensure they are not too close or too far away from each other. This means that they cannot be too close to the edges of the map but not too centralised either. So the nature of the algorithm should not be random.

Here are some example outcomes if the algorithm functions correctly: The matrix is the map and the orange elements represent the islands

Notice that when there is an odd number of elements on an even matrix then there is an island in a odd position.

Community
  • 1
Ewan Ross
  • 49
  • 2
  • seems to me that matrix 2 is incorrect. you could move 14 to 8 – Ewan Jun 04 '19 at 14:20
  • In the case of matrix 2 elements 3, shouldn't 11 and 29 be at 10 and 28? 10 is then still one forward and one diagonal from 14, but 10 and 28 are each two forward from their sides. Or at least move 29 to 28, which puts it further away from its bottom side without being appreciably closer to 14 - that is, it loses less on the diagonal with 14, than it gains on distance from the edge and gains on the diagonal with 11. You'd have to be much clearer about the weightings of various distances and various combinations of distances. – Steve Jun 04 '19 at 16:38
  • What are the expected maximum sizes (or typical sizes) for the matrixes you want to solve this in reality? 6x6? 600x600? 6 millions x 6 millions? Please clarify! – Doc Brown Jun 05 '19 at 06:21
  • @Ewan Which solution did you end up using? – Julio Henrique Bitencourt Apr 24 '21 at 14:03

3 Answers3

4

I think this problem is the same as circle packing.

Unless you want very large numbers of islands and perfect packing, the most efficient way of doing it is simply to hard code the positions

https://en.wikipedia.org/wiki/Circle_packing_in_a_square

You can see that the number of islands increases as the difference between perfectly packed and simple triangular packing becomes smaller.

Tom Au
  • 893
  • 7
  • 17
Ewan
  • 70,664
  • 5
  • 76
  • 161
0

You might want to look into Poisson Disk Sampling. There are a number algorithms for generating points that ensure that all points are more than some minimum distance apart. This is a common thing to need to do in ray tracing and other types of rendering where you need to take multiple samples close to each other (say within the space of a single pixel), but want to distribute the samples evenly across the space. This sounds similar to what you're attempting with your islands, so I think it would be a useful method for you to implement.

user1118321
  • 4,969
  • 1
  • 17
  • 25
0

Try a physics lattice.

Each island is a point which repulses all the other points by some amount, and is repulsed by some amount by the other points. Reduce the repulsion as an effect of distance.

Sum the effects up, and move the points by some fraction (say a third) of the repulsion effect.

Repeat for some number of iterations or until none of the points move.

At the end all of the points will roughly be separated, roughly equidistantly, but with enough variation to look somewhat random.

To make it look more varied assign slightly different repulsive strengths to the sides, and points. Some islands will be slightly closer, while others slightly further away. You need only vary the strength by a few units, say the average is 10 units, varying it by +-2 units.

Take a look at Amit's Blog. He has a number of articles on interesting issues like this.

Kain0_0
  • 15,888
  • 16
  • 37