1package main23import (4 "context"5 "encoding/json"6 "errors"7 "fmt"8 "math"9 "strconv"10 "strings"11)1213// A layer usually publishes the window its tiles occupy at each zoom, and the14// crawl asks for what is inside it. Some games publish none at all -- Fallout15// 76 and Marathon among them -- and a crawl with no window to read had nothing16// to ask for and captured nothing.17//18// What every map does say is where it opens, and that point is on the map by19// definition. So the shallowest level is found by fetching the tile under it20// and spreading outward from whatever answers, until the frontier runs out.21// The levels below need no window of their own: they follow the tiles that22// held content, which is what a published layer does after its first level too.2324// searchBudget caps the spread. The shallowest level of a map is a handful of25// tiles -- Appalachia is one -- so a search that has read this many has26// misread something, and should stop rather than walk the whole world.27const searchBudget = 5122829// foundWindow is where a layer's tiles turned out to be, and which way round30// they had to be asked for to find them.31type foundWindow struct {32 window tileWindow33 transposed bool34 found bool35}3637// searchWindow spreads outward from the tile the map opens on. Neighbours are38// taken in all eight directions, so a coastline meeting a corner does not end39// the search early.40func searchWindow(41 ctx context.Context,42 fetcher *fetcher,43 base string,44 set apiTileSet,45 zoom int,46 centre [2]int,47 extension string,48) (foundWindow, error) {49 // The two axes are published the other way round on some layers, and with50 // no window to compare neighbours in there is nothing yet to measure that51 // against. The tile the map opens on settles it instead: whichever way52 // round answers is the way the search reads the rest.53 for _, transposed := range []bool{false, true} {54 exists, err := tileExists(ctx, fetcher, base, set, zoom, centre, extension, transposed)55 if err != nil {56 return foundWindow{}, err57 }58 if !exists {59 continue60 }61 window, err := spread(ctx, fetcher, base, set, zoom, centre, extension, transposed)62 if err != nil {63 return foundWindow{}, err64 }65 return foundWindow{window: window, transposed: transposed, found: true}, nil66 }67 return foundWindow{}, nil68}6970func spread(71 ctx context.Context,72 fetcher *fetcher,73 base string,74 set apiTileSet,75 zoom int,76 centre [2]int,77 extension string,78 transposed bool,79) (tileWindow, error) {80 span := 1 << zoom81 window := tileWindow{minX: centre[0], minY: centre[1], maxX: centre[0], maxY: centre[1]}82 tested := map[[2]int]bool{centre: true}83 queue := [][2]int{centre}8485 for len(queue) > 0 && len(tested) <= searchBudget {86 at := queue[0]87 queue = queue[1:]88 if at != centre {89 exists, err := tileExists(ctx, fetcher, base, set, zoom, at, extension, transposed)90 if err != nil {91 return tileWindow{}, err92 }93 if !exists {94 continue95 }96 }97 window.minX, window.minY = min(window.minX, at[0]), min(window.minY, at[1])98 window.maxX, window.maxY = max(window.maxX, at[0]), max(window.maxY, at[1])99 for dy := -1; dy <= 1; dy++ {100 for dx := -1; dx <= 1; dx++ {101 next := [2]int{at[0] + dx, at[1] + dy}102 if (dx == 0 && dy == 0) || tested[next] ||103 next[0] < 0 || next[1] < 0 || next[0] >= span || next[1] >= span {104 continue105 }106 tested[next] = true107 queue = append(queue, next)108 }109 }110 }111 return window, nil112}113114func tileExists(115 ctx context.Context,116 fetcher *fetcher,117 base string,118 set apiTileSet,119 zoom int,120 at [2]int,121 extension string,122 transposed bool,123) (bool, error) {124 first, second := at[0], at[1]125 if transposed {126 first, second = second, first127 }128 url := fmt.Sprintf("%s/games/%s/%d/%d/%d.%s", base, set.Path, zoom, first, second, extension)129 if _, _, err := fetcher.get(ctx, url); err != nil {130 if errors.Is(err, errAbsent) {131 return false, nil132 }133 return false, err134 }135 return true, nil136}137138// childWindow is where the next level down can hold anything, given what the139// level above turned out to hold. It stands in for a published window on a140// layer that has none.141func childWindow(live map[[2]int]bool) (tileWindow, bool) {142 first := true143 var window tileWindow144 for parent := range live {145 left, top := parent[0]*2, parent[1]*2146 if first {147 window = tileWindow{minX: left, minY: top, maxX: left + 1, maxY: top + 1}148 first = false149 continue150 }151 window.minX, window.minY = min(window.minX, left), min(window.minY, top)152 window.maxX, window.maxY = max(window.maxX, left+1), max(window.maxY, top+1)153 }154 return window, !first155}156157// startTile is the tile holding the point the map opens on, in the same158// projection the tile pyramid is cut in.159func startTile(full *apiMapFull, zoom int) ([2]int, bool) {160 latitude, ok := numberValue(full.InitialLatitude)161 if !ok {162 return [2]int{}, false163 }164 longitude, ok := numberValue(full.InitialLongitude)165 if !ok {166 return [2]int{}, false167 }168 span := float64(int(1) << zoom)169 x := (longitude + 180) / 360 * span170 y := (1 - math.Asinh(math.Tan(latitude*math.Pi/180))/math.Pi) / 2 * span171 if math.IsNaN(x) || math.IsNaN(y) {172 return [2]int{}, false173 }174 limit := (1 << zoom) - 1175 return [2]int{176 min(max(int(x), 0), limit),177 min(max(int(y), 0), limit),178 }, true179}180181// numberValue reads a JSON number that the archive has also been seen to quote.182func numberValue(raw json.RawMessage) (float64, bool) {183 text := strings.Trim(strings.TrimSpace(string(raw)), `"`)184 if text == "" || text == "null" {185 return 0, false186 }187 value, err := strconv.ParseFloat(text, 64)188 if err != nil {189 return 0, false190 }191 return value, true192}