Is this DDA raycast algorithm good enough?

[StriderPulse599]

I'm trying to implement a DDA raycast algorithm and managed to dug up some working code, then reworked it to draw a sf::TriangleFan for light map. The only problem is how wonky the TriangleFan can be, as more than 0.1 difference between angles cause clipping

Reworked code (original: https://codereview.stackexchange.com/questions/190662/2d-raycasting-implementation):

#include <SFML\Graphics.hpp>
#include <iostream>

const int MAP_W = 10;
const int MAP_H = 10;

//map data, 1 represents wall, 0 - no wall
int map[MAP_W][MAP_H] =
{
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    { 1, 0, 0, 0, 1, 1, 0, 0, 0, 1 },
    { 1, 0, 0, 0, 1, 0, 0, 1, 0, 1 },
    { 1, 0, 0, 0, 1, 1, 1, 1, 0, 1 },
    { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
    { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 },
    { 1, 0, 0, 0, 0, 0, 1, 0, 0, 1 },
    { 1, 0, 1, 0, 0, 1, 0, 1, 0, 1 },
    { 1, 0, 1, 0, 0, 1, 0, 0, 0, 1 },
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};

sf::Vector2i playerMapPos = { 5, 5 };
sf::Vector2f playerWorldPos;

sf::Vector2f tileSize;

std::vector<std::vector<float>> bakedCakes;

//get raycast closest hit point
sf::Vector2f getDistToClosestHitPoint(sf::Vector2i rayMapPos, sf::Vector2f rayWorldPos, std::vector<float> cake)
{
    sf::Vector2f rayDir = { cake[1], cake[2]};

    float dyh = 0; //dist y to next horizontal tile
    float dxh = 0; //dist x to next horizontal tile

    if (rayWorldPos.y == rayMapPos.y * tileSize.y) dyh = tileSize.y;
   
    else
    {
        if (rayDir.y < 0) dyh = rayWorldPos.y - (rayMapPos.y * tileSize.y);
        else dyh = (rayMapPos.y + 1) * tileSize.y - rayWorldPos.y;
    }

    dxh = dyh / cake[3];
    if (rayDir.y < 0) //invert distances values when pointing upwards
    {
        dxh = -dxh;
        dyh = -dyh;
    }

    float dyv = 0; //dist y to next vertical tile
    float dxv = 0; //dist x to next vertical tile

    if (rayWorldPos.x == rayMapPos.x * tileSize.x) dxv = tileSize.x;
   
    else
    {
        if (rayDir.x < 0) dxv = rayWorldPos.x - (rayMapPos.x * tileSize.x);
        else dxv = (rayMapPos.x + 1) * tileSize.x - rayWorldPos.x;
    }

    dyv = dxv * cake[3];
    if (rayDir.x < 0) //invert distances values when pointing upwards
    {
        dxv = -dxv;
        dyv = -dyv;
    }

    //calc squares and compare them
    float sqrLenHor = dxh * dxh + dyh * dyh;
    float sqrLenVer = dxv * dxv + dyv * dyv;

    //select distances which squares are lower
    float dx = sqrLenHor < sqrLenVer ? dxh : dxv;
    float dy = sqrLenHor < sqrLenVer ? dyh : dyv;
   
    return { dx, dy };
}

sf::VertexArray hitLines(sf::TriangleFan);

void visualizePlayerRaycast(sf::RenderWindow& gameWindow, std::vector<float> cake)
{
    sf::Vector2f totalDist = { 0, 0 };

    float angle = cake[0];
   
    sf::Vector2f dir = { cake[1], cake[2] };

    //get distance to first hit point
    sf::Vector2f dist = getDistToClosestHitPoint(playerMapPos, playerWorldPos, cake);

    //first ray hit position coordinates
    sf::Vector2f rayWorldPos = { playerWorldPos.x + dist.x, playerWorldPos.y + dist.y };
    sf::Vector2i rayPosMap = { int(rayWorldPos.x / tileSize.x), int(rayWorldPos.y / tileSize.y) }; //just divide world coordinates by tile size

    bool hit = false;
    while (!hit)
    {
        //out of array range exceptions handling
        if (rayPosMap.x < 0 || rayPosMap.x >= MAP_W || rayPosMap.y < 0 || rayPosMap.y >= MAP_H) break;

        //checking that actually hit side is wall side
        int hitTileX = rayPosMap.x;
        int hitTileY = rayPosMap.y;

        //fix checking walls when hit them on their right or bottom side, check walls earlier them
        if (rayWorldPos.x == rayPosMap.x * tileSize.x && dir.x < 0) hitTileX--; //hit wall left side
        if (rayWorldPos.y == rayPosMap.y * tileSize.y && dir.y < 0) hitTileY--; //hit wall up side

        if (map[hitTileY][hitTileX] == 1)
        {
            hitLines.append({ { rayWorldPos.x, rayWorldPos.y }, sf::Color::Red });
            hit = true; //end raycasting loop
        }
        else
        {
            //move ray to next closest horizontal or vertical side
            sf::Vector2f dist = getDistToClosestHitPoint({ rayPosMap.x, rayPosMap.y }, { rayWorldPos.x, rayWorldPos.y }, cake);

            //apply new move
            rayWorldPos.x += dist.x;
            rayWorldPos.y += dist.y;

            totalDist += dist;

            //update map positions
            rayPosMap.x = rayWorldPos.x / tileSize.x;
            rayPosMap.y = rayWorldPos.y / tileSize.y;
        }
    }
   
}

void lightBaker(float angle)
{
    sf::Vector2f rayDir = { cos(angle), sin(angle) };

    std::vector<float> cake = { angle, cos(angle), sin(angle), tan(angle) };
    bakedCakes.push_back(cake);
}

int main()
{
    sf::RenderWindow gameWindow(sf::VideoMode(1000, 800), "Raycast Test");
    gameWindow.setFramerateLimit(60);
   
    for (float i = 0; i < 6.27; i += 0.01)
    {
        lightBaker(i);
    }
    lightBaker(0);
   
    tileSize = { (float)gameWindow.getView().getSize().x / MAP_W, (float)gameWindow.getView().getSize().y / MAP_H };
    playerWorldPos = { playerMapPos.x * tileSize.x, playerMapPos.y * tileSize.y, };

    while (gameWindow.isOpen())
    {
        sf::Event event;
        while (gameWindow.pollEvent(event))
        {
            if (event.type == sf::Event::Closed)
                gameWindow.close();
        }

        float speed = 5.0f;

        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Key::W)) playerWorldPos -= sf::Vector2f{ 0.0f, 1.0f } *speed;
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Key::S)) playerWorldPos += sf::Vector2f{ 0.0f, 1.0f } *speed;
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Key::A)) playerWorldPos -= sf::Vector2f{ 1.0f, 0.0f } *speed;
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Key::D)) playerWorldPos += sf::Vector2f{ 1.0f, 0.0f } *speed;

        playerMapPos = { (int)(playerWorldPos.x / tileSize.x), (int)(playerWorldPos.y / tileSize.y) };

        gameWindow.clear(sf::Color::White);

        for (int y = 0; y < MAP_H; y++)
        {
            for (int x = 0; x < MAP_W; x++)
            {
                sf::RectangleShape tile(tileSize);
                tile.setPosition(x * tileSize.x, y * tileSize.y);
                tile.setOutlineThickness(1.0f);
                tile.setOutlineColor(sf::Color::Black);

                //we need to check by [y][x] to draw correctly because of array structure
                if (map[y][x] == 1)
                {
                    //if map[y][x] is blockade, make it black
                    tile.setFillColor(sf::Color::Black);
                    tile.setOutlineColor(sf::Color::White);
                }

                gameWindow.draw(tile);
            }
        }
        //draw player
        sf::CircleShape player(25);
        player.setOrigin({ 25, 25 });
        player.setPosition(playerWorldPos);
        player.setFillColor(sf::Color::Black);
       

        hitLines.append({ playerWorldPos, sf::Color::Red });
        for (std::vector<float> cake : bakedCakes)
        {
            visualizePlayerRaycast(gameWindow, cake);
        }
        gameWindow.draw(hitLines);
        gameWindow.draw(player);
        gameWindow.display();
        hitLines.clear();
    }
}

[eXpl0it3r]

Not sure if anyone is going to review your whole algorithm implementation...

Do you have a specific question for the code? For example about the clipping?
Do you have some video showing how it looks?

[Hapax]

    for (float i = 0; i < 6.27; i += 0.01)
    {
        lightBaker(i);
    }

I'm guessing this creates 627 vectors around the circle (not perfectly even at the end, though, due to the obvious rounding of pi), right? So it's a sort of LUT?
I don't think that's what the term light baking refers to but it's up to you what you call things, of course



That aside, when you're casting rays, do you need this many? I would presume that once you hit something, you can track it in both directions until you reach the line's end points and all of the directions between could be discarded unless there is something in front. Maybe its simpler to calculate all edges that are facing the player and flatten them (in a similar way in concept to the way 3D perspective is flattened to 2D) and then check each line (and cull ones fully "behind" other lines, again like perspective culling).
Your way (although it may be the best way; I've not intensely tested it) seems to be more the "bitmap/brute force" to the other (my?) way's "vector/scalable" graphics. Just a metaphor of how I'm visualising it.



I only looked at those parts because, as eXpl0it3r mentioned, nobody is going to look through your entire code unless you have a specific issue; those parts jumped out at me.

[StriderPulse599]

    for (float i = 0; i < 6.27; i += 0.01)
    {
        lightBaker(i);
    }

I'm guessing this creates 627 vectors around the circle (not perfectly even at the end, though, due to the obvious rounding of pi), right? So it's a sort of LUT?
I don't think that's what the term light baking refers to but it's up to you what you call things, of course

That aside, when you're casting rays, do you need this many? I would presume that once you hit something, you can track it in both directions until you reach the line's end points and all of the directions between could be discarded unless there is something in front. Maybe its simpler to calculate all edges that are facing the player and flatten them (in a similar way in concept to the way 3D perspective is flattened to 2D) and then check each line (and cull ones fully "behind" other lines, again like perspective culling).
Your way (although it may be the best way; I've not intensely tested it) seems to be more the "bitmap/brute force" to the other (my?) way's "vector/scalable" graphics. Just a metaphor of how I'm visualising it.

I only looked at those parts because, as eXpl0it3r mentioned, nobody is going to look through your entire code unless you have a specific issue; those parts jumped out at me.

This is for 2D lightning, not a raycast game. The "baking" is just calculating all sin,cos,tan and couple of other values which are used by all light entities (saves some CPU). As for the name itself, I just was bit bored and now all variables in my light pipeline now resemble cake ingredients.

The reason why there is so many is because all points are then used to create a sf::TriangleFan entities that are then drawn onto light map. Drawing along hit object might be a good idea, but I'm currently busy with other things

[Hapax]

I'm currently busy with other things

Okay. Then my only question is: what do "wonky" and "clipping" mean in the following context?:

The only problem is how wonky the TriangleFan can be, as more than 0.1 difference between angles cause clipping

[StriderPulse599]

I'm currently busy with other things

Okay. Then my only question is: what do "wonky" and "clipping" mean in the following context?:

The only problem is how wonky the TriangleFan can be, as more than 0.1 difference between angles cause clipping

At higher difference between angles and bigger distance, the line between two TriangleFan points will clip through the object (or be too far off) and often create wiggle effect. It's barely noticeable up to 0.3 (depends on distance mostly), and the only alternative is instead casting one ray per tile, check if it hit something, and then cast two rays at edges of objects.

For now I need to actually focus on gameplay, then I'll see if I need fully dynamic light or static lightmap/floodfill