-
Notifications
You must be signed in to change notification settings - Fork 164
/
galaxy.py
818 lines (680 loc) · 29.8 KB
/
galaxy.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
import freeorion as fo
import sys
from collections import defaultdict
from math import acos, ceil, cos, floor, pi, sin, sqrt
from random import gauss, randint, random, uniform
import universe_tables
import util
class AdjacencyGrid:
def __init__(self, universe_width):
"""
:param float universe_width:
"""
assert universe_tables.MIN_SYSTEM_SEPARATION < universe_tables.MAX_STARLANE_LENGTH
self.min_dist = universe_tables.MIN_SYSTEM_SEPARATION
self.max_dist = universe_tables.MAX_STARLANE_LENGTH
self.cell_size = min(max(universe_width / 50, self.min_dist), self.max_dist / sqrt(2))
self.width = int(universe_width / self.cell_size) + 1
self.grid = defaultdict(set)
print(f"Adjacency Grid: width {self.width}, cell size {self.cell_size}")
def cell(self, pos):
"""Returns cell index."""
return int(pos[0] / self.cell_size), int(pos[1] / self.cell_size)
def insert_pos(self, pos):
"""Inserts pos."""
self.grid[self.cell(pos)].add(pos)
def remove_pos(self, pos):
"""Removes pos."""
self.grid[self.cell(pos)].discard(pos)
def _square_indices_containing_cell(self, cell, radius):
"""Return a square of indices containing cell."""
cell_x, cell_y = cell
upper_left_x = max(0, cell_x - radius)
upper_left_y = max(0, cell_y - radius)
lower_right_x = min(self.width - 1, cell_x + radius)
lower_right_y = min(self.width - 1, cell_y + radius)
return [(x, y) for x in range(upper_left_x, lower_right_x + 1) for y in range(upper_left_y, lower_right_y + 1)]
def _generate_rings_around_point(self, pos, max_radius=None):
"""Yields successive rings of indices containing cell."""
cell = self.cell(pos)
i_radius = 0
i_radius_max = ceil(max_radius / self.cell_size) if max_radius else (self.width + 1)
outer = set()
ring = {1}
while ring and i_radius <= i_radius_max:
inner = outer
outer = set(self._square_indices_containing_cell(cell, i_radius))
ring = outer - inner
yield ring
i_radius += 1
def neighbors(self, p):
"""Return all neighbors within max_dist."""
_neighbors = []
i_radius_close_enough = floor(self.max_dist / self.cell_size)
for i, ring in enumerate(self._generate_rings_around_point(p, self.max_dist)):
if i <= i_radius_close_enough:
_neighbors += [pos for cell in ring for pos in self.grid[cell]]
else:
_neighbors += [
pos for cell in ring for pos in self.grid[cell] if util.distance(pos, p) <= self.max_dist
]
return _neighbors
def nearest_neighbor(self, p):
"""Return nearest neighbor at any distance."""
for ring in self._generate_rings_around_point(p):
candidates = [pos for cell in ring for pos in self.grid[cell]]
if candidates:
(_, pt) = min((util.distance(pos, p), pos) for pos in candidates)
return pt
return None
def too_close_to_other_positions(self, pos):
"""
Checks if the specified position is too close to the positions stored in the grid
"""
pos_cell = self.cell(pos)
return any(
util.distance(p2, pos) < self.min_dist
for p2_cell in self._square_indices_containing_cell(pos_cell, 1)
for p2 in self.grid[p2_cell]
)
class DSet:
"""
A set of pos that is disjoint (not connected) to other sets.
If the set is of one item then it has no parent. parent equals None.
Otherwise the set points to the root/representative item of the set via parent.
A private child class of DisjointSets to store the parent and rank of a disjoint set object
"""
def __init__(self, pos):
self.pos = pos
# stores None or the parent
self.parent = None
# starts at 0, never decreases and only increases
# when this object is the parent and two equal rank sets are merged
self.rank = 0
def bind_parent(self, parent):
"""Bind to parent."""
assert self is not parent
self.parent = parent
def inc_rank(self):
"""Increment rank."""
self.rank += 1
class DisjointSets:
"""
A set of disjoint sets.
It supports the operations of:
add(pos) -- Creates a new single item set containing pos if it isn't already a set. O(1)
link(p1, p2) -- Links two sets containing p1 and p2 together.
This will add(p1) and add(p2) if necessary. O(1)
root(pos) -- Gets the root/representative object for the set.
Creates a new set with pos if not already a set. O(1)
complete_sets -- Returns a list of list of all sets. O(n)
See https://en.wikipedia.org/wiki/Disjoint-set_data_structure
"""
def __init__(self):
self.dsets = {}
def add(self, pos):
"""Creates a new single item set containing pos if it isn't already a set. O(1)"""
if pos not in self.dsets:
self.dsets[pos] = DSet(pos)
def link(self, p1, p2):
"""Creates a link between the sets containing p1 and p2"""
root1 = self.root(p1)
if p1 == p2:
# print " self link"
return
root2 = self.root(p2)
if root1 == root2:
# print " same discrete set link"
return
ds1 = self.dsets[root1]
ds2 = self.dsets[root2]
assert not ds1.parent and not ds2.parent
# Always attach the "smaller" lower rank as the child of the "larger" higher rank tree
if ds1.rank > ds2.rank:
# print " left link"
ds2.bind_parent(ds1)
else:
# print " right link"
ds1.bind_parent(ds2)
if ds1.rank == ds2.rank:
# print " even link"
ds2.inc_rank()
def root(self, pos):
"""
Returns the key position of the cluster containing pos
Adds pos if absent
"""
root = self._has_root(pos)
if root:
return root[0]
self.add(pos)
return pos
def _has_root(self, pos):
"""
Check if pos is the root of a cluster otherwise shorten
the tree while tranversing it and return the root
"""
# traverse tree and fetch parents for compression
def parents(p1, children):
# print "pp p1 ", p1.pos, " children a ", children
if p1.parent:
# print "pp deeper ", p1.pos, " chlidren b ", children
children.append(p1)
return parents(p1.parent, children)
else:
# print "pp done p1 ", p1.pos, " children c ", children
return (p1, children)
if pos not in self.dsets:
return []
(root, children) = parents(self.dsets[pos], [])
# squash the chain of children
for child in children:
child.bind_parent(root)
return [root.pos]
def complete_sets(self):
"""returns a list of list of all sets O(n)."""
ret = defaultdict(list)
for pos in self.dsets.keys():
ret[self.root(pos)].append(pos)
return list(ret.values())
class Clusterer:
"""
Computes all clusters of positions separated by more than MAX_STARLANE_LENGTH
This creates a disjoint set of all of the positions
Adds all of the seperations less than MAX_STARLANE_LENGTH
Then returns the clusters of stars when requested
"""
def __init__(self, positions, adjacency_grid):
self.adjacency_grid = adjacency_grid
self.dsets = DisjointSets()
for pos in positions:
self._add(pos)
self.clusters = set()
for cluster in self.dsets.complete_sets():
# Decorate each cluster with its length to speed sorting
self.clusters.add((len(cluster), frozenset(cluster)))
def __len__(self):
return len(self.clusters)
def _add(self, pos):
"""Adds pos."""
for neighbor in self.adjacency_grid.neighbors(pos):
# print "Clusterer adding ", pos, " and ", neighbor
self.dsets.link(pos, neighbor)
def smallest_isolated_cluster(self):
"""
Return None if all of the positions are in one cluster
or the smallest cluster
"""
# Sort (min) and return the undecorated cluster.
return None if len(self.clusters) < 2 else min(self.clusters)[1]
def stitch_clusters(self, p1, p2, stitches):
"""
Stitch the clusters containing ''p1'' and ''p2''
together with the positions in ''stitches''
This assumes that the stitching is correctly formed.
''p1'' and ''p2'' are the closest positions between
the clusters and the positions in ''stitches'' are only
between ''p1'' and ''p2''
After stitch_clusters there will be one fewer clusters in
the clusterer, unless there were fewer than two clusters
to begin with.
If ''p1'' or ''p2'' are not in clusters then stitch_clusters
just stitches two random clusters together. This preserves
the invariant that stitch_clusters always reduces the number
of clusters.
"""
len_dset1 = None
len_dset2 = None
for len_dset in self.clusters:
if p1 in len_dset[1]:
len_dset1 = len_dset
if p2 in len_dset[1]:
len_dset2 = len_dset
if not len_dset1 or not len_dset2:
util.report_error("p1 and p2 must be points in disjoint sets of positions")
if len(self.clusters) < 2:
return
len_dset1, len_dset2 = list(self.clusters)[0:2]
self.clusters.remove(len_dset1)
self.clusters.remove(len_dset2)
# Decorate the new cluster with its length to speed sorting
new_set = len_dset1[1].union(len_dset2[1]).union(frozenset(stitches))
self.clusters.add((len(new_set), new_set))
def stitching_positions(p1, p2):
"""
Returns a list of positions between p1 and p2 between MIN_SYSTEM_SEPARATION and MAX_STARLANE_LENGTH apart
"""
if 2 * universe_tables.MIN_SYSTEM_SEPARATION >= universe_tables.MAX_STARLANE_LENGTH:
util.report_error(
"MAX_STARLANE_LENGTH must be twice MIN_SYSTEM_SEPARATION to "
"allow extra positions to be added to enforce MAX_STARLANE_LENGTH"
)
return []
max_dist = universe_tables.MAX_STARLANE_LENGTH
min_dist = universe_tables.MIN_SYSTEM_SEPARATION
p1_p2_dist = util.distance(p1, p2)
if p1_p2_dist < max_dist:
return []
# Pick a random point in an 2:1 ratio ellipse and then rotate and slide it in between p1 and p2
p1_p2_theta = acos((p2[0] - p1[0]) / p1_p2_dist)
p1_p2_scale = (p1_p2_dist - 2 * min_dist) / 2
p1_p2_translation = ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)
radius_0space = uniform(0.0, 1.0)
angle_0space = uniform(0.0, 2.0 * pi)
rotated_point = (
radius_0space * p1_p2_scale * cos(angle_0space + p1_p2_theta),
radius_0space * p1_p2_scale * sin(angle_0space + p1_p2_theta),
)
p3 = (rotated_point[0] + p1_p2_translation[0], rotated_point[1] + p1_p2_translation[1])
return [p3] + stitching_positions(p1, p3) + stitching_positions(p2, p3)
def enforce_max_distance(positions, adjacency_grid):
"""
Adds extra positions between groups of positions to guarantee
that no groups of positions are separated from all other groups
of positions by more than universe_tables.MAX_STARLANE_LENGTH
Find all groups of positions, where every member is within
MAX_STARLANE_LENGTH of at least one other member of the group,
but all members of the group are more than MAX_STARLANE_LENGTH
from all positions in other groups.
For each group:
- Remove it from the adjacency grid and find its nearest neighboring position.
- Add positions between the nearest neighbor and the group to
ensure every position has at least one neighbor within
MAX_STARLANE_LENGTH.
"""
# Find all clusters
clusterer = Clusterer(positions, adjacency_grid)
if len(clusterer) == 1:
print("All systems positioned in a single connected cluster")
else:
print(f"{len(clusterer)} clusters separated by more than the MAX_STARLANE_LENGTH." " Starting to fill gaps.")
while len(clusterer) > 1:
smallest_cluster = clusterer.smallest_isolated_cluster()
print("Searching for nearest neighbor position to a cluster " f"with {len(smallest_cluster)} positions.")
for pos in smallest_cluster:
adjacency_grid.remove_pos(pos)
# Find nearest neighbour
(_, p1, p2) = min(
[
(util.distance(pos, nn), pos, nn)
for pos in smallest_cluster
for nn in [adjacency_grid.nearest_neighbor(pos)]
if nn
]
)
for pos in smallest_cluster:
adjacency_grid.insert_pos(pos)
# Add extra positions
extra_positions = stitching_positions(p1, p2)
for i_extra, p3 in enumerate(extra_positions):
print(
f"Adding {i_extra + 1} of {len(extra_positions)} extra positions at {p3} to enforce "
f"max spacing between {p1} and {p2}."
)
adjacency_grid.insert_pos(p3)
positions.append(p3)
clusterer.stitch_clusters(p1, p2, extra_positions)
if len(clusterer) == 1:
print("All systems now positioned in a single connected cluster")
else:
print(f"{len(clusterer)} clusters separated by more the MAX_STARLANE_LENGTH. " "Continuing to fill gaps.")
def calc_universe_width(shape, size):
"""
Calculates typical universe width based on galaxy shape and number of star systems.
A 150 star universe should be 1000 units across.
"""
width = (1000.0 / sqrt(150.0)) * sqrt(float(size))
if shape in [fo.galaxyShape.elliptical, fo.galaxyShape.irregular]:
width *= 1.4
elif shape == fo.galaxyShape.disc:
width *= 1.2
return width
def spiral_galaxy_calc_positions(positions, adjacency_grid, arms, size, width):
"""
Calculate positions for the spiral galaxy shapes.
"""
arm_offset = uniform(0.0, 2.0 * pi)
arm_angle = (2.0 * pi) / float(arms)
arm_spread = (0.3 * pi) / float(arms)
arm_length = 1.5 * pi
center = 0.25
for i in range(size):
attempts = 100
while attempts > 0:
radius = random()
if radius < center:
angle = uniform(0.0, 2.0 * pi)
x = radius * cos(arm_offset + angle)
y = radius * sin(arm_offset + angle)
else:
arm = randint(0, arms - 1) * arm_angle
angle = gauss(0.0, arm_spread)
x = radius * cos(arm_offset + arm + angle + radius * arm_length)
y = radius * sin(arm_offset + arm + angle + radius * arm_length)
x = (x + 1) * width / 2.0
y = (y + 1) * width / 2.0
if (x < 0.0) or (width <= x) or (y < 0.0) or (width <= y):
continue
# see if new star is too close to any existing star.
# if so, we try again or give up
if adjacency_grid.too_close_to_other_positions((x, y)):
attempts -= 1
continue
# add the new star location
pos = (x, y)
adjacency_grid.insert_pos(pos)
positions.append(pos)
break
if not attempts:
print(
f"Spiral galaxy shape: giving up on placing star {i}, can't "
"find position sufficiently far from other systems."
)
def elliptical_galaxy_calc_positions(positions, adjacency_grid, size, width):
"""
Calculate positions for the elliptical galaxy shape.
"""
ellipse_width_vs_height = uniform(0.4, 0.6)
rotation = uniform(0.0, pi)
rotation_sin = sin(rotation)
rotation_cos = cos(rotation)
gap_constant = 0.95
gap_size = 1.0 - gap_constant * gap_constant * gap_constant
for i in range(size):
attempts = 100
while attempts > 0:
radius = uniform(0.0, gap_constant)
# adjust for bigger density near center and create gap
radius = radius * radius * radius + gap_size
angle = uniform(0.0, 2.0 * pi)
# rotate for individual angle and apply elliptical shape
x1 = radius * cos(angle)
y1 = radius * sin(angle) * ellipse_width_vs_height
# rotate for ellipse angle
x = x1 * rotation_cos - y1 * rotation_sin
y = x1 * rotation_sin + y1 * rotation_cos
# move from [-1.0, 1.0] universe coordinates
x = (x + 1.0) * width / 2.0
y = (y + 1.0) * width / 2.0
# discard stars that are outside boundaries (due to possible rounding errors)
if (x < 0) or (x >= width) or (y < 0) or (y >= width):
attempts -= 1
continue
# see if new star is too close to any existing star; if so, we try again
if adjacency_grid.too_close_to_other_positions((x, y)):
attempts -= 1
continue
# add the new star location
pos = (x, y)
adjacency_grid.insert_pos(pos)
positions.append(pos)
break
if not attempts:
print(
f"Elliptical galaxy shape: giving up on placing star {i}, "
"can't find position sufficiently far from other systems"
)
def disc_galaxy_calc_positions(positions, adjacency_grid, size, width):
"""
Calculate positions for the disc galaxy shape.
"""
center_x, center_y = width / 2.0, width / 2.0
for i in range(size):
attempts = 100
while attempts > 0:
radius = uniform(0.0, width / 2.0)
angle = uniform(0.0, 2.0 * pi)
x = center_x + radius * cos(angle)
y = center_y + radius * sin(angle)
if (x < 0) or (width <= x) or (y < 0) or (width <= y):
attempts -= 1
continue
# see if new star is too close to any existing star; if so, we try again
if adjacency_grid.too_close_to_other_positions((x, y)):
attempts -= 1
continue
# add the new star location
pos = (x, y)
adjacency_grid.insert_pos(pos)
positions.append(pos)
break
if not attempts:
print(
f"Disc galaxy shape: giving up on placing star {i}, can't find"
" position sufficiently far from other systems"
)
def cluster_galaxy_calc_positions( # noqa: C901
positions: list[tuple[int, int]], adjacency_grid: AdjacencyGrid, size: int, width: float
):
"""
Calculate positions for the cluster galaxy shape and add them to positions.
"""
if size < 1:
print("Cluster galaxy requested for less than 1 star", file=sys.stderr)
return
if size == 1:
pos = (width / 2.0, width / 2.0)
positions.append(pos)
return
# Typically a galaxy with 100 systems should have ~5 clusters
avg_clusters = max(2, round(size / 20))
# Add a bit of random variation (+/- 20%)
clusters = max(2, randint(round((avg_clusters * 8) / 10), round((avg_clusters * 12) / 10)))
# probability of systems which don't belong to a cluster
system_noise = 0.15
ellipse_width_vs_height = uniform(0.2, 0.5)
# a list of tuples of tuples: first tuple holds cluster position,
# second tuple stores help values for cluster rotation (sin,cos)
clusters_position = []
for i in range(clusters):
attempts = 100
while attempts > 0:
# prevent cluster position near borders (and on border)
x = ((random() * 2.0 - 1.0) / (clusters + 1.0)) * clusters
y = ((random() * 2.0 - 1.0) / (clusters + 1.0)) * clusters
# ensure all clusters have a min separation to each other (search isn't optimized, not worth the effort)
if all(
((cp[0][0] - x) * (cp[0][0] - x) + (cp[0][1] - y) * (cp[0][1] - y)) > (2.0 / clusters)
for cp in clusters_position
):
break
attempts -= 1
rotation = uniform(0.0, pi)
clusters_position.append(((x, y), (sin(rotation), cos(rotation))))
for i in range(size):
attempts = 100
while attempts > 0:
if random() < system_noise:
x = random() * 2.0 - 1.0
y = random() * 2.0 - 1.0
else:
cluster = clusters_position[i % len(clusters_position)]
radius = random()
angle = uniform(0.0, 2.0 * pi)
x1 = radius * cos(angle)
y1 = radius * sin(angle) * ellipse_width_vs_height
x = x1 * cluster[1][1] + y1 * cluster[1][0]
y = (-x1) * cluster[1][0] + y1 * cluster[1][1]
x = x / sqrt(float(clusters)) + cluster[0][0]
y = y / sqrt(float(clusters)) + cluster[0][1]
x = (x + 1) * width / 2.0
y = (y + 1) * width / 2.0
if (x < 0) or (width <= x) or (y < 0) or (width <= y):
attempts -= 1
continue
# see if new star is too close to any existing star; if so, we try again
if adjacency_grid.too_close_to_other_positions((x, y)):
attempts -= 1
continue
# add the new star location
pos = (x, y)
adjacency_grid.insert_pos(pos)
positions.append(pos)
break
if not attempts:
print(
f"Cluster galaxy shape: giving up on placing star {i}, can't "
"find position sufficiently far from other systems"
)
def ring_galaxy_calc_positions(positions, adjacency_grid, size, width):
"""
Calculate positions for the ring galaxy shape.
"""
ring_width = width / 4.0
ring_radius = (width - ring_width) / 2.0
for i in range(size):
attempts = 100
while attempts > 0:
theta = uniform(0.0, 2.0 * pi)
radius = gauss(ring_radius, ring_width / 3.0)
x = width / 2.0 + radius * cos(theta)
y = width / 2.0 + radius * sin(theta)
if (x < 0) or (width <= x) or (y < 0) or (width <= y):
attempts -= 1
continue
# see if new star is too close to any existing star; if so, we try again
if adjacency_grid.too_close_to_other_positions((x, y)):
attempts -= 1
continue
# add the new star location
pos = (x, y)
adjacency_grid.insert_pos(pos)
positions.append(pos)
break
if not attempts:
print(
f"Ring galaxy shape: giving up on placing star {i}, can't"
" find position sufficiently far from other systems"
)
def box_galaxy_calc_positions(positions, adjacency_grid, size, width):
"""
Calculate positions for the box galaxy shape.
:param float width:
"""
for i in range(size):
attempts = 100
while attempts > 0:
x = width * random()
y = width * random()
if (x < 0) or (width <= x) or (y < 0) or (width <= y):
attempts -= 1
continue
# see if new star is too close to any existing star; if so, we try again
if adjacency_grid.too_close_to_other_positions((x, y)):
attempts -= 1
continue
# add the new star location
pos = (x, y)
adjacency_grid.insert_pos(pos)
positions.append(pos)
break
if not attempts:
print(
f"Box galaxy shape: giving up on placing star {i}, can't find"
" position sufficiently far from other systems"
)
def irregular_galaxy_calc_positions(positions, adjacency_grid, size, width):
"""
Calculate positions for the irregular galaxy shape.
"""
max_delta = max(min(float(universe_tables.MAX_STARLANE_LENGTH), width / 10.0), adjacency_grid.min_dist * 2.0)
print(f"Irregular galaxy shape: max delta distance = {max_delta}")
origin_x, origin_y = width / 2.0, width / 2.0
prev_x, prev_y = origin_x, origin_y
reset_to_origin = 0
for _ in range(size):
attempts = 100
found = False
while (attempts > 0) and not found:
attempts -= 1
x = prev_x + uniform(-max_delta, max_delta)
y = prev_y + uniform(-max_delta, max_delta)
if util.distance((x, y), (origin_x, origin_y)) > width * 0.45:
prev_x, prev_y = origin_x, origin_y
reset_to_origin += 1
continue
found = not adjacency_grid.too_close_to_other_positions((x, y))
if attempts % 10:
prev_x, prev_y = x, y
if found:
pos = (x, y)
adjacency_grid.insert_pos(pos)
positions.append(pos)
prev_x, prev_y = x, y
print(f"Reset to origin {reset_to_origin} times")
def recalc_universe_width(positions):
"""
Recalculates the universe width. This is done by shifting all positions by a delta so too much "extra space"
beyond the uppermost, lowermost, leftmost and rightmost positions is cropped, and adjust the universe width
accordingly.
Returns the new universe width and the recalculated positions.
"""
print("Recalculating universe width...")
# first, get the uppermost, lowermost, leftmost and rightmost positions
# (these are those with their x or y coordinate closest to or farthest away from the x or y axis)
min_x = min(positions, key=lambda p: p[0])[0]
min_y = min(positions, key=lambda p: p[1])[1]
max_x = max(positions, key=lambda p: p[0])[0]
max_y = max(positions, key=lambda p: p[1])[1]
print(f"...the leftmost system position is at x coordinate {min_x}")
print(f"...the uppermost system position is at y coordinate {min_y}")
print(f"...the rightmost system position is at x coordinate {max_x}")
print(f"...the lowermost system position is at y coordinate {max_y}")
# calculate the actual universe width by determining the width and height of an rectangle that encompasses all
# positions, and take the greater of the two as the new actual width for the universe
# also add a constant value to the width so we have some small space around
width = max_x - min_x
height = max_y - min_y
actual_width = max(width, height) + 20.0
print(f"...recalculated universe width: {actual_width}")
# shift all positions so the entire map is centered in a quadratic box of the width we just calculated
# this box defines the extends of our universe
delta_x = ((actual_width - width) / 2) - min_x
delta_y = ((actual_width - height) / 2) - min_y
print(f"...shifting all system positions by {delta_x}/{delta_y}")
new_positions = [(p[0] + delta_x, p[1] + delta_y) for p in positions]
print(f"...the leftmost system position is now at x coordinate {min(new_positions, key=lambda p: p[0])[0]}")
print(f"...the uppermost system position is now at y coordinate {min(new_positions, key=lambda p: p[1])[1]}")
print(f"...the rightmost system position is now at x coordinate {max(new_positions, key=lambda p: p[0])[0]}")
print(f"...the lowermost system position is now at y coordinate {max(new_positions, key=lambda p: p[1])[1]}")
return actual_width, new_positions
def calc_star_system_positions(gsd):
"""
Calculates list of positions (x, y) for a given galaxy shape,
number of systems and width
Uses universe generator helper functions provided by the API
"""
# calculate typical width for universe based on number of systems
width = calc_universe_width(gsd.shape, gsd.size)
print(f"Set universe width to {width}")
fo.set_universe_width(width)
positions = []
adjacency_grid = AdjacencyGrid(width)
print(f"Creating {gsd.shape} galaxy shape")
if gsd.shape == fo.galaxyShape.spiral2:
spiral_galaxy_calc_positions(positions, adjacency_grid, 2, gsd.size, width)
elif gsd.shape == fo.galaxyShape.spiral3:
spiral_galaxy_calc_positions(positions, adjacency_grid, 3, gsd.size, width)
elif gsd.shape == fo.galaxyShape.spiral4:
spiral_galaxy_calc_positions(positions, adjacency_grid, 4, gsd.size, width)
elif gsd.shape == fo.galaxyShape.elliptical:
elliptical_galaxy_calc_positions(positions, adjacency_grid, gsd.size, width)
elif gsd.shape == fo.galaxyShape.disc:
disc_galaxy_calc_positions(positions, adjacency_grid, gsd.size, width)
elif gsd.shape == fo.galaxyShape.cluster:
cluster_galaxy_calc_positions(positions, adjacency_grid, gsd.size, width)
elif gsd.shape == fo.galaxyShape.ring:
ring_galaxy_calc_positions(positions, adjacency_grid, gsd.size, width)
elif gsd.shape == fo.galaxyShape.irregular:
irregular_galaxy_calc_positions(positions, adjacency_grid, gsd.size, width)
# Check if any positions have been calculated...
if not positions:
# ...if not, fall back on box shape
box_galaxy_calc_positions(positions, adjacency_grid, gsd.size, width)
enforce_max_distance(positions, adjacency_grid)
# to avoid having too much "extra space" around the system positions of our galaxy map, recalculate the universe
# width and shift all positions accordingly
width, positions = recalc_universe_width(positions)
print(f"Set universe width to {width}")
fo.set_universe_width(width)
return positions