Implementend Terrain::collides for line. It still hasn't a way to return collision point. Has not been tested.
--- a/src/proto2/Terrain.cc Sun Nov 30 00:36:24 2008 +0000
+++ b/src/proto2/Terrain.cc Sun Nov 30 12:58:10 2008 +0000
@@ -19,12 +19,48 @@
}
bool Terrain::collides(const Vector &begin, const Vector &end) const {
- // TODO: Implement. Bresenhams line algorithm could be usefull
// TODO: Maybe we should have another function prototype that also
// returns the point where we collided.
- // 1. Go trough every point in line in order and check if we collide
+ // We'll use Bresenhams line algorithm to go trough all the
+ // "pixels" of the line.
+ Vector b = getPixelLocation(begin);
+ Vector e = getPixelLocation(end);
+ bool steep = (abs(e.y - b.y) > abs(e.x - b.x)); // k > 1
+ if (steep) { // Line is steep -> swap x and y coordinates
+ std::swap(b.x, b.y);
+ std::swap(e.x, e.y);
+ }
+ if (b.x > e.x) { // Line goes down -> make it go up
+ std::swap(b, e);
+ }
+ uint16_t dx = e.x - b.x;
+ uint16_t dy = abs(e.y - b.y);
+ uint16_t err = dx/2;
+ uint16_t ystep;
+ uint16_t y = b.y;
+ // Is the line ascending or descending
+ if (b.y < e.y) ystep = 1;
+ else ystep = -1;
+ // Go trough the line
+ for (uint16_t x = b.x; x <= e.x; x++) {
+ if (steep) { // X and Y coordinates must be switched if steep
+ if (terrain[y][x] != EMPTY) { // Collision!
+ return true;
+ }
+ } else {
+ if (terrain[x][y] != EMPTY) { // Collision!
+ return true;
+ }
+ }
+ err = err - dy;
+ if (err < 0) { // Check if we want to make an ystep
+ y = y + ystep;
+ err = err + dx;
+ }
+ }
+ return false; // No Collision
}
void Terrain::removeGround(const Vector &pos, const float r) {