1package main23import (4 "encoding/json"5 "fmt"6 "math"7 "sort"8 "strings"9)1011// Some maps are published as one tile sheet holding several places. Tears of12// the Kingdom stacks three elevations of one Hyrule; the Mojave Wasteland rings13// its main map with eight district insets. In both the split is already in the14// data -- the top-level regions are the pieces, and every location names one --15// so the sheet can be taken apart rather than shown whole.16//17// Which maps those are is declared rather than detected. Breath of the Wild has18// fifteen top-level regions and Palworld forty-two, and those are areas of one19// continuous map: sharding them would shatter it. Nothing in the data separates20// Mojave's nine leaf regions from Hyrule's fifteen, so guessing is not an option.21type shardMode int2223const (24 shardNone shardMode = iota25 // shardIntoWorlds gives each piece its own entry in the map picker. Use it26 // when the pieces are unrelated places that happen to share a sheet.27 shardIntoWorlds28 // shardIntoLenses keeps one map and offers the pieces as layers, so the29 // view survives switching between them. Use it when the pieces are the same30 // ground at different heights.31 shardIntoLenses32)3334var shardedWorlds = map[int64]shardMode{35 602: shardIntoWorlds, // Mojave Wasteland: eight district insets in the margins36 536: shardIntoLenses, // Hyrule: Sky, Surface and Depths of one world37}3839type shard struct {40 Region rawRegion41 Locations map[int64]bool42 Regions map[int64]bool43 // Bounds is in the shared world pixel space the tile pyramid uses.44 Bounds contentBounds45 // Surface is the same box before it was grown into the space around it: the46 // ground the piece's regions actually cover, without the margin the raster47 // keeps so a title banner is not sliced in half.48 Surface contentBounds49 Center coordinate50}5152// planShards groups a map's regions and locations under their top-level region.53//54// A piece is sized by the ground its regions cover, not by the locations55// assigned to it. A handful of locations sit outside the region that claims56// them -- forty on the Mojave sheet -- and stretching a piece to reach them57// pulled the main map back over the very insets it was being split away from.58// Locations are not clipped by these bounds, only the raster is, so a stray one59// stays reachable just beyond the edge of its map.60func planShards(raw rawMap, grid tileGrid, mode shardMode) ([]shard, error) {61 regions := make(map[int64]rawRegion, len(raw.Regions))62 for _, region := range raw.Regions {63 regions[region.ID] = region64 }65 rootOf := func(id int64) (int64, bool) {66 seen := make(map[int64]bool)67 for {68 region, ok := regions[id]69 if !ok {70 return 0, false71 }72 if region.ParentRegionID == nil || seen[id] {73 return id, true74 }75 seen[id] = true76 id = *region.ParentRegionID77 }78 }7980 byRoot := make(map[int64]*shard)81 take := func(id int64) *shard {82 if existing, ok := byRoot[id]; ok {83 return existing84 }85 created := &shard{86 Region: regions[id],87 Locations: make(map[int64]bool),88 Regions: make(map[int64]bool),89 }90 byRoot[id] = created91 return created92 }9394 extents := make(map[int64]*[4]float64)95 grow := func(root int64, x, y float64) {96 box, ok := extents[root]97 if !ok {98 box = &[4]float64{math.Inf(1), math.Inf(1), math.Inf(-1), math.Inf(-1)}99 extents[root] = box100 }101 box[0], box[1] = math.Min(box[0], x), math.Min(box[1], y)102 box[2], box[3] = math.Max(box[2], x), math.Max(box[3], y)103 }104105 for _, region := range raw.Regions {106 root, ok := rootOf(region.ID)107 if !ok {108 continue109 }110 piece := take(root)111 piece.Regions[region.ID] = true112 for _, feature := range region.Features {113 for _, point := range flattenCoordinates(feature.Geometry.Coordinates) {114 x, y := projectPoint(point[1], point[0], grid)115 grow(root, x, y)116 }117 }118 }119120 var orphans int121 placed := make(map[int64][2]float64)122 for _, group := range raw.Groups {123 for _, category := range group.Categories {124 for _, location := range category.Locations {125 if location.RegionID == nil {126 orphans++127 continue128 }129 root, ok := rootOf(*location.RegionID)130 if !ok {131 orphans++132 continue133 }134 latitude, err := number(location.Latitude)135 if err != nil {136 return nil, err137 }138 longitude, err := number(location.Longitude)139 if err != nil {140 return nil, err141 }142 take(root).Locations[location.ID] = true143 placed[location.ID] = [2]float64{projectX(longitude, grid), projectY(latitude, grid)}144 _, _ = latitude, longitude145 }146 }147 }148 if orphans > 0 {149 return nil, fmt.Errorf("%d locations belong to no region, so they would vanish when split", orphans)150 }151152 boxes := make([][4]float64, 0, len(byRoot))153 order := make([]int64, 0, len(byRoot))154 for root := range byRoot {155 box := extents[root]156 if box == nil || math.IsInf(box[0], 1) {157 continue158 }159 boxes = append(boxes, *box)160 order = append(order, root)161 }162 grown := growIntoGaps(boxes, float64(grid.Size))163164 pieces := make([]shard, 0, len(byRoot))165 for index, root := range order {166 piece := byRoot[root]167 left, top, right, bottom := grown[index][0], grown[index][1], grown[index][2], grown[index][3]168 // Bounds are measured down from the top of the world, matching how the169 // viewer clips the raster.170 piece.Bounds = contentBounds{171 X: int(left),172 Y: int(top),173 Width: int(right - left),174 Height: int(bottom - top),175 }176 box := boxes[index]177 piece.Surface = contentBounds{178 X: int(box[0]),179 Y: int(box[1]),180 Width: int(box[2] - box[0]),181 Height: int(box[3] - box[1]),182 }183 piece.Center = coordinate{184 Latitude: unprojectLatitude((top+bottom)/2, grid),185 Longitude: unprojectLongitude((left+right)/2, grid),186 }187 pieces = append(pieces, *piece)188 }189 rehomeStrays(pieces, placed)190 orderShards(pieces, mode)191 if len(pieces) < 2 {192 return nil, fmt.Errorf("only %d top-level region, nothing to split", len(pieces))193 }194 return pieces, nil195}196197// orderShards puts the pieces in the order they are offered. Layers read down198// the way they are stacked, so the sky comes before the ground beneath it.199// Separate places lead with the largest, so a sheet's main map heads its insets.200// rehomeStrays moves a location to the piece it is actually drawn on.201//202// Some locations name a region they do not sit in: on the Mojave sheet forty203// claim the main map while lying inside the panels around it. Trusting the204// claim left them floating in the dark beside the map they were split from,205// exactly where their panel used to be. Where a location sits is not in doubt,206// so position decides and the claim is treated as the mistake it is.207// growIntoGaps widens each piece into the empty space around it, stopping208// halfway to whatever it would otherwise run into.209//210// A region outlines the ground it covers, not the art drawn around it. Tears of211// the Kingdom titles each of its layers with a banner sitting just above the212// region, so cropping to the outline alone sliced the words in half. Claiming213// the space between pieces takes the banner with the layer it names, while214// stopping at the midpoint keeps the Mojave sheet's panels -- barely twenty215// pixels apart -- from showing a slice of their neighbour.216func growIntoGaps(boxes [][4]float64, world float64) [][4]float64 {217 // Far enough to reach a title banner, short enough that an isolated piece218 // does not swallow the sheet around it.219 const reach = 256220 grown := make([][4]float64, len(boxes))221 for index, box := range boxes {222 room := [4]float64{reach, reach, reach, reach}223 for other, rival := range boxes {224 if other == index {225 continue226 }227 // Only pieces sharing a span on the other axis can be run into.228 if overlaps(box[1], box[3], rival[1], rival[3]) {229 if rival[2] <= box[0] {230 room[0] = math.Min(room[0], (box[0]-rival[2])/2)231 }232 if rival[0] >= box[2] {233 room[2] = math.Min(room[2], (rival[0]-box[2])/2)234 }235 }236 if overlaps(box[0], box[2], rival[0], rival[2]) {237 if rival[3] <= box[1] {238 room[1] = math.Min(room[1], (box[1]-rival[3])/2)239 }240 if rival[1] >= box[3] {241 room[3] = math.Min(room[3], (rival[1]-box[3])/2)242 }243 }244 }245 grown[index] = [4]float64{246 math.Max(0, box[0]-room[0]),247 math.Max(0, box[1]-room[1]),248 math.Min(world, box[2]+room[2]),249 math.Min(world, box[3]+room[3]),250 }251 }252 separate(grown, boxes)253 return grown254}255256// separate undoes the growth where two pieces met in a corner. Pieces that257// share no span on either axis do not hold each other back, so both can expand258// into the same diagonal space. Whichever way they now overlap least is the way259// they are eased apart.260//261// Only the growth is ever given back. Easing two pieces apart used to be free262// to cut into the ground a piece was cut for, which took the bottom border off263// the Camp McCarran panel: the crop stopped inside the frame the panel is drawn264// with. Where two pieces genuinely cover the same ground they are left265// overlapping, because that is the sheet saying so, not the crop.266func separate(boxes, floors [][4]float64) {267 for pass := 0; pass < len(boxes); pass++ {268 clear := true269 for a := range boxes {270 for b := a + 1; b < len(boxes); b++ {271 across := math.Min(boxes[a][2], boxes[b][2]) - math.Max(boxes[a][0], boxes[b][0])272 down := math.Min(boxes[a][3], boxes[b][3]) - math.Max(boxes[a][1], boxes[b][1])273 if across <= 0 || down <= 0 {274 continue275 }276 clear = false277 if across <= down {278 give(&boxes[a], &boxes[b], across/2, 0)279 } else {280 give(&boxes[a], &boxes[b], down/2, 1)281 }282 hold(&boxes[a], floors[a])283 hold(&boxes[b], floors[b])284 }285 }286 if clear {287 return288 }289 }290}291292// hold keeps a box around the ground it was grown from.293func hold(box *[4]float64, floor [4]float64) {294 box[0] = math.Min(box[0], floor[0])295 box[1] = math.Min(box[1], floor[1])296 box[2] = math.Max(box[2], floor[2])297 box[3] = math.Max(box[3], floor[3])298}299300// give pulls two boxes back from each other along one axis, axis 0 across and301// axis 1 down.302func give(a, b *[4]float64, by float64, axis int) {303 low, high := axis, axis+2304 if a[low] < b[low] {305 a[high] -= by306 b[low] += by307 return308 }309 b[high] -= by310 a[low] += by311}312313func overlaps(lowA, highA, lowB, highB float64) bool {314 return lowA < highB && lowB < highA315}316317func rehomeStrays(pieces []shard, placed map[int64][2]float64) {318 inside := func(piece shard, at [2]float64) bool {319 b := piece.Bounds320 return at[0] >= float64(b.X) && at[0] <= float64(b.X+b.Width) &&321 at[1] >= float64(b.Y) && at[1] <= float64(b.Y+b.Height)322 }323 moved, homeless := 0, 0324 for index := range pieces {325 for id := range pieces[index].Locations {326 at, known := placed[id]327 if !known || inside(pieces[index], at) {328 continue329 }330 hosts := make([]int, 0, 2)331 for other := range pieces {332 if other != index && inside(pieces[other], at) {333 hosts = append(hosts, other)334 }335 }336 // Only an unambiguous home is worth moving to: a location inside two337 // overlapping pieces has not told us anything the claim did not.338 if len(hosts) != 1 {339 homeless++340 continue341 }342 delete(pieces[index].Locations, id)343 pieces[hosts[0]].Locations[id] = true344 moved++345 }346 }347 if moved > 0 {348 fmt.Printf(" moved %d locations to the piece they are drawn on\n", moved)349 }350 if homeless > 0 {351 fmt.Printf(" %d locations sit on no piece and stay where they were claimed\n", homeless)352 }353}354355func orderShards(pieces []shard, mode shardMode) {356 sort.Slice(pieces, func(a, b int) bool {357 if mode == shardIntoLenses {358 if pieces[a].Bounds.Y != pieces[b].Bounds.Y {359 return pieces[a].Bounds.Y < pieces[b].Bounds.Y360 }361 return pieces[a].Region.Title < pieces[b].Region.Title362 }363 areaA := pieces[a].Bounds.Width * pieces[a].Bounds.Height364 areaB := pieces[b].Bounds.Width * pieces[b].Bounds.Height365 if areaA != areaB {366 return areaA > areaB367 }368 return pieces[a].Region.Title < pieces[b].Region.Title369 })370}371372func flattenCoordinates(raw json.RawMessage) [][2]float64 {373 var value any374 if err := json.Unmarshal(raw, &value); err != nil {375 return nil376 }377 var out [][2]float64378 var walk func(any)379 walk = func(node any) {380 list, ok := node.([]any)381 if !ok {382 return383 }384 if len(list) == 2 {385 x, xOK := list[0].(float64)386 y, yOK := list[1].(float64)387 if xOK && yOK {388 out = append(out, [2]float64{x, y})389 return390 }391 }392 for _, child := range list {393 walk(child)394 }395 }396 walk(value)397 return out398}399400// projectPoint mirrors the viewer's projection so bounds land in the same world401// pixel space the tile pyramid and the raster clip already use.402func projectPoint(latitude, longitude float64, grid tileGrid) (float64, float64) {403 return projectX(longitude, grid), projectY(latitude, grid)404}405406func projectX(longitude float64, grid tileGrid) float64 {407 worldTiles := math.Pow(2, float64(grid.SourceZoom))408 xTile := ((longitude + 180) / 360) * worldTiles409 return (xTile - float64(grid.FirstTile)) * float64(grid.TileSize)410}411412func projectY(latitude float64, grid tileGrid) float64 {413 worldTiles := math.Pow(2, float64(grid.SourceZoom))414 yTile := (1 - math.Asinh(math.Tan(latitude*math.Pi/180))/math.Pi) / 2 * worldTiles415 return (yTile - float64(grid.FirstTile)) * float64(grid.TileSize)416}417418func unprojectLongitude(x float64, grid tileGrid) float64 {419 worldTiles := math.Pow(2, float64(grid.SourceZoom))420 xTile := x/float64(grid.TileSize) + float64(grid.FirstTile)421 return (xTile/worldTiles)*360 - 180422}423424func unprojectLatitude(y float64, grid tileGrid) float64 {425 worldTiles := math.Pow(2, float64(grid.SourceZoom))426 yTile := y/float64(grid.TileSize) + float64(grid.FirstTile)427 return math.Atan(math.Sinh(math.Pi*(1-2*yTile/worldTiles))) * 180 / math.Pi428}429430// splitWorld takes a sheet apart when one is declared for it, and otherwise431// hands back the single map it was given.432func splitWorld(m catalogWorld, raw rawMap, grid tileGrid) ([]catalogWorld, error) {433 mode := shardedWorlds[m.ID]434 if mode == shardNone {435 return []catalogWorld{m}, nil436 }437 pieces, err := planShards(raw, grid, mode)438 if err != nil {439 return nil, fmt.Errorf("split %s: %w", m.Title, err)440 }441 if mode == shardIntoLenses {442 return []catalogWorld{asVariants(m, pieces)}, nil443 }444 return asMaps(m, pieces), nil445}446447// asMaps gives each piece its own map. The largest keeps the sheet's name and448// leads; the rest are named after it so they sort together in the picker449// instead of scattering among the game's standalone maps.450func asMaps(m catalogWorld, pieces []shard) []catalogWorld {451 out := make([]catalogWorld, 0, len(pieces))452 for index, piece := range pieces {453 copied := m454 copied.Collections = keepShapeFeatures(455 keepPointFeatures(m.Collections, piece.Locations),456 piece.Regions, piece.Region.ID,457 )458 copied.Center = piece.Center459 copied.Lenses = boundVariants(m.Lenses, piece.Bounds, piece.Surface, 0)460 if index > 0 {461 copied.ID = piece.Region.ID462 copied.Title = m.Title + " — " + piece.Region.Title463 copied.Slug = m.Slug + "-" + slugify(piece.Region.Title)464 copied.Parent = m.Slug465 }466 out = append(out, copied)467 }468 return out469}470471// asVariants keeps one map and offers the pieces as layers. Locations and zones472// carry the piece they belong to so the viewer can show one layer at a time,473// and the view survives switching because the map itself never changes.474func asVariants(m catalogWorld, pieces []shard) catalogWorld {475 var variants []lens476 var dropped []int64477 for _, piece := range pieces {478 bound := boundVariants(m.Lenses, piece.Bounds, piece.Surface, piece.Region.ID)479 for index := range bound {480 bound[index].Name = piece.Region.Title481 }482 variants = append(variants, bound...)483 for collectionIndex := range m.Collections {484 collection := &m.Collections[collectionIndex]485 claims := piece.Regions486 if collection.Kind == kindPoint {487 claims = piece.Locations488 }489 for featureIndex := range collection.Features {490 if claims[collection.Features[featureIndex].ID] {491 collection.Features[featureIndex].Shard = piece.Region.ID492 }493 }494 }495 dropped = append(dropped, piece.Region.ID)496 }497 m.Lenses = variants498 m.Collections = keepShapeFeatures(m.Collections, nil, dropped...)499 if len(pieces) > 0 {500 m.Center = pieces[0].Center501 }502 return m503}504505// boundVariants clips each raster to the piece. The tiles are the same pyramid506// either way; only the window onto it changes. The ground the piece covers507// travels alongside the window, because they are not the same rectangle and508// anything measuring the map rather than drawing it wants the ground.509func boundVariants(variants []lens, bounds, surface contentBounds, shardID int64) []lens {510 // Easing two pieces apart can pull a window in past the ground it grew511 // from, and what the grid divides has to be drawn, so the ground is clipped512 // to the window rather than reaching beyond it.513 ground := intersectBounds(surface, bounds)514 out := make([]lens, 0, len(variants))515 for _, source := range variants {516 clipped := source517 clipped.Bounds = &contentBounds{518 X: bounds.X, Y: bounds.Y, Width: bounds.Width, Height: bounds.Height,519 }520 clipped.Surface = &contentBounds{521 X: ground.X, Y: ground.Y, Width: ground.Width, Height: ground.Height,522 }523 clipped.Shard = shardID524 out = append(out, clipped)525 }526 return out527}528529// The window a raster is cut from is not the ground the map is about. Several530// sheets are drawn inside a printed border or a wide margin of nothing -- Zion531// Canyon and Tunic sit in the middle of a full-world window -- and dividing532// that window into thirty-two named cells spends most of them on blank paper.533//534// So what the grid divides is measured from the map's own contents: where its535// locations are, and the ground its regions outline. That is the archive536// answering for each map rather than a list of maps to treat specially, and it537// says the same thing about a border whether the border is solid or patterned.538func markSurfaces(m *catalogWorld, grid tileGrid) {539 for index := range m.Lenses {540 variant := &m.Lenses[index]541 window := worldBounds(grid)542 if variant.Bounds != nil {543 window = *variant.Bounds544 }545 box, ok := contentExtent(*m, variant.Shard, window, grid)546 if !ok {547 continue548 }549 if variant.Surface != nil {550 box = unionBounds(*variant.Surface, box)551 }552 box = intersectBounds(box, window)553 variant.Surface = &box554 }555}556557// contentExtent is where a map's own contents lie, in the world pixel space the558// tiles are cut in and measured down from the top of it, as the raster clip is.559// Anything drawn outside the window is left out of the reckoning: a few560// locations sit off the sheet entirely -- three of Marathon's eighty -- and one561// of those would stretch the ground back over everything it had just left out.562func contentExtent(m catalogWorld, shard int64, window contentBounds, grid tileGrid) (contentBounds, bool) {563 left, top := math.Inf(1), math.Inf(1)564 right, bottom := math.Inf(-1), math.Inf(-1)565 found := false566 grow := func(x, y float64) {567 if x < float64(window.X) || y < float64(window.Y) ||568 x > float64(window.X+window.Width) || y > float64(window.Y+window.Height) {569 return570 }571 left, top = math.Min(left, x), math.Min(top, y)572 right, bottom = math.Max(right, x), math.Max(bottom, y)573 found = true574 }575576 for _, collection := range m.Collections {577 for _, f := range collection.Features {578 if shard != 0 && f.Shard != shard {579 continue580 }581 if collection.Kind == kindPoint {582 x, y := projectPoint(f.Lat, f.Lng, grid)583 grow(x, y)584 continue585 }586 for _, part := range f.Geometry {587 for _, point := range flattenCoordinates(part.Coordinates) {588 x, y := projectPoint(point[1], point[0], grid)589 grow(x, y)590 }591 }592 }593 }594 if !found {595 return contentBounds{}, false596 }597598 // A margin, so the outermost location sits inside a cell rather than along599 // its edge, and so a map drawn right up to its own border keeps a little of600 // what surrounds it.601 margin := math.Max(32, 0.02*math.Max(right-left, bottom-top))602 return contentBounds{603 X: int(left - margin),604 Y: int(top - margin),605 Width: int((right - left) + margin*2),606 Height: int((bottom - top) + margin*2),607 }, true608}609610func worldBounds(grid tileGrid) contentBounds {611 return contentBounds{Width: grid.Size, Height: grid.Size}612}613614func unionBounds(a, b contentBounds) contentBounds {615 left, top := min(a.X, b.X), min(a.Y, b.Y)616 right, bottom := max(a.X+a.Width, b.X+b.Width), max(a.Y+a.Height, b.Y+b.Height)617 return contentBounds{X: left, Y: top, Width: right - left, Height: bottom - top}618}619620// intersectBounds is the overlap of two rectangles, or the second of them where621// they do not meet at all.622func intersectBounds(a, b contentBounds) contentBounds {623 left, top := max(a.X, b.X), max(a.Y, b.Y)624 right, bottom := min(a.X+a.Width, b.X+b.Width), min(a.Y+a.Height, b.Y+b.Height)625 if right <= left || bottom <= top {626 return b627 }628 return contentBounds{X: left, Y: top, Width: right - left, Height: bottom - top}629}630631// keepPointFeatures pares each point collection down to the piece's own pins.632// A collection left with none is dropped, which is also what empties a group633// out of the piece's payload: no collection carries its number any more.634func keepPointFeatures(collections []worldCollection, wanted map[int64]bool) []worldCollection {635 out := make([]worldCollection, 0, len(collections))636 for _, collection := range collections {637 if collection.Kind != kindPoint {638 out = append(out, collection)639 continue640 }641 kept := make([]feature, 0, len(collection.Features))642 for _, pin := range collection.Features {643 if wanted[pin.ID] {644 kept = append(kept, pin)645 }646 }647 if len(kept) == 0 {648 continue649 }650 collection.Features = kept651 out = append(out, collection)652 }653 return out654}655656// keepShapeFeatures drops the piece's own outline. Once a region has been657// used to cut a map or a layer out of a sheet, drawing it again just traces658// the edge of what the reader is already looking at.659func keepShapeFeatures(collections []worldCollection, wanted map[int64]bool, drop ...int64) []worldCollection {660 discard := make(map[int64]bool, len(drop))661 for _, id := range drop {662 discard[id] = true663 }664 out := make([]worldCollection, 0, len(collections))665 for _, collection := range collections {666 if collection.Kind == kindPoint {667 out = append(out, collection)668 continue669 }670 kept := make([]feature, 0, len(collection.Features))671 for _, shape := range collection.Features {672 if discard[shape.ID] || (wanted != nil && !wanted[shape.ID]) {673 continue674 }675 kept = append(kept, shape)676 }677 if len(kept) == 0 {678 continue679 }680 collection.Features = kept681 out = append(out, collection)682 }683 return out684}685686func slugify(value string) string {687 return strings.Trim(strings.Map(func(r rune) rune {688 switch {689 case r >= 'a' && r <= 'z', r >= '0' && r <= '9':690 return r691 case r >= 'A' && r <= 'Z':692 return r + ('a' - 'A')693 default:694 return '-'695 }696 }, value), "-")697}