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