package main

import (
	"container/heap"
	"image"
	"image/color"
	"math"
	"math/rand"
	"sort"
)

// PointOfInterest represents a location where roads may start, end, or intersect.
type PointOfInterest struct {
	X, Y           int
	Connections    int
	TargetDegree   int
	IsExit         bool
	ArterialWeight float64
}

// PathPoint represents a single point in a road's path with bridge flag.
type PathPoint struct {
	Point    image.Point
	IsBridge bool
}

type RoadTier int

const (
	RoadTierLocal RoadTier = iota
	RoadTierCollector
	RoadTierArterial
)

// Road represents a connection between two points of interest.
type Road struct {
	Start, End *PointOfInterest
	Width      int
	Points     []PathPoint
	Importance int
	Tier       RoadTier
}

const (
	minRoadWidthPercent  = 0.1
	maxRoadWidthPercent  = 5.0
	roadWidthPercentStep = 0.1
)

func clampInt(v, lo, hi int) int {
	if v < lo {
		return lo
	}
	if v > hi {
		return hi
	}
	return v
}

func clampRoadWidthPercent(v float64) float64 {
	if v < minRoadWidthPercent {
		return minRoadWidthPercent
	}
	if v > maxRoadWidthPercent {
		return maxRoadWidthPercent
	}
	return v
}

func snapRoadWidthPercent(v float64) float64 {
	v = clampRoadWidthPercent(v)
	steps := math.Round((v - minRoadWidthPercent) / roadWidthPercentStep)
	return clampRoadWidthPercent(minRoadWidthPercent + steps*roadWidthPercentStep)
}

func normalizeRoadWidthPercentRange(minPercent, maxPercent float64) (float64, float64) {
	minPercent = snapRoadWidthPercent(minPercent)
	maxPercent = snapRoadWidthPercent(maxPercent)
	if minPercent > maxPercent {
		minPercent, maxPercent = maxPercent, minPercent
	}
	return minPercent, maxPercent
}

func getRoadWidthRangePixels(settings *Settings, width, height int) (float64, float64) {
	minPercent, maxPercent := normalizeRoadWidthPercentRange(settings.MinRoadWidth, settings.MaxRoadWidth)
	avgDim := averageImageDimension(width, height)
	if avgDim < 1 {
		avgDim = 1
	}
	minPx := (minPercent / 100.0) * avgDim
	maxPx := (maxPercent / 100.0) * avgDim
	if minPx < 1 {
		minPx = 1
	}
	if maxPx < 1 {
		maxPx = 1
	}
	return minPx, maxPx
}

// GenerateRoads creates roads on the map.
func GenerateRoads(
	img *image.RGBA,
	width,
	height int,
	settings *Settings,
	waterMask *PixelMask,
	seed int64,
) (*PixelMask, *PixelMask, *PixelMask, []image.Point) {
	roadMask, bridgeMask, exitRoadMask, roadAnchors, _ := GenerateRoadsWithPOIs(img, width, height, settings, waterMask, nil, nil, 0, false, seed)
	return roadMask, bridgeMask, exitRoadMask, roadAnchors
}

func PrepareRoadNodes(width, height int, settings *Settings, waterMask *PixelMask, seed int64) ([]*PointOfInterest, int, bool) {
	randSrc := rand.New(rand.NewSource(seed))

	if settings.NumBuildings == 0 {
		internalRoads := int(math.Round(clamp(settings.RoadDistribution, 0, 100)))
		exitRoads := max(0, settings.RoadExits)
		if internalRoads == 0 && exitRoads > 0 && settings.RoadDistribution <= 0 {
			return nil, 0, true
		}
		if internalRoads > 0 {
			roadTarget := internalRoads
			return generatePOIs(width, height, settings, waterMask, randSrc, roadTarget), roadTarget, false
		}
		return nil, 0, false
	}

	roadTarget := estimateRoadTarget(settings)
	return generatePOIs(width, height, settings, waterMask, randSrc, roadTarget), roadTarget, false
}

func GenerateRoadsWithPOIs(
	img *image.RGBA,
	width,
	height int,
	settings *Settings,
	waterMask *PixelMask,
	wallLayout *FortificationLayout,
	pois []*PointOfInterest,
	roadTarget int,
	edgeToEdgeOnly bool,
	seed int64,
) (*PixelMask, *PixelMask, *PixelMask, []image.Point, []*Road) {
	if img == nil {
		img = image.NewRGBA(image.Rect(0, 0, width, height))
	}
	randSrc := rand.New(rand.NewSource(seed))
	roadColor := color.RGBA{R: 139, G: 69, B: 19, A: 255}
	bridgeColor := color.RGBA{R: 60, G: 42, B: 33, A: 255}

	if len(pois) > 0 && wallLayout != nil && wallLayout.Mask != nil {
		nudgePOIsOutsideWalls(pois, wallLayout.Mask, waterMask, settings, width, height, randSrc)
	}

	// Edge-case mode: no buildings.
	if settings.NumBuildings == 0 && roadTarget == 0 && !edgeToEdgeOnly {
		internalRoads := int(math.Round(clamp(settings.RoadDistribution, 0, 100)))
		exitRoads := max(0, settings.RoadExits)
		if internalRoads == 0 && exitRoads == 0 {
			return NewPixelMask(width, height), NewPixelMask(width, height), NewPixelMask(width, height), nil, nil
		}
		if internalRoads > 0 {
			roadTarget = internalRoads
		} else if settings.RoadDistribution <= 0 && exitRoads > 0 {
			edgeToEdgeOnly = true
		}
	}

	var roads []*Road
	if edgeToEdgeOnly {
		roads = generateEdgeToEdgeExitRoads(max(0, settings.RoadExits), width, height, settings, randSrc, waterMask, wallLayout)
	} else {
		if roadTarget <= 0 {
			roadTarget = estimateRoadTarget(settings)
		}
		if pois == nil {
			pois = generatePOIs(width, height, settings, waterMask, randSrc, roadTarget)
		}
		if len(pois) < 2 {
			return NewPixelMask(width, height), NewPixelMask(width, height), NewPixelMask(width, height), nil, nil
		}
		roads = connectPOIs(pois, width, height, settings, randSrc, waterMask, wallLayout, roadTarget)
		roads = appendExitRoads(roads, pois, width, height, settings, randSrc, waterMask, wallLayout)
	}

	if wallLayout != nil && len(wallLayout.Gates) > 0 {
		gateRoads := generateGateRoads(wallLayout, settings, waterMask, width, height, randSrc)
		roads = append(roads, gateRoads...)
		roads = ensureGateRoadConnections(gateRoads, roads, wallLayout, settings, waterMask, width, height, randSrc)
	}

	// Filter any initial paths that illegally cross walls without a gate.
	roads = applyWallCrossingRules(roads, wallLayout, waterMask, randSrc)

	// Reduce redundant bridges while strictly preserving road network connectivity.
	roads = reduceRepeatedBridges(roads, waterMask, width, height, randSrc)

	// Guarantee that the entire road network forms a single connected component with valid wall/water routing.
	roads = ensureRoadNetworkConnected(roads, settings, randSrc, waterMask, wallLayout, width, height)

	// Final verification filter: guarantee zero wall violations under all conditions.
	roads = applyWallCrossingRules(roads, wallLayout, waterMask, randSrc)

	if len(roads) == 0 {
		return NewPixelMask(width, height), NewPixelMask(width, height), NewPixelMask(width, height), nil, nil
	}

	assignRoadWidths(roads, settings, randSrc, width, height, wallLayout)

	roadMask := NewPixelMask(width, height)
	bridgeMask := NewPixelMask(width, height)
	exitRoadMask := NewPixelMask(width, height)
	for _, road := range roads {
		drawRoadToMasks(img, road.Points, roadColor, bridgeColor, road.Width, roadMask, bridgeMask)
		if road.Start != nil && road.End != nil && (road.Start.IsExit || road.End.IsExit) {
			drawRoadToMasks(img, road.Points, roadColor, bridgeColor, road.Width, exitRoadMask, exitRoadMask)
		}
	}

	roadAnchors := collectRoadAnchors(roads, settings, waterMask, width, height)
	return roadMask, bridgeMask, exitRoadMask, roadAnchors, roads
}

func nudgePOIsOutsideWalls(pois []*PointOfInterest, wallMask, waterMask *PixelMask, settings *Settings, width, height int, randSrc *rand.Rand) {
	if len(pois) == 0 || wallMask == nil {
		return
	}
	if waterMask == nil {
		waterMask = NewPixelMask(width, height)
	}

	fakeLayout := &FortificationLayout{Mask: wallMask}
	exclusion := buildWallExclusionMask(fakeLayout, settings, width, height)
	centerX := float64(width-1) * 0.5
	centerY := float64(height-1) * 0.5

	for _, p := range pois {
		if p == nil {
			continue
		}
		if !exclusion.GetXY(p.X, p.Y) {
			continue
		}

		vx := float64(p.X) - centerX
		vy := float64(p.Y) - centerY
		vlen := math.Hypot(vx, vy)
		if vlen < 0.001 {
			theta := randSrc.Float64() * 2 * math.Pi
			vx = math.Cos(theta)
			vy = math.Sin(theta)
			vlen = 1
		}
		dx := vx / vlen
		dy := vy / vlen

		moved := false
		maxSteps := exclusion.Width + exclusion.Height
		for step := 1; step <= maxSteps; step++ {
			nx := int(math.Round(float64(p.X) + float64(step)*dx))
			ny := int(math.Round(float64(p.Y) + float64(step)*dy))
			if nx < 0 || ny < 0 || nx >= width || ny >= height {
				break
			}
			if exclusion.GetXY(nx, ny) || waterMask.GetXY(nx, ny) {
				continue
			}
			p.X = nx
			p.Y = ny
			moved = true
			break
		}
		if moved {
			continue
		}

		baseAngle := math.Atan2(dy, dx)
		for a := -6; a <= 6; a++ {
			ang := baseAngle + float64(a)*math.Pi/18.0
			adx := math.Cos(ang)
			ady := math.Sin(ang)
			for step := 1; step <= exclusion.Width+exclusion.Height; step++ {
				nx := int(math.Round(float64(p.X) + float64(step)*adx))
				ny := int(math.Round(float64(p.Y) + float64(step)*ady))
				if nx < 0 || ny < 0 || nx >= width || ny >= height {
					break
				}
				if exclusion.GetXY(nx, ny) || waterMask.GetXY(nx, ny) {
					continue
				}
				p.X = nx
				p.Y = ny
				moved = true
				break
			}
			if moved {
				break
			}
		}
	}
}

func generateEdgeToEdgeExitRoads(exitRoads, width, height int, settings *Settings, randSrc *rand.Rand, waterMask *PixelMask, wallLayout *FortificationLayout) []*Road {
	if exitRoads <= 0 {
		return nil
	}
	avgDim := float64(width+height) / 2.0
	roads := make([]*Road, 0, exitRoads)
	for i := 0; i < exitRoads; i++ {
		start, end := sampleDifferentEdgePair(width, height, randSrc)
		start.IsExit = true
		end.IsExit = true
		path := calculateRoadPath(start, end, settings.RoadCurvyness/100.0, avgDim, randSrc, waterMask, wallLayout, RoadTierArterial)
		roads = append(roads, &Road{
			Start:      start,
			End:        end,
			Points:     path,
			Importance: 1,
			Tier:       RoadTierArterial,
		})
	}
	return roads
}

func sampleDifferentEdgePair(width, height int, randSrc *rand.Rand) (*PointOfInterest, *PointOfInterest) {
	sideA := randSrc.Intn(4)
	sideB := randSrc.Intn(3)
	if sideB >= sideA {
		sideB++
	}
	return sampleEdgePOIBySide(width, height, sideA, randSrc), sampleEdgePOIBySide(width, height, sideB, randSrc)
}

func sampleEdgePOIBySide(width, height, side int, randSrc *rand.Rand) *PointOfInterest {
	switch side {
	case 0:
		return &PointOfInterest{X: randSrc.Intn(width), Y: 0}
	case 1:
		return &PointOfInterest{X: randSrc.Intn(width), Y: height - 1}
	case 2:
		return &PointOfInterest{X: 0, Y: randSrc.Intn(height)}
	default:
		return &PointOfInterest{X: width - 1, Y: randSrc.Intn(height)}
	}
}

func generatePOIs(width, height int, settings *Settings, waterMask *PixelMask, randSrc *rand.Rand, roadTarget int) []*PointOfInterest {
	distribution := clamp01(settings.RoadDistribution / 100.0)
	targetCoverage := 0.10 + 0.90*distribution
	minBuildingSizePx, maxBuildingSizePx := getBuildingSizeRangePixels(settings, width, height)
	avgBuildingSize := (minBuildingSizePx + maxBuildingSizePx) / 2.0
	if avgBuildingSize < 1 {
		avgBuildingSize = 1
	}

	coreNodes := estimateCoreNodeCount(width, height, distribution, avgBuildingSize, settings.NumBuildings)
	if coreNodes < 2 {
		coreNodes = 2
	}
	maxTotalNodes := max(2, roadTarget+1)
	if coreNodes > maxTotalNodes {
		coreNodes = maxTotalNodes
	}

	// Uniform spacing across the entire settlement footprint so nodes are evenly spread.
	uniformSpacing := avgBuildingSize * (1.15 - 0.20*distribution)
	if uniformSpacing < 6 {
		uniformSpacing = 6
	}

	warpPhaseA := randSrc.Float64() * 2 * math.Pi
	warpPhaseB := randSrc.Float64() * 2 * math.Pi

	pois := make([]*PointOfInterest, 0, coreNodes)
	maxTries := coreNodes * 80
	for tries := 0; len(pois) < coreNodes && tries < maxTries; tries++ {
		x, y, ok := sampleCorePOI(width, height, distribution, targetCoverage, warpPhaseA, warpPhaseB, randSrc)
		if !ok {
			continue
		}
		p := image.Point{X: x, Y: y}
		if waterMask != nil && waterMask.GetPoint(p) {
			continue
		}
		if isTooCloseToExisting(pois, x, y, uniformSpacing) {
			continue
		}
		pois = append(pois, &PointOfInterest{
			X:            x,
			Y:            y,
			TargetDegree: sampleTargetDegree(randSrc),
		})
	}

	if len(pois) == 0 {
		return nil
	}

	// Assign arterial weights evenly across sectors of the city.
	centerX := float64(width-1) * 0.5
	centerY := float64(height-1) * 0.5
	for _, poi := range pois {
		dx := float64(poi.X) - centerX
		dy := float64(poi.Y) - centerY
		dist := math.Hypot(dx, dy)
		maxDist := math.Hypot(centerX, centerY)
		normDist := clamp01(dist / (maxDist + 1))
		// Balanced weight based on spatial coverage and random variety
		poi.ArterialWeight = clamp01(0.40*(1.0-0.5*normDist) + 0.35*randSrc.Float64() + 0.25*clamp01((avgBuildingSize-4.0)/40.0))
	}

	return pois
}

func estimateCoreNodeCount(width, height int, distribution, avgBuildingSize float64, numBuildings int) int {
	targetArea := float64(width*height) * (0.10 + 0.90*distribution)
	spacing := avgBuildingSize * (1.30 - 0.35*distribution)
	if spacing < 6 {
		spacing = 6
	}
	byArea := int((targetArea / (spacing * spacing)) * 0.22)
	buildingPressure := int(math.Sqrt(float64(max(numBuildings, 1))) * (0.7 + distribution*0.8))
	nodes := byArea + buildingPressure
	if nodes < 8 {
		nodes = 8
	}
	maxNodes := int(clamp(float64(width*height)/45000.0, 80, 550))
	if nodes > maxNodes {
		nodes = maxNodes
	}
	return nodes
}

func sampleCorePOI(width, height int, distribution, targetCoverage, warpPhaseA, warpPhaseB float64, randSrc *rand.Rand) (int, int, bool) {
	if width <= 0 || height <= 0 {
		return 0, 0, false
	}
	if distribution >= 0.999 {
		return randSrc.Intn(width), randSrc.Intn(height), true
	}

	coverageRadius := math.Sqrt(clamp(targetCoverage, 0.01, 1.0))
	superellipsePower := 2.0 + 10.0*distribution
	warpAmp := (1.0 - distribution) * 0.18

	cx := float64(width-1) * 0.5
	cy := float64(height-1) * 0.5
	invHalfW := 1.0 / math.Max(float64(width-1)*0.5, 1.0)
	invHalfH := 1.0 / math.Max(float64(height-1)*0.5, 1.0)

	for i := 0; i < 120; i++ {
		x := randSrc.Intn(width)
		y := randSrc.Intn(height)
		nx := (float64(x) - cx) * invHalfW
		ny := (float64(y) - cy) * invHalfH

		ax := math.Abs(nx)
		ay := math.Abs(ny)
		metric := math.Pow(ax, superellipsePower) + math.Pow(ay, superellipsePower)
		theta := math.Atan2(ny, nx)
		warp := 1.0 + warpAmp*(0.55*math.Sin(3.0*theta+warpPhaseA)+0.45*math.Sin(5.0*theta+warpPhaseB))
		if warp < 0.7 {
			warp = 0.7
		}
		threshold := math.Pow(coverageRadius*warp, superellipsePower)
		if metric <= threshold {
			return x, y, true
		}
	}
	return 0, 0, false
}

func isTooCloseToExisting(pois []*PointOfInterest, x, y int, minDist float64) bool {
	minDist2 := minDist * minDist
	for _, p := range pois {
		dx := float64(p.X - x)
		dy := float64(p.Y - y)
		if dx*dx+dy*dy < minDist2 {
			return true
		}
	}
	return false
}

func sampleEdgePOI(width, height int, randSrc *rand.Rand) *PointOfInterest {
	side := randSrc.Intn(4)
	switch side {
	case 0:
		return &PointOfInterest{X: randSrc.Intn(width), Y: 0}
	case 1:
		return &PointOfInterest{X: randSrc.Intn(width), Y: height - 1}
	case 2:
		return &PointOfInterest{X: 0, Y: randSrc.Intn(height)}
	default:
		return &PointOfInterest{X: width - 1, Y: randSrc.Intn(height)}
	}
}

func sampleTargetDegree(randSrc *rand.Rand) int {
	r := randSrc.Float64()
	switch {
	case r < 0.12:
		return 2
	case r < 0.60:
		return 3
	case r < 0.92:
		return 4
	default:
		return 5
	}
}

// isSegmentWallSafe returns true if the bresenham line from a to b does not intersect wall exclusion pixels outside gates.
func isSegmentWallSafe(a, b image.Point, wallMask, gateMask *PixelMask) bool {
	if wallMask == nil {
		return true
	}
	pts := bresenhamRoad([]image.Point{a, b})
	for _, p := range pts {
		if wallMask.InBounds(p.X, p.Y) && wallMask.GetXY(p.X, p.Y) {
			if gateMask == nil || !gateMask.GetXY(p.X, p.Y) {
				return false
			}
		}
	}
	return true
}

func connectPOIs(pois []*PointOfInterest, width, height int, settings *Settings, randSrc *rand.Rand, waterMask *PixelMask, wallLayout *FortificationLayout, roadTarget int) []*Road {
	minAngle := settings.MinRoadAngle * math.Pi / 180.0
	if minAngle < 0 {
		minAngle = 0
	}

	edgeDist := math.Min(float64(width), float64(height)) * 0.35
	if roadTarget < len(pois)-1 {
		roadTarget = len(pois) - 1
	}
	collectorTarget := max(len(pois)-1, max(roadTarget, roadTarget+max(2, roadTarget/8)))
	totalBudget := max(collectorTarget, roadTarget+max(3, roadTarget/4))
	isSmallSettlement := settings.NumBuildings <= 120 || len(pois) <= 18

	var wallMask, gateMask *PixelMask
	if wallLayout != nil {
		wallMask = wallLayout.Mask
		gateMask = wallLayout.GateMask
	}

	type edgeCandidate struct {
		a, b         int
		score        float64
		dist         float64
		arterialMean float64
	}

	candidates := make([]edgeCandidate, 0, len(pois)*6)
	for i := 0; i < len(pois); i++ {
		for j := i + 1; j < len(pois); j++ {
			a := pois[i]
			b := pois[j]
			if a.IsExit && b.IsExit {
				continue
			}
			dx := float64(a.X - b.X)
			dy := float64(a.Y - b.Y)
			d := math.Hypot(dx, dy)
			if !a.IsExit && !b.IsExit && d > edgeDist {
				continue
			}
			if (a.IsExit || b.IsExit) && d > edgeDist*1.6 {
				continue
			}

			// Do not add candidate if straight path cuts through a wall outside a gate
			if !isSegmentWallSafe(image.Point{X: a.X, Y: a.Y}, image.Point{X: b.X, Y: b.Y}, wallMask, gateMask) {
				continue
			}

			arterialBias := 1.0 - math.Abs(a.ArterialWeight-b.ArterialWeight)
			distanceBias := 1.0 - clamp01(d/(edgeDist*1.4))
			score := distanceBias*0.55 + arterialBias*0.35 + randSrc.Float64()*0.10
			candidates = append(candidates, edgeCandidate{
				a:            i,
				b:            j,
				score:        score,
				dist:         d,
				arterialMean: (a.ArterialWeight + b.ArterialWeight) * 0.5,
			})
		}
	}
	if len(candidates) == 0 {
		return nil
	}

	sort.Slice(candidates, func(i, j int) bool {
		return candidates[i].score > candidates[j].score
	})

	type selectedEdge struct {
		edge edgeCandidate
		tier RoadTier
	}

	selected := make(map[uint64]bool, totalBudget)
	adjAngles := make([][]float64, len(pois))
	selectedEdges := make([]selectedEdge, 0, totalBudget)

	nodeCapacity := func(p *PointOfInterest, tier RoadTier) int {
		base := max(1, p.TargetDegree)
		switch tier {
		case RoadTierArterial:
			return max(base+1, 4)
		case RoadTierCollector:
			return base + 1
		default:
			return base
		}
	}

	addEdge := func(pick edgeCandidate, tier RoadTier) {
		key := edgeKey(pick.a, pick.b)
		selected[key] = true
		selectedEdges = append(selectedEdges, selectedEdge{edge: pick, tier: tier})
		a := pois[pick.a]
		b := pois[pick.b]
		angAB := math.Atan2(float64(b.Y-a.Y), float64(b.X-a.X))
		angBA := normalizeAngle(angAB + math.Pi)
		a.Connections++
		b.Connections++
		adjAngles[pick.a] = append(adjAngles[pick.a], angAB)
		adjAngles[pick.b] = append(adjAngles[pick.b], angBA)
	}

	canUseEdge := func(pick edgeCandidate, tier RoadTier) bool {
		key := edgeKey(pick.a, pick.b)
		if selected[key] {
			return false
		}
		a := pois[pick.a]
		b := pois[pick.b]
		if a.Connections >= nodeCapacity(a, tier) || b.Connections >= nodeCapacity(b, tier) {
			return false
		}
		angAB := math.Atan2(float64(b.Y-a.Y), float64(b.X-a.X))
		angBA := normalizeAngle(angAB + math.Pi)
		if !angleAllowed(adjAngles[pick.a], angAB, minAngle) || !angleAllowed(adjAngles[pick.b], angBA, minAngle) {
			return false
		}
		return pick.score-degreePenalty(a, b) >= -0.4
	}

	arterialCount := max(2, min(len(pois), min(12, 2+roadTarget/14)))
	arterialOrder := make([]int, len(pois))
	for i := range arterialOrder {
		arterialOrder[i] = i
	}
	sort.Slice(arterialOrder, func(i, j int) bool {
		pi := pois[arterialOrder[i]]
		pj := pois[arterialOrder[j]]
		return pi.ArterialWeight > pj.ArterialWeight
	})
	arterialNodes := make(map[int]bool, arterialCount)
	arterialMinSpacing := edgeDist * 0.50
	arterialMinSpacing2 := arterialMinSpacing * arterialMinSpacing
	for _, idx := range arterialOrder {
		if len(arterialNodes) >= arterialCount {
			break
		}
		keep := true
		for chosen := range arterialNodes {
			dx := float64(pois[chosen].X - pois[idx].X)
			dy := float64(pois[chosen].Y - pois[idx].Y)
			if dx*dx+dy*dy < arterialMinSpacing2 {
				keep = false
				break
			}
		}
		if keep {
			arterialNodes[idx] = true
		}
	}
	for _, idx := range arterialOrder {
		if len(arterialNodes) >= arterialCount {
			break
		}
		arterialNodes[idx] = true
	}

	start := arterialOrder[0]
	connected := make([]bool, len(pois))
	connected[start] = true
	connectedCount := 1

	// Phase 1: connect the major arterial skeleton spanning the city.
	arterialBudget := max(1, min(len(arterialNodes)-1, min(12, 2+roadTarget/18)))
	for len(selectedEdges) < arterialBudget {
		bestIdx := -1
		bestScore := -1.0
		for idx, c := range candidates {
			if !arterialNodes[c.a] || !arterialNodes[c.b] {
				continue
			}
			if c.dist < edgeDist*0.25 {
				continue
			}
			aConn := connected[c.a]
			bConn := connected[c.b]
			if aConn == bConn {
				continue
			}
			if !canUseEdge(c, RoadTierArterial) {
				continue
			}
			a := pois[c.a]
			b := pois[c.b]
			degPen := clamp01(float64(a.Connections+b.Connections) / 8.0)
			score := c.arterialMean*0.50 + clamp01(c.dist/edgeDist)*0.30 + c.score*0.20 - degPen*0.15
			if score > bestScore {
				bestScore = score
				bestIdx = idx
			}
		}
		if bestIdx == -1 {
			break
		}
		pick := candidates[bestIdx]
		addEdge(pick, RoadTierArterial)
		if !connected[pick.a] {
			connected[pick.a] = true
			connectedCount++
		}
		if !connected[pick.b] {
			connected[pick.b] = true
			connectedCount++
		}
	}

	// Phase 2: connect remaining nodes with collector roads.
	for connectedCount < len(pois) && len(selectedEdges) < collectorTarget {
		bestIdx := -1
		bestScore := -1.0
		for idx, c := range candidates {
			aConn := connected[c.a]
			bConn := connected[c.b]
			if aConn == bConn {
				continue
			}
			if !canUseEdge(c, RoadTierCollector) {
				continue
			}
			a := pois[c.a]
			b := pois[c.b]
			connectedBonus := 0.0
			if arterialNodes[c.a] || arterialNodes[c.b] {
				connectedBonus = 0.15
			}
			distScore := 1.0 - clamp01(c.dist/(edgeDist*1.2))
			degPen := clamp01(float64(a.Connections+b.Connections) / 7.0)
			score := c.score*0.35 + c.arterialMean*0.25 + distScore*0.40 + connectedBonus - degPen*0.12
			if score > bestScore {
				bestScore = score
				bestIdx = idx
			}
		}
		if bestIdx == -1 {
			break
		}
		pick := candidates[bestIdx]
		addEdge(pick, RoadTierCollector)
		if !connected[pick.a] {
			connected[pick.a] = true
			connectedCount++
		}
		if !connected[pick.b] {
			connected[pick.b] = true
			connectedCount++
		}
	}

	// Phase 3: add shorter local links across all districts evenly.
	for _, pick := range candidates {
		if len(selectedEdges) >= totalBudget {
			break
		}
		if pick.dist > edgeDist*0.65 {
			continue
		}
		a := pois[pick.a]
		b := pois[pick.b]
		if !canUseEdge(pick, RoadTierLocal) {
			continue
		}
		if a.Connections >= a.TargetDegree || b.Connections >= b.TargetDegree {
			continue
		}
		if isSmallSettlement && (a.Connections > 1 || b.Connections > 1) {
			continue
		}
		addEdge(pick, RoadTierLocal)
	}

	roads := make([]*Road, 0, len(selectedEdges))
	avgDim := float64(width+height) / 2
	for _, e := range selectedEdges {
		a := pois[e.edge.a]
		b := pois[e.edge.b]
		path := calculateRoadPath(a, b, settings.RoadCurvyness/100.0, avgDim, randSrc, waterMask, wallLayout, e.tier)
		imp := a.Connections + b.Connections + int(math.Round((a.ArterialWeight+b.ArterialWeight)*4))
		roads = append(roads, &Road{Start: a, End: b, Points: path, Importance: imp, Tier: e.tier})
	}

	return roads
}

func appendExitRoads(roads []*Road, pois []*PointOfInterest, width, height int, settings *Settings, randSrc *rand.Rand, waterMask *PixelMask, wallLayout *FortificationLayout) []*Road {
	if settings.RoadExits <= 0 || len(pois) == 0 {
		return roads
	}

	var wallMask, gateMask *PixelMask
	if wallLayout != nil {
		wallMask = wallLayout.Mask
		gateMask = wallLayout.GateMask
	}

	avgDim := float64(width+height) / 2
	usedEdgePoints := make([]image.Point, 0, settings.RoadExits)

	for i := 0; i < settings.RoadExits; i++ {
		edgeNode, ok := sampleNonWaterEdgePOI(width, height, randSrc, waterMask, usedEdgePoints)
		if !ok {
			continue
		}
		edgePt := image.Point{X: edgeNode.X, Y: edgeNode.Y}

		// Pick anchor reachable from the edge without illegally crossing walls
		anchor := chooseWallSafeExitAnchor(pois, edgePt, usedEdgePoints, wallMask, gateMask, randSrc)
		if anchor == nil && wallLayout != nil && len(wallLayout.Gates) > 0 {
			// Connect to nearest gate OuterEnd
			bestGateDist := math.MaxFloat64
			for _, g := range wallLayout.Gates {
				if isSegmentWallSafe(g.OuterEnd, edgePt, wallMask, gateMask) {
					d := math.Hypot(float64(g.OuterEnd.X-edgePt.X), float64(g.OuterEnd.Y-edgePt.Y))
					if d < bestGateDist {
						bestGateDist = d
						anchor = &PointOfInterest{X: g.OuterEnd.X, Y: g.OuterEnd.Y, ArterialWeight: 1.0}
					}
				}
			}
		}
		if anchor == nil {
			anchor = chooseExitAnchor(pois, usedEdgePoints, randSrc)
		}
		if anchor == nil {
			continue
		}

		path := calculateRoadPath(anchor, edgeNode, settings.RoadCurvyness/100.0, avgDim, randSrc, waterMask, wallLayout, RoadTierArterial)
		if !pathRespectsWallPassages(path, wallMask, gateMask) {
			path = findWallSafePath(image.Point{X: anchor.X, Y: anchor.Y}, edgePt, wallMask, gateMask, waterMask, width, height)
		}

		if !pathRespectsWallPassages(path, wallMask, gateMask) {
			continue
		}

		anchor.Connections++
		edgeNode.IsExit = true
		edgeNode.TargetDegree = 1
		edgeNode.Connections = 1
		importance := anchor.Connections + edgeNode.Connections + int(math.Round(anchor.ArterialWeight*3))
		roads = append(roads, &Road{
			Start:      anchor,
			End:        edgeNode,
			Points:     path,
			Importance: importance,
			Tier:       RoadTierArterial,
		})
		usedEdgePoints = append(usedEdgePoints, edgePt)
	}

	return roads
}

func chooseWallSafeExitAnchor(pois []*PointOfInterest, edgePt image.Point, usedExits []image.Point, wallMask, gateMask *PixelMask, randSrc *rand.Rand) *PointOfInterest {
	var best *PointOfInterest
	bestScore := -1.0
	for _, p := range pois {
		pPt := image.Point{X: p.X, Y: p.Y}
		if !isSegmentWallSafe(pPt, edgePt, wallMask, gateMask) {
			continue
		}
		d := math.Hypot(float64(p.X-edgePt.X), float64(p.Y-edgePt.Y))
		score := p.ArterialWeight*2.0 + clamp(1.0-d/2000.0, 0, 1)
		if score > bestScore {
			bestScore = score
			best = p
		}
	}
	return best
}

func sampleNonWaterEdgePOI(width, height int, randSrc *rand.Rand, waterMask *PixelMask, used []image.Point) (*PointOfInterest, bool) {
	minSpacing := math.Min(float64(width), float64(height)) * 0.08
	minSpacing2 := minSpacing * minSpacing

	for tries := 0; tries < 120; tries++ {
		p := sampleEdgePOI(width, height, randSrc)
		pt := image.Point{X: p.X, Y: p.Y}
		if waterMask != nil && waterMask.GetPoint(pt) {
			continue
		}
		tooClose := false
		for _, u := range used {
			dx := float64(u.X - p.X)
			dy := float64(u.Y - p.Y)
			if dx*dx+dy*dy < minSpacing2 {
				tooClose = true
				break
			}
		}
		if tooClose {
			continue
		}
		return p, true
	}
	return nil, false
}

func chooseExitAnchor(pois []*PointOfInterest, usedExits []image.Point, randSrc *rand.Rand) *PointOfInterest {
	if len(pois) == 0 {
		return nil
	}
	if len(usedExits) == 0 {
		best := pois[0]
		for i := 1; i < len(pois); i++ {
			if pois[i].ArterialWeight > best.ArterialWeight {
				best = pois[i]
			}
		}
		return best
	}

	target := usedExits[len(usedExits)-1]
	best := pois[randSrc.Intn(len(pois))]
	bestScore := -1.0
	for _, p := range pois {
		d := math.Hypot(float64(p.X-target.X), float64(p.Y-target.Y))
		score := p.ArterialWeight*2.0 + clamp(1.0-d/2000.0, 0, 1)
		if score > bestScore {
			bestScore = score
			best = p
		}
	}
	return best
}

func estimateRoadTarget(settings *Settings) int {
	if settings.NumBuildings <= 0 {
		return 0
	}
	if settings.NumBuildings < 10 {
		return settings.NumBuildings
	}
	buildings := float64(max(settings.NumBuildings, 1))
	roads := buildings / 5.0
	if buildings > 80 {
		roads += math.Pow(buildings-80.0, 0.70) * 0.30
	}
	if buildings > 500 {
		roads += math.Pow((buildings-500.0)/2.2, 0.66) * 0.20
	}
	if buildings > 1800 {
		roads *= 0.95
	}
	if buildings > 4000 {
		roads *= 0.90
	}
	result := int(math.Round(roads))
	if result < 1 {
		result = 1
	}
	return result
}

func edgeKey(a, b int) uint64 {
	if a > b {
		a, b = b, a
	}
	return (uint64(uint32(a)) << 32) | uint64(uint32(b))
}

func degreePenalty(a, b *PointOfInterest) float64 {
	penalty := 0.0
	if a.Connections >= a.TargetDegree {
		penalty += 0.20 + float64(a.Connections-a.TargetDegree)*0.12
	}
	if b.Connections >= b.TargetDegree {
		penalty += 0.20 + float64(b.Connections-b.TargetDegree)*0.12
	}
	return penalty
}

func angleAllowed(existing []float64, candidate, minAngle float64) bool {
	if minAngle <= 0 || len(existing) == 0 {
		return true
	}
	for _, ang := range existing {
		d := math.Abs(normalizeAngle(candidate - ang))
		if d > math.Pi {
			d = 2*math.Pi - d
		}
		if d < minAngle {
			return false
		}
	}
	return true
}

func normalizeAngle(a float64) float64 {
	for a <= -math.Pi {
		a += 2 * math.Pi
	}
	for a > math.Pi {
		a -= 2 * math.Pi
	}
	return a
}

func assignRoadWidths(roads []*Road, settings *Settings, randSrc *rand.Rand, width, height int, wallLayout *FortificationLayout) {
	if len(roads) == 0 {
		return
	}

	minWidth, maxWidth := getRoadWidthRangePixels(settings, width, height)
	if maxWidth < minWidth {
		minWidth, maxWidth = maxWidth, minWidth
	}

	maxImportance := 1
	for _, road := range roads {
		if road.Importance > maxImportance {
			maxImportance = road.Importance
		}
	}

	widths := make([]float64, len(roads))
	startNode := make([]int, len(roads))
	endNode := make([]int, len(roads))
	nodeIndex := make(map[image.Point]int, len(roads)*2)
	adj := make([][]int, 0, len(roads))
	getNodeID := func(p *PointOfInterest) int {
		pt := image.Point{X: p.X, Y: p.Y}
		if id, ok := nodeIndex[pt]; ok {
			return id
		}
		id := len(adj)
		nodeIndex[pt] = id
		adj = append(adj, nil)
		return id
	}

	for i, r := range roads {
		n := float64(r.Importance) / float64(maxImportance)
		jitter := (randSrc.Float64() - 0.5) * 0.16
		base := minWidth + (maxWidth-minWidth)*clamp01(n+jitter)
		widths[i] = base
		sid := getNodeID(r.Start)
		eid := getNodeID(r.End)
		startNode[i] = sid
		endNode[i] = eid
		adj[sid] = append(adj[sid], i)
		adj[eid] = append(adj[eid], i)
	}

	for i := 0; i < 2; i++ {
		next := make([]float64, len(widths))
		for ridx, w := range widths {
			total := w
			count := 1.0
			for _, nid := range []int{startNode[ridx], endNode[ridx]} {
				for _, nbr := range adj[nid] {
					if nbr == ridx {
						continue
					}
					total += widths[nbr]
					count += 1
				}
			}
			next[ridx] = w*0.55 + (total/count)*0.45
		}
		widths = next
	}

	for i, r := range roads {
		w := clamp(widths[i], minWidth, maxWidth)
		if wallLayout != nil && wallLayout.Mask != nil && len(crossedWallIDs(r.Points, wallLayout)) > 0 {
			minGateWidth := minWidth + 0.55*(maxWidth-minWidth)
			if w < minGateWidth {
				w = minGateWidth
			}
		}
		r.Width = max(1, int(math.Round(w)))
	}
}

// drawRoadToMasks draws a single road on the image including bridges.
func drawRoadToMasks(img *image.RGBA, points []PathPoint, roadColor, bridgeColor color.Color, width int, roadMask, bridgeMask *PixelMask) {
	bridgeWidth := int(math.Ceil(float64(width) * 1.15))
	if bridgeWidth < 1 {
		bridgeWidth = 1
	}

	for i := 0; i < len(points)-1; {
		p1 := points[i]
		p2 := points[i+1]
		isBridge := p1.IsBridge && p2.IsBridge
		if !isBridge {
			drawLineMasked(img, p1.Point.X, p1.Point.Y, p2.Point.X, p2.Point.Y, roadColor, width, roadMask)
			i++
			continue
		}

		start := i
		end := i + 1
		for end < len(points)-1 && points[end].IsBridge && points[end+1].IsBridge {
			end++
		}
		drawLineMasked(
			img,
			points[start].Point.X, points[start].Point.Y,
			points[end].Point.X, points[end].Point.Y,
			bridgeColor,
			bridgeWidth,
			bridgeMask,
		)
		i = end
	}
}

func bresenhamRoad(path []image.Point) []image.Point {
	if len(path) < 2 {
		return path
	}

	fullPath := make([]image.Point, 0, len(path)*8)
	for i := 0; i < len(path)-1; i++ {
		p1, p2 := path[i], path[i+1]
		dx, dy := p2.X-p1.X, p2.Y-p1.Y
		absDx, absDy := int(math.Abs(float64(dx))), int(math.Abs(float64(dy)))
		sx, sy := 1, 1
		if dx < 0 {
			sx = -1
		}
		if dy < 0 {
			sy = -1
		}
		err := absDx - absDy

		x, y := p1.X, p1.Y
		for {
			fullPath = append(fullPath, image.Point{X: x, Y: y})
			if x == p2.X && y == p2.Y {
				break
			}
			e2 := 2 * err
			if e2 > -absDy {
				err -= absDy
				x += sx
			}
			if e2 < absDx {
				err += absDx
				y += sy
			}
		}
	}
	return fullPath
}

// calculateRoadPath computes the path for a road including curves and bridges.
func calculateRoadPath(start, end *PointOfInterest, curvyness, avgDim float64, randSrc *rand.Rand, waterMask *PixelMask, wallLayout *FortificationLayout, tier RoadTier) []PathPoint {
	if start == nil || end == nil {
		return nil
	}
	dx := end.X - start.X
	dy := end.Y - start.Y
	dist := math.Hypot(float64(dx), float64(dy))

	if dist == 0 {
		p := image.Point{X: start.X, Y: start.Y}
		isBridge := waterMask != nil && waterMask.GetPoint(p)
		return []PathPoint{{Point: p, IsBridge: isBridge}}
	}

	curve := clamp(curvyness, 0, 1)
	if curve <= 0.01 || dist < 10 {
		points := bresenhamRoad([]image.Point{{X: start.X, Y: start.Y}, {X: end.X, Y: end.Y}})
		return toPathPoints(points, waterMask)
	}

	perpX, perpY := -float64(dy)/dist, float64(dx)/dist
	strength := math.Pow(curve, 1.1)
	baseAmp := clamp(dist*(0.018+0.055*strength), 1.5, avgDim*0.06)

	addControl := func(points []image.Point, t, lateral float64) []image.Point {
		x := float64(start.X) + t*float64(dx)
		y := float64(start.Y) + t*float64(dy)
		x += lateral * perpX
		y += lateral * perpY
		return append(points, image.Point{X: int(math.Round(x)), Y: int(math.Round(y))})
	}

	polyline := []image.Point{{X: start.X, Y: start.Y}}
	switch tier {
	case RoadTierArterial:
		lateral := baseAmp * (0.7 + randSrc.Float64()*0.35)
		if randSrc.Float64() < 0.5 {
			lateral = -lateral
		}
		polyline = addControl(polyline, 0.33, lateral*0.45)
		polyline = addControl(polyline, 0.66, lateral)
	case RoadTierCollector:
		lateral := baseAmp * (0.9 + randSrc.Float64()*0.45)
		if randSrc.Float64() < 0.5 {
			lateral = -lateral
		}
		polyline = addControl(polyline, 0.35, lateral*0.65)
		polyline = addControl(polyline, 0.72, lateral)
	default:
		lateralA := baseAmp * (0.65 + randSrc.Float64()*0.30)
		lateralB := lateralA * (0.35 + randSrc.Float64()*0.25)
		if randSrc.Float64() < 0.5 {
			lateralA = -lateralA
		}
		if randSrc.Float64() < 0.8 {
			lateralB = lateralA * (0.35 + randSrc.Float64()*0.20)
		} else {
			lateralB = -lateralB
		}
		polyline = addControl(polyline, 0.30, lateralA)
		polyline = addControl(polyline, 0.68, lateralB)
	}
	polyline = append(polyline, image.Point{X: end.X, Y: end.Y})

	points := bresenhamRoad(polyline)
	path := toPathPoints(points, waterMask)

	// If the curved path accidentally intersects a wall where straight line doesn't, revert to straight line
	if wallLayout != nil && wallLayout.Mask != nil && !pathRespectsWallPassages(path, wallLayout.Mask, wallLayout.GateMask) {
		straight := bresenhamRoad([]image.Point{{X: start.X, Y: start.Y}, {X: end.X, Y: end.Y}})
		path = toPathPoints(straight, waterMask)
	}

	return path
}

func toPathPoints(points []image.Point, waterMask *PixelMask) []PathPoint {
	pathPoints := make([]PathPoint, len(points))
	for i, p := range points {
		isBridge := false
		if waterMask != nil {
			isBridge = waterMask.GetPoint(p)
		}
		pathPoints[i] = PathPoint{Point: p, IsBridge: isBridge}
	}
	return pathPoints
}

func wallIDAtPoint(p image.Point, wallLayout *FortificationLayout) int {
	if wallLayout == nil || wallLayout.Mask == nil {
		return 0
	}
	if !wallLayout.Mask.InBounds(p.X, p.Y) {
		return 0
	}
	if len(wallLayout.WallIDByPixel) != wallLayout.Mask.Width*wallLayout.Mask.Height {
		return 0
	}
	return wallLayout.WallIDByPixel[p.Y*wallLayout.Mask.Width+p.X]
}

func crossedWallIDs(points []PathPoint, wallLayout *FortificationLayout) []int {
	if wallLayout == nil || wallLayout.Mask == nil || len(points) == 0 {
		return nil
	}
	seen := make(map[int]bool)
	out := make([]int, 0, 2)
	prevID := wallIDAtPoint(points[0].Point, wallLayout)
	for i := 1; i < len(points); i++ {
		currID := wallIDAtPoint(points[i].Point, wallLayout)
		if (prevID == 0 && currID > 0) || (prevID > 0 && currID == 0) {
			wid := currID
			if wid == 0 {
				wid = prevID
			}
			if wid > 0 && !seen[wid] {
				seen[wid] = true
				out = append(out, wid)
			}
		}
		prevID = currID
	}
	return out
}

func applyWallCrossingRules(roads []*Road, wallLayout *FortificationLayout, waterMask *PixelMask, randSrc *rand.Rand) []*Road {
	if len(roads) == 0 || wallLayout == nil || wallLayout.Mask == nil {
		return roads
	}
	_ = waterMask
	_ = randSrc
	filtered := make([]*Road, 0, len(roads))
	for _, road := range roads {
		if pathRespectsWallPassages(road.Points, wallLayout.Mask, wallLayout.GateMask) {
			filtered = append(filtered, road)
		}
	}
	return filtered
}

func pathRespectsWallPassages(points []PathPoint, exclusionMask, gateMask *PixelMask) bool {
	if len(points) == 0 || exclusionMask == nil {
		return true
	}
	for _, pp := range points {
		x := pp.Point.X
		y := pp.Point.Y
		if !exclusionMask.InBounds(x, y) {
			continue
		}
		if exclusionMask.GetXY(x, y) {
			if gateMask != nil && gateMask.GetXY(x, y) {
				continue
			}
			return false
		}
	}
	return true
}

// isRoadEssentialForConnectivity returns true if removing roads[skipIdx] disconnects road.Start from road.End in the graph.
func isRoadEssentialForConnectivity(roads []*Road, skipIdx int) bool {
	target := roads[skipIdx]
	if target.Start == nil || target.End == nil {
		return false
	}
	start := image.Point{X: target.Start.X, Y: target.Start.Y}
	end := image.Point{X: target.End.X, Y: target.End.Y}

	adj := make(map[image.Point][]image.Point)
	for i, r := range roads {
		if i == skipIdx || r.Start == nil || r.End == nil {
			continue
		}
		pA := image.Point{X: r.Start.X, Y: r.Start.Y}
		pB := image.Point{X: r.End.X, Y: r.End.Y}
		adj[pA] = append(adj[pA], pB)
		adj[pB] = append(adj[pB], pA)
	}

	visited := make(map[image.Point]bool)
	visited[start] = true
	queue := []image.Point{start}

	for len(queue) > 0 {
		curr := queue[0]
		queue = queue[1:]
		if curr == end {
			return false // End is still reachable without target road
		}
		for _, nbr := range adj[curr] {
			if !visited[nbr] {
				visited[nbr] = true
				queue = append(queue, nbr)
			}
		}
	}

	return true // End is unreachable without target road -> essential bridge
}

func reduceRepeatedBridges(roads []*Road, waterMask *PixelMask, width, height int, randSrc *rand.Rand) []*Road {
	if len(roads) == 0 || waterMask == nil {
		return roads
	}

	regionByPixel := buildWaterRegionMap(waterMask)
	if len(regionByPixel) == 0 {
		return roads
	}

	const repeatBridgeFactor = 0.45
	bodyBridgeCount := make(map[int]int)
	filtered := make([]*Road, 0, len(roads))

	for i, road := range roads {
		bridgedBodies := bridgedRegionIDs(road.Points, regionByPixel, width, height)
		if len(bridgedBodies) == 0 {
			filtered = append(filtered, road)
			continue
		}

		// Never delete a bridge if it disconnects the road network
		if isRoadEssentialForConnectivity(roads, i) {
			filtered = append(filtered, road)
			for _, body := range bridgedBodies {
				bodyBridgeCount[body]++
			}
			continue
		}

		keepProb := 1.0
		for _, body := range bridgedBodies {
			c := bodyBridgeCount[body]
			if c > 0 {
				keepProb *= math.Pow(repeatBridgeFactor, float64(c))
			}
		}
		if randSrc.Float64() <= keepProb {
			filtered = append(filtered, road)
			for _, body := range bridgedBodies {
				bodyBridgeCount[body]++
			}
		}
	}

	return filtered
}

func buildWaterRegionMap(waterMask *PixelMask) []int {
	if waterMask == nil || waterMask.Width <= 0 || waterMask.Height <= 0 {
		return nil
	}
	total := waterMask.Width * waterMask.Height
	region := make([]int, total)
	nextRegionID := 1

	queue := make([]int, 0, 1024)
	for idx := 0; idx < total; idx++ {
		if waterMask.Data[idx] == 0 || region[idx] != 0 {
			continue
		}
		region[idx] = nextRegionID
		queue = queue[:0]
		queue = append(queue, idx)

		for head := 0; head < len(queue); head++ {
			cur := queue[head]
			x := cur % waterMask.Width
			y := cur / waterMask.Width

			neighbors := [][2]int{
				{x - 1, y}, {x + 1, y},
				{x, y - 1}, {x, y + 1},
			}
			for _, n := range neighbors {
				nx, ny := n[0], n[1]
				if nx < 0 || ny < 0 || nx >= waterMask.Width || ny >= waterMask.Height {
					continue
				}
				nidx := ny*waterMask.Width + nx
				if waterMask.Data[nidx] == 0 || region[nidx] != 0 {
					continue
				}
				region[nidx] = nextRegionID
				queue = append(queue, nidx)
			}
		}
		nextRegionID++
	}
	return region
}

func bridgedRegionIDs(points []PathPoint, regionByPixel []int, width, height int) []int {
	if len(points) == 0 || len(regionByPixel) == 0 || width <= 0 || height <= 0 {
		return nil
	}
	seen := make(map[int]bool)
	out := make([]int, 0, 2)
	for _, pp := range points {
		if !pp.IsBridge {
			continue
		}
		x, y := pp.Point.X, pp.Point.Y
		if x < 0 || y < 0 || x >= width || y >= height {
			continue
		}
		rid := regionByPixel[y*width+x]
		if rid <= 0 || seen[rid] {
			continue
		}
		seen[rid] = true
		out = append(out, rid)
	}
	return out
}

func buildWallExclusionMask(wallLayout *FortificationLayout, settings *Settings, width, height int) *PixelMask {
	if wallLayout == nil || wallLayout.Mask == nil {
		return NewPixelMask(width, height)
	}
	_, maxRoadPx := getRoadWidthRangePixels(settings, width, height)
	margin := int(math.Ceil(maxRoadPx))
	if margin < 1 {
		margin = 1
	}
	out := NewPixelMask(width, height)
	for y := 0; y < height; y++ {
		for x := 0; x < width; x++ {
			if !wallLayout.Mask.GetXY(x, y) {
				continue
			}
			for dy := -margin; dy <= margin; dy++ {
				for dx := -margin; dx <= margin; dx++ {
					if dx*dx+dy*dy <= margin*margin {
						out.SetXY(x+dx, y+dy)
					}
				}
			}
		}
	}
	return out
}

func generateGateRoads(wallLayout *FortificationLayout, settings *Settings, waterMask *PixelMask, width, height int, randSrc *rand.Rand) []*Road {
	if wallLayout == nil || len(wallLayout.Gates) == 0 {
		return nil
	}
	_, maxRoadPx := getRoadWidthRangePixels(settings, width, height)
	roadWidth := int(math.Round(maxRoadPx + 0.5*maxRoadPx))
	if roadWidth < 1 {
		roadWidth = 1
	}

	roads := make([]*Road, 0, len(wallLayout.Gates))
	for _, gate := range wallLayout.Gates {
		outer := &PointOfInterest{X: gate.OuterEnd.X, Y: gate.OuterEnd.Y, IsExit: false}
		inner := &PointOfInterest{X: gate.InnerEnd.X, Y: gate.InnerEnd.Y, IsExit: false}
		outer.Connections = 1
		inner.Connections = 1

		pts := bresenhamRoad([]image.Point{gate.OuterEnd, gate.InnerEnd})
		path := toPathPoints(pts, waterMask)

		roads = append(roads, &Road{
			Start:      outer,
			End:        inner,
			Points:     path,
			Width:      roadWidth,
			Importance: 10,
			Tier:       RoadTierArterial,
		})
	}
	return roads
}

func ensureGateRoadConnections(gateRoads []*Road, allRoads []*Road, wallLayout *FortificationLayout, settings *Settings, waterMask *PixelMask, width, height int, randSrc *rand.Rand) []*Road {
	if len(gateRoads) == 0 || wallLayout == nil {
		return allRoads
	}

	poiSet := make(map[image.Point]*PointOfInterest)
	for _, r := range allRoads {
		if r.Start != nil {
			poiSet[image.Point{X: r.Start.X, Y: r.Start.Y}] = r.Start
		}
		if r.End != nil {
			poiSet[image.Point{X: r.End.X, Y: r.End.Y}] = r.End
		}
	}
	for _, r := range gateRoads {
		delete(poiSet, image.Point{X: r.Start.X, Y: r.Start.Y})
		delete(poiSet, image.Point{X: r.End.X, Y: r.End.Y})
	}
	pois := make([]*PointOfInterest, 0, len(poiSet))
	for _, p := range poiSet {
		pois = append(pois, p)
	}

	connectors := make([]*Road, 0, len(gateRoads)*4)
	_, maxRoadPx := getRoadWidthRangePixels(settings, width, height)
	connW := int(math.Round(maxRoadPx))
	if connW < 1 {
		connW = 1
	}

	var wallMask, gateMask *PixelMask
	if wallLayout != nil {
		wallMask = wallLayout.Mask
		gateMask = wallLayout.GateMask
	}

	for _, gr := range gateRoads {
		for _, ep := range []*PointOfInterest{gr.Start, gr.End} {
			if len(pois) == 0 {
				break
			}
			epPt := image.Point{X: ep.X, Y: ep.Y}

			type poiCandidate struct {
				poi  *PointOfInterest
				dist float64
			}
			var candidates []poiCandidate
			for _, p := range pois {
				pPt := image.Point{X: p.X, Y: p.Y}
				if !isSegmentWallSafe(epPt, pPt, wallMask, gateMask) {
					continue
				}
				d := math.Hypot(float64(p.X-ep.X), float64(p.Y-ep.Y))
				candidates = append(candidates, poiCandidate{poi: p, dist: d})
			}

			sort.Slice(candidates, func(i, j int) bool {
				return candidates[i].dist < candidates[j].dist
			})

			// Connect to up to 2 nearest wall-safe POIs on that side
			connectCount := min(2, len(candidates))
			for cIdx := 0; cIdx < connectCount; cIdx++ {
				best := candidates[cIdx].poi
				pts := bresenhamRoad([]image.Point{epPt, {X: best.X, Y: best.Y}})
				path := toPathPoints(pts, waterMask)
				ep.Connections++
				best.Connections++
				connectors = append(connectors, &Road{
					Start:      ep,
					End:        best,
					Points:     path,
					Width:      connW,
					Importance: 6,
					Tier:       RoadTierCollector,
				})
			}
		}
	}
	return append(allRoads, connectors...)
}

// gridNode represents a node in A* grid pathfinding
type gridNode struct {
	x, y      int
	gCost     float64
	fCost     float64
	index     int
	parentIdx int
}

type gridPriorityQueue []*gridNode

func (pq gridPriorityQueue) Len() int           { return len(pq) }
func (pq gridPriorityQueue) Less(i, j int) bool { return pq[i].fCost < pq[j].fCost }
func (pq gridPriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}
func (pq *gridPriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*gridNode)
	item.index = n
	*pq = append(*pq, item)
}
func (pq *gridPriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil
	item.index = -1
	*pq = old[0 : n-1]
	return item
}

// findWallSafePath generates a path of points between start and end that avoids walls (or passes through gates).
func findWallSafePath(start, end image.Point, wallMask, gateMask, waterMask *PixelMask, width, height int) []PathPoint {
	if isSegmentWallSafe(start, end, wallMask, gateMask) {
		pts := bresenhamRoad([]image.Point{start, end})
		return toPathPoints(pts, waterMask)
	}

	if wallMask == nil {
		pts := bresenhamRoad([]image.Point{start, end})
		return toPathPoints(pts, waterMask)
	}

	// Downsampled grid A* for obstacle avoidance
	step := 6
	gw := (width + step - 1) / step
	gh := (height + step - 1) / step

	sx, sy := clampInt(start.X/step, 0, gw-1), clampInt(start.Y/step, 0, gh-1)
	ex, ey := clampInt(end.X/step, 0, gw-1), clampInt(end.Y/step, 0, gh-1)

	isBlocked := func(gx, gy int) bool {
		if (gx == sx && gy == sy) || (gx == ex && gy == ey) {
			return false
		}
		if gateMask != nil {
			for dy := 0; dy < step; dy++ {
				for dx := 0; dx < step; dx++ {
					if gateMask.GetXY(gx*step+dx, gy*step+dy) {
						return false
					}
				}
			}
		}
		px := gx*step + step/2
		py := gy*step + step/2
		if !wallMask.InBounds(px, py) {
			return false
		}
		return wallMask.GetXY(px, py)
	}

	cellKey := func(x, y int) int { return y*gw + x }

	pq := make(gridPriorityQueue, 0, 256)
	heap.Init(&pq)

	allNodes := make([]*gridNode, 0, gw*gh)
	nodeMap := make(map[int]int, gw*gh)

	hCost := func(x, y int) float64 {
		return math.Hypot(float64(x-ex), float64(y-ey))
	}

	startNode := &gridNode{x: sx, y: sy, gCost: 0, fCost: hCost(sx, sy), parentIdx: -1}
	allNodes = append(allNodes, startNode)
	nodeMap[cellKey(sx, sy)] = 0
	heap.Push(&pq, startNode)

	closed := make(map[int]bool, gw*gh)
	targetIdx := -1

	dxs := []int{1, -1, 0, 0, 1, -1, 1, -1}
	dys := []int{0, 0, 1, -1, 1, 1, -1, -1}
	dcosts := []float64{1.0, 1.0, 1.0, 1.0, 1.414, 1.414, 1.414, 1.414}

	maxIterations := gw * gh * 2
	for pq.Len() > 0 && maxIterations > 0 {
		maxIterations--
		curr := heap.Pop(&pq).(*gridNode)
		currKey := cellKey(curr.x, curr.y)
		if closed[currKey] {
			continue
		}
		closed[currKey] = true

		if curr.x == ex && curr.y == ey {
			targetIdx = nodeMap[currKey]
			break
		}

		for i := 0; i < 8; i++ {
			nx, ny := curr.x+dxs[i], curr.y+dys[i]
			if nx < 0 || ny < 0 || nx >= gw || ny >= gh {
				continue
			}
			nKey := cellKey(nx, ny)
			if closed[nKey] {
				continue
			}
			if isBlocked(nx, ny) {
				continue
			}

			newG := curr.gCost + dcosts[i]
			if existingIdx, exists := nodeMap[nKey]; exists {
				nbrNode := allNodes[existingIdx]
				if newG < nbrNode.gCost {
					nbrNode.gCost = newG
					nbrNode.fCost = newG + hCost(nx, ny)
					nbrNode.parentIdx = nodeMap[currKey]
					heap.Fix(&pq, nbrNode.index)
				}
			} else {
				nbrNode := &gridNode{
					x:         nx,
					y:         ny,
					gCost:     newG,
					fCost:     newG + hCost(nx, ny),
					parentIdx: nodeMap[currKey],
				}
				idx := len(allNodes)
				allNodes = append(allNodes, nbrNode)
				nodeMap[nKey] = idx
				heap.Push(&pq, nbrNode)
			}
		}
	}

	if targetIdx == -1 {
		return nil
	}

	// Reconstruct waypoint path
	var waypoints []image.Point
	currIdx := targetIdx
	for currIdx != -1 {
		gn := allNodes[currIdx]
		waypoints = append(waypoints, image.Point{X: gn.x*step + step/2, Y: gn.y*step + step/2})
		currIdx = gn.parentIdx
	}
	// Reverse waypoints
	for i, j := 0, len(waypoints)-1; i < j; i, j = i+1, j-1 {
		waypoints[i], waypoints[j] = waypoints[j], waypoints[i]
	}
	waypoints[0] = start
	waypoints[len(waypoints)-1] = end

	pts := bresenhamRoad(waypoints)
	path := toPathPoints(pts, waterMask)
	if !pathRespectsWallPassages(path, wallMask, gateMask) {
		return nil
	}
	return path
}

func ensureRoadNetworkConnected(roads []*Road, settings *Settings, randSrc *rand.Rand, waterMask *PixelMask, wallLayout *FortificationLayout, width, height int) []*Road {
	if len(roads) <= 1 {
		return roads
	}

	avgDim := float64(width+height) / 2.0
	const maxConnectorAttempts = 48

	var wallMask, gateMask *PixelMask
	if wallLayout != nil {
		wallMask = wallLayout.Mask
		gateMask = wallLayout.GateMask
	}

	for attempts := 0; attempts < maxConnectorAttempts; attempts++ {
		nodeIndex := make(map[image.Point]int)
		nodes := make([]*PointOfInterest, 0, len(roads)*2)
		getNodeID := func(p *PointOfInterest) int {
			pt := image.Point{X: p.X, Y: p.Y}
			if id, ok := nodeIndex[pt]; ok {
				return id
			}
			id := len(nodes)
			nodeIndex[pt] = id
			nodes = append(nodes, p)
			return id
		}
		adj := make([][]int, 0, len(roads)*2)
		ensureAdj := func(n int) {
			for len(adj) <= n {
				adj = append(adj, nil)
			}
		}
		for _, r := range roads {
			if r.Start == nil || r.End == nil {
				continue
			}
			a := getNodeID(r.Start)
			b := getNodeID(r.End)
			ensureAdj(a)
			ensureAdj(b)
			adj[a] = append(adj[a], b)
			adj[b] = append(adj[b], a)
		}

		if len(nodes) == 0 {
			return roads
		}

		compID := make([]int, len(nodes))
		for i := range compID {
			compID[i] = -1
		}
		compCount := 0
		queue := make([]int, 0, len(nodes))
		for i := 0; i < len(nodes); i++ {
			if compID[i] != -1 {
				continue
			}
			compID[i] = compCount
			queue = queue[:0]
			queue = append(queue, i)
			for h := 0; h < len(queue); h++ {
				cur := queue[h]
				for _, nb := range adj[cur] {
					if compID[nb] != -1 {
						continue
					}
					compID[nb] = compCount
					queue = append(queue, nb)
				}
			}
			compCount++
		}
		if compCount <= 1 {
			return roads
		}

		// Priority 1: Shortest direct wall-safe connection between different components
		bestA, bestB := -1, -1
		bestDist2 := math.MaxFloat64
		for i := 0; i < len(nodes); i++ {
			for j := i + 1; j < len(nodes); j++ {
				if compID[i] == compID[j] {
					continue
				}
				ptA := image.Point{X: nodes[i].X, Y: nodes[i].Y}
				ptB := image.Point{X: nodes[j].X, Y: nodes[j].Y}
				if !isSegmentWallSafe(ptA, ptB, wallMask, gateMask) {
					continue
				}
				dx := float64(nodes[i].X - nodes[j].X)
				dy := float64(nodes[i].Y - nodes[j].Y)
				d2 := dx*dx + dy*dy
				if d2 < bestDist2 {
					bestDist2 = d2
					bestA, bestB = i, j
				}
			}
		}

		if bestA != -1 && bestB != -1 {
			a := nodes[bestA]
			b := nodes[bestB]
			path := calculateRoadPath(a, b, settings.RoadCurvyness/100.0, avgDim, randSrc, waterMask, wallLayout, RoadTierCollector)
			if !pathRespectsWallPassages(path, wallMask, gateMask) {
				path = findWallSafePath(image.Point{X: a.X, Y: a.Y}, image.Point{X: b.X, Y: b.Y}, wallMask, gateMask, waterMask, width, height)
			}
			if path != nil && pathRespectsWallPassages(path, wallMask, gateMask) {
				a.Connections++
				b.Connections++
				roads = append(roads, &Road{
					Start:      a,
					End:        b,
					Points:     path,
					Importance: a.Connections + b.Connections + 2,
					Tier:       RoadTierCollector,
				})
				continue
			}
		}

		// Priority 2: Connect components across walls through the closest gate
		if wallLayout != nil && len(wallLayout.Gates) > 0 {
			gateConnected := false
			for _, gate := range wallLayout.Gates {
				innerPt := gate.InnerEnd
				outerPt := gate.OuterEnd
				innerPOI := &PointOfInterest{X: innerPt.X, Y: innerPt.Y}
				outerPOI := &PointOfInterest{X: outerPt.X, Y: outerPt.Y}

				for i := 0; i < len(nodes); i++ {
					ptA := image.Point{X: nodes[i].X, Y: nodes[i].Y}
					for j := 0; j < len(nodes); j++ {
						if compID[i] == compID[j] {
							continue
						}
						ptB := image.Point{X: nodes[j].X, Y: nodes[j].Y}

						// Try path ptA -> outerPt, and ptB -> innerPt
						pathA := findWallSafePath(ptA, outerPt, wallMask, gateMask, waterMask, width, height)
						pathB := findWallSafePath(ptB, innerPt, wallMask, gateMask, waterMask, width, height)
						if pathA != nil && pathB != nil {
							gateRoadPts := bresenhamRoad([]image.Point{outerPt, innerPt})
							roads = append(roads, &Road{
								Start:      outerPOI,
								End:        innerPOI,
								Points:     toPathPoints(gateRoadPts, waterMask),
								Importance: 8,
								Tier:       RoadTierArterial,
							})
							roads = append(roads, &Road{
								Start:      nodes[i],
								End:        outerPOI,
								Points:     pathA,
								Importance: 5,
								Tier:       RoadTierCollector,
							})
							roads = append(roads, &Road{
								Start:      nodes[j],
								End:        innerPOI,
								Points:     pathB,
								Importance: 5,
								Tier:       RoadTierCollector,
							})
							nodes[i].Connections++
							nodes[j].Connections++
							gateConnected = true
							break
						}

						// Try reverse: ptA -> innerPt, and ptB -> outerPt
						pathA = findWallSafePath(ptA, innerPt, wallMask, gateMask, waterMask, width, height)
						pathB = findWallSafePath(ptB, outerPt, wallMask, gateMask, waterMask, width, height)
						if pathA != nil && pathB != nil {
							gateRoadPts := bresenhamRoad([]image.Point{outerPt, innerPt})
							roads = append(roads, &Road{
								Start:      outerPOI,
								End:        innerPOI,
								Points:     toPathPoints(gateRoadPts, waterMask),
								Importance: 8,
								Tier:       RoadTierArterial,
							})
							roads = append(roads, &Road{
								Start:      nodes[i],
								End:        innerPOI,
								Points:     pathA,
								Importance: 5,
								Tier:       RoadTierCollector,
							})
							roads = append(roads, &Road{
								Start:      nodes[j],
								End:        outerPOI,
								Points:     pathB,
								Importance: 5,
								Tier:       RoadTierCollector,
							})
							nodes[i].Connections++
							nodes[j].Connections++
							gateConnected = true
							break
						}
					}
					if gateConnected {
						break
					}
				}
				if gateConnected {
					break
				}
			}
			if gateConnected {
				continue
			}
		}

		// Priority 3: Pathfinding around walls via A*
		foundPath := false
		for i := 0; i < len(nodes) && !foundPath; i++ {
			for j := i + 1; j < len(nodes) && !foundPath; j++ {
				if compID[i] == compID[j] {
					continue
				}
				a := nodes[i]
				b := nodes[j]
				ptA := image.Point{X: a.X, Y: a.Y}
				ptB := image.Point{X: b.X, Y: b.Y}
				path := findWallSafePath(ptA, ptB, wallMask, gateMask, waterMask, width, height)
				if path != nil && pathRespectsWallPassages(path, wallMask, gateMask) {
					a.Connections++
					b.Connections++
					roads = append(roads, &Road{
						Start:      a,
						End:        b,
						Points:     path,
						Importance: a.Connections + b.Connections + 2,
						Tier:       RoadTierCollector,
					})
					foundPath = true
					break
				}
			}
		}

		if !foundPath {
			// No safe path could be found this iteration
			break
		}
	}

	return roads
}

func drawLineMasked(img *image.RGBA, x0, y0, x1, y1 int, col color.Color, width int, mask *PixelMask) {
	dx := abs(x1 - x0)
	dy := -abs(y1 - y0)
	sx := -1
	if x0 < x1 {
		sx = 1
	}
	sy := -1
	if y0 < y1 {
		sy = 1
	}
	err := dx + dy

	for {
		for i := -width / 2; i <= width/2; i++ {
			for j := -width / 2; j <= width/2; j++ {
				px := x0 + i
				py := y0 + j
				if img.Bounds().Min.X <= px && px < img.Bounds().Max.X && img.Bounds().Min.Y <= py && py < img.Bounds().Max.Y {
					img.Set(px, py, col)
					if mask != nil {
						mask.SetXY(px, py)
					}
				}
			}
		}

		if x0 == x1 && y0 == y1 {
			break
		}
		e2 := 2 * err
		if e2 >= dy {
			err += dy
			x0 += sx
		}
		if e2 <= dx {
			err += dx
			y0 += sy
		}
	}
}

func collectRoadAnchors(roads []*Road, settings *Settings, waterMask *PixelMask, width, height int) []image.Point {
	if len(roads) == 0 {
		return nil
	}

	minBuildingSizePx, maxBuildingSizePx := getBuildingSizeRangePixels(settings, width, height)
	spacing := int(math.Round(clamp((minBuildingSizePx+maxBuildingSizePx)*0.5, 8, 28)))
	switch {
	case settings.NumBuildings >= 2500:
		spacing = int(math.Round(float64(spacing) * 0.72))
	case settings.NumBuildings >= 1000:
		spacing = int(math.Round(float64(spacing) * 0.80))
	case settings.NumBuildings >= 300:
		spacing = int(math.Round(float64(spacing) * 0.90))
	}
	if spacing < 6 {
		spacing = 6
	}
	cellSize := max(4, spacing/2)

	type anchorCell struct {
		x int
		y int
	}

	cells := make(map[anchorCell][]image.Point)
	anchors := make([]image.Point, 0, len(roads)*4)

	addAnchor := func(p image.Point) {
		if p.X < 0 || p.Y < 0 || p.X >= width || p.Y >= height {
			return
		}
		if waterMask != nil && waterMask.GetPoint(p) {
			return
		}

		cx := p.X / cellSize
		cy := p.Y / cellSize
		for dy := -1; dy <= 1; dy++ {
			for dx := -1; dx <= 1; dx++ {
				key := anchorCell{x: cx + dx, y: cy + dy}
				for _, existing := range cells[key] {
					ddx := existing.X - p.X
					ddy := existing.Y - p.Y
					if ddx*ddx+ddy*ddy < spacing*spacing {
						return
					}
				}
			}
		}

		key := anchorCell{x: cx, y: cy}
		cells[key] = append(cells[key], p)
		anchors = append(anchors, p)
	}

	nodeDegree := make(map[*PointOfInterest]int, len(roads)*2)
	for _, road := range roads {
		if road.Start != nil {
			nodeDegree[road.Start]++
		}
		if road.End != nil {
			nodeDegree[road.End]++
		}
	}

	for _, road := range roads {
		if road.Start != nil && (nodeDegree[road.Start] > 1 || !road.Start.IsExit) {
			addAnchor(image.Point{X: road.Start.X, Y: road.Start.Y})
		}
		if road.End != nil && (nodeDegree[road.End] > 1 || !road.End.IsExit) {
			addAnchor(image.Point{X: road.End.X, Y: road.End.Y})
		}

		step := spacing
		if road.Tier == RoadTierArterial {
			step = int(math.Round(float64(spacing) * 1.35))
		}
		if step < 6 {
			step = 6
		}
		for i := step / 2; i < len(road.Points); i += step {
			if road.Points[i].IsBridge {
				continue
			}
			addAnchor(road.Points[i].Point)
		}
	}

	return anchors
}