415 lines
14 KiB
TypeScript
415 lines
14 KiB
TypeScript
import { describe, it, expect } from 'vitest'
|
|
import { Rng } from '../src/game/rng.ts'
|
|
import {
|
|
ALTDIR_WEST,
|
|
ALTDIR_NORTH,
|
|
ALTDIR_EAST,
|
|
ALTDIR_SOUTH,
|
|
DRLGVER_CreateVertices,
|
|
DRLGOUTDOORS_CalculatePathCoordinates,
|
|
DRLGOUTDOORS_CalculateHubCoordinates,
|
|
DRLGOUTDOORS_TestGridCellSpawnValid,
|
|
bresenhamLine,
|
|
UNIMPLEMENTED_PASSES,
|
|
TILES_PER_BLOCK,
|
|
} from '../src/game/wilderness.ts'
|
|
import type { Act1OutdoorPlan, DrlgVertex } from '../src/game/wilderness.ts'
|
|
|
|
describe('Outdoor Boundary Vertices & Grid Road Path (Issue #82)', () => {
|
|
function createMockPlan(overrides: Partial<Act1OutdoorPlan> = {}): Act1OutdoorPlan {
|
|
const gridW = 4
|
|
const gridH = 4
|
|
return {
|
|
openGates: new Map(),
|
|
claimedBorderBlocks: new Set(),
|
|
claimedBlocks: Array.from({ length: gridH }, () => Array(gridW).fill(false)),
|
|
roadObstacleBlocks: Array.from({ length: gridH }, () => Array(gridW).fill(false)),
|
|
specialPresets: [],
|
|
gateOpenings: [],
|
|
anchors: [
|
|
{
|
|
side: 'west',
|
|
anchorCell: { x: 0, y: 16 },
|
|
interiorCell: { x: 4, y: 16 },
|
|
label: 'Rogue Encampment Gate',
|
|
toLevelId: 1,
|
|
kind: 'gate',
|
|
},
|
|
{
|
|
side: 'east',
|
|
anchorCell: { x: 31, y: 16 },
|
|
interiorCell: { x: 27, y: 16 },
|
|
label: 'Cold Plains Gate',
|
|
toLevelId: 3,
|
|
kind: 'gate',
|
|
},
|
|
],
|
|
...overrides,
|
|
}
|
|
}
|
|
|
|
describe('Unimplemented Passes Audit', () => {
|
|
it('verifies DRLGVER_CreateVertices is removed from UNIMPLEMENTED_PASSES', () => {
|
|
expect(UNIMPLEMENTED_PASSES).not.toContain('DRLGVER_CreateVertices')
|
|
})
|
|
})
|
|
|
|
describe('DRLGVER_CreateVertices: 0 RNG Rolls Guarantee', () => {
|
|
it('consumes exactly 0 RNG rolls during vertex and path construction', () => {
|
|
const rng = new Rng(0x12345678)
|
|
const initialSeed = rng.seed
|
|
const plan = createMockPlan()
|
|
|
|
const result = DRLGVER_CreateVertices(plan, 4, 4, rng)
|
|
|
|
expect(rng.seed).toBe(initialSeed)
|
|
expect(result.vertices.length).toBeGreaterThan(0)
|
|
expect(result.polylines.length).toBe(plan.anchors.length)
|
|
})
|
|
})
|
|
|
|
describe('DRLGVER_CreateVertices: Closed Cyclic Linked List', () => {
|
|
it('constructs 4 corner vertices in clockwise order with relative coordinates', () => {
|
|
const plan = createMockPlan({ anchors: [] })
|
|
const gridW = 4
|
|
const gridH = 4
|
|
const tileW = gridW * TILES_PER_BLOCK
|
|
const tileH = gridH * TILES_PER_BLOCK
|
|
const origin = { x: 100, y: 200 }
|
|
|
|
const result = DRLGVER_CreateVertices(plan, gridW, gridH, undefined, origin)
|
|
const cyclic = result.cyclicVertices!
|
|
|
|
expect(cyclic).toBeDefined()
|
|
expect(cyclic.length).toBe(4)
|
|
|
|
const [v0, v1, v2, v3] = cyclic
|
|
expect(v0).toMatchObject({ x: 0, y: 0, direction: ALTDIR_NORTH, dwFlags: 0, type: 'corner' })
|
|
expect(v1).toMatchObject({ x: tileW, y: 0, direction: ALTDIR_EAST, dwFlags: 0, type: 'corner' })
|
|
expect(v2).toMatchObject({ x: tileW, y: tileH, direction: ALTDIR_SOUTH, dwFlags: 0, type: 'corner' })
|
|
expect(v3).toMatchObject({ x: 0, y: tileH, direction: ALTDIR_WEST, dwFlags: 0, type: 'corner' })
|
|
|
|
// Check next pointers (clockwise)
|
|
expect(v0.next).toBe(v1)
|
|
expect(v1.next).toBe(v2)
|
|
expect(v2.next).toBe(v3)
|
|
expect(v3.next).toBe(v0)
|
|
|
|
// Check prev pointers (counter-clockwise)
|
|
expect(v0.prev).toBe(v3)
|
|
expect(v3.prev).toBe(v2)
|
|
expect(v2.prev).toBe(v1)
|
|
expect(v1.prev).toBe(v0)
|
|
})
|
|
|
|
it('inserts border connection vertices into appropriate edges with correct dwFlags and order', () => {
|
|
const plan = createMockPlan({
|
|
anchors: [
|
|
{
|
|
side: 'north',
|
|
anchorCell: { x: 16, y: 0 },
|
|
interiorCell: { x: 16, y: 4 },
|
|
label: 'North Gate',
|
|
toLevelId: 4,
|
|
kind: 'gate',
|
|
},
|
|
{
|
|
side: 'east',
|
|
anchorCell: { x: 32, y: 20 },
|
|
interiorCell: { x: 28, y: 20 },
|
|
label: 'East Preset',
|
|
toLevelId: 5,
|
|
kind: 'preset',
|
|
},
|
|
{
|
|
side: 'south',
|
|
anchorCell: { x: 24, y: 32 },
|
|
interiorCell: { x: 24, y: 28 },
|
|
label: 'South Gate',
|
|
toLevelId: 6,
|
|
kind: 'gate',
|
|
},
|
|
{
|
|
side: 'west',
|
|
anchorCell: { x: 0, y: 12 },
|
|
interiorCell: { x: 4, y: 12 },
|
|
label: 'West Gate',
|
|
toLevelId: 7,
|
|
kind: 'gate',
|
|
},
|
|
],
|
|
})
|
|
|
|
const result = DRLGVER_CreateVertices(plan, 4, 4)
|
|
const cyclic = result.cyclicVertices!
|
|
|
|
// 4 corners + 4 inserted border vertices = 8 vertices
|
|
expect(cyclic.length).toBe(8)
|
|
|
|
// Verify full cycle traversal via next
|
|
let curr = result.head!
|
|
const visitedForward: DrlgVertex[] = []
|
|
for (let i = 0; i < cyclic.length; i += 1) {
|
|
visitedForward.push(curr)
|
|
curr = curr.next!
|
|
}
|
|
expect(curr).toBe(result.head!)
|
|
expect(visitedForward.length).toBe(8)
|
|
|
|
// Verify full cycle traversal via prev
|
|
let prevNode = result.head!
|
|
const visitedBackward: DrlgVertex[] = []
|
|
for (let i = 0; i < cyclic.length; i += 1) {
|
|
visitedBackward.push(prevNode)
|
|
prevNode = prevNode.prev!
|
|
}
|
|
expect(prevNode).toBe(result.head!)
|
|
|
|
// Find inserted vertices and verify flags:
|
|
// Gate: dwFlags = 1 (connection)
|
|
// Preset: dwFlags = 3 (1 = connection | 2 = preset)
|
|
const northV = cyclic.find(v => v.direction === ALTDIR_NORTH && v.type === 'gate')
|
|
expect(northV).toBeDefined()
|
|
expect(northV!.dwFlags).toBe(1)
|
|
expect(northV!.x).toBe(16)
|
|
expect(northV!.y).toBe(0)
|
|
|
|
const eastV = cyclic.find(v => v.direction === ALTDIR_EAST && v.type === 'preset')
|
|
expect(eastV).toBeDefined()
|
|
expect(eastV!.dwFlags).toBe(3) // dwFlags |= 1 | 2
|
|
expect(eastV!.x).toBe(32)
|
|
expect(eastV!.y).toBe(20)
|
|
|
|
const southV = cyclic.find(v => v.direction === ALTDIR_SOUTH && v.type === 'gate')
|
|
expect(southV).toBeDefined()
|
|
expect(southV!.dwFlags).toBe(1)
|
|
expect(southV!.x).toBe(24)
|
|
expect(southV!.y).toBe(32)
|
|
|
|
const westV = cyclic.find(v => v.direction === ALTDIR_WEST && v.type === 'gate')
|
|
expect(westV).toBeDefined()
|
|
expect(westV!.dwFlags).toBe(1)
|
|
expect(westV!.x).toBe(0)
|
|
expect(westV!.y).toBe(12)
|
|
})
|
|
|
|
it('inserts span endpoint vertices [v15, v16] when provided for wide connections', () => {
|
|
const plan = createMockPlan({
|
|
anchors: [
|
|
{
|
|
side: 'north',
|
|
anchorCell: { x: 16, y: 0 },
|
|
interiorCell: { x: 16, y: 4 },
|
|
label: 'North River Span',
|
|
toLevelId: 4,
|
|
kind: 'preset',
|
|
span: [12, 20],
|
|
} as any,
|
|
],
|
|
})
|
|
|
|
const result = DRLGVER_CreateVertices(plan, 4, 4)
|
|
const cyclic = result.cyclicVertices!
|
|
|
|
// 4 corners + 2 span vertices = 6
|
|
expect(cyclic.length).toBe(6)
|
|
|
|
const northSpans = cyclic.filter(v => v.direction === ALTDIR_NORTH && v.type === 'preset')
|
|
expect(northSpans.length).toBe(2)
|
|
expect(northSpans[0]!.x).toBe(12)
|
|
expect(northSpans[1]!.x).toBe(20)
|
|
expect(northSpans[0]!.label).toContain('(Start)')
|
|
expect(northSpans[1]!.label).toContain('(End)')
|
|
})
|
|
})
|
|
|
|
describe('DRLGOUTDOORS_CalculatePathCoordinates', () => {
|
|
it('correctly snaps coordinates according to 8-cell grid rules for all 4 directions', () => {
|
|
const origin = { x: 0, y: 0 }
|
|
|
|
// ALTDIR_WEST (0): relX = 8 * Math.trunc(relX / 8) + 11
|
|
const westSnapped = DRLGOUTDOORS_CalculatePathCoordinates({
|
|
x: 0,
|
|
y: 16,
|
|
direction: ALTDIR_WEST,
|
|
}, origin)
|
|
expect(westSnapped.x).toBe(8 * Math.trunc(0 / 8) + 11) // 11
|
|
expect(westSnapped.y).toBe(16)
|
|
|
|
// ALTDIR_NORTH (1): relY = 8 * Math.trunc(relY / 8) + 11
|
|
const northSnapped = DRLGOUTDOORS_CalculatePathCoordinates({
|
|
x: 16,
|
|
y: 0,
|
|
direction: ALTDIR_NORTH,
|
|
}, origin)
|
|
expect(northSnapped.x).toBe(16)
|
|
expect(northSnapped.y).toBe(8 * Math.trunc(0 / 8) + 11) // 11
|
|
|
|
// ALTDIR_EAST (2): relX = 8 * Math.trunc(relX / 8) - 5
|
|
const eastSnapped = DRLGOUTDOORS_CalculatePathCoordinates({
|
|
x: 32,
|
|
y: 16,
|
|
direction: ALTDIR_EAST,
|
|
}, origin)
|
|
expect(eastSnapped.x).toBe(8 * Math.trunc(32 / 8) - 5) // 32 - 5 = 27
|
|
expect(eastSnapped.y).toBe(16)
|
|
|
|
// ALTDIR_SOUTH (3): relY = 8 * Math.trunc(relY / 8) - 5
|
|
const southSnapped = DRLGOUTDOORS_CalculatePathCoordinates({
|
|
x: 16,
|
|
y: 32,
|
|
direction: ALTDIR_SOUTH,
|
|
}, origin)
|
|
expect(southSnapped.x).toBe(16)
|
|
expect(southSnapped.y).toBe(8 * Math.trunc(32 / 8) - 5) // 32 - 5 = 27
|
|
})
|
|
|
|
it('supports D2MOO C++ style (pLevel, pVertex1, pVertex2) signature and populates pVertex2', () => {
|
|
const mockLevel = { nPosX: 10, nPosY: 20 }
|
|
const pVertex1 = { nPosX: 42, nPosY: 20, nDirection: ALTDIR_EAST }
|
|
const pVertex2: { nPosX?: number; nPosY?: number; x?: number; y?: number } = {}
|
|
|
|
const res = DRLGOUTDOORS_CalculatePathCoordinates(mockLevel, pVertex1, pVertex2)
|
|
|
|
// relX = 42 - 10 = 32 -> 8 * trunc(32 / 8) - 5 = 27 -> 27 + 10 = 37
|
|
// relY = 20 - 20 = 0 -> 0 + 20 = 20
|
|
expect(res.x).toBe(37)
|
|
expect(res.y).toBe(20)
|
|
expect(pVertex2.x).toBe(37)
|
|
expect(pVertex2.y).toBe(20)
|
|
expect(pVertex2.nPosX).toBe(37)
|
|
expect(pVertex2.nPosY).toBe(20)
|
|
})
|
|
})
|
|
|
|
describe('DRLGOUTDOORS_TestGridCellSpawnValid', () => {
|
|
it('validates cell bitmask 0x1B81 and road obstacle blocks', () => {
|
|
const plan = {
|
|
gridFlags: [
|
|
[0, 0x0001],
|
|
[0x0080, 0x1000],
|
|
],
|
|
roadObstacleBlocks: [
|
|
[false, false],
|
|
[false, true],
|
|
],
|
|
}
|
|
|
|
// (0,0) has 0 -> valid
|
|
expect(DRLGOUTDOORS_TestGridCellSpawnValid(0, 0, plan)).toBe(true)
|
|
// (1,0) has 0x0001 (bit 0 in 0x1B81) -> invalid
|
|
expect(DRLGOUTDOORS_TestGridCellSpawnValid(1, 0, plan)).toBe(false)
|
|
// (0,1) has 0x0080 (bit 7 in 0x1B81) -> invalid
|
|
expect(DRLGOUTDOORS_TestGridCellSpawnValid(0, 1, plan)).toBe(false)
|
|
// (1,1) has roadObstacleBlocks = true -> invalid
|
|
expect(DRLGOUTDOORS_TestGridCellSpawnValid(1, 1, plan)).toBe(false)
|
|
})
|
|
})
|
|
|
|
describe('DRLGOUTDOORS_CalculateHubCoordinates', () => {
|
|
it('returns center of level when nVertices === 1', () => {
|
|
const plan = createMockPlan({
|
|
anchors: [
|
|
{
|
|
side: 'west',
|
|
anchorCell: { x: 0, y: 16 },
|
|
interiorCell: { x: 4, y: 16 },
|
|
label: 'Single Gate',
|
|
kind: 'gate',
|
|
},
|
|
],
|
|
})
|
|
|
|
const hub = DRLGOUTDOORS_CalculateHubCoordinates(plan, 6, 6)
|
|
expect(hub.bx).toBe(3) // floor(6 / 2)
|
|
expect(hub.by).toBe(3) // floor(6 / 2)
|
|
expect(hub.x).toBe(3 * TILES_PER_BLOCK + 4)
|
|
expect(hub.y).toBe(3 * TILES_PER_BLOCK + 4)
|
|
})
|
|
|
|
it('anchors to bridge coordinates when bridge flag is set', () => {
|
|
const plan = createMockPlan({
|
|
dwFlags: 0x10,
|
|
specialPresets: [
|
|
{
|
|
name: 'Blood Moor Bridge',
|
|
bx: 2,
|
|
by: 3,
|
|
blocksX: 1,
|
|
blocksY: 1,
|
|
ds1: {} as any,
|
|
},
|
|
],
|
|
} as any)
|
|
|
|
const hub = DRLGOUTDOORS_CalculateHubCoordinates(plan, 6, 6)
|
|
expect(hub.bx).toBe(2)
|
|
expect(hub.by).toBe(3)
|
|
expect(hub.x).toBe(8 * 2 + 3) // 19
|
|
expect(hub.y).toBe(8 * 3 + 3) // 27
|
|
})
|
|
|
|
it('computes average coordinates and spirals outward radius 0..7 avoiding obstacles', () => {
|
|
// 2 anchors on west and east borders
|
|
// anchor 1: cell (0, 8) -> bx = 0, by = 1
|
|
// anchor 2: cell (32, 24) -> bx = 4, by = 3
|
|
// sumX = 0 + 32 = 32 -> avgX = floor(32 / 16) = 2
|
|
// sumY = 8 + 24 = 32 -> avgY = floor(32 / 16) = 2
|
|
// If (2, 2) is blocked by road obstacle, spiral radius 1 tests [-1,0] -> (1, 2)
|
|
const obstacleBlocks = Array.from({ length: 5 }, () => Array(5).fill(false))
|
|
obstacleBlocks[2]![2] = true // Block (2, 2)
|
|
|
|
const plan = createMockPlan({
|
|
anchors: [
|
|
{
|
|
side: 'west',
|
|
anchorCell: { x: 0, y: 8 },
|
|
interiorCell: { x: 4, y: 8 },
|
|
label: 'West',
|
|
kind: 'gate',
|
|
},
|
|
{
|
|
side: 'east',
|
|
anchorCell: { x: 32, y: 24 },
|
|
interiorCell: { x: 28, y: 24 },
|
|
label: 'East',
|
|
kind: 'gate',
|
|
},
|
|
],
|
|
roadObstacleBlocks: obstacleBlocks,
|
|
})
|
|
|
|
const hub = DRLGOUTDOORS_CalculateHubCoordinates(plan, 5, 5)
|
|
// Radius 1 first direction is { x: -1, y: 0 } -> testX = 2 - 1 = 1, testY = 2
|
|
expect(hub.bx).toBe(1)
|
|
expect(hub.by).toBe(2)
|
|
})
|
|
})
|
|
|
|
describe('Bresenham Grid Line Rasterization', () => {
|
|
it('produces deterministic contiguous grid line without diagonal gaps', () => {
|
|
const points = bresenhamLine(2, 3, 7, 6)
|
|
|
|
expect(points.length).toBeGreaterThan(0)
|
|
expect(points[0]).toEqual({ x: 2, y: 3 })
|
|
expect(points[points.length - 1]).toEqual({ x: 7, y: 6 })
|
|
|
|
for (let i = 1; i < points.length; i += 1) {
|
|
const pPrev = points[i - 1]!
|
|
const pCurr = points[i]!
|
|
const dx = Math.abs(pCurr.x - pPrev.x)
|
|
const dy = Math.abs(pCurr.y - pPrev.y)
|
|
expect(dx).toBeLessThanOrEqual(1)
|
|
expect(dy).toBeLessThanOrEqual(1)
|
|
expect(dx + dy).toBeGreaterThan(0)
|
|
}
|
|
})
|
|
|
|
it('guarantees deterministic identical output across runs with 0 RNG', () => {
|
|
const line1 = bresenhamLine(10, 20, 50, 80)
|
|
const line2 = bresenhamLine(10, 20, 50, 80)
|
|
expect(line1).toEqual(line2)
|
|
})
|
|
})
|
|
})
|