nel/src/misc/grid_traversal.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17
  18 #include "stdmisc.h"
  19 #include "nel/misc/grid_traversal.h"
  20 #include "nel/misc/vector_2f.h"
  21
  22 #ifdef DEBUG_NEW
  23         #define new DEBUG_NEW
  24 #endif
  25
  26 namespace NLMISC
  27 {
  28
  29 // ********************************************************************************************************************************
  30 void    CGridTraversal::startTraverse(const NLMISC::CVector2f &start, sint &nextX, sint &nextY)
  31 {
  32         nextX = (sint) floorf(start.x);
  33         nextY = (sint) floorf(start.y);
  34 }
  35
  36 // ********************************************************************************************************************************
  37 bool    CGridTraversal::traverse(const NLMISC::CVector2f &start, const NLMISC::CVector2f &dir, sint &x, sint &y)
  38 {
  39         if (dir.x > 0.f)
  40         {
  41                 float lambdaX = (x + 1.f - start.x) / dir.x;
  42                 if (dir.y > 0.f)
  43                 {
  44                         float lambdaY = (y + 1 - start.y) / dir.y;
  45                         if (lambdaX < lambdaY)
  46                         {
  47                                 if (lambdaX > 1.f) return false;
  48                                 ++ x;
  49                                 return true;
  50                         }
  51                         else
  52                         {
  53                                 if (lambdaY > 1.f) return false;
  54                                 ++ y;
  55                                 return true;
  56                         }
  57                 }
  58                 else if (dir.y < 0.f)
  59                 {
  60                         float lambdaY = (y - start.y) / dir.y;
  61                         if (lambdaX < lambdaY)
  62                         {
  63                                 if (lambdaX > 1.f) return false;
  64                                 ++ x;
  65                                 return true;
  66                         }
  67                         else
  68                         {
  69                                 if (lambdaY > 1.f) return false;
  70                                 -- y;
  71                                 return true;
  72                         }
  73                 }
  74                 ++ x;
  75                 return x <= (sint) floorf(start.x + dir.x);
  76         }
  77         else if (dir.x < 0.f)
  78         {
  79                 float lambdaX = (x - start.x) / dir.x;
  80                 if (dir.y > 0.f)
  81                 {
  82                         float lambdaY = (y + 1.f - start.y) / dir.y;
  83                         if (lambdaX < lambdaY)
  84                         {
  85                                 if (lambdaX > 1.f) return false;
  86                                 -- x;
  87                                 return true;
  88                         }
  89                         else
  90                         {
  91                                 if (lambdaY > 1.f) return false;
  92                                 ++ y;
  93                                 return true;
  94                         }
  95                 }
  96                 else if (dir.y < 0.f)
  97                 {
  98                         float lambdaY = (y - start.y) / dir.y;
  99                         if (lambdaX < lambdaY)
 100                         {
 101                                 if (lambdaX > 1.f) return false;
 102                                 -- x;
 103                                 return true;
 104                         }
 105                         else
 106                         {
 107                                 if (lambdaY > 1.f) return false;
 108                                 -- y;
 109                                 return true;
 110                         }
 111                 }
 112                 -- x;
 113                 return x >= (sint) floorf(start.x + dir.x);
 114         }
 115
 116         if (dir.y > 0.f)
 117         {
 118                 ++ y;
 119                 return y <= (sint) floorf(start.y + dir.y);
 120
 121         }
 122         else if (dir.y < 0.f)
 123         {
 124                 -- y;
 125                 return y >= (sint) floorf(start.y + dir.y);
 126         }
 127         return false;
 128 }
 129
 130 } // NLMISC