Jump to content
  • Advertisement
Sign in to follow this  
ferrous

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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:

320px-Bresenham_circle.svg.png

 

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 this post


Link to post
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!