254 lines
8.8 KiB
TypeScript
254 lines
8.8 KiB
TypeScript
import { describe, it, expect } from 'vitest'
|
|
import { Rng } from '../src/game/rng.ts'
|
|
import {
|
|
catmullRomPoint,
|
|
sampleCatmullRomSpline,
|
|
createDrlgVertices,
|
|
DRLGVER_CreateVertices,
|
|
buildOutdoorRoadPolylines,
|
|
buildRoadNetworkPolylines,
|
|
TILES_PER_BLOCK,
|
|
} from '../src/game/wilderness.ts'
|
|
import type { Act1OutdoorPlan } from '../src/game/wilderness.ts'
|
|
|
|
// Act I outdoor levels (2-7, 17, 39) come from the 1:1 D2MOO DRLG port in
|
|
// src/game/drlg (verified by tests/drlg-act1-oracle.test.ts); the Act I dirt
|
|
// path rasterizer and its end-to-end cases were removed with the invented
|
|
// generator. The vertex-graph / spline helpers below are still used by the
|
|
// Acts 2-5 wilderness generator.
|
|
describe('Control Vertex Graph & Spline Roads (Issue #66)', () => {
|
|
describe('Catmull-Rom Spline Mathematics & Sampling', () => {
|
|
it('accurately interpolates start and end control points at t=0 and t=1', () => {
|
|
const p0 = { x: 0, y: 0 }
|
|
const p1 = { x: 10, y: 20 }
|
|
const p2 = { x: 30, y: 50 }
|
|
const p3 = { x: 60, y: 60 }
|
|
|
|
const start = catmullRomPoint(p0, p1, p2, p3, 0)
|
|
expect(start.x).toBeCloseTo(p1.x)
|
|
expect(start.y).toBeCloseTo(p1.y)
|
|
|
|
const end = catmullRomPoint(p0, p1, p2, p3, 1)
|
|
expect(end.x).toBeCloseTo(p2.x)
|
|
expect(end.y).toBeCloseTo(p2.y)
|
|
|
|
const mid = catmullRomPoint(p0, p1, p2, p3, 0.5)
|
|
expect(mid.x).toBeGreaterThan(p1.x)
|
|
expect(mid.x).toBeLessThan(p2.x)
|
|
expect(mid.y).toBeGreaterThan(p1.y)
|
|
expect(mid.y).toBeLessThan(p2.y)
|
|
})
|
|
|
|
it('generates smooth continuous points along a multi-segment spline', () => {
|
|
const controlPoints = [
|
|
{ x: 10, y: 10 },
|
|
{ x: 25, y: 18 },
|
|
{ x: 45, y: 35 },
|
|
{ x: 70, y: 65 },
|
|
]
|
|
const bounds = { width: 100, height: 100 }
|
|
const sampled = sampleCatmullRomSpline(controlPoints, bounds)
|
|
|
|
expect(sampled.length).toBeGreaterThan(controlPoints.length)
|
|
expect(sampled[0]).toEqual({ x: 10, y: 10 })
|
|
expect(sampled[sampled.length - 1]).toEqual({ x: 70, y: 65 })
|
|
|
|
// Verify continuity: adjacent points have step <= 2 cells
|
|
for (let i = 0; i < sampled.length - 1; i += 1) {
|
|
const dx = Math.abs(sampled[i + 1]!.x - sampled[i]!.x)
|
|
const dy = Math.abs(sampled[i + 1]!.y - sampled[i]!.y)
|
|
expect(Math.max(dx, dy)).toBeLessThanOrEqual(2)
|
|
}
|
|
})
|
|
|
|
it('exhibits natural non-orthogonal/non-45° curvature with continuous angles', () => {
|
|
// S-curve spline
|
|
const controlPoints = [
|
|
{ x: 10, y: 10 },
|
|
{ x: 20, y: 35 },
|
|
{ x: 50, y: 40 },
|
|
{ x: 60, y: 70 },
|
|
]
|
|
const bounds = { width: 80, height: 80 }
|
|
const sampled = sampleCatmullRomSpline(controlPoints, bounds)
|
|
|
|
// Calculate slopes / directions between points sampled along the spline
|
|
const uniqueAngles = new Set<number>()
|
|
for (let i = 0; i < sampled.length - 3; i += 3) {
|
|
const dx = sampled[i + 3]!.x - sampled[i]!.x
|
|
const dy = sampled[i + 3]!.y - sampled[i]!.y
|
|
if (dx !== 0 || dy !== 0) {
|
|
const angle = Math.round((Math.atan2(dy, dx) * 180) / Math.PI)
|
|
uniqueAngles.add(angle)
|
|
}
|
|
}
|
|
|
|
// In a pure 45°/90° grid path, angles would only be {0, 45, 90, 135, 180, -45, -90, -135}.
|
|
// A Catmull-Rom spline curves smoothly with many distinct angles across the S-curve.
|
|
expect(uniqueAngles.size).toBeGreaterThanOrEqual(4)
|
|
const nonGridAngles = Array.from(uniqueAngles).filter(a => a % 45 !== 0)
|
|
expect(nonGridAngles.length).toBeGreaterThan(0)
|
|
})
|
|
|
|
it('clamps spline points strictly within bounds', () => {
|
|
const controlPoints = [
|
|
{ x: -10, y: -5 },
|
|
{ x: 20, y: 30 },
|
|
{ x: 120, y: 110 },
|
|
]
|
|
const bounds = { width: 80, height: 80 }
|
|
const sampled = sampleCatmullRomSpline(controlPoints, bounds)
|
|
|
|
for (const pt of sampled) {
|
|
expect(pt.x).toBeGreaterThanOrEqual(0)
|
|
expect(pt.x).toBeLessThan(80)
|
|
expect(pt.y).toBeGreaterThanOrEqual(0)
|
|
expect(pt.y).toBeLessThan(80)
|
|
}
|
|
})
|
|
|
|
it('deflects spline points around obstacle blocks', () => {
|
|
const bounds = { width: 80, height: 80 }
|
|
const roadObstacleBlocks = Array.from({ length: 10 }, () =>
|
|
Array.from({ length: 10 }, () => false),
|
|
)
|
|
// Mark block (bx=3, by=3) as an obstacle (cells 24..31 in x and y)
|
|
roadObstacleBlocks[3]![3] = true
|
|
|
|
const controlPoints = [
|
|
{ x: 10, y: 28 },
|
|
{ x: 45, y: 28 },
|
|
]
|
|
const sampled = sampleCatmullRomSpline(controlPoints, bounds, roadObstacleBlocks)
|
|
|
|
// No point should fall inside the obstacle block (bx=3, by=3)
|
|
for (const pt of sampled) {
|
|
const bx = Math.floor(pt.x / TILES_PER_BLOCK)
|
|
const by = Math.floor(pt.y / TILES_PER_BLOCK)
|
|
expect(roadObstacleBlocks[by]?.[bx]).toBe(false)
|
|
}
|
|
})
|
|
})
|
|
|
|
describe('DRLGVER Control Vertex Graph Generation', () => {
|
|
it('creates vertices for gates, hub, presets, and inflections with polylines', () => {
|
|
const plan: Act1OutdoorPlan = {
|
|
openGates: new Map([
|
|
['top_4', 3],
|
|
['bottom_4', 3],
|
|
['left_4', 3],
|
|
]),
|
|
claimedBorderBlocks: new Set(['top_4', 'bottom_4', 'left_4']),
|
|
claimedBlocks: Array.from({ length: 10 }, () => Array.from({ length: 10 }, () => false)),
|
|
roadObstacleBlocks: Array.from({ length: 10 }, () => Array.from({ length: 10 }, () => false)),
|
|
specialPresets: [
|
|
{
|
|
name: 'Den of Evil',
|
|
ds1: null as any,
|
|
bx: 7,
|
|
by: 7,
|
|
blocksX: 2,
|
|
blocksY: 2,
|
|
},
|
|
],
|
|
anchors: [
|
|
{
|
|
label: 'North Gate',
|
|
anchorCell: { x: 36, y: 0 },
|
|
interiorCell: { x: 36, y: 8 },
|
|
side: 'north',
|
|
kind: 'gate',
|
|
},
|
|
{
|
|
label: 'South Gate',
|
|
anchorCell: { x: 36, y: 79 },
|
|
interiorCell: { x: 36, y: 71 },
|
|
side: 'south',
|
|
kind: 'gate',
|
|
},
|
|
{
|
|
label: 'West Gate',
|
|
anchorCell: { x: 0, y: 36 },
|
|
interiorCell: { x: 8, y: 36 },
|
|
side: 'west',
|
|
kind: 'gate',
|
|
},
|
|
{
|
|
label: 'Den of Evil Entrance',
|
|
anchorCell: { x: 56, y: 56 },
|
|
interiorCell: { x: 56, y: 52 },
|
|
kind: 'preset',
|
|
},
|
|
],
|
|
}
|
|
|
|
const rng = new Rng(0x1234_5678)
|
|
const res = createDrlgVertices(plan, 10, 10, rng)
|
|
|
|
expect(res.vertices.length).toBeGreaterThanOrEqual(4)
|
|
expect(res.polylines.length).toBe(plan.anchors.length)
|
|
expect(res.lines).toBe(res.polylines)
|
|
|
|
// Verify vertex types
|
|
const types = res.vertices.map(v => v.type)
|
|
expect(types).toContain('hub')
|
|
expect(types).toContain('gate')
|
|
expect(types).toContain('preset')
|
|
|
|
const hub = res.vertices.find(v => v.type === 'hub')!
|
|
expect(hub).toBeDefined()
|
|
expect(hub.x).toBeGreaterThan(0)
|
|
expect(hub.y).toBeGreaterThan(0)
|
|
|
|
// Verify DRLGVER_CreateVertices alias parity
|
|
const aliasRes = DRLGVER_CreateVertices(plan, 10, 10, new Rng(0x1234_5678))
|
|
expect(aliasRes.vertices.length).toBe(res.vertices.length)
|
|
expect(aliasRes.polylines.length).toBe(res.polylines.length)
|
|
|
|
// Verify buildOutdoorRoadPolylines and buildRoadNetworkPolylines
|
|
const polylines = buildOutdoorRoadPolylines(plan, 10, 10, new Rng(0x1234_5678))
|
|
expect(polylines.length).toBe(res.polylines.length)
|
|
const aliasPolylines = buildRoadNetworkPolylines(plan, 10, 10, new Rng(0x1234_5678))
|
|
expect(aliasPolylines).toEqual(polylines)
|
|
})
|
|
|
|
it('ensures central hub is relocated if primary centroid is blocked by obstacles', () => {
|
|
const obstacleBlocks = Array.from({ length: 10 }, () =>
|
|
Array.from({ length: 10 }, () => false),
|
|
)
|
|
// Block centroid block (5, 5)
|
|
obstacleBlocks[5]![5] = true
|
|
|
|
const plan: Act1OutdoorPlan = {
|
|
openGates: new Map(),
|
|
claimedBorderBlocks: new Set(),
|
|
claimedBlocks: obstacleBlocks,
|
|
roadObstacleBlocks: obstacleBlocks,
|
|
specialPresets: [],
|
|
anchors: [
|
|
{
|
|
label: 'West Gate',
|
|
anchorCell: { x: 0, y: 40 },
|
|
interiorCell: { x: 8, y: 40 },
|
|
side: 'west',
|
|
kind: 'gate',
|
|
},
|
|
{
|
|
label: 'East Gate',
|
|
anchorCell: { x: 79, y: 40 },
|
|
interiorCell: { x: 71, y: 40 },
|
|
side: 'east',
|
|
kind: 'gate',
|
|
},
|
|
],
|
|
}
|
|
|
|
const res = createDrlgVertices(plan, 10, 10, new Rng(42))
|
|
const hub = res.vertices.find(v => v.type === 'hub')!
|
|
const hubBx = Math.floor(hub.x / TILES_PER_BLOCK)
|
|
const hubBy = Math.floor(hub.y / TILES_PER_BLOCK)
|
|
expect(obstacleBlocks[hubBy]![hubBx]).toBe(false)
|
|
})
|
|
})
|
|
})
|