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 <string.h>
  16 #include <vector>
  17 #include <cmath>
  18
  19 #include "v2.h"
  20 #include "rect.h"
  21
  22
  23 #define RAND       femath::Rand
  24 #define RAND_N     femath::RandN
  25 #define RAND_2     (femath::Rand()&1)
  26 #define RAND_4     (femath::Rand()&3)
  27 #define RAND_8     (femath::Rand()&7)
  28 #define RAND_16    (femath::Rand()&15)
  29 #define RAND_32    (femath::Rand()&31)
  30 #define RAND_64    (femath::Rand()&63)
  31 #define RAND_128   (femath::Rand()&127)
  32 #define RAND_256   (femath::Rand()&255)
  33 #define RAND_GOOD  femath::RandGood
  34
  35
  36 struct __attribute__((__packed__)) PRNGSeed {
  37   union __attribute__((__packed__)) {
  38     uint8_t seed[sizeof(uint64_t)*2];
  39     struct __attribute__((__packed__)) {
  40       uint64_t state;
  41       uint64_t inc;
  42     };
  43   };
  44 };
  45
  46
  47 // *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
  48 // Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)
  49 struct PCG32 {
  50 private:
  51   PRNGSeed seed;
  52
  53 public:
  54   PCG32 (uint64_t astate, uint64_t ainc=1) { setSeed(astate, ainc); }
  55   PCG32 (const PRNGSeed aseed) { seed = aseed; }
  56
  57   inline void setSeed (uint64_t astate, uint64_t ainc=1) { seed.state = astate; seed.inc = ainc; }
  58   inline void setSeed (const PRNGSeed aseed) { seed = aseed; }
  59
  60   inline PRNGSeed getSeed () const { return seed; }
  61
  62   void rndseed ();
  63
  64   inline uint32_t rand32 () {
  65     uint64_t oldstate = this->seed.state;
  66     // advance internal state
  67     this->seed.state = oldstate*6364136223846793005ULL+(this->seed.inc|1);
  68     // calculate output function (XSH RR), uses old state for max ILP
  69     uint32_t xorshifted = ((oldstate>>18u)^oldstate)>>27u;
  70     uint32_t rot = oldstate>>59u;
  71     return (xorshifted>>rot)|(xorshifted<<((-rot)&31)); //k8: UB(?), but i don't care
  72   }
  73 };
  74
  75
  76 class outputfile;
  77 class inputfile;
  78 class TextInput;
  79 template <class type> struct fearray;
  80
  81
  82 class femath {
  83 public:
  84   static sLong Rand ();
  85   static void SetSeed (const PRNGSeed aseed);
  86   static void SetSeed (feuLong);
  87   static void RandSeed ();
  88   static sLong RandN (sLong N) { return (sLong)((double)N*Rand()/0x80000000); }
  89   static sLong RandGood (sLong N) { return (sLong)((double)N*Rand()/0x80000000); }
  90   static int WeightedRand (sLong *Possibility, sLong TotalPossibility);
  91   static int WeightedRand (const std::vector<sLong> &Possibility, sLong TotalPossibility);
  92   static double CalculateAngle (v2 Direction);
  93   static void CalculateEnvironmentRectangle (rect &Rect, const rect &MotherRect, v2 Origo, int Radius);
  94   static truth Clip (int &SourceX, int &SourceY, int &DestX, int &DestY, int &Width, int &Height,
  95     int XSize, int YSize, int DestXSize, int DestYSize);
  96   static void SaveSeed ();
  97   static void LoadSeed ();
  98   static sLong SumArray (const fearray<sLong> &Vector);
  99   static int LoopRoll (int ContinueChance, int Max);
 100   static void GenerateFractalMap (int **Map, int Side, int StartStep, int Randomness);
 101   static void SavePRNG (outputfile &SaveFile);
 102   static void LoadPRNG (inputfile &SaveFile);
 103
 104 protected:
 105   static PCG32 prng;
 106   static PRNGSeed savedSeed;
 107 };
 108
 109
 110 struct interval {
 111   sLong Randomize () const { return Min < Max ? Min + RAND() % (Max - Min + 1) : Min; }
 112   sLong Min;
 113   sLong Max;
 114 };
 115
 116
 117 struct region {
 118   v2 Randomize () const { return v2(X.Randomize(), Y.Randomize()); }
 119   interval X;
 120   interval Y;
 121 };
 122
 123
 124 void ReadData (interval &I, TextInput &SaveFile);
 125 void ReadData (region &R, TextInput &SaveFile);
 126
 127 outputfile &operator << (outputfile &SaveFile, const interval &I);
 128 inputfile &operator >> (inputfile &SaveFile, interval &I);
 129 outputfile &operator << (outputfile &SaveFile, const region &R);
 130 inputfile &operator >> (inputfile &SaveFile, region &R);
 131 outputfile &operator << (outputfile &SaveFile, const PRNGSeed &R);
 132 inputfile &operator >> (inputfile &SaveFile, PRNGSeed &R);
 133
 134
 135 template <class controller> class mapmath {
 136 public:
 137   static truth DoLine (int X1, int Y1, int X2, int Y2, int Flags=0);
 138   static truth DoLineOneDir (int X1, int Y1, int X2, int Y2, int Flags=0);
 139   static void DoArea ();
 140   static void DoQuadriArea (int, int, int, int, int);
 141 };
 142
 143
 144 template <class controller> inline truth mapmath<controller>::DoLine (int X1, int Y1, int X2, int Y2, int Flags) {
 145   truth res = DoLineOneDir(X1, Y1, X2, Y2, Flags);
 146   if (!res && (Flags&LINE_BOTH_DIRS) != 0) {
 147     if (Flags&SKIP_FIRST) Flags = (Flags&~SKIP_FIRST)|SKIP_LAST;
 148     res = DoLineOneDir(X2, Y2, X1, Y1, Flags);
 149   }
 150   return res;
 151 }
 152
 153 template <class controller> inline truth mapmath<controller>::DoLineOneDir (int X1, int Y1, int X2, int Y2, int Flags) {
 154   if (!(Flags & SKIP_FIRST)) controller::Handler(X1, Y1);
 155   cint DeltaX = abs(X2 - X1);
 156   cint DeltaY = abs(Y2 - Y1);
 157   cint DoubleDeltaX = DeltaX<<1;
 158   cint DoubleDeltaY = DeltaY<<1;
 159   cint XChange = X1<X2 ? 1 : -1;
 160   cint YChange = Y1<Y2 ? 1 : -1;
 161   int x = X1, y = Y1;
 162   if (DeltaX >= DeltaY) {
 163     int c = DeltaX;
 164     cint End = X2;
 165     while (x != End) {
 166       x += XChange;
 167       c += DoubleDeltaY;
 168       if (c >= DoubleDeltaX) {
 169         c -= DoubleDeltaX;
 170         y += YChange;
 171       }
 172       if ((Flags&SKIP_LAST) && x == X2 && y == Y2) break;
 173       if (!controller::Handler(x, y)) return (x == End && !(Flags & ALLOW_END_FAILURE));
 174     }
 175   } else {
 176     int c = DeltaY;
 177     cint End = Y2;
 178     while (y != End) {
 179       y += YChange;
 180       c += DoubleDeltaX;
 181       if (c >= DoubleDeltaY) {
 182         c -= DoubleDeltaY;
 183         x += XChange;
 184       }
 185       if ((Flags&SKIP_LAST) && x == X2 && y == Y2) break;
 186       if (!controller::Handler(x, y)) return (y == End && !(Flags & ALLOW_END_FAILURE));
 187     }
 188   }
 189   return true;
 190 }
 191
 192
 193 struct basequadricontroller {
 194   static cint OrigoDeltaX[4];
 195   static cint OrigoDeltaY[4];
 196   static int OrigoX, OrigoY;
 197   static int StartX, StartY;
 198   static int XSize, YSize;
 199   static int RadiusSquare;
 200   static truth SectorCompletelyClear;
 201 };
 202
 203
 204 template <class controller> struct quadricontroller : public basequadricontroller {
 205   static truth Handler (int, int);
 206   static int GetStartX (int I) {
 207     SectorCompletelyClear = true;
 208     return StartX = (OrigoX<<1)+OrigoDeltaX[I];
 209   }
 210   static int GetStartY (int I) {
 211     return StartY = (OrigoY<<1)+OrigoDeltaY[I];
 212   }
 213 };
 214
 215
 216 template <class controller> truth quadricontroller<controller>::Handler (int x, int y) {
 217   cint HalfX = x>>1, HalfY = y>>1;
 218   if (HalfX >= 0 && HalfY >= 0 && HalfX < XSize && HalfY < YSize) {
 219     feuLong& SquareTick = controller::GetTickReference(HalfX, HalfY);
 220     cint SquarePartIndex = (x&1)+((y&1)<<1);
 221     culong Mask = SquarePartTickMask[SquarePartIndex];
 222     if ((SquareTick & Mask) < controller::ShiftedTick[SquarePartIndex]) {
 223       SquareTick = (SquareTick & ~Mask) | controller::ShiftedQuadriTick[SquarePartIndex];
 224       int DeltaX = OrigoX-HalfX, DeltaY = OrigoY-HalfY;
 225       if (DeltaX*DeltaX+DeltaY*DeltaY <= RadiusSquare) {
 226         if (SectorCompletelyClear) {
 227           if (controller::Handler(x, y)) return true;
 228           SectorCompletelyClear = false;
 229         } else {
 230           return mapmath<controller>::DoLine(StartX, StartY, x, y, SKIP_FIRST|ALLOW_END_FAILURE|LINE_BOTH_DIRS);
 231         }
 232       }
 233     }
 234   }
 235   return false;
 236 }
 237
 238
 239 const cint ChangeXArray[4][3] = {
 240   { -1,  0, -1 },
 241   {  0,  1,  1 },
 242   { -1, -1,  0 },
 243   {  1,  0,  1 }
 244 };
 245 const cint ChangeYArray[4][3] = {
 246   { -1, -1,  0 },
 247   { -1, -1,  0 },
 248   {  0,  1,  1 },
 249   {  0,  1,  1 }
 250 };
 251
 252
 253 template <class controller> inline void mapmath<controller>::DoArea () {
 254   int Buffer[2][2048];
 255   int *OldStack = Buffer[0];
 256   int *NewStack = Buffer[1];
 257   for (int c1 = 0; c1 < 4; ++c1) {
 258     cint *ChangeX = ChangeXArray[c1], *ChangeY = ChangeYArray[c1];
 259     int OldStackPos = 0, NewStackPos = 0;
 260     int StartX = controller::GetStartX(c1);
 261     int StartY = controller::GetStartY(c1);
 262     for (int c2 = 0; c2 < 3; ++c2) {
 263       OldStack[OldStackPos] = StartX+ChangeX[c2];
 264       OldStack[OldStackPos + 1] = StartY+ChangeY[c2];
 265       OldStackPos += 2;
 266     }
 267     while (OldStackPos) {
 268       while (OldStackPos) {
 269         OldStackPos -= 2;
 270         cint X = OldStack[OldStackPos], Y = OldStack[OldStackPos+1];
 271         if (controller::Handler(X, Y)) {
 272           for (int c2 = 0; c2 < 3; ++c2) {
 273             NewStack[NewStackPos] = X+ChangeX[c2];
 274             NewStack[NewStackPos+1] = Y+ChangeY[c2];
 275             NewStackPos += 2;
 276           }
 277         }
 278       }
 279       OldStackPos = NewStackPos;
 280       NewStackPos = 0;
 281       int *T = OldStack;
 282       OldStack = NewStack;
 283       NewStack = T;
 284     }
 285   }
 286 }
 287
 288
 289 template <class controller> inline void mapmath<controller>::DoQuadriArea (int OrigoX, int OrigoY, int RadiusSquare, int XSize, int YSize) {
 290   basequadricontroller::OrigoX = OrigoX;
 291   basequadricontroller::OrigoY = OrigoY;
 292   basequadricontroller::RadiusSquare = RadiusSquare;
 293   basequadricontroller::XSize = XSize;
 294   basequadricontroller::YSize = YSize;
 295   for (int c = 0; c < 4; ++c) {
 296     controller::Handler((OrigoX<<1)+basequadricontroller::OrigoDeltaX[c], (OrigoY<<1)+basequadricontroller::OrigoDeltaY[c]);
 297   }
 298   mapmath<quadricontroller<controller> >::DoArea();
 299 }
 300
 301
 302 /* Chance for n < Max to be returned is (1-CC)*CC^n, for n == Max chance is CC^n. */
 303 inline int femath::LoopRoll (int ContinueChance, int Max) {
 304   int R;
 305   for (R = 0; RAND_N(100) < ContinueChance && R < Max; ++R);
 306   return R;
 307 }
 308
 309
 310 template <class type, class predicate> type *&ListFind (type *&Start, predicate Predicate) {
 311   type **E;
 312   for(E = &Start; *E && !Predicate(*E); E = &(*E)->Next);
 313   return *E;
 314 }
 315
 316
 317 template <class type> struct pointercomparer {
 318   pointercomparer (const type *Element) : Element(Element) { }
 319   truth operator()(const type *E) const { return E == Element; }
 320   const type *Element;
 321 };
 322
 323
 324 #endif