List cells in a 2D grid that belong in a sector / portion of a circle

Question

Are there any algorithms to find out which cells in a 2D grid lie inside/is part of a slice of a circle - a pie slice shaped region?

Essentially, as per image below, I need to list out all the green cell coordinates.

At the moment, I am ray casting (using DDA based line interpolation) from the starting red cell, and sweeping across the area in with (arbitrarily chosen) small fixed angle increments, casting multiple rays; but this does not guarantee all cells will be covered.

Are there any approaches to this problem?

Answer 1

If it helps I have a similar image from helping someone with this problem a long time ago. It better illustrates the constraints (you can ignore the near plane since your example doesn't have one):

As you can see you're trying to figure out which corners are inside of the region. You have to make sure they're within the circle which is a distance check. Say our camera is at cameraPosition represented by an (x, y) vector then for each point you're checking just do:

if ((point.x - cameraPosition.x) * (point.x - cameraPosition.x) + (point.y - cameraPosition.y) * (point.y - cameraPosition.y) < radius * radius)

Then you need to figure out if the points are inside of the two lines (3 in my example image, but we'll just use the two long lines). To do this you can use a dot product test. Generate your two vector using (cos(angle), sin(angle)) or however best works for you. Then for the left and right ray find it's left hand normal. (y, -x) or (-y, x) depending on your coordinate system. Then for each point we'll take the dot product between the (point - cameraPosition) and the normal. This will tell us which side of the ray our point is on. If it's on the wrong side we can discard it.

normalLeftX = -sin(angle1)
normalLeftY = cos(angle1)
normalRightX = sin(angle2)
normalRightY = -cos(angle2)
pointRayX = point.x - cameraPosition.x;
pointRayY = point.y - cameraPosition.y;
if (pointRayX * normalLeftX + pointRayY * normalLeftY > 0 &&
    pointRayX * normalRightX + pointRayY * normalRightY > 0)

(You might have to flip the normals between (y, -x) and (-y, x) if I made a mistake).

Combining all 3 checks will test if the point is inside. When a point is inside that means all 4 adjacent tiles are inside. (I'll let someone else expand it to code if they want).

I will point out that this algorithm is very closely related to an optimal vector processing algorithm for triangle rasterization. It would be completely overkill but you can use it if you have to test large amounts of tiles.

https://software.intel.com/en-us/articles/rasterization-on-larrabee

Answer 2

Your best bet is looking around for "Roguelike Vision Algorithms." This result seems to have a goodly collection, discussing existing methods--including raycasting--and then suggesting the author's own method. His algorithm contains more code than I am willing to copy-paste to this answer, but involves treating cells as walls with beveled edges and using some manner of raycasting:

Whether or not you are interested in "shadow casting" (that is, if a cell inside the cone is prevents areas behind it from being "visible") will likely play a large part in determining which method suits your needs.