# Given an arc of radius X, what tiles does it pass over? (2d)

This topic is 2143 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

So I was thinking about this for a pathfinding problem, where I have something traveling along an arc of a circle (centerPt, start angle, end angle, clockwise/CCW) and I have a grid underneath that I use for pathfinding.

Now the brute force way is to obviously just sample the arc at a certain granularity, and find out which tile each sampled point was in/on.

But I was wondering if there was any easier\quicker way to to solve the problem.  A bounding box won't work, as it will pick up tiles\squares that aren't actually on the arc.

##### Share on other sites

Assuming the circle is centred on a tile, it's the same algorithm for drawing a circle using square pixels, http://en.wikipedia.org/wiki/Midpoint_circle_algorithm , but the pixels are actually your tiles.

Read that article especially the section "drawing incomplete octants".

EDIT: There is also Wu's algorithm for antialiased circles, if you want the circle to be slightly thicker than 1 tile.

Edited by Paradigm Shifter

##### Share on other sites

Ah, interesting, I actually recall doing that algorithm for drawing a circle back at school in the olden days.  It looks like it would obviously miss tiles though:

But Wu's algorithm sounds like it might be what I'm looking for, with the bonus that it has variations for plotting thickness, which could come in handy for when I am dealing with a wider object traveling on an arc.

##### Share on other sites

Yeah check out Wu's circle drawing algorithm, I couldn't find it on wikipedia (it is mentioned on there though) but there is sample code on the internet. You can ignore the calculation for the shade of the pixel if you just want tile coverage.

Edited by Paradigm Shifter

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 16
• 11
• 9
• 24
• 50