• Create Account

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

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

3 replies to this topic

### #1ferrous  Members   -  Reputation: 611

Like
0Likes
Like

Posted 03 December 2013 - 06:43 PM

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.

### #2Paradigm Shifter  Crossbones+   -  Reputation: 4748

Like
1Likes
Like

Posted 03 December 2013 - 11:19 PM

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, 04 December 2013 - 12:10 AM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

### #3ferrous  Members   -  Reputation: 611

Like
0Likes
Like

Posted 04 December 2013 - 12:45 AM

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.

### #4Paradigm Shifter  Crossbones+   -  Reputation: 4748

Like
0Likes
Like

Posted 04 December 2013 - 12:50 AM

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, 04 December 2013 - 12:52 AM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS