1package tiles23import (4 "encoding/base64"5 "errors"6 "fmt"7 "image"8 "image/color"9 "image/draw"10 "image/jpeg"11 "image/png"12 "io"13 "os"14 "path/filepath"15 "sort"16 "strconv"17 "strings"1819 // WebP sources decode through image.Decode like any other. Go encodes none,20 // so levels folded down from one are written as JPEG or PNG.21 _ "golang.org/x/image/webp"22)2324// Deriving a pyramid, once a plan has decided what it is.25//26// The shape of the work is one rule and its consequences. The deepest complete27// captured level is the one to trust: it is copied through byte for byte,28// because re-encoding cannot add detail a capture never had and for the29// JPEG-sourced game maps it only stores compression noise at a larger size.30// Every shallower level is folded down from the level above it -- not taken from31// whatever intermediate levels the capture happens to hold, which are separately32// encoded pictures of varying completeness. Partial levels above the complete one33// are copied while they stay contiguous, and a reader falls back to the parent34// tile wherever coverage says nothing.35//36// A level's background tile is found once, on the level we trust, and omitted37// everywhere. Reusing one hash across every level keeps a sparse deep level from38// having its handful of real tiles voted "background" by its own majority, and39// skipping the omission entirely when no flat colour could be sampled means a40// hole is never left that nothing can paint over.4142// Derive builds one pyramid under root and reports it as a register entry. The43// entry carries no stamp: stamping is the caller's, because a caller that44// carried a pyramid over rather than deriving it stamps the same way.45func Derive(root string, plan Plan) (Pyramid, error) {46 // A warped variant is derived from another picture rather than from its own47 // capture: it has no complete level of its own to fold down, so it renders48 // its deepest level first and then folds down like anything else.49 if plan.Warp != nil {50 return deriveWarp(root, plan)51 }52 maxZoom := plan.MaxSourceZoom - plan.Frame.BaseZoom53 fullZoom := plan.MaxFullZoom - plan.Frame.BaseZoom54 formats := make([]string, maxZoom+1)55 coverage := make(map[string]*Coverage)5657 drawn, err := drawingFor(plan, fullZoom)58 if err != nil {59 return Pyramid{}, err60 }6162 full := plan.Levels[plan.MaxFullZoom]63 filler := placeholder(full)64 backgroundHex, err := placeholderColor(full, filler)65 if err != nil {66 return Pyramid{}, err67 }68 if backgroundHex == "" {69 // Nothing flat enough to stand in for the omitted tiles, so nothing is70 // omitted: a hole nobody can paint over is worse than a duplicated tile.71 filler = ""72 }73 background := parseHex(backgroundHex)7475 format, mask, err := writeLevel(root, plan, plan.MaxFullZoom, fullZoom, full, filler, drawn)76 if err != nil {77 return Pyramid{}, err78 }79 formats[fullZoom] = format80 if mask != nil {81 coverage[strconv.Itoa(fullZoom)] = mask82 }8384 for localZoom := fullZoom - 1; localZoom >= 0; localZoom-- {85 derived := plan.Format86 if !plan.Interpolate || derived == "png" {87 derived = "png"88 }89 // A WebP source level copies through as it came, but nothing here90 // encodes WebP, so the levels folded down from it take JPEG.91 if derived == "webp" {92 derived = "jpg"93 }94 mask, err := deriveLevel(root, plan.Name, localZoom,95 formats[localZoom+1], derived, !plan.Interpolate, background)96 if err != nil {97 return Pyramid{}, err98 }99 formats[localZoom] = derived100 if mask != nil {101 coverage[strconv.Itoa(localZoom)] = mask102 }103 }104105 // Partially captured levels above the complete one. These have gaps by106 // definition. A level that survives with nothing in it ends the pyramid:107 // advertising a zoom with no tiles would only produce misses.108 for localZoom := fullZoom + 1; localZoom <= maxZoom; localZoom++ {109 sourceZoom := localZoom + plan.Frame.BaseZoom110 format, mask, err := writeLevel(root, plan, sourceZoom, localZoom, plan.Levels[sourceZoom], filler, nil)111 if err != nil {112 return Pyramid{}, err113 }114 if mask == nil {115 maxZoom = localZoom - 1116 formats = formats[:localZoom]117 break118 }119 formats[localZoom] = format120 coverage[strconv.Itoa(localZoom)] = mask121 }122123 if len(coverage) == 0 {124 coverage = nil125 }126 sourceZoom, firstTile := plan.Frame.Window()127 return Pyramid{128 TileSet: plan.TileSet,129 Name: plan.Name,130 MinZoom: 0,131 MaxZoom: maxZoom,132 FullZoom: fullZoom,133 SourceZoom: plan.MaxSourceZoom,134 Window: Window{SourceZoom: sourceZoom, FirstTile: firstTile},135 Formats: formats,136 Bounds: plan.Bounds,137 Interpolate: plan.Interpolate,138 Background: backgroundHex,139 Coverage: coverage,140 LensName: plan.LensName,141 AlignedWith: plan.AlignedWith,142 }, nil143}144145// writeLevel puts one whole level on disk, omitting tiles that are copies of146// the level's background. A level is either copied from the capture or drawn147// from the source's own vectors; which one it is, is the only difference148// between the two paths, and everything downstream of here cannot tell.149func writeLevel(150 root string,151 plan Plan,152 sourceZoom, localZoom int,153 tiles []Tile,154 filler string,155 drawn *drawing,156) (string, *Coverage, error) {157 if len(tiles) == 0 {158 return "", nil, fmt.Errorf("captured level %d holds no tile", sourceZoom)159 }160 format := tiles[0].Format161 for _, tile := range tiles {162 if tile.Format != format {163 return "", nil, fmt.Errorf("captured level %d mixes %s and %s", sourceZoom, format, tile.Format)164 }165 }166 origin := plan.Frame.Origin(sourceZoom)167 span := 1 << localZoom168 mask := &coverageMask{total: span * span}169170 if drawn != nil {171 if format != "png" {172 return "", nil, fmt.Errorf(173 "level %d is drawn, and a drawing is written as PNG, not %s", sourceZoom, format)174 }175 if err := drawn.level(root, plan.Name, localZoom, origin, tiles, filler, mask); err != nil {176 return "", nil, err177 }178 return format, mask.build(), nil179 }180181 for _, tile := range tiles {182 if filler != "" && tile.Ref.ContentHash == filler {183 continue184 }185 x, y := tile.Ref.X-origin, tile.Ref.Y-origin186 if err := copyFile(tile.Path, tilePath(root, plan.Name, localZoom, x, y, format)); err != nil {187 return "", nil, err188 }189 mask.mark(x, y)190 }191 return format, mask.build(), nil192}193194// deriveLevel folds the level above down by two. Parents with no surviving195// children are skipped, so omitted background propagates down the pyramid.196func deriveLevel(197 root, name string,198 zoom int,199 childFormat, format string,200 nearest bool,201 background color.Color,202) (*Coverage, error) {203 childRoot := filepath.Join(root, name, strconv.Itoa(zoom+1))204 parents := make(map[[2]int]bool)205 err := filepath.WalkDir(childRoot, func(path string, entry os.DirEntry, walkErr error) error {206 if errors.Is(walkErr, os.ErrNotExist) {207 return nil208 }209 if walkErr != nil {210 return walkErr211 }212 if entry.IsDir() || normalizeExt(filepath.Ext(path)) != childFormat {213 return nil214 }215 y, err := strconv.Atoi(strings.TrimSuffix(entry.Name(), filepath.Ext(entry.Name())))216 if err != nil {217 return fmt.Errorf("read child row from %s: %w", path, err)218 }219 x, err := strconv.Atoi(filepath.Base(filepath.Dir(path)))220 if err != nil {221 return fmt.Errorf("read child column from %s: %w", path, err)222 }223 parents[[2]int{x / 2, y / 2}] = true224 return nil225 })226 if err != nil {227 return nil, err228 }229230 keys := make([][2]int, 0, len(parents))231 for key := range parents {232 keys = append(keys, key)233 }234 sort.Slice(keys, func(i, j int) bool {235 if keys[i][1] != keys[j][1] {236 return keys[i][1] < keys[j][1]237 }238 return keys[i][0] < keys[j][0]239 })240 span := 1 << zoom241 mask := &coverageMask{total: span * span}242 for _, parent := range keys {243 composite := image.NewNRGBA(image.Rect(0, 0, TileSize*2, TileSize*2))244 // A quadrant whose child was omitted as background must still carry the245 // background colour: a derived JPEG has no alpha to fall back on.246 draw.Draw(composite, composite.Bounds(), &image.Uniform{C: background}, image.Point{}, draw.Src)247 for offsetY := range 2 {248 for offsetX := range 2 {249 path := tilePath(root, name, zoom+1, parent[0]*2+offsetX, parent[1]*2+offsetY, childFormat)250 child, err := decode(path)251 if errors.Is(err, os.ErrNotExist) {252 continue253 }254 if err != nil {255 return nil, err256 }257 target := image.Rect(offsetX*TileSize, offsetY*TileSize,258 (offsetX+1)*TileSize, (offsetY+1)*TileSize)259 draw.Draw(composite, target, child, child.Bounds().Min, draw.Src)260 }261 }262 if err := encode(tilePath(root, name, zoom, parent[0], parent[1], format),263 downsample(composite, nearest), format); err != nil {264 return nil, err265 }266 mask.mark(parent[0], parent[1])267 }268 return mask.build(), nil269}270271// downsample halves a 2x2 composite into one tile. Pixel art is sampled272// nearest-neighbour so the grid survives instead of being blurred into itself;273// everything else is a box filter over the four pixels that become one.274func downsample(source *image.NRGBA, nearest bool) *image.NRGBA {275 target := image.NewNRGBA(image.Rect(0, 0, TileSize, TileSize))276 for y := range TileSize {277 for x := range TileSize {278 at := target.PixOffset(x, y)279 sourceX, sourceY := x*2, y*2280 if nearest {281 copy(target.Pix[at:at+4], source.Pix[source.PixOffset(sourceX, sourceY):][:4])282 continue283 }284 offsets := [4]int{285 source.PixOffset(sourceX, sourceY),286 source.PixOffset(sourceX+1, sourceY),287 source.PixOffset(sourceX, sourceY+1),288 source.PixOffset(sourceX+1, sourceY+1),289 }290 for channel := range 4 {291 sum := 0292 for _, offset := range offsets {293 sum += int(source.Pix[offset+channel])294 }295 target.Pix[at+channel] = uint8((sum + 2) / 4)296 }297 }298 }299 return target300}301302// placeholderColor reports the flat colour of a level's background tile, so a303// reader can paint it behind the raster and an omitted tile looks exactly as it304// did when it was shipped as a file. It answers "" when the tile is not flat305// enough for one colour to stand in for it.306func placeholderColor(tiles []Tile, hash string) (string, error) {307 if hash == "" {308 return "", nil309 }310 var sample string311 for _, tile := range tiles {312 if tile.Ref.ContentHash == hash {313 sample = tile.Path314 break315 }316 }317 if sample == "" {318 return "", nil319 }320 value, err := decode(sample)321 if err != nil {322 return "", err323 }324 bounds := value.Bounds()325 var sums [3]int64326 var count int64327 lowest := [3]uint32{^uint32(0), ^uint32(0), ^uint32(0)}328 highest := [3]uint32{}329 for y := bounds.Min.Y; y < bounds.Max.Y; y += 4 {330 for x := bounds.Min.X; x < bounds.Max.X; x += 4 {331 r, g, b, _ := value.At(x, y).RGBA()332 for channel, component := range [3]uint32{r >> 8, g >> 8, b >> 8} {333 sums[channel] += int64(component)334 lowest[channel] = min(lowest[channel], component)335 highest[channel] = max(highest[channel], component)336 }337 count++338 }339 }340 if count == 0 {341 return "", nil342 }343 for channel := range lowest {344 if highest[channel]-lowest[channel] > 12 {345 return "", nil346 }347 }348 return fmt.Sprintf("#%02x%02x%02x", sums[0]/count, sums[1]/count, sums[2]/count), nil349}350351// parseHex turns "#rrggbb" into a colour, defaulting to opaque black when the352// level had no flat background to sample.353func parseHex(value string) color.Color {354 if len(value) != 7 || value[0] != '#' {355 return color.NRGBA{A: 0xff}356 }357 component, err := strconv.ParseUint(value[1:], 16, 32)358 if err != nil {359 return color.NRGBA{A: 0xff}360 }361 return color.NRGBA{362 R: uint8(component >> 16),363 G: uint8(component >> 8),364 B: uint8(component),365 A: 0xff,366 }367}368369// coverageMask accumulates the tiles actually written for one level and encodes370// them as a bitset once the level is finished.371type coverageMask struct {372 present map[[2]int]bool373 total int374}375376func (m *coverageMask) mark(x, y int) {377 if m.present == nil {378 m.present = make(map[[2]int]bool)379 }380 m.present[[2]int{x, y}] = true381}382383// build answers nil when the level is empty or exactly full, so a complete level384// costs nothing in the register and an absent entry reads as "all of it".385func (m *coverageMask) build() *Coverage {386 if len(m.present) == 0 || len(m.present) == m.total {387 return nil388 }389 minX, minY := int(^uint(0)>>1), int(^uint(0)>>1)390 maxX, maxY := -1, -1391 for key := range m.present {392 minX, minY = min(minX, key[0]), min(minY, key[1])393 maxX, maxY = max(maxX, key[0]), max(maxY, key[1])394 }395 width, height := maxX-minX+1, maxY-minY+1396 bits := make([]byte, (width*height+7)/8)397 for key := range m.present {398 index := (key[1]-minY)*width + (key[0] - minX)399 bits[index/8] |= 1 << (index % 8)400 }401 return &Coverage{402 X: minX, Y: minY, W: width, H: height,403 Bits: base64.StdEncoding.EncodeToString(bits),404 }405}406407func tilePath(root, name string, zoom, x, y int, format string) string {408 return filepath.Join(root, name, strconv.Itoa(zoom), strconv.Itoa(x), strconv.Itoa(y)+"."+format)409}410411func normalizeExt(ext string) string {412 value := strings.ToLower(strings.TrimPrefix(ext, "."))413 switch value {414 case "jpeg":415 return "jpg"416 case "png", "webp":417 return value418 default:419 return "jpg"420 }421}422423func copyFile(from, to string) error {424 if err := os.MkdirAll(filepath.Dir(to), 0o755); err != nil {425 return err426 }427 input, err := os.Open(from)428 if err != nil {429 return err430 }431 defer input.Close()432 output, err := os.Create(to)433 if err != nil {434 return err435 }436 if _, err := io.Copy(output, input); err != nil {437 output.Close()438 return err439 }440 return output.Close()441}442443func decode(path string) (image.Image, error) {444 file, err := os.Open(path)445 if err != nil {446 return nil, err447 }448 defer file.Close()449 value, _, err := image.Decode(file)450 if err != nil {451 return nil, fmt.Errorf("decode %s: %w", path, err)452 }453 return value, nil454}455456func encode(path string, value image.Image, format string) error {457 if err := os.MkdirAll(filepath.Dir(path), 0o755); err != nil {458 return err459 }460 file, err := os.Create(path)461 if err != nil {462 return err463 }464 var encodeErr error465 switch format {466 case "png":467 encoder := png.Encoder{CompressionLevel: png.BestSpeed}468 encodeErr = encoder.Encode(file, value)469 default:470 encodeErr = jpeg.Encode(file, value, &jpeg.Options{Quality: 90})471 }472 if encodeErr != nil {473 file.Close()474 return fmt.Errorf("encode %s: %w", path, encodeErr)475 }476 return file.Close()477}