5
\$\begingroup\$

I have implemented a 2D raycast algorithm in SFML to detect walls in a 2D game:

raycast

How it works

  1. Player can move in every direction by w s a d keys. Cursor sets actual player direction vector, which is calculated from atan2() function.

  2. Program is calculating next vertical and horizontal side distances using player position and tangents. Then it compares their squares (pythagoras). Then it chooses the lowest and move ray by that coords. raycast

  3. Here starts raycast loop, program is checking that ray is pointing to wall. When ray is pointing in right and down there is no problem, but when it is pointing to left or up we need to fix wall checking by checking one wall earlier.

  4. If there was no wall, we repeat step 2 and 3.

Code:

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

using namespace sf;

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

const auto PI = acos(-1.0);

enum TileType
{
    EMPTY,
    BLOCKADE
};

//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;

//check window events
void checkEvents(RenderWindow & gameWindow)
{
    Event event;
    while (gameWindow.pollEvent(event))
    {
        if (event.type == Event::Closed)
            gameWindow.close();
    }
}

//update player movement
void updateSteering()
{
    float speed = 5.0f;

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

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

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

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

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

//get raycast closest hit point
sf::Vector2f getDistToClosestHitPoint(float angle, sf::Vector2i rayMapPos, sf::Vector2f rayWorldPos)
{
    sf::Vector2f rayDir = { cos(angle), sin(angle) };

    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 / tan(angle);
    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 * tan(angle);
    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 };
}

void drawMap(RenderWindow & gameWindow)
{
    for (int y = 0; y < MAP_H; y++)
    {
        for (int x = 0; x < MAP_W; x++)
        {
            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] == TileType::BLOCKADE)
            {
                //if map[y][x] is blockade, make it black
                tile.setFillColor(sf::Color::Black);
                tile.setOutlineColor(sf::Color::White);
            }

            gameWindow.draw(tile);
        }
    }
}

void visualizePlayerRaycast(RenderWindow & gameWindow)
{
    //draw line going from player position to next hit positions
    VertexArray hitLines(LinesStrip);
    hitLines.append({ playerWorldPos, Color::Red });

    //get mouse pos
    auto mousePos = Mouse::getPosition(gameWindow);

    //get player rotation angle and direction vector
    float angle = atan2(mousePos.y - playerWorldPos.y, mousePos.x - playerWorldPos.x);
    sf::Vector2f dir = { cos(angle), sin(angle) };

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

    //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;

    //raycast loop
    while (!hit)
    {
        //drawing ray hit lines
        hitLines.append({ { rayWorldPos.x, rayWorldPos.y }, sf::Color::Red });

        //drawing hit point circles
        CircleShape hitPoint(5);
        hitPoint.setOrigin({ 5, 5 });
        hitPoint.setPosition({ rayWorldPos.x, rayWorldPos.y });
        hitPoint.setFillColor(sf::Color::Red);
        gameWindow.draw(hitPoint);

        //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) //hit wall left side
        {
            hitTileX--;
        }

        if (rayWorldPos.y == rayPosMap.y * tileSize.y && dir.y < 0) //hit wall up side
        {
            hitTileY--;
        }

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

            //draw triangle for better visualization of distance
            sf::VertexArray triangleVisual(LinesStrip);
            triangleVisual.append({ { rayWorldPos.x, rayWorldPos.y }, Color::Magenta });
            triangleVisual.append({ { rayWorldPos.x + dist.x, rayWorldPos.y }, Color::Magenta });
            triangleVisual.append({ { rayWorldPos.x + dist.x, rayWorldPos.y + dist.y }, Color::Magenta });
            gameWindow.draw(triangleVisual);

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

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


    gameWindow.draw(hitLines);
}

void render(RenderWindow & gameWindow)
{
    gameWindow.clear(Color::White);
    drawMap(gameWindow);

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

    visualizePlayerRaycast(gameWindow);
    gameWindow.display();
}

int main()
{
    RenderWindow gameWindow(VideoMode(1000, 800), "Raycast Test");
    gameWindow.setFramerateLimit(60);

    //initialization
    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())
    {
        checkEvents(gameWindow);
        updateSteering();
        render(gameWindow);
    }
}

I want to know how can I optimize it. Is it implemented properly?

\$\endgroup\$
  • \$\begingroup\$ Did you forget to include <cmath>? \$\endgroup\$ – yuri Mar 28 '18 at 11:30
  • \$\begingroup\$ No I don't, that's weird but I don't need cmath to work with mathematical functions. But I don't have defined PI or M_PI. I defined it in code but it's not used. I was using it when checking atan2 angles converting them to degrees, and forgot to remove. \$\endgroup\$ – Tomek Mar 28 '18 at 11:39
  • \$\begingroup\$ There’s a way to precompute all the ray casts and use bit logic to determine visibility, so if that’s of interest (and allowable in available memory) I could write up some pointers and get you started. You shouldn’t have to compute any ray casts on the fly. If precomputing isn’t of interest, then I might have some other suggestions, but it’ll be half a day before I can follow up properly. \$\endgroup\$ – Rethunk Mar 31 '18 at 19:38
  • \$\begingroup\$ @Rethunk That's interesting thanks, could you give me some reference/example? \$\endgroup\$ – Tomek Apr 2 '18 at 9:21
  • \$\begingroup\$ @Tomek: Answer posted below. Whether it's quite what you were looking for or not, I hope it gives you a few ideas to explore. The most basic idea is simply that the "fastest" calculation may be precomputing all the advance in advance, and then using those answers on the fly. The paper I mention in my answer may appear far beyond what you need, BUT I strongly recommend reading and understanding it to learn an interesting take on precomputation for the sake of speed. \$\endgroup\$ – Rethunk Apr 3 '18 at 11:50
2
\$\begingroup\$

Since your scene is static, at least until another scene is generated, you can perform all of your raycasting at the time of scene generation. You shouldn't have to recalculate rays every cycle.

Though you'll have to adapt it to your purposes, there is a method for precomputing line fits that you can read about in the paper "A Fast Rule-Based Parameter Free Discrete Hough Transform" by Genswein & Yang (1999):

https://www.researchgate.net/publication/220359297_A_Fast_Rule-Based_Parameter_Free_Discrete_Hough_Transform

Briefly put, your code would calculate all possible lines of sight before the maze or game appears on screen for the first time. You could almost certainly simplify the line-fitting technique mentioned in the paper above, but the general technique is worth knowing as a means for precomputing fits in a 2D digital image.

  1. For each and every pixel, assign a binary representation of all the digital lines that pass through that pixel within some NxN grid of pixels. (You may be able to use your full 10x10 grid; breaking down a grid into subgrids introduces some complexity.)
  2. In your case, rather than representing a line as simply the edge-to-edge representation using the numbering scheme described in the paper, keep track of both the edge-to-edge line segment as well as the valid end points within your white/black (open/closed, available/blocked) grid.
  3. For each pixel, maintain a container (e.g. map, hash, list, array) of allowed moves.
  4. On keyboard input, check for validity of the allowed move.
  5. (UI nicety) If a move would be disallowed because the character would bump into a wall, allow the character to move just a little bit but then snap back to the original position, and briefly show the bumped wall lightening in color. This helps indicate that a move was attempted but disallowed.

The technique above would allow both for move dynamics and for checking line of sight from any pixel.

If you want to check the line of sight such that it can slip between pixels--meaning that the digital line connecting a pixel and its termination at a wall can touch a black pixel corner, for example--then you have a few additional options:

  1. Start with the technique as described above for a 10x10 grid, then introduce some logic to precompute edge cases.
  2. Create a finer line-of-sight grid. Your character may move in a 10x10 grid, but the light-of-sight grid could be something like 100x100. The Discrete Hough Transform technique describe above works for (arbitrarily) large grids, but that requires steps to break the main grid into smaller grids and then combine results.

There are other ways to handle precomputation that you might like better, depending on how you want to purse the problem:

  • Polygon/line intersection. Your black blocks represent one or more connected polygons. There are methods to check lines of sight from particular pixels is akin to calculating polygon/line intersections.
  • OpenGL. OpenGL creates 2D displays of 3D scenes using either ortho or perspective projections. A character in your game would see the world as a perspective projection. Given a 2D projection of a 3D world, you can use an octree or red-black tree or some other method to quickly calculate intersections. (This is something to keep in mind if you make a move from 2D to 3D gaming.)
  • Radial "spin casting": for each discrete point (x,y) that a character can occupy, cast rays out every N degrees. Calculate the point at which each ray intersects a wall (see polygon/line intersection above). For that (x,y) point, maintain a map of allowed directional moves. Map those directional moves (e.g. 45 degrees right and down) to combinations of keyboard inputs. If you only allow up, down, left, right to create eight directions, you don't have many casts to compute.

A lot of this may be overcomplicated for what you want to do, BUT it's worth knowing some of the techniques for future use. Given some complicated method that can be used to precompute lines, you can find a way to simplify the technique to fit your application.

To summarize:

  • Precompute allowed moves or look directions for each pixel (x,y). Whether these are calculated at scene generation, or calculated and then serialized/deserialized to/from the disk depends on your application.
  • At each pixel in a scene that the player will occupy for some period of time, store a map, hash, array, or some other representation of allowed moves. Make the code readable at first, and then if desired change the representation to something pure binary and use binary AND to calculate allowed moves. (For example, if allowed moves up, right, down, left are encoded as 1100, and if current keyboard input to the right is encoded as 0100; ANDing those together yields 0100, a non-zero value meaning the attempted move is valid. But don't code that low level unless it gains needed speed!)
  • If/when memory is an issue, consider precomputing only currently relevant portions of the grid, replace high-level readable code with binary code, etc., etc.

Good luck!

\$\endgroup\$
2
\$\begingroup\$

1) Raycasting has to be ultra quick

To keep the ray-tracing quicker in bigger maps or even in 3D maps, consider using bit-shifting in place of multiplication/division or even some assembly modules.

Trigonometric functions in your routines are also time expensive, consider using trigonometric look-up tables for sine, cosine and tangent. For example float sin[]= {0.0,0.26,0.5,0.707 ...} corresponding to 0,15,30,45....,360 degrees simplifying the angles as multiple of 15 degree.

2) FPS of animation has to be kept constant

Your animation speed will vary from system to system. Consider measuring the lapse between consecutive renderings and keep the incremental step size same. This will also ensure that your animation speed will remain same in all devices.

3) Use double buffering for flicker free animation

Use are redrawing both the background and the foreground in every render pass. Although SFML graphics is based on OpenGl, it can lead to no so smooth animation. You can use double buffering to draw next frame ahead in the memory for a smooth rendering.

\$\endgroup\$
  • \$\begingroup\$ I was asking more about properly of my algorithm implemetation, or possible code simplicitation. \$\endgroup\$ – Tomek Mar 28 '18 at 17:11
  • \$\begingroup\$ @Tomek: These points are specifically related to your implementations. \$\endgroup\$ – ark1974 Mar 28 '18 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.