acdream/docs/research/transition_pseudocode.md

AC Collision Transition System — Pseudocode

Research document for porting the retail AC collision/transition system to acdream. Cross-referenced between ACE's Transition.cs (interpretation aid) and the decompiled retail client chunk_00530000.c (ground truth).

Naming convention: ACE names throughout, with decompiled addresses in comments.

---

Table of Contents

1. Data Structures
2. FindTransitionalPosition — main entry point
3. TransitionalInsert — per-step collision check
4. FindEnvCollisions — BSP query against environment
5. StepUp / StepDown — step height handling
6. AdjustOffset / SlideSphere — wall slide projection
7. ValidateTransition — post-step validation
8. Already Ported — what exists in CollisionPrimitives.cs
9. Key Constants
10. ACE vs Decompiled Differences

---

1. Data Structures

TransitionState (enum)

Invalid   = 0  -- transition failed completely
OK        = 1  -- no collision, position accepted
Collided  = 2  -- hard collision, cannot pass
Adjusted  = 3  -- position was nudged to resolve overlap
Slid      = 4  -- position was projected along a surface

Transition (main orchestrator)

ObjectInfo    : ObjectInfo      -- flags, step heights, object reference
SpherePath    : SpherePath      -- movement path with sphere(s)
CollisionInfo : CollisionInfo   -- accumulated collision results
CellArray     : CellArray       -- scratch buffer for cell enumeration

SpherePath (movement descriptor)

NumSphere          : int           -- 1 or 2 spheres (foot + body)
LocalSphere[0..1]  : Sphere        -- spheres in object-local space
GlobalSphere[0..1] : Sphere        -- spheres transformed to world (at CheckPos)
GlobalCurrCenter[0..1] : Sphere    -- spheres transformed to world (at CurPos)
BeginPos, EndPos   : Position      -- start and end of the requested move
CurPos             : Position      -- last accepted position
CheckPos           : Position      -- candidate position being tested
CurCell, CheckCell : ObjCell       -- cells for CurPos and CheckPos
GlobalOffset       : Vector3       -- the offset being applied this step
InsertType         : InsertType    -- Transition(0), Placement(1), InitialPlacement(2)

-- Step-up state
StepUp             : bool
StepUpNormal       : Vector3
Collide            : bool          -- set when a collide-then-find-walkable is pending

-- Step-down state
StepDown           : bool
StepDownAmt        : float
WalkInterp         : float         -- interpolation factor [0..1], shrinks as step-down progresses

-- Walkable tracking
Walkable           : Polygon       -- the polygon we are standing on
WalkableCheckPos   : Sphere        -- position used for walkable checks
WalkableUp         : Vector3       -- up vector for the walkable surface
WalkablePos        : Position      -- local-space position of the walkable
WalkableScale      : float
WalkableAllowance  : float         -- minimum Z component of normal to be "walkable"

-- Backup for restore
BackupCell         : ObjCell
BackupCheckPos     : Position

-- Misc flags
NegPolyHit         : bool          -- secondary sphere hit a polygon (deferred)
NegStepUp          : bool          -- the deferred hit wants a step-up
NegCollisionNormal : Vector3       -- normal of the deferred hit
CellArrayValid     : bool
HitsInteriorCell   : bool
BuildingCheck      : bool
ObstructionEthereal: bool
CheckWalkable      : bool
PlacementAllowsSliding : bool      -- default true

CollisionInfo (accumulated results)

ContactPlaneValid          : bool
ContactPlane               : Plane
ContactPlaneCellID         : uint
ContactPlaneIsWater        : bool

LastKnownContactPlaneValid : bool
LastKnownContactPlane      : Plane
LastKnownContactPlaneCellID: uint
LastKnownContactPlaneIsWater: bool

SlidingNormalValid         : bool
SlidingNormal              : Vector3    -- XY only (Z zeroed)

CollisionNormalValid       : bool
CollisionNormal            : Vector3

CollidedWithEnvironment    : bool
FramesStationaryFall       : int        -- gravity fall-through safety counter

AdjustOffset               : Vector3
CollideObject              : List<PhysicsObj>
LastCollidedObject         : PhysicsObj

ObjectInfo (flags + per-object properties)

State          : ObjectInfoState flags  -- Contact, OnWalkable, IsViewer, PathClipped,
                                        -- FreeRotate, PerfectClip, EdgeSlide, etc.
StepUpHeight   : float
StepDownHeight : float
Ethereal       : bool
StepDown       : bool       -- true unless the object is a missile
Scale          : float

---

2. FindTransitionalPosition

ACE: Transition.FindTransitionalPosition() Decompiled: Not directly in chunk_00530000; lives in the PhysicsObj transition caller.

This is the main entry point for moving an object from BeginPos to EndPos.

function FindTransitionalPosition() -> bool:
    if SpherePath.BeginCell is null:
        return false

    -- Calculate movement and subdivide into steps
    offset = BeginPos.GetOffset(EndPos)        -- total movement vector
    dist = length(offset)
    step = dist / LocalSphere[0].Radius

    if IsViewer:
        if dist <= EPSILON:
            numSteps = 0
            offsetPerStep = Zero
        else:
            offsetPerStep = offset * (1 / step)
            numSteps = floor(step) + 1
    else:
        if step > 1.0:
            numSteps = ceil(step)
            offsetPerStep = offset * (1 / numSteps)
        elif offset != Zero:
            offsetPerStep = offset
            numSteps = 1
        else:
            offsetPerStep = Zero
            numSteps = 0

    -- Safety cap: abort if too many steps (retail uses 30; ACE bumped to 1000)
    if numSteps > MAX_STEPS and not IsSightObj:
        return false

    -- Apply free rotation if flagged
    if FreeRotate:
        CurPos.Frame.Orientation = EndPos.Frame.Orientation

    SetCheckPos(CurPos, CurCell)

    -- Zero-step case: just validate cell membership
    if numSteps <= 0:
        if not FreeRotate:
            CurPos.Frame.Orientation = EndPos.Frame.Orientation
        find_cell_list(...)   -- rebuild cell array for current position
        return true

    -- Main stepping loop
    for step = 0 to numSteps-1:

        -- IsViewer: last step uses remaining distance instead of fixed step size
        if IsViewer and step == numSteps - 1:
            remaining = dist - LocalSphere[0].Radius * (numSteps - 1)
            offsetPerStep = offset * (remaining / dist)

        -- Apply contact-plane and sliding-normal adjustments to the offset
        GlobalOffset = AdjustOffset(offsetPerStep)

        -- Non-viewer: abort if adjusted offset is negligible
        if not IsViewer:
            if GlobalOffset.LengthSquared < EPSILON^2:
                return (step != 0 and transitionState == OK)

        -- Interpolate rotation if not free-rotating
        if not FreeRotate:
            delta = (step + 1) / numSteps
            CheckPos.Frame.InterpolateRotation(BeginPos, EndPos, delta)

        -- Reset per-step collision state
        CollisionInfo.SlidingNormalValid = false
        CollisionInfo.ContactPlaneValid = false
        CollisionInfo.ContactPlaneIsWater = false

        if InsertType != Transition:
            -- Placement mode: try insert, validate placement
            result = TransitionalInsert(3)
            transitionState = ValidatePlacementTransition(result)
            if transitionState == OK: return true
            if not PlacementAllowsSliding: return false
            AddOffsetToCheckPos(GlobalOffset)
        else:
            -- Transition mode: apply offset first, then check
            AddOffsetToCheckPos(GlobalOffset)
            result = TransitionalInsert(3)
            transitionState = ValidateTransition(result)
            if FramesStationaryFall > 0: break

        -- PathClipped objects stop on any collision normal
        if CollisionNormalValid and PathClipped: break

    return transitionState == OK

Key insight: step subdivision

The movement is divided so each sub-step travels at most one sphere radius. This ensures the sphere cannot "tunnel" through thin walls. The IsViewer path uses a slightly different calculation (floor + 1 instead of ceil) because viewers need to reach the exact endpoint on the last step.

---

3. TransitionalInsert

ACE: Transition.TransitionalInsert(int num_insertion_attempts) Decompiled: Part of the CTransition methods in chunk_00530000.

Per-step collision detection. Checks the current cell, then neighboring cells, then handles step-up, step-down, and slide responses.

function TransitionalInsert(maxAttempts) -> TransitionState:
    if CheckCell is null: return OK
    if maxAttempts <= 0: return Invalid

    for attempt = 0 to maxAttempts-1:

        -- Phase 1: Check collisions in current cell
        transitState = InsertIntoCell(CheckCell, maxAttempts)

        switch transitState:
            case OK:
                -- Phase 2: Check neighboring cells
                transitState = CheckOtherCells(CheckCell)
                if transitState != OK: NegPolyHit = false
                if transitState == Collided: return Collided
            case Collided:
                return Collided
            case Adjusted:
                NegPolyHit = false
            case Slid:
                ContactPlaneValid = false
                ContactPlaneIsWater = false
                NegPolyHit = false

        -- Phase 3: Post-collision response
        if transitState == OK:
            if not Collide:
                -- Handle deferred secondary-sphere polygon hit
                if NegPolyHit and not StepDown and not StepUp:
                    NegPolyHit = false
                    if NegStepUp:
                        if not StepUp(NegCollisionNormal):
                            transitState = StepUpSlide()
                    else:
                        transitState = SlideSphere(NegCollisionNormal, GlobalCurrCenter[0])

                -- Handle step-down when in contact but no ground found
                elif not ContactPlaneValid and Contact and not StepDown
                     and CheckCell != null and ObjectInfo.StepDown:

                    zVal = LandingZ (or GetWalkableZ if OnWalkable)
                    stepDownHeight = 0.04 (or ObjectInfo.StepDownHeight if OnWalkable)
                    WalkableAllowance = zVal
                    SaveCheckPos()

                    -- Split into half-steps if step height > 2*radius
                    radsum = GlobalSphere[0].Radius * 2
                    if NumSphere < 2 and radsum < stepDownHeight:
                        stepDownHeight = GlobalSphere[0].Radius * 0.5

                    if radsum >= stepDownHeight:
                        if StepDown(stepDownHeight, zVal):
                            Walkable = null; return OK
                    else:
                        stepDownHeight *= 0.5
                        if StepDown(stepDownHeight, zVal) or StepDown(stepDownHeight, zVal):
                            Walkable = null; return OK

                    -- Edge slide fallback
                    if EdgeSlide(transitState, stepDownHeight, zVal):
                        return transitState

                else:
                    return OK   -- clean transition, no issues

            else:
                -- Collide flag is set: find-walkable-then-validate pattern
                Collide = false
                reset = false

                if ContactPlaneValid and CheckWalkable(LandingZ):
                    -- Try re-inserting as Placement to verify position
                    save InsertType
                    InsertType = Placement
                    transitState = TransitionalInsert(maxAttempts)
                    restore InsertType

                    if transitState != OK:
                        transitState = OK
                        reset = true
                else:
                    reset = true

                Walkable = null

                if not reset: return transitState

                -- Reset: collision was not resolvable by stepping
                RestoreCheckPos()
                ContactPlaneValid = false
                ContactPlaneIsWater = false

                if LastKnownContactPlaneValid:
                    LastKnownContactPlaneValid = false
                    StopVelocity()    -- zero out the object's velocity
                else:
                    SetCollisionNormal(StepUpNormal)

                return Collided

    return transitState

InsertIntoCell

function InsertIntoCell(cell, maxAttempts) -> TransitionState:
    if cell is null: return Collided

    for i = 0 to maxAttempts-1:
        transitState = cell.FindCollisions(this)
        switch transitState:
            case OK, Collided:
                return transitState
            case Slid:
                ContactPlaneValid = false
                ContactPlaneIsWater = false
                -- continue loop (retry after slide)

    return transitState   -- returns last state (usually Slid)

CheckOtherCells

function CheckOtherCells(currCell) -> TransitionState:
    -- Build list of cells the sphere touches
    find_cell_list(CellArray, newCell, SpherePath)

    for each cell in CellArray:
        if cell == currCell: skip

        collides = cell.FindCollisions(this)
        switch collides:
            case Slid:
                ContactPlaneValid = false
                ContactPlaneIsWater = false
                return Slid
            case Collided, Adjusted:
                return collides

    CheckCell = newCell

    if newCell != null:
        AdjustCheckPos(newCell.ID)
        return OK

    if StepDown:
        return Collided

    -- Try to resolve position to outdoor cell
    adjustedPos = copy of CheckPos
    if is_outdoor(adjustedPos):
        AdjustToOutside(adjustedPos)
    if adjustedPos.CellID != 0:
        AdjustCheckPos(adjustedPos.CellID)
        SetCheckPos(adjustedPos, null)
        -- Rebuild cell array and re-check
        find_cell_list(...)
        return OK

    return Collided

---

4. FindEnvCollisions

LandCell (outdoor terrain)

ACE: LandCell.FindEnvCollisions()

function LandCell.FindEnvCollisions(transition) -> TransitionState:
    -- Check entry restrictions (e.g., PK zones, housing)
    transitState = check_entry_restrictions(transition)
    if transitState != OK: return transitState

    -- Find which terrain triangle we are over
    blockOffset = GetBlockOffset(CheckPos.CellID, this.ID)
    localPoint = GlobalLowPoint - blockOffset
    walkable = find_terrain_poly(localPoint)   -- returns one of 2 triangles per cell
    if walkable not found: return OK

    -- Water check: entirely-water cells block non-viewer, non-missile objects
    if block_water_type == EntirelyWater and not IsViewer and not Missile:
        return Collided

    waterDepth = get_water_depth(localPoint)

    -- Create local-space check sphere
    checkPos = copy of GlobalSphere[0]
    checkPos.Center -= blockOffset

    -- Delegate to ValidateWalkable
    return ValidateWalkable(checkPos, walkable.Plane, isWater, waterDepth, this.ID)

ValidateWalkable

ACE: ObjectInfo.ValidateWalkable()

The core terrain collision response. Two paths: IsViewer (camera) and normal objects.

function ValidateWalkable(checkSphere, contactPlane, isWater, waterDepth, cellID):

    if IsViewer:
        -- Camera collision: adjust along movement ray to stay above ground
        dist = dot(checkSphere.Center, contactPlane.Normal) + contactPlane.D - checkSphere.Radius
        if dist > -EPSILON and BeginPos is indoor:
            return OK   -- camera can clip through terrain when coming from indoors

        offset = checkSphere.Center - GlobalCurrCenter[0].Center
        angle = dist / dot(offset, contactPlane.Normal)
        if (angle <= 0 or angle > 1) and BeginPos is indoor:
            return OK

        AddOffsetToCheckPos(offset * -angle)
        SetCollisionNormal(contactPlane.Normal)
        CollidedWithEnvironment = true
        return Adjusted

    else:
        -- Normal object: signed distance from low point to terrain plane
        lowPoint = checkSphere.Center - (0, 0, checkSphere.Radius)
        dist = dot(lowPoint, contactPlane.Normal) + contactPlane.D + waterDepth

        if dist >= -EPSILON:
            -- Above or touching the surface
            if dist <= EPSILON:
                -- Resting on surface: set contact plane
                if StepDown or not OnWalkable or is_valid_walkable(contactPlane.Normal):
                    SetContactPlane(contactPlane, isWater, cellID)
                if not Contact and not StepDown:
                    SetCollisionNormal(contactPlane.Normal)
                    CollidedWithEnvironment = true
            return OK

        else:
            -- Below the surface
            if CheckWalkable: return Collided   -- walkable probe

            zDist = dist / contactPlane.Normal.Z

            if StepDown or not OnWalkable or is_valid_walkable(contactPlane.Normal):
                SetContactPlane(contactPlane, isWater, cellID)

                if StepDown:
                    -- Validate step-down interpolation
                    interp = (1 - (-1 / (StepDownAmt * WalkInterp)) * zDist) * WalkInterp
                    if interp >= WalkInterp or interp < -0.1:
                        return Collided
                    WalkInterp = interp

                AddOffsetToCheckPos(0, 0, -zDist)

            if not Contact and not StepDown:
                SetCollisionNormal(contactPlane.Normal)
                CollidedWithEnvironment = true

            return Adjusted

EnvCell (indoor BSP)

ACE: EnvCell.FindEnvCollisions()

function EnvCell.FindEnvCollisions(transition) -> TransitionState:
    transitState = check_entry_restrictions(transition)
    if transitState != OK: return transitState

    ObstructionEthereal = false

    if CellStructure.PhysicsBSP is null:
        return OK

    -- Transform spheres into cell-local space
    CacheLocalSpaceSphere(cellPos, scale=1.0)

    if InsertType == InitialPlacement:
        transitState = PhysicsBSP.placement_insert(transition)
    else:
        transitState = PhysicsBSP.find_collisions(transition, scale=1.0)

    if transitState != OK and not Contact:
        CollidedWithEnvironment = true

    return transitState

BSPTree.find_collisions (indoor collision core)

ACE: BSPTree.find_collisions() Decompiled: Part of the BSP traversal functions in chunk_00530000.

function BSPTree.find_collisions(transition, scale) -> TransitionState:
    center = LocalSpaceCurrCenter[0].Center    -- current pos in local space
    localSphere = LocalSpaceSphere[0]          -- check pos in local space
    movement = localSphere.Center - center

    -- Placement / Ethereal: simple solid intersection test
    if InsertType == Placement or ObstructionEthereal:
        clearCell = true
        if BuildingCheck: clearCell = not HitsInteriorCell
        if sphere_intersects_solid(localSphere, clearCell):
            return Collided
        if NumSphere > 1 and sphere_intersects_solid(localSphere[1], clearCell):
            return Collided
        return OK

    -- Walkable probe
    if CheckWalkable:
        return hits_walkable(localSphere, LocalSpaceZ) ? Collided : OK

    -- Step-down: find walkable surface below
    if StepDown:
        return step_sphere_down(transition, localSphere, scale)

    -- Collide flag: find a walkable surface to land on
    if Collide:
        validPos = copy of localSphere
        changed = false
        find_walkable(validPos, hitPoly, movement, LocalSpaceZ, changed)
        if changed:
            offset = (validPos.Center - localSphere.Center) transformed to global * scale
            AddOffsetToCheckPos(offset)
            contactPlane = hitPoly.Plane transformed to global
            SetContactPlane(contactPlane)
            SetWalkable(validPos, hitPoly, LocalSpaceZ, LocalSpacePos, scale)
            return Adjusted
        return OK

    -- Normal collision: sphere vs BSP polygon intersection
    hitPoly = null
    contactPoint = Zero

    if Contact:
        -- Object is on the ground: step-up on collision, slide on secondary sphere
        if sphere_intersects_poly(localSphere, movement, hitPoly, contactPoint):
            globNormal = LocalSpacePos.LocalToGlobalVec(hitPoly.Plane.Normal)
            if StepUp(globNormal): return OK
            return StepUpSlide()

        if NumSphere > 1:
            if sphere_intersects_poly(localSphere[1], movement, hitPoly2, contactPoint):
                return slide_sphere(hitPoly2.Plane.Normal)
            -- Deferred hits: NegPolyHit
            if hitPoly2 != null: SetNegPolyHit(false, hitPoly2); return OK
            if hitPoly  != null: SetNegPolyHit(true,  hitPoly);  return OK

        return OK

    -- Not in contact: first collision triggers Collide mode
    if sphere_intersects_poly(localSphere, movement, hitPoly, contactPoint) or hitPoly != null:
        if PathClipped:
            return collide_with_pt(localSphere, center, hitPoly, contactPoint, scale)

        collisionNormal = LocalSpacePos.LocalToGlobalVec(hitPoly.Plane.Normal)
        WalkableAllowance = LandingZ
        SetCollide(collisionNormal)  -- saves backup pos, sets Collide flag
        return Adjusted

    -- Secondary sphere
    if NumSphere > 1:
        if sphere_intersects_poly(localSphere[1], movement, hitPoly, contactPoint) or hitPoly != null:
            collisionNormal = LocalSpacePos.LocalToGlobalVec(hitPoly.Plane.Normal)
            SetCollisionNormal(collisionNormal)
            return Collided

    return OK

BSP Traversal: sphere_intersects_poly

ACE: BSPNode.sphere_intersects_poly() / BSPLeaf.sphere_intersects_poly() Already ported: BSPQuery.SphereIntersectsPoly() in BSPQuery.cs

function BSPNode.sphere_intersects_poly(checkPos, movement, hitPoly, contactPoint) -> bool:
    -- Broad phase: bounding sphere rejection
    if not BoundingSphere.Intersects(checkPos): return false

    -- Classify sphere against splitting plane
    dist = dot(SplittingPlane.Normal, checkPos.Center) + SplittingPlane.D
    reach = checkPos.Radius - EPSILON

    if dist >= reach:
        return PosNode.sphere_intersects_poly(...)
    if dist <= -reach:
        return NegNode.sphere_intersects_poly(...)

    -- Straddles: check both
    if PosNode.sphere_intersects_poly(...): return true
    return NegNode.sphere_intersects_poly(...)

function BSPLeaf.sphere_intersects_poly(checkPos, movement, hitPoly, contactPoint) -> bool:
    if NumPolys == 0 or not BoundingSphere.Intersects(checkPos): return false

    for each polygon:
        if polygon.pos_hits_sphere(checkPos, movement, contactPoint, hitPoly):
            return true
    return false

Note: pos_hits_sphere is the polygon-level test corresponding to our already-ported CollisionPrimitives.SphereIntersectsPoly(). The difference is that pos_hits_sphere also returns the contact point and sets the hitPoly reference even when the sphere overlaps but does not fully intersect (important for the hitPoly != null fallback paths in find_collisions).

---

5. StepUp / StepDown

StepUp

ACE: Transition.StepUp(Vector3 collisionNormal)

Called when an object walking on the ground hits a wall. Tries to "step up" onto the obstacle by doing a step-down from a raised position.

function StepUp(collisionNormal) -> bool:
    ContactPlaneValid = false
    ContactPlaneIsWater = false

    SpherePath.StepUp = true
    StepUpNormal = collisionNormal

    stepDownHeight = 0.04            -- default step probe height
    zLandingValue = LandingZ         -- default walkable Z threshold (0.0872)

    if OnWalkable:
        zLandingValue = GetWalkableZ()       -- object's specific walkable threshold
        stepDownHeight = ObjectInfo.StepUpHeight  -- object's specific step height

    WalkableAllowance = zLandingValue
    BackupCell = CheckCell
    BackupCheckPos = copy of CheckPos

    -- The step-up trick: StepDown with StepUp=true skips the
    -- downward offset (the sphere is already at the collision point,
    -- which is above the step). StepDown then probes downward to
    -- find a walkable surface.
    success = StepDown(stepDownHeight, zLandingValue)

    SpherePath.StepUp = false
    Walkable = null

    if not success:
        RestoreCheckPos()

    return success

StepDown

ACE: Transition.StepDown(float stepDownHeight, float zVal)

Probes downward from the current check position to find a walkable surface.

function StepDown(stepDownHeight, zVal) -> bool:
    NegPolyHit = false
    SpherePath.StepDown = true
    StepDownAmt = stepDownHeight
    WalkInterp = 1.0

    -- If NOT in step-up mode, apply the downward offset
    if not StepUp:
        CellArrayValid = false
        offset = (0, 0, -stepDownHeight)
        CheckPos.Frame.Origin.Z -= stepDownHeight
        CacheGlobalSphere(offset)

    -- Run collision detection with step-down flag active
    transitState = TransitionalInsert(5)     -- 5 attempts for step-down

    SpherePath.StepDown = false

    -- Accept the step-down if:
    --   1. Collision detection returned OK
    --   2. A valid contact plane was found
    --   3. The contact plane is walkable (Normal.Z >= zVal)
    --   4. Edge-slide check passes (if applicable)
    if transitState == OK
       and ContactPlaneValid
       and ContactPlane.Normal.Z >= zVal
       and (not EdgeSlide or StepUp or CheckWalkable(zVal)):

        -- Validate the final position with a placement insert
        save InsertType
        InsertType = Placement
        transitState = TransitionalInsert(1)
        restore InsertType

        return transitState == OK

    return false

StepSphereUp (object-vs-object)

ACE: Sphere.StepSphereUp()

When an object on the ground collides with another sphere-based object:

function StepSphereUp(center, transition, disp, radsum) -> TransitionState:
    radsum += EPSILON

    -- If the obstacle is taller than our step-up height, slide instead
    if StepUpHeight < radsum - disp.Z:
        return SlideSphere(center, transition, disp, 0)

    -- Otherwise, try a full Transition.StepUp
    collisionNormal = GlobalCurrCenter[0].Center - center
    if Transition.StepUp(collisionNormal):
        return OK
    else:
        return StepUpSlide()

step_sphere_down (BSP indoor)

ACE: BSPTree.step_sphere_down()

Finds a walkable surface below the sphere in BSP geometry:

function step_sphere_down(transition, checkPos, scale) -> TransitionState:
    step_down_amount = -(StepDownAmt * WalkInterp)
    movement = LocalSpaceZ * step_down_amount * (1 / scale)

    validPos = copy of checkPos
    changed = false
    polyHit = null

    find_walkable(validPos, polyHit, movement, LocalSpaceZ, changed)

    if changed:
        adjusted = validPos.Center - checkPos.Center
        offset = LocalSpacePos.LocalToGlobalVec(adjusted) * scale
        CheckPos.Frame.Origin += offset
        CacheGlobalSphere(offset)

        contactPlane = polyHit.Plane transformed to global, D *= scale
        SetContactPlane(contactPlane, false)
        ContactPlaneCellID = CheckPos.ObjCellID
        SetWalkable(validPos, polyHit, LocalSpaceZ, LocalSpacePos, scale)

        return Adjusted

    return OK

---

6. AdjustOffset / SlideSphere

AdjustOffset

ACE: Transition.AdjustOffset(Vector3 offset)

Adjusts the per-step movement offset to account for existing contact planes and sliding normals. This is called BEFORE applying the offset to CheckPos.

function AdjustOffset(offset) -> Vector3:
    result = copy of offset
    checkSlide = false

    -- Check if we should apply sliding
    slidingAngle = dot(result, SlidingNormal)
    if SlidingNormalValid:
        if slidingAngle < 0:
            checkSlide = true
        else:
            SlidingNormalValid = false

    -- No contact plane: simple sliding projection
    if not ContactPlaneValid:
        if checkSlide:
            result -= SlidingNormal * slidingAngle
        return result

    -- Have a contact plane: project movement onto the contact surface
    collisionAngle = dot(result, ContactPlane.Normal)
    slideOffset = cross(ContactPlane.Normal, SlidingNormal)

    if checkSlide:
        -- Project movement along the intersection of contact plane and slide plane
        if normalize(slideOffset) fails:
            result = Zero
        else:
            result = dot(slideOffset, result) * slideOffset
    elif collisionAngle <= 0:
        -- Moving into the contact plane: remove the component into the plane
        result -= ContactPlane.Normal * collisionAngle
    else:
        -- Moving away from contact plane: snap to plane
        ContactPlane.SnapToPlane(result)

    -- Safety: ensure sphere stays above contact plane
    if ContactPlaneCellID != 0 and not ContactPlaneIsWater:
        globSphere = GlobalSphere[0]
        blockOffset = GetBlockOffset(CheckPos.CellID, ContactPlaneCellID)
        dist = dot(globSphere.Center - blockOffset, ContactPlane.Normal) + ContactPlane.D
        if dist < globSphere.Radius - EPSILON:
            zDist = (globSphere.Radius - dist) / ContactPlane.Normal.Z
            if globSphere.Radius > abs(zDist):
                AddOffsetToCheckPos(0, 0, zDist)

    return result

SlideSphere (wall slide — environment collision normal variant)

ACE: Sphere.SlideSphere(Transition, ref Vector3 collisionNormal, Vector3 currPos) Decompiled: FUN_00538180 at 0x00538180

This is the primary slide function used after environment (BSP) collisions.

function SlideSphere(transition, collisionNormal, currPos) -> TransitionState:
    -- Degenerate case: zero collision normal
    if collisionNormal == Zero:
        halfOffset = (currPos - Center) * 0.5
        AddOffsetToCheckPos(halfOffset)
        return Adjusted

    SetCollisionNormal(collisionNormal)

    blockOffset = GetBlockOffset(CurPos.CellID, CheckPos.CellID)
    gDelta = blockOffset + (Center - currPos)    -- global displacement from curr to check

    -- Get the contact plane (prefer current, fall back to last known)
    contactPlane = ContactPlaneValid ? ContactPlane : LastKnownContactPlane

    -- Project movement along the crease between collision normal and contact plane
    direction = cross(collisionNormal, contactPlane.Normal)
    dirLenSq = direction.LengthSquared

    if dirLenSq >= EPSILON:
        -- Crease exists: project displacement onto it
        diff = dot(direction, gDelta)
        invDirLenSq = 1 / dirLenSq
        offset = direction * diff * invDirLenSq

        if offset.LengthSquared < EPSILON:
            return Collided

        offset -= gDelta     -- subtract current displacement to get correction
        AddOffsetToCheckPos(offset)
        return Slid

    -- Collision normal and contact plane are parallel
    if dot(collisionNormal, contactPlane.Normal) >= 0:
        -- Same direction: project out along collision normal
        diff = dot(collisionNormal, gDelta)
        offset = -collisionNormal * diff
        AddOffsetToCheckPos(offset)
        return Slid

    -- Opposing normals: give up, reverse direction
    collisionNormal = -gDelta
    if normalize(collisionNormal) succeeds:
        SetCollisionNormal(collisionNormal)
    return OK   -- note: returns OK, not Collided — this resets for retry

SlideSphere (object-vs-object variant)

ACE: Sphere.SlideSphere(Vector3 center, Transition, Vector3 disp, int sphereNum)

Used when sliding off another physics object (sphere-sphere collision).

function SlideSphere_Object(center, transition, disp, sphereNum) -> TransitionState:
    globSphere = GlobalSphere[sphereNum]

    -- Collision normal: from obstacle center to our current center
    collisionNormal = GlobalCurrCenter[sphereNum].Center - center
    if normalize(collisionNormal) fails:
        return Collided

    SetCollisionNormal(collisionNormal)

    contactPlane = ContactPlaneValid ? ContactPlane : LastKnownContactPlane
    skid_dir = contactPlane.Normal
    direction = cross(collisionNormal, skid_dir)

    blockOffset = GetBlockOffset(CurPos.CellID, CheckPos.CellID)
    globOffset = globSphere.Center - GlobalCurrCenter[sphereNum].Center + blockOffset
    dirLenSq = direction.LengthSquared

    if dirLenSq >= EPSILON:
        skid_dir = dot(globOffset, direction) * direction
        invDirLenSq = 1 / dirLenSq
        skid_dir *= invDirLenSq
        direction = skid_dir

        if direction.LengthSquared < EPSILON:
            return Collided

        direction -= globOffset
        AddOffsetToCheckPos(direction)
        return Slid

    -- Parallel case
    if dot(skid_dir, disp) < 0:
        return Collided

    direction = -dot(globOffset, collisionNormal) * collisionNormal
    AddOffsetToCheckPos(direction)
    return Slid

---

7. ValidateTransition

ACE: Transition.ValidateTransition()

Called after each step to validate the result and update state.

function ValidateTransition(transitionState) -> TransitionState:
    moved = false   -- _redo in ACE

    if transitionState == OK and CheckPos != CurPos:
        -- Movement succeeded: accept the new position
        CurPos = CheckPos
        CurCell = CheckCell
        CacheGlobalCurrCenter()
        SetCheckPos(CurPos, CurCell)
        moved = true

    elif transitionState == OK:
        -- No movement (same position): accept as-is
        SetCurrentCheckPos()

    elif transitionState == Invalid:
        -- Do nothing, leave state as-is
        pass

    else:
        -- Collision/slide/adjusted: revert to current position
        if LastKnownContactPlaneValid:
            StopVelocity()
            -- Check if we are resting on the last known contact plane
            angle = dot(LastKnownContactPlane.Normal, GlobalCurrCenter[0].Center)
                    + LastKnownContactPlane.D
            if GlobalSphere[0].Radius + EPSILON > abs(angle):
                SetContactPlane(LastKnownContactPlane, LastKnownContactPlaneIsWater)
                ContactPlaneCellID = LastKnownContactPlaneCellID
                if OnWalkable: moved = true

        if not CollisionNormalValid:
            SetCollisionNormal(UnitZ)    -- default: push up

        SetCheckPos(CurPos, CurCell)
        find_cell_list(...)
        transitionState = OK

    -- Update sliding normal from collision
    if CollisionNormalValid:
        SetSlidingNormal(CollisionNormal)  -- XY only, Z zeroed

    -- Gravity fall-through safety (FramesStationaryFall)
    if not IsViewer and HasGravity:
        if not moved:
            if FramesStationaryFall > 0:
                if FramesStationaryFall > 1:
                    -- After 3 frames of no movement with gravity:
                    -- create a synthetic floor under the object
                    FramesStationaryFall = 3
                    syntheticPlane.Normal = UnitZ
                    syntheticPlane.D = GlobalSphere[0].Radius - GlobalSphere[0].Center.Z
                    SetContactPlane(syntheticPlane, false)
                    ContactPlaneCellID = CheckPos.ObjCellID
                    if not Contact:
                        SetCollisionNormal(UnitZ)
                        CollidedWithEnvironment = true
                else:
                    FramesStationaryFall = 2
            else:
                FramesStationaryFall = 1
        else:
            FramesStationaryFall = 0

    -- Preserve contact plane for next step
    LastKnownContactPlaneValid = ContactPlaneValid
    if ContactPlaneValid:
        LastKnownContactPlane = ContactPlane
        LastKnownContactPlaneCellID = ContactPlaneCellID
        LastKnownContactPlaneIsWater = ContactPlaneIsWater
        State |= Contact
        if is_valid_walkable(ContactPlane.Normal):
            State |= OnWalkable
        else:
            State &= ~OnWalkable
    else:
        State &= ~(Contact | OnWalkable)

    return transitionState

Key insight: FramesStationaryFall

This is a safety valve for objects with gravity that get stuck. After 3 consecutive frames where gravity is active but the object hasn't actually moved, the system creates a synthetic horizontal floor plane under the object. This prevents objects from falling through the world indefinitely.

---

8. Already Ported

The following functions are already ported in src/AcDream.Core/Physics/CollisionPrimitives.cs:

Function	Decompiled Address	CollisionPrimitives Method
SphereIntersectsRay	FUN_005384e0	SphereIntersectsRay()
ray_plane_intersect	FUN_00539060	RayPlaneIntersect()
calc_normal	FUN_00539110	CalcNormal()
sphere_intersects_poly	FUN_00539500	SphereIntersectsPoly()
find_time_of_collision	FUN_00539ba0	FindTimeOfCollision()
hits_walkable	FUN_0053a230	HitsWalkable()
find_walkable_collision	FUN_0053a040	FindWalkableCollision()
slide_sphere (parametric)	FUN_00538eb0	SlideSphere()
land_on_sphere	FUN_00538f50	LandOnSphere()

The following are ported in src/AcDream.Core/Physics/BSPQuery.cs:

Function	BSPQuery Method
BSPNode.sphere_intersects_poly (tree traversal)	BSPQuery.SphereIntersectsPoly()

Not Yet Ported (needed for full transition system)

ACE Class/Method	Purpose
Transition (entire class)	Main orchestrator
SpherePath	Movement descriptor and sphere caching
CollisionInfo	Collision result accumulation
ObjectInfo	Object flags and validation
BSPTree.find_collisions	Indoor BSP collision dispatcher
BSPTree.step_sphere_down	BSP step-down walkable search
BSPTree.step_sphere_up	BSP step-up via Transition.StepUp
BSPTree.placement_insert	Placement collision with iterative push-out
BSPNode.sphere_intersects_solid	Solid-region intersection test
BSPNode.sphere_intersects_solid_poly	Solid-region with polygon identification
BSPNode.find_walkable	Walkable surface search in BSP
BSPNode.hits_walkable	Quick walkable probe
Sphere.IntersectsSphere	Object-vs-object collision
Sphere.StepSphereUp	Object step-up response
Sphere.StepSphereDown	Object step-down response
Sphere.SlideSphere (both variants)	Wall slide projection
Sphere.CollideWithPoint	PerfectClip collision adjustment
Sphere.LandOnSphere	Landing on spherical object
LandCell.FindEnvCollisions	Outdoor terrain collision
EnvCell.FindEnvCollisions	Indoor BSP collision
ObjCell.FindObjCollisions	Object-vs-object in a cell
ObjCell.find_cell_list	Cell enumeration for sphere
LandCell.add_all_outside_cells	Neighbor cell enumeration

---

9. Key Constants

Constant	Value	ACE Name	Decompiled Address
EPSILON	0.0002	PhysicsGlobals.EPSILON	_DAT_007ca5d8 area
EPSILON_SQ	0.00000004	PhysicsGlobals.EpsilonSq
LandingZ	0.0871557	PhysicsGlobals.LandingZ	_DAT_007ca580
FloorZ	0.6642	PhysicsGlobals.FloorZ
DefaultStepHeight	0.01	PhysicsGlobals.DefaultStepHeight
Step-down probe	0.04	hardcoded in StepUp/TransitionalInsert	0x3D23D70A
Gravity	-9.8	PhysicsGlobals.Gravity
MaxVelocity	50.0	PhysicsGlobals.MaxVelocity
DummySphereRadius	0.1	PhysicsGlobals.DummySphereRadius
Max steps	30 (retail) / 1000 (ACE)	hardcoded in FindTransitionalPosition
BSP cell epsilon	0.01	hardcoded in sphere_intersects_cell_bsp
Placement iterations	20	hardcoded in placement_insert
Adjust-to-plane iterations	15	hardcoded in adjust_to_plane

ObjectInfoState Flags

Contact         = 0x001  -- object is touching a surface
OnWalkable      = 0x002  -- object is on a walkable surface
IsViewer        = 0x004  -- this is the camera
PathClipped     = 0x008  -- PerfectClip movement (missiles)
FreeRotate      = 0x010  -- rotation is set directly, not interpolated
PerfectClip     = 0x040  -- precise collision adjustment
IsImpenetrable  = 0x080
IsPlayer        = 0x100
EdgeSlide       = 0x200  -- precipice edge-slide behavior enabled
IgnoreCreatures = 0x400

TransitionState Summary

OK (1)       -- Position accepted. Move succeeded.
Collided (2) -- Hard stop. Cannot pass. Revert to CurPos.
Adjusted (3) -- Position was nudged to resolve penetration. Re-check needed.
Slid (4)     -- Position was projected along a surface. Re-check needed.
Invalid (0)  -- Internal error state. Should not propagate.

---

10. ACE vs Decompiled Differences

1. Max steps: Retail client uses 30 as the maximum number of sub-steps. ACE bumped this to 1000 with a comment, likely to handle server-side edge cases with large movements. For acdream (a client), 30 is correct.

2. collide_with_point (FUN_00538180): The decompiled code at 0x00538180 shows the SlideSphere function with explicit struct offset arithmetic. ACE's version matches the algorithm but uses cleaner variable naming. The key structure: the function computes cross(collisionNormal, contactPlane.Normal) to find the slide direction, then projects the displacement onto it. Both versions handle the parallel-normal degenerate case identically.

3. FUN_005387c0 (find_collisions at 0x005387C0): This is labeled as CTransition::find_collisions in the function map but actually corresponds to Sphere.IntersectsSphere in ACE — the object-vs-object collision dispatcher. The decompiled code shows the same branching structure: check ObstructionEthereal/Placement, then StepDown, then CheckWalkable, then Contact/OnWalkable paths. The constant at offset 0x1cc corresponds to ObstructionEthereal, 0x174 to InsertType, 0x178 to StepDown, etc.

4. Global constants: The decompiled code references globals by address (_DAT_007ca5d8, _DAT_007938b0, etc.). These map to:

   • _DAT_007ca5d8 = EPSILON squared (~1e-8) in some contexts, EPSILON (~2e-4) in others
   • _DAT_007938b0 = 1.0f (used as 1.0f / dirLenSq identity)
   • _DAT_007938b8 = 0.5f (used in half-offset calculations)
   • _DAT_007938c0 = 1.0f
   • _DAT_007ca580 = LandingZ (0.0871557)
   • DAT_00796344 = 0.0f (zero constant)

5. SetCollisionNormal normalization: ACE's CollisionInfo.SetCollisionNormal normalizes and checks for small vectors. The decompiled code (FUN_004524a0) does the same check. If normalization fails (near-zero vector), ACE sets CollisionNormal to Zero; the decompiled code returns 0 to indicate failure.

6. Edge slide behavior: ACE's EdgeSlide method has additional complexity around PrecipiceSlide that handles walking off edges of walkable surfaces. The decompiled code for this is spread across multiple functions. The algorithm finds the crossed edge of the walkable polygon and uses that edge normal for the slide direction, preventing the player from walking off cliffs.