src/heightmap.h

   1 /*
   2 Minetest-c55
   3 Copyright (C) 2010 celeron55, Perttu Ahola <celeron55@gmail.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation; either version 2 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 /*
  21 (c) 2010 Perttu Ahola <celeron55@gmail.com>
  22 */
  23
  24 #ifndef HEIGHTMAP_HEADER
  25 #define HEIGHTMAP_HEADER
  26
  27 #include <iostream>
  28 #include <time.h>
  29 #include <sstream>
  30
  31 #include "debug.h"
  32 #include "common_irrlicht.h"
  33 #include "exceptions.h"
  34 #include "utility.h"
  35 #include "serialization.h"
  36
  37 #define GROUNDHEIGHT_NOTFOUND_SETVALUE (-10e6)
  38 #define GROUNDHEIGHT_VALID_MINVALUE    ( -9e6)
  39
  40 class Heightmappish
  41 {
  42 public:
  43         virtual f32 getGroundHeight(v2s16 p, bool generate=true) = 0;
  44         virtual void setGroundHeight(v2s16 p, f32 y, bool generate=true) = 0;
  45
  46         v2f32 getSlope(v2s16 p)
  47         {
  48                 f32 y0 = getGroundHeight(p, false);
  49
  50                 v2s16 dirs[] = {
  51                         v2s16(1,0),
  52                         v2s16(0,1),
  53                 };
  54
  55                 v2f32 fdirs[] = {
  56                         v2f32(1,0),
  57                         v2f32(0,1),
  58                 };
  59
  60                 v2f32 slopevector(0.0, 0.0);
  61
  62                 for(u16 i=0; i<2; i++){
  63                         f32 y1 = 0.0;
  64                         f32 y2 = 0.0;
  65                         f32 count = 0.0;
  66
  67                         v2s16 p1 = p - dirs[i];
  68                         y1 = getGroundHeight(p1, false);
  69                         if(y1 > GROUNDHEIGHT_VALID_MINVALUE){
  70                                 y1 -= y0;
  71                                 count += 1.0;
  72                         }
  73                         else
  74                                 y1 = 0;
  75
  76                         v2s16 p2 = p + dirs[i];
  77                         y2 = getGroundHeight(p2, false);
  78                         if(y2 > GROUNDHEIGHT_VALID_MINVALUE){
  79                                 y2 -= y0;
  80                                 count += 1.0;
  81                         }
  82                         else
  83                                 y2 = 0;
  84
  85                         if(count < 0.001)
  86                                 return v2f32(0.0, 0.0);
  87
  88                         /*
  89                                 If y2 is higher than y1, slope is positive
  90                         */
  91                         f32 slope = (y2 - y1)/count;
  92
  93                         slopevector += fdirs[i] * slope;
  94                 }
  95
  96                 return slopevector;
  97         }
  98
  99 };
 100
 101 // TODO: Get rid of this dummy wrapper
 102 class Heightmap : public Heightmappish /*, public ReferenceCounted*/
 103 {
 104 };
 105
 106 class WrapperHeightmap : public Heightmap
 107 {
 108         Heightmappish *m_target;
 109 public:
 110
 111         WrapperHeightmap(Heightmappish *target):
 112                 m_target(target)
 113         {
 114                 if(target == NULL)
 115                         throw NullPointerException();
 116         }
 117
 118         f32 getGroundHeight(v2s16 p, bool generate=true)
 119         {
 120                 return m_target->getGroundHeight(p, generate);
 121         }
 122         void setGroundHeight(v2s16 p, f32 y, bool generate=true)
 123         {
 124                 m_target->setGroundHeight(p, y, generate);
 125         }
 126 };
 127
 128 /*
 129         Base class that defines a generator that gives out values at
 130         positions in 2-dimensional space.
 131         Can be given to UnlimitedHeightmap to feed stuff.
 132
 133         These are always serialized as readable text ending in "\n"
 134 */
 135 class ValueGenerator
 136 {
 137 public:
 138         ValueGenerator(){}
 139         virtual ~ValueGenerator(){}
 140
 141         static ValueGenerator* deSerialize(std::string line);
 142
 143         static ValueGenerator* deSerialize(std::istream &is)
 144         {
 145                 std::string line;
 146                 std::getline(is, line, '\n');
 147                 return deSerialize(line);
 148         }
 149
 150         void serializeBase(std::ostream &os)
 151         {
 152                 os<<getName()<<" ";
 153         }
 154
 155         // Virtual methods
 156         virtual const char * getName() const = 0;
 157         virtual f32 getValue(v2s16 p) = 0;
 158         virtual void serialize(std::ostream &os) = 0;
 159 };
 160
 161 class ConstantGenerator : public ValueGenerator
 162 {
 163 public:
 164         f32 m_value;
 165
 166         ConstantGenerator(f32 value)
 167         {
 168                 m_value = value;
 169         }
 170
 171         const char * getName() const
 172         {
 173                 return "constant";
 174         }
 175
 176         f32 getValue(v2s16 p)
 177         {
 178                 return m_value;
 179         }
 180
 181         void serialize(std::ostream &os)
 182         {
 183                 serializeBase(os);
 184
 185                 std::ostringstream ss;
 186                 //ss.imbue(std::locale("C"));
 187
 188                 ss<<m_value<<"\n";
 189
 190                 os<<ss.str();
 191         }
 192 };
 193
 194 class LinearGenerator : public ValueGenerator
 195 {
 196 public:
 197         f32 m_height;
 198         v2f m_slope;
 199
 200         LinearGenerator(f32 height, v2f slope)
 201         {
 202                 m_height = height;
 203                 m_slope = slope;
 204         }
 205
 206         const char * getName() const
 207         {
 208                 return "linear";
 209         }
 210
 211         f32 getValue(v2s16 p)
 212         {
 213                 return m_height + m_slope.X * p.X + m_slope.Y * p.Y;
 214         }
 215
 216         void serialize(std::ostream &os)
 217         {
 218                 serializeBase(os);
 219
 220                 std::ostringstream ss;
 221                 //ss.imbue(std::locale("C"));
 222
 223                 ss<<m_height<<" "<<m_slope.X<<" "<<m_slope.Y<<"\n";
 224
 225                 os<<ss.str();
 226         }
 227 };
 228
 229 class PowerGenerator : public ValueGenerator
 230 {
 231 public:
 232         f32 m_height;
 233         v2f m_slope;
 234         f32 m_power;
 235
 236         PowerGenerator(f32 height, v2f slope, f32 power)
 237         {
 238                 m_height = height;
 239                 m_slope = slope;
 240                 m_power = power;
 241         }
 242
 243         const char * getName() const
 244         {
 245                 return "power";
 246         }
 247
 248         f32 getValue(v2s16 p)
 249         {
 250                 return m_height
 251                                 + m_slope.X * pow((f32)p.X, m_power)
 252                                 + m_slope.Y * pow((f32)p.Y, m_power);
 253         }
 254
 255         void serialize(std::ostream &os)
 256         {
 257                 serializeBase(os);
 258
 259                 std::ostringstream ss;
 260                 //ss.imbue(std::locale("C"));
 261
 262                 ss<<m_height<<" "
 263                         <<m_slope.X<<" "
 264                         <<m_slope.Y<<" "
 265                         <<m_power<<"\n";
 266
 267                 os<<ss.str();
 268         }
 269 };
 270
 271 class FixedHeightmap : public Heightmap
 272 {
 273         // A meta-heightmap on which this heightmap is located
 274         // (at m_pos_on_master * m_blocksize)
 275         Heightmap * m_master;
 276         // Position on master heightmap (in blocks)
 277         v2s16 m_pos_on_master;
 278         s32 m_blocksize; // This is (W-1) = (H-1)
 279         // These are the actual size of the data
 280         s32 W;
 281         s32 H;
 282         f32 *m_data;
 283
 284 public:
 285
 286         FixedHeightmap(Heightmap * master,
 287                         v2s16 pos_on_master, s32 blocksize):
 288                 m_master(master),
 289                 m_pos_on_master(pos_on_master),
 290                 m_blocksize(blocksize)
 291         {
 292                 W = m_blocksize+1;
 293                 H = m_blocksize+1;
 294                 m_data = NULL;
 295                 m_data = new f32[(blocksize+1)*(blocksize+1)];
 296
 297                 for(s32 i=0; i<(blocksize+1)*(blocksize+1); i++){
 298                         m_data[i] = GROUNDHEIGHT_NOTFOUND_SETVALUE;
 299                 }
 300         }
 301
 302         ~FixedHeightmap()
 303         {
 304                 if(m_data)
 305                         delete[] m_data;
 306         }
 307
 308         v2s16 getPosOnMaster()
 309         {
 310                 return m_pos_on_master;
 311         }
 312
 313         /*
 314                 TODO: BorderWrapper class or something to allow defining
 315                 borders that wrap to an another heightmap. The algorithm
 316                 should be allowed to edit stuff over the border and on
 317                 the border in that case, too.
 318                 This will allow non-square heightmaps, too. (probably)
 319         */
 320
 321         void print()
 322         {
 323                 printf("FixedHeightmap::print(): size is %ix%i\n", W, H);
 324                 for(s32 y=0; y<H; y++){
 325                         for(s32 x=0; x<W; x++){
 326                                 /*if(getSeeded(v2s16(x,y)))
 327                                         printf("S");*/
 328                                 f32 n = getGroundHeight(v2s16(x,y));
 329                                 if(n < GROUNDHEIGHT_VALID_MINVALUE)
 330                                         printf("  -   ");
 331                                 else
 332                                         printf("% -5.1f ", getGroundHeight(v2s16(x,y)));
 333                         }
 334                         printf("\n");
 335                 }
 336         }
 337
 338         bool overborder(v2s16 p)
 339         {
 340                 return (p.X < 0 || p.X >= W || p.Y < 0 || p.Y >= H);
 341         }
 342
 343         bool atborder(v2s16 p)
 344         {
 345                 if(overborder(p))
 346                         return false;
 347                 return (p.X == 0 || p.X == W-1 || p.Y == 0 || p.Y == H-1);
 348         }
 349
 350         void setGroundHeight(v2s16 p, f32 y, bool generate=false)
 351         {
 352                 /*dstream<<"FixedHeightmap::setGroundHeight(("
 353                                 <<p.X<<","<<p.Y
 354                                 <<"), "<<y<<")"<<std::endl;*/
 355                 if(overborder(p))
 356                         throw InvalidPositionException();
 357                 m_data[p.Y*W + p.X] = y;
 358         }
 359
 360         // Returns true on success, false on railure.
 361         bool setGroundHeightParent(v2s16 p, f32 y, bool generate=false)
 362         {
 363                 /*// Position on master
 364                 v2s16 blockpos_nodes = m_pos_on_master * m_blocksize;
 365                 v2s16 nodepos_master = blockpos_nodes + p;
 366                 dstream<<"FixedHeightmap::setGroundHeightParent(("
 367                                 <<p.X<<","<<p.Y
 368                                 <<"), "<<y<<"): nodepos_master=("
 369                                 <<nodepos_master.X<<","
 370                                 <<nodepos_master.Y<<")"<<std::endl;
 371                 m_master->setGroundHeight(nodepos_master, y, false);*/
 372
 373                 // Try to set on master
 374                 bool master_got_it = false;
 375                 if(overborder(p) || atborder(p))
 376                 {
 377                         try{
 378                                 // Position on master
 379                                 v2s16 blockpos_nodes = m_pos_on_master * m_blocksize;
 380                                 v2s16 nodepos_master = blockpos_nodes + p;
 381                                 m_master->setGroundHeight(nodepos_master, y, false);
 382
 383                                 master_got_it = true;
 384                         }
 385                         catch(InvalidPositionException &e)
 386                         {
 387                         }
 388                 }
 389
 390                 if(overborder(p))
 391                         return master_got_it;
 392
 393                 setGroundHeight(p, y);
 394
 395                 return true;
 396         }
 397
 398         f32 getGroundHeight(v2s16 p, bool generate=false)
 399         {
 400                 if(overborder(p))
 401                         return GROUNDHEIGHT_NOTFOUND_SETVALUE;
 402                 return m_data[p.Y*W + p.X];
 403         }
 404
 405         f32 getGroundHeightParent(v2s16 p)
 406         {
 407                 /*v2s16 blockpos_nodes = m_pos_on_master * m_blocksize;
 408                 return m_master->getGroundHeight(blockpos_nodes + p, false);*/
 409
 410                 if(overborder(p) == false){
 411                         f32 h = getGroundHeight(p);
 412                         if(h > GROUNDHEIGHT_VALID_MINVALUE)
 413                                 return h;
 414                 }
 415
 416                 // Position on master
 417                 v2s16 blockpos_nodes = m_pos_on_master * m_blocksize;
 418                 f32 h = m_master->getGroundHeight(blockpos_nodes + p, false);
 419                 return h;
 420         }
 421
 422         f32 avgNeighbours(v2s16 p, s16 d);
 423
 424         f32 avgDiagNeighbours(v2s16 p, s16 d);
 425
 426         void makeDiamond(
 427                         v2s16 center,
 428                         s16 a,
 429                         f32 randmax,
 430                         core::map<v2s16, bool> &next_squares);
 431
 432         void makeSquare(
 433                         v2s16 center,
 434                         s16 a,
 435                         f32 randmax,
 436                         core::map<v2s16, bool> &next_diamonds);
 437
 438         void DiamondSquare(f32 randmax, f32 randfactor);
 439
 440         /*
 441                 corners: [i]=XY: [0]=00, [1]=10, [2]=11, [3]=10
 442         */
 443         void generateContinued(f32 randmax, f32 randfactor, f32 *corners);
 444
 445
 446         static u32 serializedLength(u8 version, u16 blocksize);
 447         u32 serializedLength(u8 version);
 448         void serialize(u8 *dest, u8 version);
 449         void deSerialize(u8 *source, u8 version);
 450         /*static FixedHeightmap * deSerialize(u8 *source, u32 size,
 451                         u32 &usedsize, Heightmap *master, u8 version);*/
 452 };
 453
 454 class OneChildHeightmap : public Heightmap
 455 {
 456         s16 m_blocksize;
 457
 458 public:
 459
 460         FixedHeightmap m_child;
 461
 462         OneChildHeightmap(s16 blocksize):
 463                 m_blocksize(blocksize),
 464                 m_child(this, v2s16(0,0), blocksize)
 465         {
 466         }
 467
 468         f32 getGroundHeight(v2s16 p, bool generate=true)
 469         {
 470                 if(p.X < 0 || p.X > m_blocksize
 471                                 || p.Y < 0 || p.Y > m_blocksize)
 472                         return GROUNDHEIGHT_NOTFOUND_SETVALUE;
 473                 return m_child.getGroundHeight(p);
 474         }
 475         void setGroundHeight(v2s16 p, f32 y, bool generate=true)
 476         {
 477                 //dstream<<"OneChildHeightmap::setGroundHeight()"<<std::endl;
 478                 if(p.X < 0 || p.X > m_blocksize
 479                                 || p.Y < 0 || p.Y > m_blocksize)
 480                         throw InvalidPositionException();
 481                 m_child.setGroundHeight(p, y);
 482         }
 483 };
 484
 485
 486 /*
 487         This is a dynamic container of an arbitrary number of heightmaps
 488         at arbitrary positions.
 489
 490         It is able to redirect queries to the corresponding heightmaps and
 491         it generates new heightmaps on-the-fly according to the relevant
 492         parameters.
 493
 494         It doesn't have a master heightmap because it is meant to be used
 495         as such itself.
 496
 497         Child heightmaps are spaced at m_blocksize distances, and are of
 498         size (m_blocksize+1)*(m_blocksize+1)
 499
 500         This is used as the master heightmap of a Map object.
 501 */
 502 class UnlimitedHeightmap: public Heightmap
 503 {
 504 private:
 505
 506         core::map<v2s16, FixedHeightmap*> m_heightmaps;
 507         s16 m_blocksize;
 508
 509         ValueGenerator *m_randmax_generator;
 510         ValueGenerator *m_randfactor_generator;
 511         ValueGenerator *m_base_generator;
 512
 513 public:
 514
 515         UnlimitedHeightmap(
 516                         s16 blocksize,
 517                         ValueGenerator *randmax_generator,
 518                         ValueGenerator *randfactor_generator,
 519                         ValueGenerator *base_generator
 520                         ):
 521                 m_blocksize(blocksize),
 522                 m_randmax_generator(randmax_generator),
 523                 m_randfactor_generator(randfactor_generator),
 524                 m_base_generator(base_generator)
 525         {
 526                 assert(m_randmax_generator != NULL);
 527                 assert(m_randfactor_generator != NULL);
 528                 assert(m_base_generator != NULL);
 529         }
 530
 531         ~UnlimitedHeightmap()
 532         {
 533                 core::map<v2s16, FixedHeightmap*>::Iterator i;
 534                 i = m_heightmaps.getIterator();
 535                 for(; i.atEnd() == false; i++)
 536                 {
 537                         delete i.getNode()->getValue();
 538                 }
 539
 540                 delete m_randmax_generator;
 541                 delete m_randfactor_generator;
 542                 delete m_base_generator;
 543         }
 544
 545         /*void setParams(f32 randmax, f32 randfactor)
 546         {
 547                 m_randmax = randmax;
 548                 m_randfactor = randfactor;
 549         }*/
 550
 551         void print();
 552
 553         v2s16 getNodeHeightmapPos(v2s16 p)
 554         {
 555                 return v2s16(
 556                                 (p.X>=0 ? p.X : p.X-m_blocksize+1) / m_blocksize,
 557                                 (p.Y>=0 ? p.Y : p.Y-m_blocksize+1) / m_blocksize);
 558         }
 559
 560         // Can throw an InvalidPositionException
 561         FixedHeightmap * getHeightmap(v2s16 p, bool generate=true);
 562
 563         f32 getGroundHeight(v2s16 p, bool generate=true);
 564         void setGroundHeight(v2s16 p, f32 y, bool generate=true);
 565
 566         /*static UnlimitedHeightmap * deSerialize(u8 *source, u32 maxsize,
 567                         u32 &usedsize, u8 version);*/
 568
 569         //SharedBuffer<u8> serialize(u8 version);
 570         void serialize(std::ostream &os, u8 version);
 571         static UnlimitedHeightmap * deSerialize(std::istream &istr);
 572 };
 573
 574 #endif
 575