Bresenham's line algorithm

Advertisemen

For the game I'm working on, I'm using a very inefficient algorithm at one point, so slow that in fact I spent a day learning the Boost Thread library in order to make it multithread. And even then it was still slow.

It doesn't matter that it's slow (not fast paced gameplay) but it still takes a couple of second in Debug mode. A couple of seconds that could be sped up, low and behold I stumbled across the required algorithm (very, very lucky)

Bresenham's Line Algorithm

Currently I've just demoed up a small console program to get an understanding of how the algorithm works:

Code (ninja style - no comments!):

#include <iostream>

#include <string>

#include <vector>

#include <ctime>

using namespace std;

struct line

{

       vector<pair<int,int>> Pos;

};

class Map

{

public:

       Map(int Y, int X) : YSize(Y), XSize(X)

       {

              if (X < 3 || Y < 3)

              {

                     cerr << "XSize and YSize must be at least 3" << endl;

                     return;

              }

              //Create borders

              for (int y = 0; y < Y; y++)

              {

                     string Row;

                     for (int x = 0; x < X; x++)

                           if (x == 0 || y == 0 || x == X-1 || y == Y-1)

                                  Row.push_back('#');

                           else

                                  Row.push_back(' ');

                     Tiles.push_back(Row);

              }

       }

       void Print()

       {

              for (int y = 0; y < YSize; y++)

                     cout << Tiles[y] << endl;

       }

lass="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0cm; mso-layout-grid-align: none; text-autospace: none;">       line GetLine( int x0, int y0, int x1, int y1 )

       {

              line Line;

              bool steep = abs(y1-y0) > abs(x1-x0);

              if (steep)

              {

                     swap(x0,y0);

                     swap(x1,y1);

              }

              if (x0 > x1)

              {

                     swap(x0,x1);

                     swap(y0,y1);

              }

              int dx = x1 - x0;

              int dy = abs(y1 - y0);

              int error = dx/2;

              int ystep;

              int y = y0;

              if (y0 < y1)

                     ystep = 1;

              else

                     ystep = -1;

              for (int x = x0; x < x1; x++)

              {

                     if (steep)

                           Line.Pos.push_back( pair<int,int>(y,x) );

                     else

                           Line.Pos.push_back( pair<int,int>(x,y) );

                    

                     error -= dy;

                     if (error < 0)

                     {

                           y += ystep;

                           error += dx;

                     }

              }

              return Line;

       }

       void AddLineToMap(const line& l)

       {

              for (int i = 0; i < l.Pos.size(); i++)

              {

                     const int *x = &l.Pos[i].first;

                     const int *y = &l.Pos[i].second;

                    

                     Tiles[*y][*x] = '*';

              }

       }

       int YSize;

       int XSize;

       vector<string> Tiles;

};

int main()

{

       srand(time(0));

       Map map(31, 31);

       map.Print();

       cout << "***" << endl;

       line myline = map.GetLine(5,5,6,27);

       map.AddLineToMap(myline);

      

       myline = map.GetLine(4,10,16,10);

       map.AddLineToMap(myline);

      

       myline = map.GetLine(25,5,25,29);

       map.AddLineToMap(myline);

      

       myline = map.GetLine(13,17,9,8);

       map.AddLineToMap(myline);

       map.Print();

       return 0;

}

Advertisemen