I'm trying to implement a function that takes a ray as its start and end position and returns all intersections with the map grid. I wrote following code and got a problem. Function returns correct intersections only when player's position is integer value. So, I need to make an offset depending on player position in tile. I tried to implement this with my poor linear algebra understanding, but every solution was incorrect and show unexplainable behavior, so now I seek for your help


std::vector<vec2> Render::getRayIntersections(float x1, float y1, float x2, float y2, int step) 
    std::vector<vec2> points;

    float dx = x2 - x1;
    float dy = y2 - y1;
    int steps = std::max(std::abs(dx), std::abs(dy));

    float xInc = static_cast<float>(dx) / steps;
    float yInc = static_cast<float>(dy) / steps;

    float x = static_cast<float>(x1);
    float y = static_cast<float>(y1);

    for (int i = 0; i <= steps / step; ++i) {
        points.emplace_back(static_cast<int>(x), static_cast<int>(y));
        x += xInc * step;
        y += yInc * step;

    return points;

UPD: step is just a multiplier to apply this algorithm to the 2D preview where each tile has the size equal to step. In current case each tile is 16 pixels, so step = 16

As you can see, when player is on a grid center, so its position is integer, algorithm works. But when player is inside the tile, you can see that intersection points just follow the player without any offset and I get wrong result.

Gif where you can see my problem

  • \$\begingroup\$ I've written up an algorithm for this in this previous answer — does that help you? (Also, here's a version that works for a swept disc, not only an infinitely thin ray) You can also read a paper about the approach if you want something more in-depth. \$\endgroup\$
    – DMGregory
    Aug 16, 2023 at 2:04
  • \$\begingroup\$ Well, I implemented the algorithm. The trouble was the idea to calculate intersections with the grid in one loop, but I figured out that it becomes way easier to impalement the correct algorithm if we separate calculations for vertical and horizontal lines, so all we need to do is calculate player intile coordinates and add intersections on the line firstly for one axis and then for another, in separated loops. I leave my project here, so you can see algorithm I made: github \$\endgroup\$ Aug 29, 2023 at 16:27
  • \$\begingroup\$ Want to post your solution as an Answer below that you can mark as Accepted? \$\endgroup\$
    – DMGregory
    Aug 29, 2023 at 17:57


You must log in to answer this question.

Browse other questions tagged .