# HG changeset patch
# User saiam
# Date 1228049890 0
# Node ID 73109c5652d388bf27ee602d918f592fc5683413
# Parent  b264b39224e50ca73f457496466107d8fcb29312
Implementend Terrain::collides for line. It still hasn't a way to return collision point. Has not been tested.

diff -r b264b39224e5 -r 73109c5652d3 src/proto2/Terrain.cc
--- 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) {