Raycaster отображает фантомные перпендикулярные грани стен

Question

Вывод выглядит так:

Вы должны просто увидеть плоскую сплошную красную стену с одной стороны, синюю стену с другой, зеленую с другой, желтую с другой (см. Определение карты, testMapTilesЭто просто карта с четырьмя стенами). И все же существуют призрачные грани стен различной высоты, которые перпендикулярны реальным стенам. Зачем?

Обратите внимание, что белые "пробелы" на самом деле не являются пробелами: они пытаются нарисовать стену высоты Infinity (расстояние 0). Если вы специально учитываете это (эта версия кода этого не делает) и просто ограничиваете его на высоте экрана, то вы видите там очень высокую стену.

Исходный код ниже. Это простой Haskell, использующий Haste для компиляции в JavaScript и рендеринга в canvas. Он основан на коде C++ из этого руководства, хотя обратите внимание, что я заменил mapX а также mapY с tileX а также tileYи у меня нет ray префикс для pos а также dir в основном цикле. Любые несоответствия из кода C++, вероятно, и являются причиной того, что ломает все, но я, похоже, не могу их найти после многократного изучения этого кода.

Любая помощь?

import Data.Array.IArray
import Control.Arrow (first, second)

import Control.Monad (forM_)

import Haste
import Haste.Graphics.Canvas

data MapTile = Empty | RedWall | BlueWall | GreenWall | YellowWall deriving (Eq)

type TilemapArray = Array (Int, Int) MapTile

emptyTilemapArray :: (Int, Int) -> TilemapArray
emptyTilemapArray dim@(w, h) = listArray ((1, 1), dim) $ replicate (w * h) Empty

testMapTiles :: TilemapArray
testMapTiles =
    let arr = emptyTilemapArray (16, 16)
        myBounds@((xB, yB), (w, h)) = bounds arr
    in  listArray myBounds $ flip map (indices arr) (\(x, y) ->
            if x == xB then RedWall
            else if y == yB then BlueWall
            else if x == w then GreenWall
            else if y == h then YellowWall
            else Empty)

type Vec2 a = (a, a)
type DblVec2 = Vec2 Double
type IntVec2 = Vec2 Int

add :: (Num a) => Vec2 a -> Vec2 a -> Vec2 a
add (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)

mul :: (Num a) => Vec2 a -> a -> Vec2 a
mul (x, y) factor = (x * factor, y * factor)

rot :: (Floating a) => Vec2 a -> a -> Vec2 a
rot (x, y) angle =
    (x * (cos angle) - y * (sin angle), x * (sin angle) + y * (cos angle))

dbl :: Int -> Double
dbl = fromIntegral

-- fractional part of a float
-- `truncate` matches behaviour of C++'s int()
frac :: Double -> Double
frac d = d - dbl (truncate d)

-- get whole and fractional parts of a float
split :: Double -> (Int, Double)
split d = (truncate d, frac d)

-- stops 'Warning: Defaulting the following constraint(s) to type ‘Integer’'
square :: Double -> Double
square = (^ (2 :: Int))

-- raycasting algorithm based on code here:
-- http://lodev.org/cgtutor/raycasting.html#Untextured_Raycaster_

data HitSide = NorthSouth | EastWest deriving (Show)

-- direction, tile, distance
type HitInfo = (HitSide, IntVec2, Double)

-- pos: start position
-- dir: initial direction
-- plane: camera "plane" (a line, really, perpendicular to the direction)
traceRays :: TilemapArray -> Int -> DblVec2 -> DblVec2 -> DblVec2 -> [HitInfo]
traceRays arr numRays pos dir plane = 
    flip map [0..numRays] $ \x -> 
        let cameraX = 2 * ((dbl x) / (dbl numRays)) - 1
        in  traceRay arr pos $ dir `add` (plane `mul` cameraX)

traceRay :: TilemapArray -> DblVec2 -> DblVec2 -> HitInfo
traceRay arr pos@(posX, posY) dir@(dirX, dirY) =
    -- map tile we're in (whole part of position)
    -- position within map tile (fractional part of position)
    let ((tileX, fracX), (tileY, fracY)) = (split posX, split posY)
        tile = (tileX, tileY)
    -- length of ray from one x or y-side to next x or y-side
        deltaDistX = sqrt $ 1 + (square dirY / square dirX)
        deltaDistY = sqrt $ 1 + (square dirX / square dirY)
        deltaDist  = (deltaDistX, deltaDistY)
    -- direction of step
        stepX = if dirX < 0 then -1 else 1
        stepY = if dirY < 0 then -1 else 1
        step  = (stepX, stepY)
    -- length of ray from current position to next x or y-side
        sideDistX = deltaDistX * if dirX < 0 then fracX else 1 - fracX
        sideDistY = deltaDistY * if dirY < 0 then fracY else 1 - fracY
        sideDist  = (sideDistX, sideDistY)
        (hitSide, wallTile) = traceRayInner arr step deltaDist tile sideDist
    in  (hitSide, wallTile, calculateDistance hitSide pos dir wallTile step)

traceRayInner :: TilemapArray -> IntVec2 -> DblVec2 -> IntVec2 -> DblVec2 -> (HitSide, IntVec2)
traceRayInner arr step@(stepX, stepY) deltaDist@(deltaDistX, deltaDistY) tile sideDist@(sideDistX, sideDistY)
    -- a wall has been hit, report hit direction and coördinates
    | arr ! tile /= Empty   = (hitSide, tile)
    -- advance until a wall is hit
    | otherwise             = case hitSide of
        EastWest ->
            let newSideDist = first (deltaDistX+) sideDist
                newTile     = first (stepX+) tile
            in
                traceRayInner arr step deltaDist newTile newSideDist
        NorthSouth ->
            let newSideDist = second (deltaDistY+) sideDist
                newTile     = second (stepY+) tile
            in
                traceRayInner arr step deltaDist newTile newSideDist
    where
        hitSide = if sideDistX < sideDistY then EastWest else NorthSouth

-- calculate distance projected on camera direction
-- (an oblique distance would give a fisheye effect)
calculateDistance :: HitSide -> DblVec2 -> DblVec2 -> IntVec2 -> IntVec2 -> Double
calculateDistance EastWest (startX, _) (dirX, _) (tileX, _) (stepX, _) =
    ((dbl tileX) - startX + (1 - dbl stepX) / 2) / dirX
calculateDistance NorthSouth (_, startY) (_, dirY) (_, tileY) (_, stepY) =
    ((dbl tileY) - startY + (1 - dbl stepY) / 2) / dirY

-- calculate the height of the vertical line on-screen based on the distance
calculateHeight :: Double -> Double -> Double
calculateHeight screenHeight 0 = screenHeight
calculateHeight screenHeight perpWallDist = screenHeight / perpWallDist

width   :: Double
height  :: Double
(width, height) = (640, 480)

main :: IO ()
main = do
    cvElem <- newElem "canvas" `with` [
            attr "width" =: show width,
            attr "height" =: show height
        ]
    addChild cvElem documentBody
    Just canvas <- getCanvas cvElem
    let pos     = (8, 8)
        dir     = (-1, 0)
        plane   = (0, 0.66)
    renderGame canvas pos dir plane

renderGame :: Canvas -> DblVec2 -> DblVec2 -> DblVec2 -> IO ()
renderGame canvas pos dir plane = do
    let rays    = traceRays testMapTiles (floor width) pos dir plane
    render canvas $ forM_ (zip [0..width - 1] rays) (\(x, (side, tile, dist)) ->
        let lineHeight  = calculateHeight height dist
            wallColor   = case testMapTiles ! tile of
                RedWall     -> RGB 255 0 0
                BlueWall    -> RGB 0 255 0
                GreenWall   -> RGB 0 0 255
                YellowWall  -> RGB 255 255 0
                _           -> RGB 255 255 255
            shadedWallColor = case side of
                EastWest    -> 
                    let (RGB r g b) = wallColor
                    in  RGB (r `div` 2) (g `div` 2) (b `div` 2)
                NorthSouth  -> wallColor
        in  color shadedWallColor $ do
                translate (x, height / 2) $ stroke $ do
                    line (0, -lineHeight / 2) (0, lineHeight / 2))
    -- 25fps
    let fps             = 25
        timeout         = (1000 `div` fps) :: Int
        rots_per_min    = 1
        rots_per_sec    = dbl rots_per_min / 60
        rots_per_frame  = rots_per_sec / dbl fps
        tau             = 2 * pi
        increment       = tau * rots_per_frame 

    setTimeout timeout $ do
       renderGame canvas pos (rot dir $ -increment) (rot plane $ -increment)

HTML-страница:

<!doctype html>
<meta charset=utf-8>
<title>Raycaster</title>

<noscript>If you're seeing this message, either your browser doesn't support JavaScript, or it is disabled for some reason. This game requires JavaScript to play, so you'll need to make sure you're using a browser which supports it, and enable it, to play.</noscript>
<script src=raycast.js></script>

Answer 1

"Призрачные лица" происходят из-за неправильного HitSide сообщается: вы говорите, что лицо попало в горизонтальное движение (EastWest), но на самом деле попал в вертикальное движение (NorthSouth), или наоборот.

Почему тогда он сообщает о неверном значении? if sideDistX < sideDistY then EastWest else NorthSouth кажется довольно надежным, не так ли? И это.

Проблема не в том, как мы рассчитали это значение. Это когда мы вычислили это значение. Функция расчета расстояния должна знать направление, в котором мы двигались, чтобы добраться до стены. Однако на самом деле мы указали направление, в котором мы будем двигаться, если бы мы продолжали движение (то есть, если бы эта плитка не была стеной или мы по какой-то причине игнорировали ее).

Посмотрите на код на Haskell:

traceRayInner arr step@(stepX, stepY) deltaDist@(deltaDistX, deltaDistY) tile sideDist@(sideDistX, sideDistY)
    -- a wall has been hit, report hit direction and coördinates
    | arr ! tile /= Empty   = (hitSide, tile)
    -- advance until a wall is hit
    | otherwise             = case hitSide of
        EastWest ->
            let newSideDist = first (deltaDistX+) sideDist
                newTile     = first (stepX+) tile
            in
                traceRayInner arr step deltaDist newTile newSideDist
        NorthSouth ->
            let newSideDist = second (deltaDistY+) sideDist
                newTile     = second (stepY+) tile
            in
                traceRayInner arr step deltaDist newTile newSideDist
    where
        hitSide = if sideDistX < sideDistY then EastWest else NorthSouth

Обратите внимание, что мы делаем вещи в следующем порядке:

1. подсчитывать hitSide
2. проверьте, была ли повреждена стена, и если да, сообщите hitSide
3. переехать

Сравните это с оригинальным кодом C++:

//perform DDA
while (hit == 0)
{
  //jump to next map square, OR in x-direction, OR in y-direction
  if (sideDistX < sideDistY)
  {
    sideDistX += deltaDistX;
    mapX += stepX;
    side = 0;
  }
  else
  {
    sideDistY += deltaDistY;
    mapY += stepY;
    side = 1;
  }
  //Check if ray has hit a wall
  if (worldMap[mapX][mapY] > 0) hit = 1;
}

Это делает вещи в другом порядке:

1. проверьте, была ли повреждена стена, и если да, сообщите side (эквивалентно hitSide)
2. двигаться и рассчитывать side

Код C++ рассчитывает только side когда он движется, а затем сообщает об этом значении, если попадает в стену. Таким образом, он сообщает, как он двигался, чтобы ударить стену.

Код Haskell рассчитывает side движется он или нет: так что это правильно для каждого хода, но когда он ударяет о стену, он сообщает, как он двигался, если бы продолжал идти.

Таким образом, код на Haskell можно исправить, переставив его так, чтобы он проверял наличие попадания после перемещения и, если да, сообщает hitSide ценность от этого движения. Это не красивый код, но он работает:

traceRayInner arr step@(stepX, stepY) deltaDist@(deltaDistX, deltaDistY) tile sideDist@(sideDistX, sideDistY) =
    let hitSide = if sideDistX < sideDistY then EastWest else NorthSouth
    in  case hitSide of
        EastWest ->
            let newSideDist = first (deltaDistX+) sideDist
                newTile     = first (stepX+) tile
            in  case arr ! newTile of
                -- advance until a wall is hit
                Empty   ->  traceRayInner arr step deltaDist newTile newSideDist
                -- a wall has been hit, report hit direction and coördinates
                _       ->  (hitSide, newTile)
        NorthSouth ->
            let newSideDist = second (deltaDistY+) sideDist
                newTile     = second (stepY+) tile
            in  case arr ! newTile of
                -- advance until a wall is hit
                Empty   ->  traceRayInner arr step deltaDist newTile newSideDist
                -- a wall has been hit, report hit direction and coördinates
                _       ->  (hitSide, newTile)

Задача решена!

---

Примечание: я выяснил, что было не так после выполнения алгоритма на бумаге. В то время как в этом конкретном случае это произошло именно так, последние два HitSide значения совпали, стало очевидно, что они могут не в каждом случае. Итак, большое спасибо Madsy на Фриноде #algorithms за предложение попробовать это на бумаге.:)