La galaxia a partir de una semilla
En resumen: Epic Cosmos es una estrategia espacial completa que se construye lección a lección. La primera lección construye la galaxia: un generador con semilla, de 12 a 20 sistemas en una cuadrícula de 5 por 4, rutas como un grafo (primero un árbol de expansión mínimo, luego otras adicionales), una comprobación de conectividad con búsqueda en anchura y planetas con pesos.
Problema
Una galaxia nueva cada vez
En esta serie hacemos un segundo juego, muy distinto de Arcanum: Epic Cosmos, una estrategia espacial por turnos, otra vez completa y otra vez en la consola. Aquí no hay un héroe que recorre un mapa. Diriges un imperio: un sistema con una capital, unos pocos recursos y una primera flota. Colonizas planetas, investigas tecnologías, construyes una flota y compites con dos o tres rivales que juegan solos. La victoria es conquistar la galaxia, investigar la Puerta Estelar o ganar por economía, y si nadie lo consigue, tras 150 turnos gana el más fuerte.
Un juego así solo tiene sentido si cada partida ocurre en una galaxia nueva: los sistemas están en otro sitio, las rutas pasan por otro lado, los planetas son ricos en otras cosas. Pero también existe la exigencia contraria. Un error que comunica un jugador tiene que repetirse exactamente. Una partida guardada no puede pesar una galaxia entera. Y la comprobación del sitio ejecuta el juego en cuatro lenguajes y compara las salidas byte a byte.
Las dos exigencias caben en un número: la semilla. La galaxia no se guarda, se vuelve a hacer a partir de la semilla, igual cada vez. Esta lección trata de cómo se hace. Empieza con el juego y después construye su primera parte.
Turno 1/150 Imperio Terrano (A) puntos 20M70+8 G60+4 C20+3 U5+1 ciencia +3No se investiga nada (r número). Ciencia acumulada: 0Imperio Terrano empieza en el sistema Elara: capital,astillero, laboratorio y tu primera flota.Coloniza planetas, investiga tecnologías, construye una flota.En combate I vence a B, B vence a F, F vence a I.Victoria: conquista la galaxia, investiga la Puerta Estelar oproduce 9800. Tras 150 turnos gana el más fuerte. Escribehelp.
Enter o map: al mapa help: comandosPruébalo
Jugar
Este es el juego de verdad: la versión de JavaScript, ejecutada en el navegador. Aquí no hay teclas. Escribes un comando en la línea bajo la pantalla y pulsas Enter. Empieza con help, luego map, luego sys 1: verás el mapa, el sistema en el que estás y sus planetas.
Epic Cosmos: el imperio
Un sistema, una primera flota y una galaxia entera. Los rivales ya están pensando.
Escribe los comandos en la línea de abajo y pulsa Enter (help los muestra todos; una línea vacía es map). Las partidas guardadas se quedan en este navegador.
Los comandos más importantes (help los muestra todos, una línea vacía es map):
mapmuestra el mapa de la galaxia:[ 1 ]son los sistemas, los puntos son las rutas, las letras son los imperios.sys Nmuestra el sistema N: sus planetas, qué producen y qué flotas hay allí.empmuestra los imperios,techel árbol de tecnologías,fleetslas flotas.col Pcoloniza el planeta P,b mine Pconstruye en él una mina,r Xinvestiga una tecnología.ship T N Pconstruye N naves de tipo T,go A Benvía una flota del sistema A al B por las rutas.endtermina el turno,wait Nsalta hasta N turnos,save 1yload 1sirven para guardar.
La victoria es una de tres: conquista (caen todos los imperios menos el tuyo), ciencia (investigas la Puerta Estelar, la última tecnología) o economía (produces 9800 en total). El juego dura 150 turnos como máximo.
Más precisamente, para curiosos
El juego en el navegador es el mismo archivo que verás en las lecciones y ejecutarás en tu ordenador. Solo se ha sustituido el bloque que en Node lee los argumentos y escribe las partidas guardadas en archivos: aquí la entrada viene del campo bajo la pantalla y las partidas están en la memoria del navegador (localStorage). Cada partida nueva de la página toma una semilla del reloj, así que su galaxia es distinta de la de los mapas de más abajo (esos usan la semilla 2026, la de la terminal por defecto). La partida guardada conserva la semilla.
La idea
Qué hay dentro
- Una galaxia de 12 a 20 sistemas y 3 o 4 imperios. Cada sistema tiene de uno a tres planetas. Hay cuatro recursos: metal (M), gas (G), cristal (C) y uranio (U).
- Planetas y edificios. Colonizas un planeta y construyes una mina (más recursos), un laboratorio (ciencia), un astillero (naves) y una fortaleza (defensa).
- Un árbol de tecnologías: trece tecnologías con requisitos, desde «Perforación profunda» hasta «Puerta estelar». No puedes investigar algo antes de haber investigado aquello de lo que depende.
- Flotas. Cuatro tipos de nave: interceptor, bombardero, fragata y acorazado. En combate el interceptor vence al bombardero, el bombardero vence a la fragata y la fragata vence al interceptor (piedra, papel, tijera). Las flotas se mueven por las rutas.
- Una batalla en la que los movimientos se resuelven a la vez. Todas las órdenes de un turno se cumplen juntas, no una tras otra.
- Rivales con inteligencia artificial y carácter. Señor de la guerra (ataca), Constructor (se expande y construye) y Erudito (persigue la ciencia). Cada uno sopesa qué le aporta más en este turno.
- Diplomacia: paz y guerra, con un tiempo mínimo de paz. Eventos aleatorios: un meteorito, piratas, disturbios, un descubrimiento y más.
- Victoria de tres maneras, guardado en tres ranuras y una simulación de miles de partidas solo de IA con la que se ajusta el equilibrio.
Toda la partida con la que se comprueba el juego son 192 comandos y 5175 líneas de salida: del primer turno al final.
La idea
El mapa del código
El juego es un archivo de unas 3900 líneas en cada lenguaje. Dentro está dividido en partes (regiones), y cada parte pertenece a una de seis capas:
| Capa | Partes | Líneas |
|---|---|---|
| Datos y textos | io-text text data data-load | 1023 |
| Entrada, salida, dibujo | random buffer terminal map-draw | 230 |
| Las pantallas y los comandos | screen screen-stack screens commands | 584 |
| El mundo: galaxia y tecnologías | world graph galaxy-gen tech-tree topo event-bus | 474 |
| Los imperios: flotas, economía, rivales | fleets battle economy diplomacy events ai-rivals turn victory | 1194 |
| Guardado, simulación, ejecución | save load simulate main node | 395 |
Los números son de la versión de JavaScript y se calculan al construir el sitio. Parte de esto ya lo conoces de Arcanum: el generador random, el búfer y las pantallas, la pila de pantallas y el bus de eventos son las mismas ideas. Lo nuevo está en las capas «El mundo» y «Los imperios». Esta lección trata de random, world, graph y galaxy-gen.
La idea
Un código, cuatro lenguajes, una salida
El juego está escrito cuatro veces: en Java, C#, Python y JavaScript, parte por parte y con los mismos nombres. La comprobación del sitio lo ejecuta en los cuatro lenguajes con los 192 comandos grabados (en búlgaro, inglés, alemán y español) y exige exactamente la misma salida, byte a byte. También ejecuta la simulación del equilibrio. Si una versión tira un dado de otra manera, la galaxia es otra y la comprobación falla.
Aquí está el mapa del primer turno (el comando map) de la galaxia con la semilla 2026. Los sistemas son [ 1 ] … [16], los puntos entre ellos son las rutas, y Aa, Bb, Cc y Dd son las capitales de los cuatro imperios.
Turno 1/150 Imperio Terrano (A) puntos 20M70+8 G60+4 C20+3 U5+1 ciencia +3No se investiga nada (r número). Ciencia acumulada: 0 [ 1]..........[ 2].. Aa . ...[ 3]........[ 4]..........[ 5] .. .. ..Bb . . . .... .. .. . [ 6] . .[ 8] . . [ 7]... . . . .. . . . . ...[10]........[11].....[12] . [ 9].... . . ... . . .. ... [13] Dd .... . .... . .. ... Cc .... . ... ... ... . [14]........[15] [16] . . .
A:Imperio Terra C:Unión de Lira D:Academia de V B:Hegemonía de
help: comandos end: fin del turno sys N: un sistemaY el sistema en el que empiezas (sys 1): dos planetas (uno es tuyo, con mina, laboratorio, astillero y fortaleza) y la primera flota.
Turno 1/150 Imperio Terrano (A) puntos 20M70+8 G60+4 C20+3 U5+1 ciencia +3No se investiga nada (r número). Ciencia acumulada: 0Sistema 1 Elara, estrella amarilla. Rutas a: 2Planeta 1 Elara I, oceánica (Imperio Terrano) riqueza M3 G3 C2 U1 minas 1 lab sí astillero sí fortaleza 1Planeta 2 Elara II, gigante gaseoso (libre) riqueza M1 G4 C1 U0Flota de Imperio Terrano: 3I 2B 2F
Enter o map: al mapa help: comandos¿Cómo sale la misma salida si cada lenguaje tiene su propio Random? El juego no usa el generador incorporado. Tiene uno propio, pequeño e igual en todas partes, solo con números enteros. Es el primer tema de la lección.
La idea
Ejecútalo en tu ordenador
El archivo entero está aquí: [Cosmos.java](/games/cosmos/es/Cosmos.java), [Cosmos.cs](/games/cosmos/es/Cosmos.cs), [cosmos.py](/games/cosmos/es/cosmos.py), [cosmos.js](/games/cosmos/es/cosmos.js). Ponlo en una carpeta vacía y ejecútalo:
python cosmos.pyEn la terminal el juego limpia la pantalla y usa colores. Con --plain imprime los fotogramas como texto simple. Con --seed=2026 la galaxia es siempre la misma (esa es también la semilla por defecto), y con --lang=es el juego está en español (también existen en y de). Con --simulate=200 juega 200 partidas solo de IA e imprime el equilibrio. Las partidas guardadas están en la carpeta saves junto al juego.
La idea
Cómo lo vamos a construir
El módulo son seis lecciones. Cada una toma una parte del juego, explica por qué es así y la construye con programas más pequeños que puedes ejecutar; después muestra esa misma parte en el archivo real.
- La galaxia a partir de una semilla (esta lección): un generador con semilla, estrellas y planetas, rutas como un grafo, conectividad.
- El árbol de tecnologías: un grafo dirigido sin ciclos, requisitos, orden topológico, qué se puede investigar ahora.
- Las flotas y la batalla espacial: resolver los movimientos a la vez, papeles de las naves, una simulación de batalla.
- Los rivales: imperios con inteligencia artificial, valoración de la utilidad, el carácter de un imperio.
- El turno de la galaxia: las fases de un turno, eventos aleatorios, diplomacia, el bus de eventos.
- Toda la estrategia: victoria, guardado, equilibrio con una simulación.
La idea
La semilla
El generador está en la región random del juego. Aquí está, como en el original:
# mulberry32: un generador pequeño con semilla. Solo enteros de 32 bits (máscara & 0xFFFFFFFF y un# imul manual), por eso da la misma secuencia en cada lenguaje.MASK32 = 0xFFFFFFFF
# Math.imul de JavaScript: el producto del que solo quedan los 32 bits bajos.def imul(a, b): return (a * b) & MASK32
# "x >>> 0" de JavaScript: un número a 32 bits sin signo (un no-número y el infinito pasan a ser 0).def to_uint32(value): if value != value or value == float('inf') or value == float('-inf'): return 0 return int(value) & MASK32
class Random: def __init__(self, seed): self.state = to_uint32(seed)
def next32(self): self.state = (self.state + 0x6D2B79F5) & MASK32 z = self.state z = imul(z ^ (z >> 15), z | 1) z = (z ^ (z + imul(z ^ (z >> 7), z | 61))) & MASK32 return (z ^ (z >> 14)) & MASK32
# De 0 a n-1, sin fracciones. def next_int(self, n): return self.next32() % n
# De min a max, ambos incluidos. def range(self, low, high): return low + self.next_int(high - low + 1)
def chance(self, percent): return self.next_int(100) < percent
# Mezcla la lista en el sitio (Fisher-Yates, de atrás hacia delante). def shuffle(self, items): i = len(items) - 1 while i > 0: j = self.next_int(i + 1) keep = items[i] items[i] = items[j] items[j] = keep i -= 1Solo tres líneas son el núcleo: next32 cambia un número (state) y deriva otro de él, nextInt(n) toma su resto al dividir por n, y range, chance y shuffle se construyen sobre nextInt. Entre dos llamadas no cambia nada más. Por eso dos copias del generador con el mismo número inicial (la semilla) dan la misma secuencia, y con otro número dan otra.
El programa lo muestra: tres generadores, dos con la semilla 2026 y uno con 2027, dan seis números cada uno de 0 a 99. Después se mezcla con shuffle una lista de ocho celdas, como el juego mezcla las celdas de la cuadrícula:
for seed in [2026, 2026, 2027]: rng = Random(seed) rolls = [rng.next_int(100) for _ in range(6)] print(f"semilla {seed}: {' '.join(str(v) for v in rolls)}")
cells = list(range(8))Random(2026).shuffle(cells)print(f"celdas mezcladas: {' '.join(str(v) for v in cells)}")semilla 2026: 75 58 22 36 57 62semilla 2026: 75 58 22 36 57 62semilla 2027: 50 47 63 23 32 32celdas mezcladas: 3 2 6 4 1 0 5 7Las dos primeras líneas son idénticas hasta el último número, y la tercera no tiene nada que ver con ellas. La mezcla es la misma en los cuatro lenguajes porque shuffle solo llama a nextInt en un orden estrictamente fijo: del final al principio, y en cada paso elige con quién intercambiar. Es el algoritmo de Fisher-Yates.
imul recorta el producto a 32 bits con una máscara. Sin eso los números seguirían creciendo y diferirían de los de los otros lenguajes.La idea
La galaxia es un grafo
Una galaxia son dos cosas: sistemas (estrellas con planetas) y rutas entre ellos, por las que se mueven las flotas. Una estructura así se llama grafo: los sistemas son los vértices y las rutas son las aristas. Una ruta va entre dos sistemas y vale en las dos direcciones.
La forma más sencilla de guardarlo es que cada sistema conozca a sus vecinos. Un sistema es una clase con un número, un lugar en el mapa y una lista links:
class StarSystem: def __init__(self, system_id, x, y): self.id = system_id self.x = x self.y = y self.links = []En el juego la misma clase está en la región world: tiene además un nombre, el color de la estrella (roja, amarilla o azul) y una lista de sus planetas.
class StarSystem: def __init__(self, system_id, name, x, y): self.id = system_id self.name = name self.x = x self.y = y # La clase de la estrella: 0 roja, 1 amarilla, 2 azul. self.cls = 1 self.links = [] self.planets = []Una ruta entre A y B significa que B está en la lista de A y A está en la lista de B. Por eso una ruta se añade con una función que escribe en dos sitios. Las listas se mantienen ordenadas por número: insertSorted inserta en el lugar correcto, no al final.
def insert_sorted(items, value): at = len(items) while at > 0 and items[at - 1] > value: at -= 1 items.insert(at, value)
def has_lane(systems, a, b): return b in systems[a].links
def add_lane(systems, a, b): insert_sorted(systems[a].links, b) insert_sorted(systems[b].links, a)El orden importa por una cosa: cuando el juego recorre los vecinos, los ve siempre en el mismo orden, en todos los lenguajes. Si estuvieran en el orden en que se añadieron, las distintas versiones llegarían a lo mismo por caminos distintos y las salidas diferirían.
El programa pone seis sistemas, añade las rutas en un orden revuelto e imprime los vecinos de cada uno. Los números de los sistemas en pantalla empiezan en 1, y en la memoria en 0: numbers suma 1 antes de mostrarlos.
systems = [StarSystem(i, i * 10, 0) for i in range(6)]lanes = [(4, 0), (0, 2), (0, 1), (2, 3), (3, 5), (1, 4)]for a, b in lanes: add_lane(systems, a, b)
for system in systems: print(f"sistema {system.id + 1}: {numbers(system.links)}")print("ruta 1-3: " + ("sí" if has_lane(systems, 0, 2) else "no"))print("ruta 1-4: " + ("sí" if has_lane(systems, 0, 3) else "no"))sistema 1: 2 3 5sistema 2: 1 5sistema 3: 1 4sistema 4: 3 6sistema 5: 1 2sistema 6: 4ruta 1-3: síruta 1-4: noMira el sistema 1: las rutas hacia los sistemas 5 (añadida primero), 3 y 2 se imprimen como «2 3 5», en orden ascendente, no en el orden en que se añadieron. Los sistemas 1 y 3 tienen una ruta, 1 y 4 no.
La idea
¿Está conectada la galaxia?
El juego solo tiene sentido si se puede llegar de cada sistema a cada uno de los demás. Si no, las flotas no pueden pasar y un imperio en una isla no se puede atacar. Queremos un grafo conexo: desde cada vértice hay un camino hasta cualquier otro.
La comprobación es la búsqueda en anchura (BFS). Empiezas en un sistema y lanzas una ola: primero el propio sistema está a distancia 0, luego sus vecinos a 1, los vecinos de estos a 2, y así sucesivamente. La cola guarda los sistemas que esperan su turno. Los sistemas a los que la ola no llega se quedan en −1.
def bfs(systems, start): dist = [-1] * len(systems) queue = [start] dist[start] = 0 head = 0 while head < len(queue): current = queue[head] head += 1 for nxt in systems[current].links: if dist[nxt] < 0: dist[nxt] = dist[current] + 1 queue.append(nxt) return distEl grafo es conexo exactamente cuando la ola desde el sistema 1 llega a todos: ningún −1.
def is_connected(systems): for d in bfs(systems, 0): if d < 0: return False return TrueEl programa hace dos «islas» (sistemas 1 a 4 y 5 a 7), imprime las distancias desde el sistema 1 y si está conectada. Luego añade una ruta entre ellas:
systems = [StarSystem(i, i * 10, 0) for i in range(7)]lanes = [(0, 1), (1, 2), (2, 3), (4, 5), (5, 6)]for a, b in lanes: add_lane(systems, a, b)print("distancias desde el sistema 1: " + " ".join(str(d) for d in bfs(systems, 0)))print("conectada: " + ("sí" if is_connected(systems) else "no"))
add_lane(systems, 3, 4)print("distancias desde el sistema 1: " + " ".join(str(d) for d in bfs(systems, 0)))print("conectada: " + ("sí" if is_connected(systems) else "no"))distancias desde el sistema 1: 0 1 2 3 -1 -1 -1conectada: nodistancias desde el sistema 1: 0 1 2 3 4 5 6conectada: síAntes de la ruta, los sistemas 5, 6 y 7 están en −1: la ola no pasó. Después de la ruta entre 4 y 5 la ola llega a ellos con las distancias 4, 5 y 6.
def is_connected(systems):
for d in bfs(systems, 0):
if d < :
return False
return TrueUn sistema no alcanzado se queda en −1, así que la comprobación busca un número menor que cero. Si compruebas d == 0, solo encontrarás el inicio; con d > 0, casi cualquier sistema.
En el juego la misma función está en la región graph, pero la búsqueda guarda además el padre de cada sistema: aquel desde el que se descubrió. Retrocediendo por los padres se obtiene el camino más corto:
# Búsqueda en anchura desde un sistema: distancia en rutas (-1 es inalcanzable) y padre en el camino.def bfs(systems, start): dist = [-1] * len(systems) parent = [-1] * len(systems) queue = [start] dist[start] = 0 head = 0 while head < len(queue): current = queue[head] head += 1 for nxt in systems[current].links: if dist[nxt] < 0: dist[nxt] = dist[current] + 1 parent[nxt] = current queue.append(nxt) return SimpleNamespace(dist=dist, parent=parent)# El camino más corto como lista de sistemas, con los dos extremos; vacío si no hay camino.def shortest_path(systems, start, to): result = bfs(systems, start) if result.dist[to] < 0: return [] path = [to] current = to while current != start: current = result.parent[current] path.append(current) path.reverse() return pathEl juego usa este camino cuando una flota va hacia un destino lejano: go 1 9 no dice por qué sistemas pasar, y en cada turno la flota da el siguiente paso del camino más corto (nextStep). La inteligencia artificial de los rivales usa la misma función.
Un detalle que es honesto decir: isConnected está en el original, pero el juego mismo nunca la llama. La conectividad está garantizada por el árbol, y la función sirve para comprobar, como la del programa de arriba y la del ejercicio de abajo.
La idea
Estrellas en una cuadrícula
Ahora hagamos la galaxia en sí. Los sistemas no se lanzan a puntos aleatorios del mapa: algunos se amontonarían unos sobre otros y otros quedarían solos en el vacío. El juego usa una cuadrícula: el mapa tiene 5 columnas por 4 filas, 20 celdas. De ellas se eligen de 12 a 20, y en cada celda elegida la estrella está en un lugar aleatorio.
COLS = 5ROWS = 4CELL_W = 12CELL_H = 4
def place_stars(rng, count): cells = list(range(COLS * ROWS)) rng.shuffle(cells) chosen = cells[:count] chosen.sort() systems = [] for i in range(count): col = chosen[i] % COLS row = chosen[i] // COLS x = col * CELL_W + rng.next_int(6) y = row * CELL_H + rng.next_int(2) systems.append(StarSystem(i, x, y)) return systemsTres pasos: shuffle mezcla los números de las celdas, se toman las primeras count y se ordenan (para que los sistemas queden numerados de izquierda a derecha y de arriba abajo), y en cada celda la estrella recibe un pequeño desplazamiento aleatorio. Las celdas mantienen separadas a las estrellas, y el azar las hace distintas de una partida a otra.
En el juego la cantidad de sistemas no viene dada. La primera tirada del generador la decide: 12 + nextInt(9) es un número de 12 a 20.
La idea
Rutas: primero el árbol, luego las adicionales
Queda decidir qué estrellas se conectan. Si pones rutas en pares al azar, no puedes estar seguro de que nada quede en una isla. Si pones todas las rutas, el mapa se vuelve una telaraña. El juego usa una solución en dos pasos.
Primero un árbol. Empiezas en el sistema 1. En cada paso buscas la ruta más corta desde un sistema del árbol hasta un sistema fuera de él y la añades. El sistema nuevo entra en el árbol. Repites hasta que entren todos. Este algoritmo se llama árbol de expansión mínimo (Prim). El árbol tiene exactamente número de sistemas − 1 rutas, y está claro por qué el grafo es conexo: cada sistema nuevo entra con una ruta hacia los ya conectados.
Luego las adicionales. Un árbol no tiene ciclos: entre dos sistemas hay un único recorrido, y puede ser largo. Por eso cada sistema recibe también una ruta hacia el sistema más cercano con el que aún no tiene ninguna, pero solo si ese está lo bastante cerca, ninguno de los dos tiene ya 4 rutas y la tirada del dado es menor que 55 %. Salen recorridos circulares y una elección.
La distancia es el cuadrado de la distancia, sin raíz (solo comparamos cuál es menor): dy se multiplica por 3 porque los caracteres de la consola son más altos que anchos.
def squared_distance(a, b): dx = a.x - b.x dy = (a.y - b.y) * 3 return dx * dx + dy * dydef connect(systems, rng): count = len(systems) in_tree = [False] * count in_tree[0] = True for step in range(1, count): best_a = -1 best_b = -1 best_d = 0 for a in range(count): if not in_tree[a]: continue for b in range(count): if in_tree[b]: continue d = squared_distance(systems[a], systems[b]) if best_a < 0 or d < best_d: best_a = a best_b = b best_d = d add_lane(systems, best_a, best_b) in_tree[best_b] = True for a in range(count): best = -1 best_d = 0 for b in range(count): if b == a or has_lane(systems, a, b): continue d = squared_distance(systems[a], systems[b]) if best < 0 or d < best_d: best = b best_d = d if best >= 0 and best_d <= 420 and len(systems[a].links) < 4 and len(systems[best].links) < 4 and rng.chance(55): add_lane(systems, a, best)Dos detalles hacen que la salida sea igual. Con distancias iguales gana la primera encontrada (d < bestD, no <=), es decir, el número menor. Y la probabilidad (rng.chance(55)) va la última en la condición con &&: el dado solo se tira para una ruta que de otro modo se añadiría. Si se tirara antes, las dos variantes serían razonables, pero cada tirada toma un número del generador y todo lo posterior cambiaría: de las mismas semillas saldrían otras galaxias.
Míralo
La galaxia en movimiento
Los doce sistemas de la galaxia con la semilla 18. Fíjate en los contadores de arriba: las islas bajan de 12 a 1 mientras crecen las rutas del árbol; luego vienen las rutas adicionales en otro color y por último la ola de la búsqueda.
def connect(systems, rng): count = len(systems) in_tree = [False] * count in_tree[0] = True for step in range(1, count): best_a = -1 best_b = -1 best_d = 0 for a in range(count): if not in_tree[a]: continue for b in range(count): if in_tree[b]: continue d = squared_distance(systems[a], systems[b]) if best_a < 0 or d < best_d: best_a = a best_b = b best_d = d add_lane(systems, best_a, best_b) in_tree[best_b] = True for a in range(count): best = -1 best_d = 0 for b in range(count): if b == a or has_lane(systems, a, b): continue d = squared_distance(systems[a], systems[b]) if best < 0 or d < best_d: best = b best_d = d if best >= 0 and best_d <= 420 and len(systems[a].links) < 4 and len(systems[best].links) < 4 and rng.chance(55): add_lane(systems, a, best)def connect(systems, rng): count = len(systems) in_tree = [False] * count in_tree[0] = True for step in range(1, count): best_a = -1 best_b = -1 best_d = 0 for a in range(count): if not in_tree[a]: continue for b in range(count): if in_tree[b]: continue d = squared_distance(systems[a], systems[b]) if best_a < 0 or d < best_d: best_a = a best_b = b best_d = d add_lane(systems, best_a, best_b) in_tree[best_b] = True for a in range(count): best = -1 best_d = 0 for b in range(count): if b == a or has_lane(systems, a, b): continue d = squared_distance(systems[a], systems[b]) if best < 0 or d < best_d: best = b best_d = d if best >= 0 and best_d <= 420 and len(systems[a].links) < 4 and len(systems[best].links) < 4 and rng.chance(55): add_lane(systems, a, best)def bfs(systems, start): dist = [-1] * len(systems) queue = [start] dist[start] = 0 head = 0 while head < len(queue): current = queue[head] head += 1 for nxt in systems[current].links: if dist[nxt] < 0: dist[nxt] = dist[current] + 1 queue.append(nxt) return dist
def is_connected(systems): for d in bfs(systems, 0): if d < 0: return False return TruePaso a paso, en palabras
- 12 estrellas en una cuadrícula de 5 por 4 (20 celdas): las celdas elegidas se encienden. Aún no hay ninguna ruta, así que cada sistema es una isla: 12 islas.
- Primero el árbol de expansión mínimo (Prim). Empieza en el sistema 1. En cada paso se busca la ruta más corta desde un sistema del árbol hasta uno que está fuera.
- La ruta encontrada se añade y el sistema nuevo entra en el árbol. Tras 5 rutas quedan 7 islas: cada ruta une dos islas en una.
- 11 rutas y una isla. Cada sistema nuevo entra con exactamente una ruta, así que ninguno queda solo: la galaxia está conectada antes de las rutas adicionales.
- Luego las rutas adicionales (otro color): hacia el sistema no conectado más cercano, si está cerca, tiene menos de 4 rutas y la tirada es menor que 55 %. Salen 3 rutas alternativas.
- La comprobación: búsqueda en anchura desde el sistema 1. La ola avanza capa por capa y anota la distancia de cada sistema en rutas (0, 1, 2…).
- Ni un solo −1: la ola llegó a los 12 sistemas, así que la galaxia está conectada. Con la misma semilla este dibujo es el mismo cada vez.
La idea
La galaxia entera a partir de una semilla
Queda juntarlo todo: semilla, número de sistemas, estrellas, rutas. La función galaxy(seed) es todo el generador. La segunda función, describe, convierte una galaxia en texto: así dos galaxias se comparan con un solo ==.
def galaxy(seed): rng = Random(seed) count = 12 + rng.next_int(9) systems = place_stars(rng, count) connect(systems, rng) return systems
def describe(systems): text = "" for system in systems: text += f"{system.id + 1} ({system.x},{system.y}): {numbers(system.links)}\n" return textEl programa hace la galaxia con la semilla 18 (12 sistemas, 14 rutas: 11 del árbol y 3 adicionales), la hace otra vez con la misma semilla y con la siguiente, y al final comprueba 200 semillas distintas:
systems = galaxy(18)print(describe(systems), end="")lanes = sum(len(system.links) for system in systems) // 2print(f"rutas: {lanes} ({lanes - len(systems) + 1} adicionales)")print("conectada: " + ("sí" if is_connected(systems) else "no"))
first = describe(systems)print("la misma semilla otra vez, la misma galaxia: " + ("sí" if describe(galaxy(18)) == first else "no"))print("otra semilla, otra galaxia: " + ("sí" if describe(galaxy(19)) != first else "no"))
ok = 0for seed in range(1, 201): if is_connected(galaxy(seed)): ok += 1print("semillas 1-200: conectadas " + str(ok) + " de 200")1 (5,5): 22 (12,4): 1 5 63 (36,5): 4 6 74 (50,5): 35 (17,9): 2 6 96 (24,8): 2 3 5 77 (37,8): 3 6 11 128 (3,12): 99 (17,12): 5 8 1010 (27,12): 911 (40,12): 7 1212 (53,12): 7 11rutas: 14 (3 adicionales)conectada: síla misma semilla otra vez, la misma galaxia: síotra semilla, otra galaxia: sísemillas 1-200: conectadas 200 de 200Aquí importan tres cosas. Primera: la misma semilla es la misma galaxia hasta la última coordenada. Segunda: la semilla siguiente es una galaxia totalmente distinta. Tercera: las 200 son conexas: no es suerte, sino consecuencia del árbol. Esta comprobación es una pequeña prueba de propiedad: no preguntamos «cómo es esta galaxia», sino «¿es cierto para cada galaxia que es conexa?».
Así es la función real del juego. Hace lo mismo, pero además da un nombre a cada estrella (los nombres se mezclan con otro shuffle) y un color (roja, amarilla o azul), y trabaja sobre el mundo compartido world:
def generate_systems(world, count): rng = world.rng cells = [] for i in range(MAP_COLS * MAP_ROWS): cells.append(i) rng.shuffle(cells) chosen = cells[:count] chosen.sort() names = [] for i in range(len(STAR_NAMES)): names.append(i) rng.shuffle(names) for i in range(count): col = chosen[i] % MAP_COLS row = chosen[i] // MAP_COLS x = col * CELL_W + rng.next_int(6) y = row * CELL_H + rng.next_int(2) system = StarSystem(i, STAR_NAMES[names[i]], x, y) system.cls = rng.next_int(3) world.systems.append(system) # El árbol de expansión mínimo (Prim): con distancias iguales gana el número menor. in_tree = [False] * count in_tree[0] = True for step in range(1, count): best_a = -1 best_b = -1 best_d = 0 for a in range(count): if not in_tree[a]: continue for b in range(count): if in_tree[b]: continue d = squared_distance(world.systems[a], world.systems[b]) if best_a < 0 or d < best_d: best_a = a best_b = b best_d = d add_lane(world.systems, best_a, best_b) in_tree[best_b] = True # Rutas adicionales: hacia el vecino más cercano aún no enlazado, si no está demasiado lejos. for a in range(count): best = -1 best_d = 0 for b in range(count): if b == a or has_lane(world.systems, a, b): continue d = squared_distance(world.systems[a], world.systems[b]) if best < 0 or d < best_d: best = b best_d = d if best >= 0 and best_d <= 420 and len(world.systems[a].links) < 4 and len(world.systems[best].links) < 4 and rng.chance(55): add_lane(world.systems, a, best)Todo lo que el juego sabe vive en la clase World: la semilla, el generador, los sistemas, los planetas, los imperios y las flotas. Por eso la partida guardada está en un solo lugar y newWorld(seed) es lo único que hace una galaxia:
class World: def __init__(self, seed): self.seed = seed self.rng = Random(seed) self.turn = 1 self.systems = [] self.planets = [] self.empires = [] self.fleets = [] self.queue = [] self.offers = [] self.news = [] self.turn_lines = [] self.bus = EventBus() self.victory = None self.fort_left = {} self.stats = SimpleNamespace(battles=0, lost=0, colonies=0, techs=0, events=0) self.last = SimpleNamespace(battle=[]) self.quiet = False self.alert = 0 self.pace = 100
def living_count(self): n = 0 for e in self.empires: if e.alive: n += 1 return nY cómo la usa newWorld. La semilla se convierte en el mundo: el número de sistemas, las rutas, luego las capitales de los imperios y los planetas, y por último cada imperio recibe un planeta natal:
# El mundo entero desde una semilla. human es el jugador (en la simulación no hay), personalities es una lista# opcional de caracteres, uno por imperio.def new_world(seed, human, personalities, quiet): load_data() world = World(seed) world.quiet = quiet world.pace = RIVAL_PACE if human else 100 install_subscribers(world, quiet) rng = world.rng count = 12 + rng.next_int(9) generate_systems(world, count) rivals = 2 + rng.next_int(2) if count >= 15 else 2 defs = [0] pool = [1, 2, 3] rng.shuffle(pool) for i in range(rivals): defs.append(pool[i]) capitals = pick_capitals(world, len(defs)) generate_planets(world, capitals) for i in range(len(defs)): empire = Empire(i, EMPIRE_DEFS[defs[i]], len(defs)) if personalities is not None: empire.personality = PERSONALITIES[personalities[i]] empire.human = human and i == 0 world.empires.append(empire) place_homeworld(world, empire, capitals[i]) return worldLas capitales se eligen con una búsqueda en anchura: la primera es el sistema más a la izquierda, y cada siguiente es la más lejana (por rutas) de las ya elegidas. Así los imperios empiezan lo más lejos posible unos de otros:
# Las capitales: la primera es el sistema más a la izquierda; cada siguiente es la más lejana (por rutas) de las ya elegidas.def pick_capitals(world, count): chosen = [] first = 0 for system in world.systems: if system.x < world.systems[first].x: first = system.id chosen.append(first) nearest = list(bfs(world.systems, first).dist) while len(chosen) < count: best = -1 for system in world.systems: if system.id in chosen: continue if best < 0 or nearest[system.id] > nearest[best]: best = system.id chosen.append(best) d = bfs(world.systems, best).dist for i in range(len(nearest)): if d[i] < nearest[i]: nearest[i] = d[i] return chosenLa idea
Planetas con pesos
Cada sistema tiene de uno a tres planetas, y no todos son igual de probables: un planeta tiene un 30 % de probabilidad, dos tienen un 45 %, tres un 25 %. El tipo de planeta también tiene pesos (rocoso, gigante gaseoso, helado, oceánico, volcánico). Necesitamos una función que elija un elemento según su peso.
La idea: tiras un número de 0 hasta la suma de los pesos y recorres la lista restando el peso de cada elemento, hasta que la tirada sea menor que el peso actual.
def pick_weighted(rng, weights): total = 0 for w in weights: total += w roll = rng.next_int(total) for i in range(len(weights)): if roll < weights[i]: return i roll -= weights[i] return len(weights) - 1Con los pesos 30, 45 y 25 la suma es 100. Una tirada de 0 a 29 es el índice 0, de 30 a 74 el índice 1, de 75 a 99 el índice 2. El programa tira 1000 veces (los planetas son índice + 1) y luego toma por separado el número de planetas de los primeros ocho sistemas:
weights = [30, 45, 25]rng = Random(2026)counts = [0, 0, 0]for _ in range(1000): counts[pick_weighted(rng, weights)] += 1print(f"planetas en 1000 sistemas: 1={counts[0]} 2={counts[1]} 3={counts[2]}")
few = Random(7)planets = [pick_weighted(few, weights) for _ in range(8)]print(f"los primeros 8 sistemas: {numbers(planets)}")planetas en 1000 sistemas: 1=299 2=467 3=234los primeros 8 sistemas: 2 3 2 2 3 3 1 1De 1000 sistemas, alrededor del 30 %, 45 % y 25 % tienen 1, 2 y 3 planetas. No es exacto: los pesos son probabilidades, no cuotas. Pero con la misma semilla los números son siempre los mismos.
Un planeta es una clase con un tipo, riqueza en los cuatro recursos y un dueño:
class Planet: def __init__(self, planet_id, system_id, index, type_index, rich): self.id = planet_id self.system_id = system_id self.index = index self.type_index = type_index self.rich = rich self.owner = -1 self.mines = 0 self.lab = 0 self.yard = 0 self.fort = 0 self.siege = 0El generatePlanets real usa la misma función dos veces: para la cantidad y para el tipo de cada planeta. Luego tira un número más para cada recurso (riqueza de 0 a 4), y el color de la estrella suma uno a un recurso: la roja al gas, la amarilla al metal, la azul al cristal.
def generate_planets(world, capitals): rng = world.rng type_weights = [] for ptype in PLANET_TYPES: type_weights.append(ptype.weight) for system in world.systems: is_capital = system.id in capitals roll = pick_weighted(rng, [30, 45, 25]) + 1 count = 2 if is_capital and roll < 2 else roll for index in range(count): type_index = pick_weighted(rng, type_weights) ptype = PLANET_TYPES[type_index] rich = [] for r in range(RES_COUNT): value = clamp(ptype.base[r] + rng.next_int(3) - 1, 0, 4) rich.append(value) # La estrella pesa: la roja da gas, la amarilla metal, la azul cristal. if system.cls == 0: rich[1] = min_of(5, rich[1] + 1) elif system.cls == 1: rich[0] = min_of(5, rich[0] + 1) else: rich[2] = min_of(5, rich[2] + 1) planet = Planet(len(world.planets), system.id, index, type_index, rich) world.planets.append(planet) system.planets.append(planet.id)Pruébalo
Predice la salida
Seis sistemas, numerados desde 0. Las rutas son 0-1, 1-2, 2-3, 0-4, 4-3 y 3-5: un anillo de cinco sistemas y uno más colgado de él. ¿Qué imprime el programa?
systems = [StarSystem(i, i * 10, 0) for i in range(6)]lanes = [(0, 1), (1, 2), (2, 3), (0, 4), (4, 3), (3, 5)]for a, b in lanes: add_lane(systems, a, b)print(" ".join(str(d) for d in bfs(systems, 0)))El sistema 0 está a 0. Sus vecinos 1 y 4 están a 1. Desde 1 se llega a 2 (a 2) y desde 4 a 3 (también a 2): un atajo por 4, no por 1 y 2 (eso sería 3). Desde 3 se llega a 5 (a 3). Los números van en el orden de los sistemas: «0 1 2 2 1 3». La segunda opción ignora la ruta 4-3; la tercera es la respuesta correcta con las distancias contadas desde 1.
Pruébalo
Encuentra el error
Un compañero cambió una línea en el bucle del árbol. El programa hace galaxias a partir de 200 semillas y cuenta las conexas. Antes eran las 200, ahora son:
def connect(systems, rng): count = len(systems) in_tree = [False] * count in_tree[0] = True for step in range(1, count - 1): best_a = -1 best_b = -1 best_d = 0 for a in range(count): if not in_tree[a]: continue for b in range(count): if in_tree[b]: continue d = squared_distance(systems[a], systems[b]) if best_a < 0 or d < best_d: best_a = a best_b = b best_d = d add_lane(systems, best_a, best_b) in_tree[best_b] = True for a in range(count): best = -1 best_d = 0 for b in range(count): if b == a or has_lane(systems, a, b): continue d = squared_distance(systems[a], systems[b]) if best < 0 or d < best_d: best = b best_d = d if best >= 0 and best_d <= 420 and len(systems[a].links) < 4 and len(systems[best].links) < 4 and rng.chance(55): add_lane(systems, a, best)
ok = 0for seed in range(1, 201): if is_connected(galaxy(seed)): ok += 1print("semillas 1-200: conectadas " + str(ok) + " de 200")semillas 1-200: conectadas 150 de 200¿Qué línea tiene la culpa?
Elige la línea con el error.
El bucle del árbol se queda un paso corto: count − 1 en vez de count, así que el último sistema nunca entra en el árbol. Si las rutas adicionales lo conectan por casualidad (la probabilidad es del 55 % y tiene que estar cerca), la galaxia es conexa; si no, queda una isla. La prueba de propiedad atrapó justo eso: en 50 de las 200 galaxias. Lo correcto es step < count: los pasos son el número de sistemas menos uno (de 1 a count − 1).
Más precisamente
Lo que no hay en este sistema
Una galaxia a partir de una semilla tiene pocas reglas, pero detrás hay decisiones.
El árbol es sencillo. El algoritmo de Prim aquí tiene tres bucles anidados: para un árbol de 20 sistemas son unos pocos miles de comparaciones. En un grafo mayor (millones de vértices) se usa una cola de prioridad y Prim va en O(E log V). Aquí el bucle simple es más corto, fácil de leer e igual en los cuatro lenguajes.
Las rutas adicionales no están garantizadas. Por eso algunas galaxias son casi árboles: cadenas largas sin rodeos. Es una decisión para el juego: esos mapas son más tácticos (un paso clave que vigilar). Cuántas rutas adicionales hay (55 %, como mucho 4 por sistema, cerca) se ajusta con una simulación, igual que el equilibrio.
La conectividad es una elección, no una ley. En otros juegos las islas están bien: no todo es alcanzable. Aquí es al revés: la conectividad es una condición del juego. Por eso conviene comprobarla, como hace el programa con 200 semillas.
La semilla no es toda la historia. La misma semilla da la misma galaxia solo mientras el generador llame a nextInt en el mismo orden. Si añades una tirada nueva al principio, cambian todas las galaxias de todas las semillas antiguas, y las partidas guardadas antiguas se cargan en un mundo distinto. Por eso en un juego real un cambio en la generación debe ser un cambio de versión: la partida guardada tiene una versión de formato justo para casos así.
Las rutas valen en las dos direcciones. El grafo aquí no es dirigido. El árbol de tecnologías (la lección siguiente) es distinto: «A debe ir antes que B» vale en un solo sentido. Allí el grafo es dirigido.
Ejercicio
Islas
Resuelve la tarea en tu editor.
Islas. El programa lee en la primera línea de la entrada el número de sistemas n y el número de rutas m, y luego m líneas con dos números cada una (desde 1). Imprime cuántas islas tiene la galaxia (las islas son grupos de sistemas conectados entre sí), cuántos sistemas tiene la isla más grande y si la galaxia es conexa.
Con la entrada 8 5 | 1 2 | 2 3 | 4 5 | 6 7 | 7 8 (una por línea) la salida es:
islas: 3isla más grande: 3conectada: noPista: lanza una búsqueda en anchura desde el primer sistema que aún no se haya visto y marca todo lo que alcance. Las veces que empieces de nuevo son las islas que hay.
Más tareas
- El camino más corto. Amplía el programa para que lea dos números más e imprima el camino más corto entre ellos por los sistemas, o «no hay camino» si no existe. El padre de cada sistema es la clave.
- ¿Cuántas rutas añadir? ¿Cuál es el menor número de rutas que hay que añadir para que una galaxia con
kislas sea conexa? Prueba con algunos ejemplos y encuentra la regla. - ¿Cuántas semillas no son conexas sin el árbol? Quita el bucle del árbol y ejecuta la comprobación con 200 semillas. ¿Cuántas galaxias quedan conectadas solo por las rutas adicionales?
Test