src/felib/femath.h

   1 /*
   2  *
   3  *  Iter Vehemens ad Necem (IVAN)
   4  *  Copyright (C) Timo Kiviluoto
   5  *  Released under the GNU General
   6  *  Public License
   7  *
   8  *  See LICENSING which should be included
   9  *  along with this file for more details
  10  *
  11  */
  12 #ifndef __FELIB_FEMATH_H__
  13 #define __FELIB_FEMATH_H__
  14
  15 #include <vector>
  16 #include <cmath>
  17
  18 #include "v2.h"
  19 #include "rect.h"
  20
  21
  22 #define RAND       femath::Rand
  23 #define RAND_N     femath::RandN
  24 #define RAND_2     (femath::Rand() & 1)
  25 #define RAND_4     (femath::Rand() & 3)
  26 #define RAND_8     (femath::Rand() & 7)
  27 #define RAND_16    (femath::Rand() & 15)
  28 #define RAND_32    (femath::Rand() & 31)
  29 #define RAND_64    (femath::Rand() & 63)
  30 #define RAND_128   (femath::Rand() & 127)
  31 #define RAND_256   (femath::Rand() & 255)
  32 #define RAND_GOOD  femath::RandGood
  33
  34
  35 class outputfile;
  36 class inputfile;
  37 template <class type> struct fearray;
  38
  39
  40 class femath {
  41 public:
  42   static sLong Rand ();
  43   static void SetSeed (feuLong);
  44   static sLong RandN (sLong N) { return sLong(double(N)*Rand()/0x80000000); }
  45   static sLong RandGood (sLong N) { return sLong(double(N)*Rand()/0x80000000); }
  46   static int WeightedRand (sLong *Possibility, sLong TotalPossibility);
  47   static int WeightedRand (const std::vector<sLong> &Possibility, sLong TotalPossibility);
  48   static double CalculateAngle (v2 Direction);
  49   static void CalculateEnvironmentRectangle (rect &Rect, const rect &MotherRect, v2 Origo, int Radius);
  50   static truth Clip (int &SourceX, int &SourceY, int &DestX, int &DestY, int &Width, int &Height,
  51     int XSize, int YSize, int DestXSize, int DestYSize);
  52   static void SaveSeed ();
  53   static void LoadSeed ();
  54   static sLong SumArray (const fearray<sLong> &Vector);
  55   static int LoopRoll (int ContinueChance, int Max);
  56   static void GenerateFractalMap (int **Map, int Side, int StartStep, int Randomness);
  57
  58 protected:
  59   static feuLong mt[];
  60   static sLong mti;
  61   static feuLong mtb[];
  62   static sLong mtib;
  63 };
  64
  65
  66 struct interval {
  67   sLong Randomize () const { return Min < Max ? Min + RAND() % (Max - Min + 1) : Min; }
  68   sLong Min;
  69   sLong Max;
  70 };
  71
  72
  73 struct region {
  74   v2 Randomize () const { return v2(X.Randomize(), Y.Randomize()); }
  75   interval X;
  76   interval Y;
  77 };
  78
  79
  80 void ReadData (interval &I, inputfile &SaveFile);
  81 void ReadData (region &R, inputfile &SaveFile);
  82
  83 outputfile &operator << (outputfile &SaveFile, const interval &I);
  84 inputfile &operator >> (inputfile &SaveFile, interval &I);
  85 outputfile &operator << (outputfile &SaveFile, const region &R);
  86 inputfile &operator >> (inputfile &SaveFile, region &R);
  87
  88
  89 template <class controller> class mapmath {
  90 public:
  91   static truth DoLine (int X1, int Y1, int X2, int Y2, int Flags=0);
  92   static void DoArea ();
  93   static void DoQuadriArea (int, int, int, int, int);
  94 };
  95
  96
  97 template <class controller> inline truth mapmath<controller>::DoLine (int X1, int Y1, int X2, int Y2, int Flags) {
  98   if (!(Flags & SKIP_FIRST)) controller::Handler(X1, Y1);
  99   cint DeltaX = abs(X2 - X1);
 100   cint DeltaY = abs(Y2 - Y1);
 101   cint DoubleDeltaX = DeltaX<<1;
 102   cint DoubleDeltaY = DeltaY<<1;
 103   cint XChange = X1<X2 ? 1 : -1;
 104   cint YChange = Y1<Y2 ? 1 : -1;
 105   int x = X1, y = Y1;
 106   if (DeltaX >= DeltaY) {
 107     int c = DeltaX;
 108     cint End = X2;
 109     while (x != End) {
 110       x += XChange;
 111       c += DoubleDeltaY;
 112       if (c >= DoubleDeltaX) {
 113         c -= DoubleDeltaX;
 114         y += YChange;
 115       }
 116       if (!controller::Handler(x, y)) return x == End && !(Flags & ALLOW_END_FAILURE);
 117     }
 118   } else {
 119     int c = DeltaY;
 120     cint End = Y2;
 121     while (y != End) {
 122       y += YChange;
 123       c += DoubleDeltaX;
 124       if (c >= DoubleDeltaY) {
 125         c -= DoubleDeltaY;
 126         x += XChange;
 127       }
 128       if (!controller::Handler(x, y)) return y == End && !(Flags & ALLOW_END_FAILURE);
 129     }
 130   }
 131   return true;
 132 }
 133
 134
 135 struct basequadricontroller {
 136   static cint OrigoDeltaX[4];
 137   static cint OrigoDeltaY[4];
 138   static int OrigoX, OrigoY;
 139   static int StartX, StartY;
 140   static int XSize, YSize;
 141   static int RadiusSquare;
 142   static truth SectorCompletelyClear;
 143 };
 144
 145
 146 template <class controller> struct quadricontroller : public basequadricontroller {
 147   static truth Handler (int, int);
 148   static int GetStartX (int I) {
 149     SectorCompletelyClear = true;
 150     return StartX = (OrigoX<<1)+OrigoDeltaX[I];
 151   }
 152   static int GetStartY (int I) {
 153     return StartY = (OrigoY<<1)+OrigoDeltaY[I];
 154   }
 155 };
 156
 157
 158 template <class controller> truth quadricontroller<controller>::Handler (int x, int y) {
 159   cint HalfX = x>>1, HalfY = y>>1;
 160   if (HalfX >= 0 && HalfY >= 0 && HalfX < XSize && HalfY < YSize) {
 161     feuLong& SquareTick = controller::GetTickReference(HalfX, HalfY);
 162     cint SquarePartIndex = (x&1)+((y&1)<<1);
 163     culong Mask = SquarePartTickMask[SquarePartIndex];
 164     if ((SquareTick & Mask) < controller::ShiftedTick[SquarePartIndex]) {
 165       SquareTick = (SquareTick & ~Mask) | controller::ShiftedQuadriTick[SquarePartIndex];
 166       int DeltaX = OrigoX-HalfX, DeltaY = OrigoY-HalfY;
 167       if (DeltaX*DeltaX+DeltaY*DeltaY <= RadiusSquare) {
 168         if (SectorCompletelyClear) {
 169           if (controller::Handler(x, y)) return true;
 170           SectorCompletelyClear = false;
 171         } else {
 172           return mapmath<controller>::DoLine(StartX, StartY, x, y, SKIP_FIRST|ALLOW_END_FAILURE);
 173         }
 174       }
 175     }
 176   }
 177   return false;
 178 }
 179
 180
 181 const cint ChangeXArray[4][3] = {
 182   { -1,  0, -1 },
 183   {  0,  1,  1 },
 184   { -1, -1,  0 },
 185   {  1,  0,  1 }
 186 };
 187 const cint ChangeYArray[4][3] = {
 188   { -1, -1,  0 },
 189   { -1, -1,  0 },
 190   {  0,  1,  1 },
 191   {  0,  1,  1 }
 192 };
 193
 194
 195 template <class controller> inline void mapmath<controller>::DoArea () {
 196   int Buffer[2][2048];
 197   int *OldStack = Buffer[0];
 198   int *NewStack = Buffer[1];
 199   for (int c1 = 0; c1 < 4; ++c1) {
 200     cint *ChangeX = ChangeXArray[c1], *ChangeY = ChangeYArray[c1];
 201     int OldStackPos = 0, NewStackPos = 0;
 202     int StartX = controller::GetStartX(c1);
 203     int StartY = controller::GetStartY(c1);
 204     for (int c2 = 0; c2 < 3; ++c2) {
 205       OldStack[OldStackPos] = StartX+ChangeX[c2];
 206       OldStack[OldStackPos + 1] = StartY+ChangeY[c2];
 207       OldStackPos += 2;
 208     }
 209     while (OldStackPos) {
 210       while (OldStackPos) {
 211         OldStackPos -= 2;
 212         cint X = OldStack[OldStackPos], Y = OldStack[OldStackPos+1];
 213         if (controller::Handler(X, Y)) {
 214           for (int c2 = 0; c2 < 3; ++c2) {
 215             NewStack[NewStackPos] = X+ChangeX[c2];
 216             NewStack[NewStackPos+1] = Y+ChangeY[c2];
 217             NewStackPos += 2;
 218           }
 219         }
 220       }
 221       OldStackPos = NewStackPos;
 222       NewStackPos = 0;
 223       int *T = OldStack;
 224       OldStack = NewStack;
 225       NewStack = T;
 226     }
 227   }
 228 }
 229
 230
 231 template <class controller> inline void mapmath<controller>::DoQuadriArea (int OrigoX, int OrigoY, int RadiusSquare, int XSize, int YSize) {
 232   basequadricontroller::OrigoX = OrigoX;
 233   basequadricontroller::OrigoY = OrigoY;
 234   basequadricontroller::RadiusSquare = RadiusSquare;
 235   basequadricontroller::XSize = XSize;
 236   basequadricontroller::YSize = YSize;
 237   for (int c = 0; c < 4; ++c) {
 238     controller::Handler((OrigoX<<1)+basequadricontroller::OrigoDeltaX[c], (OrigoY<<1)+basequadricontroller::OrigoDeltaY[c]);
 239   }
 240   mapmath<quadricontroller<controller> >::DoArea();
 241 }
 242
 243
 244 /* Chance for n < Max to be returned is (1-CC)*CC^n, for n == Max chance is CC^n. */
 245 inline int femath::LoopRoll (int ContinueChance, int Max) {
 246   int R;
 247   for (R = 0; RAND_N(100) < ContinueChance && R < Max; ++R);
 248   return R;
 249 }
 250
 251
 252 template <class type, class predicate> type *&ListFind (type *&Start, predicate Predicate) {
 253   type **E;
 254   for(E = &Start; *E && !Predicate(*E); E = &(*E)->Next);
 255   return *E;
 256 }
 257
 258
 259 template <class type> struct pointercomparer {
 260   pointercomparer (const type *Element) : Element(Element) { }
 261   truth operator()(const type *E) const { return E == Element; }
 262   const type *Element;
 263 };
 264
 265
 266 #endif