CODEWITHSUNDEEP
actionscript-3mathgridtiles
Marty
Marty

Reputation: 39466

How do I select a set of grid cells along a given angle quickly?

I have set up a grid class that contains theoretical cells.

I have a method collectCells() which accepts a starting point, radians and distance as arguments. I want this method to return an Array containing all the cells that are along a given angle and that are within the specified distance from the starting point, e.g.

enter image description here

The easiest way for me to do this is just loop through all the pixels in the given direction and pick cells up as I go, something like:

for(var i:int = 0; i<distance; i++)
{
    startPoint.x += Math.cos(radians);
    startPoint.y += Math.sin(radians);

    if( start point falls within uncollected cell) collect cell;
}

This is obviously really poor, as the loop will be as long as the distance I specify - extremely slow.

I tried something different, creating a nextCell() method which accepts the last collected cell and radians. The method threw a point 25 pixels in the direction specified by radians, collected the resulting cell and then started over from that cell for a given amount of cells.

I didn't really think about this approach clearly enough, and once done realized that I had a problem, being that the actual path I'm testing gets broken each time the next cell is sought, e.g.

enter image description here

Where the green dotted line is the desired path, and the blue lines are the paths that make up each nextCell() call because the check is made from the centre of each cell.

What is the correct way to efficiently collect the cells in a given direction over a specified distance (pixels)?

Upvotes: 2

Views: 279

Answers (1)

Valentin Simonov
Valentin Simonov

Reputation: 1768

Or you could use Bresenham's line drawing algorithm. Because literally you are trying to draw a pixel width line but with huge pixels.

Upvotes: 2

Related Questions