From 7d76673fa0707d204c7d084c8f90c8133c22a31a Mon Sep 17 00:00:00 2001 From: historia <[not public]> Date: Mon, 29 Jun 2026 18:13:33 -0400 Subject: feat: migrated map (and bfs) to full 3D instead of individual 2D maps on different planes. --- internal/game/render_map.go | 339 +++++++++++++------------------------------- 1 file changed, 101 insertions(+), 238 deletions(-) (limited to 'internal/game/render_map.go') diff --git a/internal/game/render_map.go b/internal/game/render_map.go index 6b80688..b210e77 100644 --- a/internal/game/render_map.go +++ b/internal/game/render_map.go @@ -47,59 +47,19 @@ type mapCell struct { } type mapGraph struct { - posToRoom map[[2]int]int - roomToPos map[int][2]int + posToRoom map[[3]int]int dist map[int]int } +// The map BFS always seeds the player's room at the grid origin, so the +// player's z-plane is constant. +const playerZ = 0 - -func buildGraph(g *Game, startRoomID int, visited map[int]bool) *mapGraph { - mg := &mapGraph{ - posToRoom: make(map[[2]int]int), - roomToPos: make(map[int][2]int), - dist: make(map[int]int), - } - - type node struct { - roomID int - x, y int - } - queue := []node{{startRoomID, 0, 0}} - mg.posToRoom[[2]int{0, 0}] = startRoomID - mg.roomToPos[startRoomID] = [2]int{0, 0} - mg.dist[startRoomID] = 0 - - for len(queue) > 0 { - n := queue[0] - queue = queue[1:] - - room, ok := loadRoom(g, n.roomID) - if !ok { - continue - } - - if visited != nil && !visited[n.roomID] { - continue - } - - for dir, delta := range world.DirectionDeltas { - targetID, ok := exitTarget(room, dir) - if !ok { - continue - } - if _, seen := mg.roomToPos[targetID]; seen { - continue - } - nx, ny := n.x+delta[0], n.y+delta[1] - mg.posToRoom[[2]int{nx, ny}] = targetID - mg.roomToPos[targetID] = [2]int{nx, ny} - mg.dist[targetID] = mg.dist[n.roomID] + 1 - queue = append(queue, node{targetID, nx, ny}) - } - } - - return mg +func buildGraph(g *Game, startRoomID int) *mapGraph { + rg := world.BuildGrid(startRoomID, func(id int) (*world.Room, bool) { + return loadRoom(g, id) + }, nil, nil) + return &mapGraph{posToRoom: rg.RoomAt, dist: rg.Dist} } func renderMapCells(grid [][]mapCell, colorMode string, startRow, endRow int, border rune) []string { @@ -128,7 +88,7 @@ func renderMapCells(grid [][]mapCell, colorMode string, startRow, endRow int, bo func buildTinyMap(g *Game, sess *net.Session, roomID int, mg mapGlyphs) []string { visited := roomsVisited(sess) - bg := buildGraph(g, roomID, visited) + bg := buildGraph(g, roomID) colorMode := colorModeFor(sess) atSpec := resolveMapAt(g, sess) @@ -147,9 +107,10 @@ func buildTinyMap(g *Game, sess *net.Session, roomID int, mg mapGlyphs) []string } } + pz := playerZ for y := -1; y <= 1; y++ { for x := -1; x <= 1; x++ { - pos := [2]int{x, y} + pos := [3]int{x, y, pz} rid, ok := bg.posToRoom[pos] if !ok { continue @@ -171,8 +132,8 @@ func buildTinyMap(g *Game, sess *net.Session, roomID int, mg mapGlyphs) []string for y := -1; y <= 1; y++ { for x := -1; x <= 0; x++ { - leftPos := [2]int{x, y} - rightPos := [2]int{x + 1, y} + leftPos := [3]int{x, y, pz} + rightPos := [3]int{x + 1, y, pz} leftRoom, leftOK := bg.posToRoom[leftPos] rightRoom, rightOK := bg.posToRoom[rightPos] if !leftOK || !rightOK { @@ -186,8 +147,8 @@ func buildTinyMap(g *Game, sess *net.Session, roomID int, mg mapGlyphs) []string for y := -1; y <= 0; y++ { for x := -1; x <= 1; x++ { - topPos := [2]int{x, y} - bottomPos := [2]int{x, y + 1} + topPos := [3]int{x, y, pz} + bottomPos := [3]int{x, y + 1, pz} topRoom, topOK := bg.posToRoom[topPos] bottomRoom, bottomOK := bg.posToRoom[bottomPos] if !topOK || !bottomOK { @@ -199,119 +160,50 @@ func buildTinyMap(g *Game, sess *net.Session, roomID int, mg mapGlyphs) []string } } - // NE connectors: (x,y) -> (x+1, y-1), connector at grid[2*y+1][2*x+3] + // Diagonal connectors. Each maps room (x,y) to a diagonal neighbor; the + // grid cell between them is 2*y/2*x offset by ±1 in each axis. for y := 0; y <= 1; y++ { for x := -1; x <= 0; x++ { - aPos, bPos := [2]int{x, y}, [2]int{x + 1, y - 1} - aRoom, aOK := bg.posToRoom[aPos] - bRoom, bOK := bg.posToRoom[bPos] - if !aOK || !bOK { - continue - } - if cell, ok := ctx.connectorCell(aRoom, bRoom, world.Northeast, world.Southwest); ok { - gr, gc := 2*y+1, 2*x+3 - key := [2]int{gr, gc} - if isDiagonalGlyph(grid[gr][gc].char) { - if grid[gr][gc].char != cell.char { - prev := ctx.diagPairs[key] - spec := color.Average( - color.Average(ctx.nodeSpec(prev[0]), ctx.nodeSpec(prev[1])), - color.Average(ctx.nodeSpec(aRoom), ctx.nodeSpec(bRoom)), - ) - grid[gr][gc] = mapCell{char: 'X', spec: spec} - } - } else { - grid[gr][gc] = cell - ctx.diagPairs[key] = [2]int{aRoom, bRoom} - } + // NE: (x,y) -> (x+1, y-1), connector at grid[2*y+1][2*x+3] + aRoom, aOK := bg.posToRoom[[3]int{x, y, pz}] + bRoom, bOK := bg.posToRoom[[3]int{x + 1, y - 1, pz}] + if aOK && bOK { + ctx.placeDiagonal(grid, 2*y+1, 2*x+3, aRoom, bRoom, world.Northeast, world.Southwest) } } } - // NW connectors: (x,y) -> (x-1, y-1), connector at grid[2*y+1][2*x+1] for y := 0; y <= 1; y++ { for x := 0; x <= 1; x++ { - aPos, bPos := [2]int{x, y}, [2]int{x - 1, y - 1} - aRoom, aOK := bg.posToRoom[aPos] - bRoom, bOK := bg.posToRoom[bPos] - if !aOK || !bOK { - continue - } - if cell, ok := ctx.connectorCell(aRoom, bRoom, world.Northwest, world.Southeast); ok { - gr, gc := 2*y+1, 2*x+1 - key := [2]int{gr, gc} - if isDiagonalGlyph(grid[gr][gc].char) { - if grid[gr][gc].char != cell.char { - prev := ctx.diagPairs[key] - spec := color.Average( - color.Average(ctx.nodeSpec(prev[0]), ctx.nodeSpec(prev[1])), - color.Average(ctx.nodeSpec(aRoom), ctx.nodeSpec(bRoom)), - ) - grid[gr][gc] = mapCell{char: 'X', spec: spec} - } - } else { - grid[gr][gc] = cell - ctx.diagPairs[key] = [2]int{aRoom, bRoom} - } + // NW: (x,y) -> (x-1, y-1), connector at grid[2*y+1][2*x+1] + aRoom, aOK := bg.posToRoom[[3]int{x, y, pz}] + bRoom, bOK := bg.posToRoom[[3]int{x - 1, y - 1, pz}] + if aOK && bOK { + ctx.placeDiagonal(grid, 2*y+1, 2*x+1, aRoom, bRoom, world.Northwest, world.Southeast) } } } - // SE connectors: (x,y) -> (x+1, y+1), connector at grid[2*y+3][2*x+3] for y := -1; y <= 0; y++ { for x := -1; x <= 0; x++ { - aPos, bPos := [2]int{x, y}, [2]int{x + 1, y + 1} - aRoom, aOK := bg.posToRoom[aPos] - bRoom, bOK := bg.posToRoom[bPos] - if !aOK || !bOK { - continue - } - if cell, ok := ctx.connectorCell(aRoom, bRoom, world.Southeast, world.Northwest); ok { - gr, gc := 2*y+3, 2*x+3 - key := [2]int{gr, gc} - if isDiagonalGlyph(grid[gr][gc].char) { - if grid[gr][gc].char != cell.char { - prev := ctx.diagPairs[key] - spec := color.Average( - color.Average(ctx.nodeSpec(prev[0]), ctx.nodeSpec(prev[1])), - color.Average(ctx.nodeSpec(aRoom), ctx.nodeSpec(bRoom)), - ) - grid[gr][gc] = mapCell{char: 'X', spec: spec} - } - } else { - grid[gr][gc] = cell - ctx.diagPairs[key] = [2]int{aRoom, bRoom} - } + // SE: (x,y) -> (x+1, y+1), connector at grid[2*y+3][2*x+3] + aRoom, aOK := bg.posToRoom[[3]int{x, y, pz}] + bRoom, bOK := bg.posToRoom[[3]int{x + 1, y + 1, pz}] + if aOK && bOK { + ctx.placeDiagonal(grid, 2*y+3, 2*x+3, aRoom, bRoom, world.Southeast, world.Northwest) } } } - // SW connectors: (x,y) -> (x-1, y+1), connector at grid[2*y+3][2*x+1] for y := -1; y <= 0; y++ { for x := 0; x <= 1; x++ { - aPos, bPos := [2]int{x, y}, [2]int{x - 1, y + 1} - aRoom, aOK := bg.posToRoom[aPos] - bRoom, bOK := bg.posToRoom[bPos] - if !aOK || !bOK { - continue - } - if cell, ok := ctx.connectorCell(aRoom, bRoom, world.Southwest, world.Northeast); ok { - gr, gc := 2*y+3, 2*x+1 - key := [2]int{gr, gc} - if isDiagonalGlyph(grid[gr][gc].char) { - if grid[gr][gc].char != cell.char { - prev := ctx.diagPairs[key] - spec := color.Average( - color.Average(ctx.nodeSpec(prev[0]), ctx.nodeSpec(prev[1])), - color.Average(ctx.nodeSpec(aRoom), ctx.nodeSpec(bRoom)), - ) - grid[gr][gc] = mapCell{char: 'X', spec: spec} - } - } else { - grid[gr][gc] = cell - ctx.diagPairs[key] = [2]int{aRoom, bRoom} - } + // SW: (x,y) -> (x-1, y+1), connector at grid[2*y+3][2*x+1] + aRoom, aOK := bg.posToRoom[[3]int{x, y, pz}] + bRoom, bOK := bg.posToRoom[[3]int{x - 1, y + 1, pz}] + if aOK && bOK { + ctx.placeDiagonal(grid, 2*y+3, 2*x+1, aRoom, bRoom, world.Southwest, world.Northeast) } } } + cur, _ := loadRoom(g, roomID) if cur != nil { if upTarget, hasUp := exitTarget(cur, world.Up); hasUp { @@ -354,7 +246,7 @@ func buildTinyMap(g *Game, sess *net.Session, roomID int, mg mapGlyphs) []string func buildFullMap(g *Game, sess *net.Session, roomID, mapWidth, mapHeight int, mg mapGlyphs) []string { visited := roomsVisited(sess) - bg := buildGraph(g, roomID, visited) + bg := buildGraph(g, roomID) colorMode := colorModeFor(sess) atSpec := resolveMapAt(g, sess) @@ -375,8 +267,12 @@ func buildFullMap(g *Game, sess *net.Session, roomID, mapWidth, mapHeight int, m cx := mapWidth / 2 cy := mapHeight / 2 + pz := playerZ for pos, rid := range bg.posToRoom { + if pos[2] != pz { + continue + } gr := cy + pos[1]*2 gc := cx + pos[0]*2 if gr < 0 || gr >= mapHeight || gc < 0 || gc >= mapWidth { @@ -395,9 +291,12 @@ func buildFullMap(g *Game, sess *net.Session, roomID, mapWidth, mapHeight int, m } for pos, rid := range bg.posToRoom { + if pos[2] != pz { + continue + } x, y := pos[0], pos[1] - if rightID, exists := bg.posToRoom[[2]int{x + 1, y}]; exists { + if rightID, exists := bg.posToRoom[[3]int{x + 1, y, pz}]; exists { gr := cy + y*2 gc := cx + x*2 + 1 if gr >= 0 && gr < mapHeight && gc >= 0 && gc < mapWidth { @@ -407,7 +306,7 @@ func buildFullMap(g *Game, sess *net.Session, roomID, mapWidth, mapHeight int, m } } - if bottomID, exists := bg.posToRoom[[2]int{x, y + 1}]; exists { + if bottomID, exists := bg.posToRoom[[3]int{x, y + 1, pz}]; exists { gr := cy + y*2 + 1 gc := cx + x*2 if gr >= 0 && gr < mapHeight && gc >= 0 && gc < mapWidth { @@ -417,96 +316,20 @@ func buildFullMap(g *Game, sess *net.Session, roomID, mapWidth, mapHeight int, m } } - if neID, exists := bg.posToRoom[[2]int{x + 1, y - 1}]; exists { - gr := cy + y*2 - 1 - gc := cx + x*2 + 1 - if gr >= 0 && gr < mapHeight && gc >= 0 && gc < mapWidth { - if cell, ok := ctx.connectorCell(rid, neID, world.Northeast, world.Southwest); ok { - key := [2]int{gr, gc} - if isDiagonalGlyph(grid[gr][gc].char) { - if grid[gr][gc].char != cell.char { - prev := ctx.diagPairs[key] - spec := color.Average( - color.Average(ctx.nodeSpec(prev[0]), ctx.nodeSpec(prev[1])), - color.Average(ctx.nodeSpec(rid), ctx.nodeSpec(neID)), - ) - grid[gr][gc] = mapCell{char: 'X', spec: spec} - } - } else { - grid[gr][gc] = cell - ctx.diagPairs[key] = [2]int{rid, neID} - } - } - } + if neID, exists := bg.posToRoom[[3]int{x + 1, y - 1, pz}]; exists { + ctx.placeDiagonal(grid, cy+y*2-1, cx+x*2+1, rid, neID, world.Northeast, world.Southwest) } - if nwID, exists := bg.posToRoom[[2]int{x - 1, y - 1}]; exists { - gr := cy + y*2 - 1 - gc := cx + x*2 - 1 - if gr >= 0 && gr < mapHeight && gc >= 0 && gc < mapWidth { - if cell, ok := ctx.connectorCell(rid, nwID, world.Northwest, world.Southeast); ok { - key := [2]int{gr, gc} - if isDiagonalGlyph(grid[gr][gc].char) { - if grid[gr][gc].char != cell.char { - prev := ctx.diagPairs[key] - spec := color.Average( - color.Average(ctx.nodeSpec(prev[0]), ctx.nodeSpec(prev[1])), - color.Average(ctx.nodeSpec(rid), ctx.nodeSpec(nwID)), - ) - grid[gr][gc] = mapCell{char: 'X', spec: spec} - } - } else { - grid[gr][gc] = cell - ctx.diagPairs[key] = [2]int{rid, nwID} - } - } - } + if nwID, exists := bg.posToRoom[[3]int{x - 1, y - 1, pz}]; exists { + ctx.placeDiagonal(grid, cy+y*2-1, cx+x*2-1, rid, nwID, world.Northwest, world.Southeast) } - if seID, exists := bg.posToRoom[[2]int{x + 1, y + 1}]; exists { - gr := cy + y*2 + 1 - gc := cx + x*2 + 1 - if gr >= 0 && gr < mapHeight && gc >= 0 && gc < mapWidth { - if cell, ok := ctx.connectorCell(rid, seID, world.Southeast, world.Northwest); ok { - key := [2]int{gr, gc} - if isDiagonalGlyph(grid[gr][gc].char) { - if grid[gr][gc].char != cell.char { - prev := ctx.diagPairs[key] - spec := color.Average( - color.Average(ctx.nodeSpec(prev[0]), ctx.nodeSpec(prev[1])), - color.Average(ctx.nodeSpec(rid), ctx.nodeSpec(seID)), - ) - grid[gr][gc] = mapCell{char: 'X', spec: spec} - } - } else { - grid[gr][gc] = cell - ctx.diagPairs[key] = [2]int{rid, seID} - } - } - } + if seID, exists := bg.posToRoom[[3]int{x + 1, y + 1, pz}]; exists { + ctx.placeDiagonal(grid, cy+y*2+1, cx+x*2+1, rid, seID, world.Southeast, world.Northwest) } - if swID, exists := bg.posToRoom[[2]int{x - 1, y + 1}]; exists { - gr := cy + y*2 + 1 - gc := cx + x*2 - 1 - if gr >= 0 && gr < mapHeight && gc >= 0 && gc < mapWidth { - if cell, ok := ctx.connectorCell(rid, swID, world.Southwest, world.Northeast); ok { - key := [2]int{gr, gc} - if isDiagonalGlyph(grid[gr][gc].char) { - if grid[gr][gc].char != cell.char { - prev := ctx.diagPairs[key] - spec := color.Average( - color.Average(ctx.nodeSpec(prev[0]), ctx.nodeSpec(prev[1])), - color.Average(ctx.nodeSpec(rid), ctx.nodeSpec(swID)), - ) - grid[gr][gc] = mapCell{char: 'X', spec: spec} - } - } else { - grid[gr][gc] = cell - ctx.diagPairs[key] = [2]int{rid, swID} - } - } - } + if swID, exists := bg.posToRoom[[3]int{x - 1, y + 1, pz}]; exists { + ctx.placeDiagonal(grid, cy+y*2+1, cx+x*2-1, rid, swID, world.Southwest, world.Northeast) } } @@ -629,6 +452,35 @@ func (c *mapRenderCtx) coloredCell(roomA, roomB int, glyph rune) (mapCell, bool) return mapCell{char: glyph, spec: color.Average(c.nodeSpec(roomA), c.nodeSpec(roomB))}, true } +// placeDiagonal draws the diagonal link between two grid-adjacent rooms at +// grid[gr][gc], handling the criss-cross case: when a diagonal glyph is already +// present and the new link runs the opposite way, the cell becomes a blocked +// 'X' colored from both crossing links' endpoints. Out-of-bounds targets and +// rooms with no link between them are no-ops. +func (c *mapRenderCtx) placeDiagonal(grid [][]mapCell, gr, gc, roomA, roomB int, dirAB, dirBA world.ExitDir) { + if gr < 0 || gr >= len(grid) || gc < 0 || gc >= len(grid[gr]) { + return + } + cell, ok := c.connectorCell(roomA, roomB, dirAB, dirBA) + if !ok { + return + } + key := [2]int{gr, gc} + if isDiagonalGlyph(grid[gr][gc].char) { + if grid[gr][gc].char != cell.char { + prev := c.diagPairs[key] + spec := color.Average( + color.Average(c.nodeSpec(prev[0]), c.nodeSpec(prev[1])), + color.Average(c.nodeSpec(roomA), c.nodeSpec(roomB)), + ) + grid[gr][gc] = mapCell{char: 'X', spec: spec} + } + return + } + grid[gr][gc] = cell + c.diagPairs[key] = [2]int{roomA, roomB} +} + type exitState int const ( @@ -763,13 +615,24 @@ func loadRoom(g *Game, roomID int) (*world.Room, bool) { } func stripBlankRows(lines []string) []string { - var out []string - for _, line := range lines { + top := -1 + for i, line := range lines { if strings.TrimSpace(line) != "" { - out = append(out, line) + top = i + break + } + } + if top < 0 { + return nil + } + bottom := top + for i := len(lines) - 1; i > bottom; i-- { + if strings.TrimSpace(lines[i]) != "" { + bottom = i + break } } - return out + return lines[top : bottom+1] } func leftTrimCommon(lines []string) []string { -- cgit v1.2.3