《MMO 服务器开发》10.1 任务依赖图与循环检测

// file: internal/quest/graph.go
// tier: L1
// verify: go test ./internal/quest/

package quest

import (
	"errors"
	"fmt"
	"sort"
)

// QuestID identifies a quest definition. Definitions come from the config table;
// per-player runtime progress lives in the progress service (see 10.2).
type QuestID uint32

// QuestDef is one row of the quest config table. Prereqs are quests that must be
// *completed* before this quest can be accepted.
type QuestDef struct {
	ID       QuestID
	MinLevel int
	Prereqs  []QuestID
}

// ErrCycle is returned when the prerequisite graph is not a DAG.
var ErrCycle = errors.New("quest: prerequisite cycle")

// ErrUnknownPrereq is returned when a quest references an undefined prereq.
var ErrUnknownPrereq = errors.New("quest: unknown prerequisite")

// Graph is the quest prerequisite graph. Edges point from a prerequisite to the
// quest that depends on it (prereq -> dependent), which is the direction that
// makes "what does completing X unlock?" a direct adjacency lookup.
type Graph struct {
	defs  map[QuestID]QuestDef
	edges map[QuestID][]QuestID
}

// NewGraph validates and indexes a slice of quest definitions. It rejects
// duplicate IDs and dangling prerequisite references at load time, so the
// running server never has to defend against a half-valid table.
func NewGraph(defs []QuestDef) (*Graph, error) {
	g := &Graph{
		defs:  make(map[QuestID]QuestDef, len(defs)),
		edges: make(map[QuestID][]QuestID),
	}
	for _, d := range defs {
		if _, dup := g.defs[d.ID]; dup {
			return nil, fmt.Errorf("quest: duplicate id %d", d.ID)
		}
		g.defs[d.ID] = d
	}
	for _, d := range defs {
		for _, p := range d.Prereqs {
			if _, ok := g.defs[p]; !ok {
				return nil, fmt.Errorf("%w: %d depends on %d", ErrUnknownPrereq, d.ID, p)
			}
			g.edges[p] = append(g.edges[p], d.ID)
		}
	}
	return g, nil
}

// Def returns the definition for id and whether it exists.
func (g *Graph) Def(id QuestID) (QuestDef, bool) {
	d, ok := g.defs[id]
	return d, ok
}

// Len reports how many quests the graph holds.
func (g *Graph) Len() int { return len(g.defs) }

// TopoSort returns quests in an order where every quest appears after all of its
// prerequisites (Kahn's algorithm). When a cycle exists it returns ErrCycle plus
// the prefix that could be ordered; the caller should use FindCycle to show the
// designer the actual loop.
func (g *Graph) TopoSort() ([]QuestID, error) {
	indeg := make(map[QuestID]int, len(g.defs))
	for id := range g.defs {
		indeg[id] = 0
	}
	for _, ds := range g.edges {
		for _, d := range ds {
			indeg[d]++
		}
	}

	ready := make([]QuestID, 0, len(g.defs))
	for id, n := range indeg {
		if n == 0 {
			ready = append(ready, id)
		}
	}
	sortIDs(ready)

	out := make([]QuestID, 0, len(g.defs))
	for len(ready) > 0 {
		id := ready[0]
		ready = ready[1:]
		out = append(out, id)
		for _, d := range g.edges[id] {
			indeg[d]--
			if indeg[d] == 0 {
				ready = append(ready, d)
			}
		}
		sortIDs(ready) // keep output deterministic across runs
	}

	if len(out) != len(g.defs) {
		return out, ErrCycle
	}
	return out, nil
}

// FindCycle returns one concrete prerequisite cycle as a closed path
// (first element repeated at the end), or nil when the graph is a DAG. It runs
// an iterative DFS with three colours so a deep chain cannot blow the stack, and
// reconstructs the loop from the parent chain instead of just reporting "there
// is a cycle somewhere" — designers need the exact ring they drew.
func (g *Graph) FindCycle() []QuestID {
	const (
		white = 0
		gray  = 1
		black = 2
	)
	color := make(map[QuestID]int, len(g.defs))
	parent := make(map[QuestID]QuestID)

	roots := make([]QuestID, 0, len(g.defs))
	for id := range g.defs {
		roots = append(roots, id)
	}
	sortIDs(roots)

	type frame struct {
		id   QuestID
		next int
	}
	for _, root := range roots {
		if color[root] != white {
			continue
		}
		color[root] = gray
		stack := []frame{{root, 0}}
		for len(stack) > 0 {
			f := &stack[len(stack)-1]
			if f.next < len(g.edges[f.id]) {
				child := g.edges[f.id][f.next]
				f.next++
				switch color[child] {
				case white:
					color[child] = gray
					parent[child] = f.id
					stack = append(stack, frame{child, 0})
				case gray:
					// Back edge f.id -> child: child is still on the stack, so
					// the loop is child ... f.id -> child.
					cyc := []QuestID{}
					for cur := f.id; ; cur = parent[cur] {
						cyc = append(cyc, cur)
						if cur == child {
							break
						}
					}
					reverse(cyc)
					return append(cyc, child)
				}
			} else {
				color[f.id] = black
				stack = stack[:len(stack)-1]
			}
		}
	}
	return nil
}

// Unlockable returns the quests a player may accept right now: every prereq is
// in completed, the quest is not itself completed, and the level gate passes.
// The result is sorted by ID so the network sync payload is byte-stable.
func (g *Graph) Unlockable(completed map[QuestID]bool, level int) []QuestID {
	var out []QuestID
	for id, d := range g.defs {
		if completed[id] || d.MinLevel > level {
			continue
		}
		ok := true
		for _, p := range d.Prereqs {
			if !completed[p] {
				ok = false
				break
			}
		}
		if ok {
			out = append(out, id)
		}
	}
	sortIDs(out)
	return out
}

func sortIDs(s []QuestID) {
	sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
}

func reverse(s []QuestID) {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}

// snippet: internal/quest/graph_test.go（节选）

func TestTopoSortDetectsCycle(t *testing.T) {
	// 1 -> 2 -> 3 -> 1 : a three-node ring.
	g, err := NewGraph([]QuestDef{
		{ID: 1, Prereqs: []QuestID{3}},
		{ID: 2, Prereqs: []QuestID{1}},
		{ID: 3, Prereqs: []QuestID{2}},
	})
	if err != nil {
		t.Fatalf("NewGraph: %v", err)
	}
	if _, err := g.TopoSort(); !errors.Is(err, ErrCycle) {
		t.Fatalf("TopoSort err = %v, want ErrCycle", err)
	}
	cyc := g.FindCycle()
	if len(cyc) != 4 {
		t.Fatalf("cycle = %v, want 4 entries (closed path)", cyc)
	}
	if cyc[0] != cyc[len(cyc)-1] {
		t.Fatalf("cycle %v is not closed", cyc)
	}
	// Every consecutive pair must be a real dependency edge.
	for i := 0; i+1 < len(cyc); i++ {
		from, to := cyc[i], cyc[i+1]
		if !hasEdge(g, from, to) {
			t.Fatalf("cycle %v: %d->%d is not an edge", cyc, from, to)
		}
	}
}