Sign in to follow this  
deakster

2D Line segment coverage over a grid

Recommended Posts

In a 2d grid where each cell is 1 unit by 1 unit, how could I find the cells that a line segment overlaps? If anyone could direct me to some articles (or a brief explanation here), it would be much appreciated.

Share this post


Link to post
Share on other sites
Depending on exactly what you're after Bresenham's algorithm may do what you want. Although since it's concerned with line drawing it won't nessessarity give you all the cells that overlap - if you need something more precise then you might be able to adapt Wu lines or just break it down into lots of line-rectangle tests.

Share this post


Link to post
Share on other sites
(Warning: I am not great at math, nor am I an expert in programming)

If your line is 1 unit wide, you can just use a line algorithm, such as the one shown on this page, and instead of drawing pixels, whatever the algorithm 'plots' you know is the next cell that the line overlaps, and you can then calculate whatever you are wanting to calculate. (For example, check if a enemy unit is in the way, if and damage it)

For example, in psuedocode:

function CheckCell(int col, int row)
{
//Check if a enemy is on this cell.
if(EnemyIsOnCell(col, row) == true)
{
//Damage the enemy (or whatever).
DamageEnemy(GetEnemyOnCell(col, row), GetDamageAmount())

//Return true to stop checking the cells. For example, if you want
//only the first enemy in a line to be hit. If you don't want the,
//line to stop, make this function return void instead of a bool.
return true
}

return false
}

function CheckCellsInLine(int fromX, fromY, toX, toY)
{
Line line;

//Setup the starting and ending points.
line.Start(fromX, fromY)
line.End(toX, toY)

//While we haven't reached the end of the line, traverse it, and
//pass each point to our CheckCell() function above.
while(!line.EndOfLine())
{
//Move along the line to the next point.
line.Step()

//Get the point the line is currently over.
int cellX, cellY
line.GetPoint(&cellX, &cellY)

//Check the cell (see func above).
if(CheckCell(cellX, cellY) == true)
break //If CheckCell wants to stop the line, let it do so.
}
}


If you are wanting to know how to draw a line in the first place, you can look over, use, or do whatever you want to this code: (Code from my current WIP game, had alot of help from some GameDev.net users when trying to get the line code working)

//Line.h
#ifndef LINE_H
#define LINE_H

struct LinePoint
{
int x;
int y;
};

LinePoint NewLinePoint(int x, int y);

typedef bool (LineFunctionPointer)(LinePoint *point);

class Line
{
private:
//Where the line starts.
LinePoint startingPoint;
//Where the line ends.
LinePoint endingPoint;
//The amount to increment the current position by, on each 'step'.
LinePoint deltaIncrement;
//Used to offset the line when calculating the next point.
LinePoint offsetPoint;
//The current position along the line.
LinePoint currentPoint;

//Used by the Step() function.
int error;

void _ConfigurePoints();

public:
Line::Line();
Line::Line(LinePoint start, LinePoint end);
Line::~Line();

//Starts a new line, with a new starting and ending point.
void SetPoints(LinePoint start, LinePoint end);
//Steps along the line 'x' times, where x is 'steps'. Returns false if it reaches the end
//of the line. 'point' points to where the line stopped.
bool Step(LinePoint *point, int steps = 1);
//Returns the point where the line is currently at.
LinePoint GetLastStep();
//Resets the point where the line is currently, back to the starting point.
void Reset();
//Switches the direction the line traverses. (From foreward to backward, or vice versa)
//You may want to call Reset() afterward, to reset the current step, depending on your needs.
//This actually just swaps the ending and starting points.
void Reverse();

//Used to loop through the entire line at one time, calling the callback function on each step.
//If the callback returns true, the function will end.
void Traverse(LineFunctionPointer *callback);
//Used to loop through the line backward, calling the callback function on each step.
//If the callback returns true, the function will end.
void ReverseTraverse(LineFunctionPointer *callback);
};

#endif /* LINE_H */

//Line.cpp
#include "Line.h"

#define SWAP(x,y) { temp = x; x = y; y = temp; }

LinePoint NewLinePoint(int x, int y)
{
LinePoint newPoint;
newPoint.x = x;
newPoint.y = y;
return newPoint;
}

int abs(int value)
{
if(value > 0)
return value;
else
return -value;
}

/////////////////////////////////////////////////////////////////////////////////////////////

Line::Line()
{
startingPoint.x = 0; startingPoint.y = 0;
endingPoint.x = 0; endingPoint.y = 0;
deltaIncrement.x = 0; deltaIncrement.y = 0;
offsetPoint.x = 0; offsetPoint.y = 0;
currentPoint.x = 0; currentPoint.y = 0;
error = 0;
}

Line::Line(LinePoint start, LinePoint end)
{
this->SetPoints(start, end);
}

Line::~Line()
{

}

//Starts a new line, with a new starting and ending point.
void Line::SetPoints(LinePoint start, LinePoint end)
{
startingPoint = start;
endingPoint = end;

currentPoint = start;

deltaIncrement.x = 0; deltaIncrement.y = 0;
offsetPoint.x = 0; offsetPoint.y = 0;

this->_ConfigurePoints();
}

//Steps along the line 'x' times, where x is 'steps'. Returns false if it reaches the end
//of the line. 'point' points to where the line stopped.
bool Line::Step(LinePoint *point, int steps)
{
if(point)
*point = currentPoint;

for(int i = 0; i < steps; i++)
{
if(deltaIncrement.x > deltaIncrement.y)
{
if(currentPoint.x != endingPoint.x)
{
error -= deltaIncrement.y;

if(error < 0)
{
currentPoint.y += offsetPoint.y;
error += deltaIncrement.x;
}

currentPoint.x += offsetPoint.x;
}
else
return false;
}
else
{
if(currentPoint.y != endingPoint.y)
{
error -= deltaIncrement.x;

if(error < 0)
{
currentPoint.x += offsetPoint.x;
error += deltaIncrement.y;
}

currentPoint.y += offsetPoint.y;
}
else
return false;
}
}

return true;
}

//Returns the point where the line is currently at.
LinePoint Line::GetLastStep()
{
return currentPoint;
}

//Resets the point where the line is currently, back to the starting point.
void Line::Reset()
{
currentPoint = startingPoint;
}

//Switches the direction the line traverses. (From foreward to backward, or vice versa)
//You may want to call Reset() afterward, to reset the current step, depending on your needs.
//This actually just swaps the ending and starting points.
void Line::Reverse()
{
LinePoint tempPoint = startingPoint;
startingPoint = endingPoint;
endingPoint = tempPoint;

this->_ConfigurePoints();
}

//Used to quickly loop through the entire line at one time, calling the callback function on each step.
void Line::Traverse(LineFunctionPointer *callback)
{
if(!callback)
return;

LinePoint currentPoint = startingPoint;

if((*callback)(&currentPoint) == true)
return;

if(deltaIncrement.x > deltaIncrement.y)
{
int error = deltaIncrement.x / 2;

while(currentPoint.x != endingPoint.x)
{
error -= deltaIncrement.y;

if(error < 0)
{
currentPoint.y += offsetPoint.y;
error += deltaIncrement.x;
}

currentPoint.x += offsetPoint.x;

if((*callback)(&currentPoint) == true)
return;
}
}
else
{
int error = deltaIncrement.y / 2;

while(currentPoint.y != endingPoint.y)
{
error -= deltaIncrement.x;

if(error < 0)
{
currentPoint.x += offsetPoint.x;
error += deltaIncrement.y;
}

currentPoint.y += offsetPoint.y;

if((*callback)(&currentPoint) == true)
return;
}
}
}

//Used to loop through the line backward, calling the callback function on each step.
void Line::ReverseTraverse(LineFunctionPointer *callback)
{
this->Reverse();
this->Traverse(callback);
this->Reverse();
}

void Line::_ConfigurePoints()
{
deltaIncrement.x = abs(endingPoint.x - startingPoint.x);
deltaIncrement.y = abs(endingPoint.y - startingPoint.y);

if(startingPoint.x > endingPoint.x)
offsetPoint.x = -1;
else
offsetPoint.x = 1;

if(startingPoint.y > endingPoint.y)
offsetPoint.y = -1;
else
offsetPoint.y = 1;

if(deltaIncrement.x > deltaIncrement.y)
error = deltaIncrement.x / 2;
else
error = deltaIncrement.y / 2;
}

Share this post


Link to post
Share on other sites
Thanks guys, it is the 2d version of 3ddda I'm looking for. Note, I am not trying to draw a line, the thickness of the line is 0. I am trying to determine which cells a line of thickness 0 overlaps.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this