Help needed with 2d Raycasting with Bresenham's algorithms

The situation

I’m stuck for days at a (first trivial…) problem which I can’t solve right now which is why I am asking here.

For my next game I need to calculate the sight for each unit. The game shows a fog of war as long no unit is in range to see through. First I had a naive approach where I simply removed the fog around a unit. This was not sufficient since certain objects can hide a units line of sight.

Back to the drawing board I’ve implemented raycasting with Bresenham’s algorithms.
First I calculate the circle of sight with the circle algorithm, then I do a raytrace with the line algorithm from the center (units position) to every point on the circle.

This approach works as expected but has some artifacts in the corners where the algorithm doesn’t catch by design:

error


My question is:

Does somebody know how modify the algorithm for this case or has a alternative?
I’ve stuck since two days and can’t figure it out. Tested around with some state tables but the math is not strong with me… :sweat_smile:

Sample Project

I have created a sample project for this which you can find on Github
With the arrow keys you can control the character, with A/B you can change the sight distance.

The issue is visible starting at a distance of 4.

The project is made in platformio. To build it with Arduino IDE just change the name of the “src” directory to “2DRaycast
There is also a Hex file available.

2 Likes

Just to clarify:

Do you want to know why your algorithm is missing those tiles you highlighted?
Or do you want to know how to make your algorithm do that?


Asuming you want it to not do that…

My own thoughts

Without looking at any code, this is how I’d choose to calculate the circle of sight:

  • First calculate the rectangle that contains the circle of sight (i.e. its width and height are the diameter of the circle, and its centre is the player’s position)
  • Use that rectangle to identify a subset of tiles that could be visible (this is an optimisation so you don’t waste time checking all tiles)*
  • For every tile in that subset, measure the distance from that tile to the player**
  • If that distance is less than the circle’s radius, that tile is within the circle of sight

* I.e.

// These 4 variables form a rectangle of space
auto left = (player.getX() - sightRadius);
auto right = (player.getX() + sightRadius);
auto top = (player.getY() - sightRadius);
auto bottom = (player.getY() + sightRadius);

// This varies depending on your coordinate system
// But you should get the idea
for(auto y = top; y <= bottom; ++y)
  for(auto x = left; x <= right; ++x)
    // get tile at x, y

** Note that this can take advantage of the ‘distance squared’ optimisation. I.e. instead of measuring distance as sqrt(x * x + y * y), you can skip the sqrt and just square the other distance.

I.e.

auto diffX = (player.getX() - tile.getX());
auto diffY = (player.getY() - tile.getY());
auto squareDistance = ((diffX * diffX) + (diffY * diffY));
auto squareRadius = (sightRadius * sightRadius);

bool tileVisible = (squareDistance <= squareRadius);

Shadowcasting

Have you considered using shadowcasting instead?

Traditionally roguelikes used shadowcasting instead of pure raytracing.

Eric Lippert (former co-author of the C# compiler and general C# know-it-all) wrote about the technique in a series of articles on his blog Fabulous Adventures In Coding.

The first one explains the general idea of shadowcasting:

The second one discusses a C# implementation:

It’s very long though.

2 Likes

Multiply all your coordinates by 2, do the raycast and divide by 2 when reading from the map.
It should hit each cell in the way at least once.

2 Likes

I know why it does it, and yes i want to fill these tiles.

This is what i have done in my naive approach. That gets nasty if i need to react to obstacles.

That’s what the current code does. :wink:

Oh boy, certainly not the cleanest way, but it works :sweat_smile:

4 Likes

Right, I’ll think about it.

In that case, call it shadowcasting rather than raycasting.
The two approaches are different:

Raycasting - The simplest approach is to trace lines from the center out to all of the mapcells at the edge of the radius and stopping when a mapcell is blocking line of sight. The problem with this approach is that many mapcells are visited several times, most often near the starting point and more seldom at the edges.

Shadowcasting - Shadowcasting divides the Field of View calculations into eight octants and visits the mapcells in a totally different way than normal raycasting, described above. Instead of tracing lines from the center out to the edges, shadowcasting visits mapcells row by row or column by column, starting with the nearest row or column and working it’s way outward.

(From roguebasin.)
There’s also more detail about the difference in this article.

Problem solved then I guess.

1 Like

Haha, I think the “clean” way would be to use a triangle-fill algorithm instead (do two casts, fill in the triangle they form), but that might be more resource-intensive.

1 Like

Oh my bad, thought it’s working the same way! then you are correct and i will take a deep look into it!
Thank you!

1 Like

That last article from adammil is particularly useful because it also mentions other approaches, has a table showing the performance differences and gives some C# code demonstrating the approaches.

Unfortunately the images are all done using traditional roguelike console characters instead of tiles, so the graphics are a bit confusing.

1 Like