Raycaster顯示幻影的垂直牆面臨

Question

輸出看起來是這樣的：

你應該只看到一面平坦，連續紅色的牆，在另一藍色的牆，綠的另一個，另一個黃色（見地圖的定義，testMapTiles，它只是一張四面牆的地圖）。然而，這些虛幻的牆面不同高度，這是垂直於真實的牆壁。爲什麼？

請注意，白色「間隙」實際上並沒有間隙：它試圖繪製高度爲Infinity（距離0）的牆。如果你明確地說明了這個問題（這個版本的代碼沒有），只是在屏幕高度上蓋上，那麼你就會看到那裏的牆壁很高。

源代碼如下。這是普通的Haskell，使用Haste編譯成JavaScript並渲染爲畫布。它是基於從this tutorial的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的值匹配，很明顯，它們可能不是在所有情況下。所以，非常感謝Freenode的#algorithms上的Madsy，建議在紙上試用它。 :)