1package netwalk23import (4 "errors"5 "math"6 "math/rand/v2"7)89const maxGenerateAttempts = 641011type generateProfile struct {12 ParentDegreeWeights [5]int13 OrthogonalPackedWeight int14 DiagonalPackedWeight int15 SpanGrowthWeight int16 MinSpanRatio float6417}1819var legacyGenerateProfile = generateProfile{20 ParentDegreeWeights: [5]int{16, 16, 8, -2, -4},21}2223func Generate(size, targetActive int) (Puzzle, error) {24 return GenerateSeeded(size, targetActive, rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64())))25}2627func GenerateSeeded(size, targetActive int, rng *rand.Rand) (Puzzle, error) {28 return generateSeededWithProfile(size, targetActive, legacyGenerateProfile, rng)29}3031func GenerateSeededWithDensity(size int, fillRatio float64, profile generateProfile, rng *rand.Rand) (Puzzle, error) {32 return generateSeededWithProfile(size, targetActiveFromFillRatio(size, fillRatio), profile, rng)33}3435func generateSeededWithProfile(size, targetActive int, profile generateProfile, rng *rand.Rand) (Puzzle, error) {36 if size <= 1 {37 return Puzzle{}, errors.New("netwalk size must be at least 2")38 }39 if targetActive < 2 {40 targetActive = 241 }42 if targetActive > size*size {43 targetActive = size * size44 }4546 for attempt := 0; attempt < maxGenerateAttempts; attempt++ {47 puzzle := buildTreePuzzle(size, targetActive, profile, rng)48 scramblePuzzle(&puzzle, rng)49 if !analyzePuzzle(puzzle).solved {50 return puzzle, nil51 }52 }5354 return Puzzle{}, errors.New("failed to generate netwalk puzzle")55}5657type frontierEdge struct {58 from point59 to point60}6162type activeBounds struct {63 minX int64 maxX int65 minY int66 maxY int67}6869func buildTreePuzzle(size, targetActive int, profile generateProfile, rng *rand.Rand) Puzzle {70 puzzle := newPuzzle(size)71 root := point{X: size / 2, Y: size / 2}72 puzzle.Root = root7374 active := map[point]struct{}{root: {}}75 adjacency := map[point]directionMask{root: 0}7677 for len(active) < targetActive {78 bounds := measureActiveBounds(active)79 frontier := collectFrontier(size, active)80 if len(frontier) == 0 {81 break82 }8384 edge := frontier[weightedFrontierIndex(size, frontier, active, adjacency, bounds, profile, rng)]85 active[edge.to] = struct{}{}86 adjacency[edge.to] = 08788 dir := directionBetween(edge.from, edge.to)89 adjacency[edge.from] |= dir90 adjacency[edge.to] |= opposite(dir)91 }9293 for p := range active {94 kind := nodeCell95 if p == root {96 kind = serverCell97 }98 puzzle.Tiles[p.Y][p.X] = tile{99 BaseMask: adjacency[p],100 Kind: kind,101 }102 }103104 return puzzle105}106107func collectFrontier(size int, active map[point]struct{}) []frontierEdge {108 frontier := make([]frontierEdge, 0, len(active)*2)109 for y := range size {110 for x := range size {111 cell := point{X: x, Y: y}112 if _, ok := active[cell]; !ok {113 continue114 }115 for _, dir := range directions {116 next := point{X: cell.X + dir.dx, Y: cell.Y + dir.dy}117 if next.X < 0 || next.X >= size || next.Y < 0 || next.Y >= size {118 continue119 }120 if _, ok := active[next]; ok {121 continue122 }123 frontier = append(frontier, frontierEdge{from: cell, to: next})124 }125 }126 }127 return frontier128}129130func targetActiveFromFillRatio(size int, fillRatio float64) int {131 if size <= 1 {132 return 2133 }134 target := int(math.Round(float64(size*size) * fillRatio))135 if target < 2 {136 return 2137 }138 if target > size*size {139 return size * size140 }141 return target142}143144func measureActiveBounds(active map[point]struct{}) activeBounds {145 first := true146 bounds := activeBounds{}147 for p := range active {148 if first {149 bounds = activeBounds{minX: p.X, maxX: p.X, minY: p.Y, maxY: p.Y}150 first = false151 continue152 }153 if p.X < bounds.minX {154 bounds.minX = p.X155 }156 if p.X > bounds.maxX {157 bounds.maxX = p.X158 }159 if p.Y < bounds.minY {160 bounds.minY = p.Y161 }162 if p.Y > bounds.maxY {163 bounds.maxY = p.Y164 }165 }166 return bounds167}168169func (b activeBounds) spanX() int {170 return b.maxX - b.minX + 1171}172173func (b activeBounds) spanY() int {174 return b.maxY - b.minY + 1175}176177func weightedFrontierIndex(178 size int,179 frontier []frontierEdge,180 active map[point]struct{},181 adjacency map[point]directionMask,182 bounds activeBounds,183 profile generateProfile,184 rng *rand.Rand,185) int {186 if len(frontier) == 1 {187 return 0188 }189190 weights := make([]int, len(frontier))191 total := 0192 for i, edge := range frontier {193 weight := frontierWeight(size, edge, active, adjacency, bounds, profile)194 weights[i] = weight195 total += weight196 }197198 pick := rng.IntN(total)199 running := 0200 for i, weight := range weights {201 running += weight202 if pick < running {203 return i204 }205 }206 return len(frontier) - 1207}208209func frontierWeight(210 size int,211 edge frontierEdge,212 active map[point]struct{},213 adjacency map[point]directionMask,214 bounds activeBounds,215 profile generateProfile,216) int {217 deg := degree(adjacency[edge.from])218 if deg >= len(profile.ParentDegreeWeights) {219 deg = len(profile.ParentDegreeWeights) - 1220 }221222 weight := 64 + profile.ParentDegreeWeights[deg]223 orthogonal, diagonal := packedNeighborCounts(size, edge, active)224 weight += orthogonal * profile.OrthogonalPackedWeight225 weight += diagonal * profile.DiagonalPackedWeight226 weight += spanGrowthScore(size, edge.to, bounds, profile)227 if weight < 1 {228 return 1229 }230 return weight231}232233func packedNeighborCounts(234 size int,235 edge frontierEdge,236 active map[point]struct{},237) (int, int) {238 orthogonal := 0239 diagonal := 0240 for _, dir := range directions {241 next := point{X: edge.to.X + dir.dx, Y: edge.to.Y + dir.dy}242 if next == edge.from || !inBounds(size, next) {243 continue244 }245 if _, ok := active[next]; ok {246 orthogonal++247 }248 }249250 for _, delta := range [][2]int{{-1, -1}, {1, -1}, {1, 1}, {-1, 1}} {251 next := point{X: edge.to.X + delta[0], Y: edge.to.Y + delta[1]}252 if !inBounds(size, next) {253 continue254 }255 if _, ok := active[next]; ok {256 diagonal++257 }258 }259 return orthogonal, diagonal260}261262func spanGrowthScore(size int, candidate point, bounds activeBounds, profile generateProfile) int {263 target := minSpanTarget(size, profile.MinSpanRatio)264 if target == 0 || profile.SpanGrowthWeight == 0 {265 return 0266 }267268 score := 0269 if bounds.spanX() < target && (candidate.X < bounds.minX || candidate.X > bounds.maxX) {270 score += profile.SpanGrowthWeight271 }272 if bounds.spanY() < target && (candidate.Y < bounds.minY || candidate.Y > bounds.maxY) {273 score += profile.SpanGrowthWeight274 }275 return score276}277278func minSpanTarget(size int, ratio float64) int {279 if size <= 0 || ratio <= 0 {280 return 0281 }282 target := int(math.Ceil(float64(size) * ratio))283 if target < 1 {284 return 1285 }286 if target > size {287 return size288 }289 return target290}291292func inBounds(size int, p point) bool {293 return p.X >= 0 && p.X < size && p.Y >= 0 && p.Y < size294}295296func scramblePuzzle(puzzle *Puzzle, rng *rand.Rand) {297 if puzzle == nil {298 return299 }300301 changed := 0302 nonEmpty := 0303 for y := range puzzle.Size {304 for x := range puzzle.Size {305 t := &puzzle.Tiles[y][x]306 if !isActive(*t) {307 continue308 }309 nonEmpty++310 options := uniqueRotations(t.BaseMask)311 rotation := options[rng.IntN(len(options))]312 t.Rotation = rotation313 t.InitialRotation = rotation314 if rotation != 0 {315 changed++316 }317 }318 }319320 if changed > 0 || nonEmpty == 0 {321 return322 }323324 active := make([]point, 0, nonEmpty)325 for y := range puzzle.Size {326 for x := range puzzle.Size {327 if isActive(puzzle.Tiles[y][x]) {328 active = append(active, point{X: x, Y: y})329 }330 }331 }332 for _, p := range active {333 t := &puzzle.Tiles[p.Y][p.X]334 options := uniqueRotations(t.BaseMask)335 if len(options) <= 1 {336 continue337 }338 t.Rotation = options[1%len(options)]339 t.InitialRotation = t.Rotation340 return341 }342}343344func directionBetween(from, to point) directionMask {345 switch {346 case to.X == from.X && to.Y == from.Y-1:347 return north348 case to.X == from.X+1 && to.Y == from.Y:349 return east350 case to.X == from.X && to.Y == from.Y+1:351 return south352 case to.X == from.X-1 && to.Y == from.Y:353 return west354 default:355 return 0356 }357}358359func opposite(mask directionMask) directionMask {360 switch mask {361 case north:362 return south363 case east:364 return west365 case south:366 return north367 case west:368 return east369 default:370 return 0371 }372}