《游戏服务端编程实践》7.3.1 地图数据结构设计

// file: ch07/map/map.go
// tier: L1
// verify: go test ./ch07/map/

package worldmap

import (
	"errors"
	"math"
	"sort"
)

var (
	ErrEntityExists   = errors.New("map: entity already exists")
	ErrEntityNotFound = errors.New("map: entity not found")
	ErrInvalidHandle  = errors.New("map: stale entity handle")
)

// EntityID 在单张地图内唯一，跨地图需要再加 mapID。
type EntityID uint64

type Vec2 struct {
	X float64
	Y float64
}

func (v Vec2) Distance(o Vec2) float64 {
	return math.Hypot(v.X-o.X, v.Y-o.Y)
}

// Entity 是地图对外可见的实体状态。
type Entity struct {
	ID        EntityID
	Pos       Vec2
	Dir       float64 // 弧度
	Speed     float64 // 单位/秒
	ViewRange float64
	Hidden    bool
}

// EntityHandle 用“ID + 代”避免删除后旧引用误命中新实体。
type EntityHandle struct {
	ID  EntityID
	Gen uint32
}

type Cell struct {
	X int
	Y int
}

// GridAOI 只负责格子归属，不解释业务语义。
type GridAOI struct {
	cellSize float64
	cells    map[Cell]map[EntityID]struct{}
	where    map[EntityID]Cell
}

func NewGridAOI(cellSize float64) (*GridAOI, error) {
	if cellSize <= 0 {
		return nil, errors.New("aoi: cell size must be positive")
	}
	return &GridAOI{
		cellSize: cellSize,
		cells:    make(map[Cell]map[EntityID]struct{}),
		where:    make(map[EntityID]Cell),
	}, nil
}

func (g *GridAOI) CellSize() float64 {
	return g.cellSize
}

// CellOf 使用 floor，负坐标才会落到正确的左侧/下方格子。
func (g *GridAOI) CellOf(pos Vec2) Cell {
	return Cell{
		X: int(math.Floor(pos.X / g.cellSize)),
		Y: int(math.Floor(pos.Y / g.cellSize)),
	}
}

func (g *GridAOI) Add(id EntityID, pos Vec2) Cell {
	c := g.CellOf(pos)
	g.setCell(id, c)
	g.where[id] = c
	return c
}

func (g *GridAOI) Remove(id EntityID) {
	c, ok := g.where[id]
	if !ok {
		return
	}
	delete(g.cells[c], id)
	if len(g.cells[c]) == 0 {
		delete(g.cells, c)
	}
	delete(g.where, id)
}

// Move 返回移动前后的格子；只有跨格才算 changed。
func (g *GridAOI) Move(id EntityID, pos Vec2) (from, to Cell, changed bool) {
	to = g.CellOf(pos)
	from, ok := g.where[id]
	if !ok {
		g.Add(id, pos)
		return Cell{}, to, true
	}
	if from == to {
		return from, to, false
	}
	delete(g.cells[from], id)
	if len(g.cells[from]) == 0 {
		delete(g.cells, from)
	}
	g.setCell(id, to)
	g.where[id] = to
	return from, to, true
}

func (g *GridAOI) EntitiesIn(c Cell) []EntityID {
	out := make([]EntityID, 0, len(g.cells[c]))
	for id := range g.cells[c] {
		out = append(out, id)
	}
	sort.Slice(out, func(i, j int) bool { return out[i] < out[j] })
	return out
}

func (g *GridAOI) Count() int {
	return len(g.where)
}

func (g *GridAOI) setCell(id EntityID, c Cell) {
	set := g.cells[c]
	if set == nil {
		set = make(map[EntityID]struct{})
		g.cells[c] = set
	}
	set[id] = struct{}{}
}

type entityState struct {
	Entity
	hasSent      bool
	lastSentTick uint64
	lastSentPos  Vec2
	lastSentDir  float64
}

// Map 的状态只允许地图 goroutine 读写；对外的查询返回副本。
type Map struct {
	ID       string
	aoi      *GridAOI
	entities map[EntityID]*entityState
	gens     map[EntityID]uint32
	nextID   EntityID
	tick     uint64
}

func NewMap(id string, cellSize float64) (*Map, error) {
	aoi, err := NewGridAOI(cellSize)
	if err != nil {
		return nil, err
	}
	return &Map{
		ID:       id,
		aoi:      aoi,
		entities: make(map[EntityID]*entityState),
		gens:     make(map[EntityID]uint32),
	}, nil
}

func (m *Map) AddEntity(pos Vec2) (EntityHandle, error) {
	m.nextID++
	return m.AddEntityAt(m.nextID, pos)
}

func (m *Map) AddEntityAt(id EntityID, pos Vec2) (EntityHandle, error) {
	if id == 0 {
		return EntityHandle{}, errors.New("map: entity id 0 is reserved")
	}
	if _, ok := m.entities[id]; ok {
		return EntityHandle{}, ErrEntityExists
	}
	h := EntityHandle{ID: id, Gen: m.gens[id]}
	m.entities[id] = &entityState{Entity: Entity{ID: id, Pos: pos}}
	m.aoi.Add(id, pos)
	return h, nil
}

func (m *Map) RemoveEntity(h EntityHandle) error {
	if _, err := m.entity(h); err != nil {
		return err
	}
	delete(m.entities, h.ID)
	m.gens[h.ID]++
	m.aoi.Remove(h.ID)
	return nil
}

func (m *Map) Get(h EntityHandle) (Entity, bool) {
	st, err := m.entity(h)
	if err != nil {
		return Entity{}, false
	}
	return st.Entity, true
}

func (m *Map) Len() int {
	return len(m.entities)
}

func (m *Map) TickCount() uint64 {
	return m.tick
}

func (m *Map) entity(h EntityHandle) (*entityState, error) {
	if m.gens[h.ID] != h.Gen {
		return nil, ErrInvalidHandle
	}
	st, ok := m.entities[h.ID]
	if !ok {
		return nil, ErrInvalidHandle
	}
	return st, nil
}

// QueryRange 先按格子粗筛，再按圆形半径精筛；隐藏实体不返回。
func (m *Map) QueryRange(center Vec2, radius float64) []EntityID {
	if radius < 0 {
		radius = 0
	}
	c := m.aoi.CellOf(center)
	span := int(math.Ceil(radius / m.aoi.CellSize()))
	out := make([]EntityID, 0, 8)
	for y := c.Y - span; y <= c.Y+span; y++ {
		for x := c.X - span; x <= c.X+span; x++ {
			for id := range m.aoi.cells[Cell{X: x, Y: y}] {
				st := m.entities[id]
				if st == nil || st.Hidden {
					continue
				}
				if st.Pos.Distance(center) <= radius {
					out = append(out, id)
				}
			}
		}
	}
	sort.Slice(out, func(i, j int) bool { return out[i] < out[j] })
	return out
}

// SnapshotFor 返回观察者可见的实体副本；观察者自己始终包含在内。
func (m *Map) SnapshotFor(h EntityHandle, radius float64) ([]Entity, error) {
	observer, err := m.entity(h)
	if err != nil {
		return nil, err
	}
	if radius <= 0 {
		radius = observer.ViewRange
	}
	seen := make(map[EntityID]Entity)
	seen[observer.ID] = observer.Entity
	for _, id := range m.QueryRange(observer.Pos, radius) {
		if st := m.entities[id]; st != nil {
			seen[id] = st.Entity
		}
	}
	out := make([]Entity, 0, len(seen))
	for _, ent := range seen {
		out = append(out, ent)
	}
	sort.Slice(out, func(i, j int) bool { return out[i].ID < out[j].ID })
	return out, nil
}

cd .local/checks/gs-practice-lab && gofmt -l ch07/map && go vet ./ch07/map/ && go test ./ch07/map/ -count=1

ok  	gspractice/ch07/map	0.424s