3 Copyright (C) 2010 celeron55, Perttu Ahola <celeron55@gmail.com>
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.
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.
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.
21 (c) 2010 Perttu Ahola <celeron55@gmail.com>
24 #include "heightmap.h"
30 ValueGenerator* ValueGenerator::deSerialize(std::string line)
32 std::istringstream ss(line);
33 //ss.imbue(std::locale("C"));
36 std::getline(ss, name, ' ');
38 if(name == "constant")
43 return new ConstantGenerator(value);
45 else if(name == "linear")
54 return new LinearGenerator(height, slope);
56 else if(name == "power")
67 return new PowerGenerator(height, slope, power);
71 throw SerializationError
72 ("Invalid heightmap generator (deSerialize)");
80 f32 FixedHeightmap::avgNeighbours(v2s16 p, s16 d)
90 for(u16 i=0; i<4; i++){
91 v2s16 p2 = p + dirs[i] * d;
92 f32 n = getGroundHeightParent(p2);
93 if(n < GROUNDHEIGHT_VALID_MINVALUE)
98 assert(count > 0.001);
102 f32 FixedHeightmap::avgDiagNeighbours(v2s16 p, s16 d)
112 for(u16 i=0; i<4; i++){
113 v2s16 p2 = p + dirs[i] * d;
114 f32 n = getGroundHeightParent(p2);
115 if(n < GROUNDHEIGHT_VALID_MINVALUE)
120 assert(count > 0.001);
125 Adds a point to transform into a diamond pattern
126 center = Center of the diamond phase (center of a square)
127 a = Side length of the existing square (2, 4, 8, ...)
129 Adds the center points of the next squares to next_squares as
132 void FixedHeightmap::makeDiamond(
136 core::map<v2s16, bool> &next_squares)
138 /*dstream<<"makeDiamond(): center="
139 <<"("<<center.X<<","<<center.Y<<")"
140 <<", a="<<a<<", randmax="<<randmax
141 <<", next_squares.size()="<<next_squares.size()
144 f32 n = avgDiagNeighbours(center, a/2);
145 // Add (-1.0...1.0) * randmax
146 n += ((float)myrand() / (float)(MYRAND_MAX/2) - 1.0)*randmax;
147 bool worked = setGroundHeightParent(center, n);
151 next_squares[center + a/2*v2s16(-1,0)] = true;
152 next_squares[center + a/2*v2s16(1,0)] = true;
153 next_squares[center + a/2*v2s16(0,-1)] = true;
154 next_squares[center + a/2*v2s16(0,1)] = true;
159 Adds a point to transform into a square pattern
160 center = The point that is added. The center of a diamond.
161 a = Diameter of the existing diamond. (2, 4, 8, 16, ...)
163 Adds center points of the next diamonds to next_diamonds.
165 void FixedHeightmap::makeSquare(
169 core::map<v2s16, bool> &next_diamonds)
171 /*dstream<<"makeSquare(): center="
172 <<"("<<center.X<<","<<center.Y<<")"
173 <<", a="<<a<<", randmax="<<randmax
174 <<", next_diamonds.size()="<<next_diamonds.size()
177 f32 n = avgNeighbours(center, a/2);
178 // Add (-1.0...1.0) * randmax
179 n += ((float)myrand() / (float)(MYRAND_MAX/2) - 1.0)*randmax;
180 bool worked = setGroundHeightParent(center, n);
184 next_diamonds[center + a/4*v2s16(1,1)] = true;
185 next_diamonds[center + a/4*v2s16(-1,1)] = true;
186 next_diamonds[center + a/4*v2s16(-1,-1)] = true;
187 next_diamonds[center + a/4*v2s16(1,-1)] = true;
191 void FixedHeightmap::DiamondSquare(f32 randmax, f32 randfactor)
199 // Check that a is a power of two
203 core::map<v2s16, bool> next_diamonds;
204 core::map<v2s16, bool> next_squares;
206 next_diamonds[v2s16(a/2, a/2)] = true;
210 next_squares.clear();
212 for(core::map<v2s16, bool>::Iterator
213 i = next_diamonds.getIterator();
214 i.atEnd() == false; i++)
216 v2s16 p = i.getNode()->getKey();
217 makeDiamond(p, a, randmax, next_squares);
222 next_diamonds.clear();
224 for(core::map<v2s16, bool>::Iterator
225 i = next_squares.getIterator();
226 i.atEnd() == false; i++)
228 v2s16 p = i.getNode()->getKey();
229 makeSquare(p, a, randmax, next_diamonds);
235 randmax *= randfactor;
239 void FixedHeightmap::generateContinued(f32 randmax, f32 randfactor,
242 DSTACK(__FUNCTION_NAME);
243 /*dstream<<"FixedHeightmap("<<m_pos_on_master.X
244 <<","<<m_pos_on_master.Y
245 <<")::generateContinued()"<<std::endl;*/
247 // Works only with blocksize=2,4,8,16,32,64,...
250 // Check that a is a power of two
254 // Overwrite with GROUNDHEIGHT_NOTFOUND_SETVALUE
255 for(s16 y=0; y<=a; y++){
256 for(s16 x=0; x<=a; x++){
258 setGroundHeight(p, GROUNDHEIGHT_NOTFOUND_SETVALUE);
263 Seed borders from master heightmap
264 NOTE: Does this actually have any effect on the output?
268 v2s16 neighbour_start;
269 v2s16 heightmap_start;
275 { // Z- edge on X-axis
276 v2s16(0, -1), // neighbour_start
277 v2s16(0, 0), // heightmap_start
280 { // Z+ edge on X-axis
281 v2s16(0, m_blocksize),
282 v2s16(0, m_blocksize),
285 { // X- edge on Z-axis
290 { // X+ edge on Z-axis
291 v2s16(m_blocksize, 0),
292 v2s16(m_blocksize, 0),
297 for(s16 i=0; i<4; i++){
298 v2s16 npos = seeds[i].neighbour_start + m_pos_on_master * m_blocksize;
299 v2s16 hpos = seeds[i].heightmap_start;
300 for(s16 s=0; s<m_blocksize+1; s++){
301 f32 h = m_master->getGroundHeight(npos, false);
302 //dstream<<"h="<<h<<std::endl;
303 if(h < GROUNDHEIGHT_VALID_MINVALUE)
306 setGroundHeight(hpos, h);
307 hpos += seeds[i].dir;
308 npos += seeds[i].dir;
312 /*dstream<<"borders seeded:"<<std::endl;
316 Fill with corners[] (if not already set)
324 for(u16 i=0; i<4; i++){
325 v2s16 npos = dirs[i] * a;
326 // Don't replace already seeded corners
327 f32 h = getGroundHeight(npos);
328 if(h > GROUNDHEIGHT_VALID_MINVALUE)
330 setGroundHeight(dirs[i] * a, corners[i]);
333 /*dstream<<"corners filled:"<<std::endl;
336 DiamondSquare(randmax, randfactor);
339 u32 FixedHeightmap::serializedLength(u8 version, u16 blocksize)
341 if(!ser_ver_supported(version))
342 throw VersionMismatchException("ERROR: FixedHeightmap format not supported");
346 /*// [0] s32 blocksize
347 // [4] v2s16 pos_on_master
348 // [8] s32 data[W*H] (W=H=blocksize+1)
349 return 4 + 4 + (blocksize+1)*(blocksize+1)*4;*/
351 // [8] s32 data[W*H] (W=H=blocksize+1)
352 return (blocksize+1)*(blocksize+1)*4;
356 u32 FixedHeightmap::serializedLength(u8 version)
358 return serializedLength(version, m_blocksize);
361 void FixedHeightmap::serialize(u8 *dest, u8 version)
363 //dstream<<"FixedHeightmap::serialize"<<std::endl;
365 if(!ser_ver_supported(version))
366 throw VersionMismatchException("ERROR: FixedHeightmap format not supported");
370 /*writeU32(&dest[0], m_blocksize);
371 writeV2S16(&dest[4], m_pos_on_master);
373 for(u32 i=0; i<nodecount; i++)
375 writeS32(&dest[8+i*4], (s32)(m_data[i]*1000.0));
379 for(u32 i=0; i<nodecount; i++)
381 writeS32(&dest[i*4], (s32)(m_data[i]*1000.0));
386 void FixedHeightmap::deSerialize(u8 *source, u8 version)
388 /*dstream<<"FixedHeightmap::deSerialize m_blocksize="
389 <<m_blocksize<<std::endl;*/
391 if(!ser_ver_supported(version))
392 throw VersionMismatchException("ERROR: FixedHeightmap format not supported");
396 u32 nodecount = (m_blocksize+1)*(m_blocksize+1);
397 for(u32 i=0; i<nodecount; i++)
399 m_data[i] = ((f32)readS32(&source[i*4]))/1000.0;
402 /*printf("source[0,1,2,3]=%x,%x,%x,%x\n",
406 (int)source[3]&0xff);
408 dstream<<"m_data[0]="<<m_data[0]<<", "
409 <<"readS32(&source[0])="<<readS32(&source[0])
411 dstream<<"m_data[4*4]="<<m_data[4*4]<<", "
412 <<"readS32(&source[4*4])="<<readS32(&source[4*4])
418 void setcolor(f32 h, f32 rangemin, f32 rangemax)
421 const char *colors[] =
430 u16 colorcount = sizeof(colors)/sizeof(colors[0]);
431 f32 scaled = (h - rangemin) / (rangemax - rangemin);
432 u8 color = scaled * colorcount;
433 if(color > colorcount-1)
434 color = colorcount-1;
435 /*printf("rangemin=%f, rangemax=%f, h=%f -> color=%i\n",
440 printf("%s", colors[color]);
441 //printf("\x1b[31;40m");
442 //printf("\x1b[44;1m");
456 void UnlimitedHeightmap::print()
462 core::map<v2s16, FixedHeightmap*>::Iterator i;
463 i = m_heightmaps.getIterator();
465 printf("UnlimitedHeightmap::print(): empty.\n");
468 for(; i.atEnd() == false; i++)
470 v2s16 p = i.getNode()->getValue()->getPosOnMaster();
471 if(p.X < minx) minx = p.X;
472 if(p.Y < miny) miny = p.Y;
473 if(p.X > maxx) maxx = p.X;
474 if(p.Y > maxy) maxy = p.Y;
476 minx = minx * m_blocksize;
477 miny = miny * m_blocksize;
478 maxx = (maxx+1) * m_blocksize;
479 maxy = (maxy+1) * m_blocksize;
480 printf("UnlimitedHeightmap::print(): from (%i,%i) to (%i,%i)\n",
481 minx, miny, maxx, maxy);
485 f32 rangemax = -1e10;
486 for(s32 y=miny; y<=maxy; y++){
487 for(s32 x=minx; x<=maxx; x++){
488 f32 h = getGroundHeight(v2s16(x,y), false);
489 if(h < GROUNDHEIGHT_VALID_MINVALUE)
499 for(s32 x=minx; x<=maxx; x++){
504 for(s32 y=miny; y<=maxy; y++){
506 for(s32 x=minx; x<=maxx; x++){
507 f32 n = getGroundHeight(v2s16(x,y), false);
508 if(n < GROUNDHEIGHT_VALID_MINVALUE)
512 setcolor(n, rangemin, rangemax);
513 printf("% -5.1f", getGroundHeight(v2s16(x,y), false));
521 FixedHeightmap * UnlimitedHeightmap::getHeightmap(v2s16 p_from, bool generate)
523 DSTACK("UnlimitedHeightmap::getHeightmap()");
525 We want to check that all neighbours of the wanted heightmap
527 This is because generating the neighboring heightmaps will
528 modify the current one.
533 // Go through all neighbors (corners also) and the current one
534 // and generate every one of them.
535 for(s16 x=p_from.X-1; x<=p_from.X+1; x++)
536 for(s16 y=p_from.Y-1; y<=p_from.Y+1; y++)
541 core::map<v2s16, FixedHeightmap*>::Node *n = m_heightmaps.find(p);
548 FixedHeightmap *heightmap = new FixedHeightmap(this, p, m_blocksize);
550 m_heightmaps.insert(p, heightmap);
553 m_base_generator->getValue(p+v2s16(0,0)),
554 m_base_generator->getValue(p+v2s16(1,0)),
555 m_base_generator->getValue(p+v2s16(1,1)),
556 m_base_generator->getValue(p+v2s16(0,1)),
559 f32 randmax = m_randmax_generator->getValue(p);
560 f32 randfactor = m_randfactor_generator->getValue(p);
562 heightmap->generateContinued(randmax, randfactor, corners);
566 core::map<v2s16, FixedHeightmap*>::Node *n = m_heightmaps.find(p_from);
570 return n->getValue();
574 throw InvalidPositionException
575 ("Something went really wrong in UnlimitedHeightmap::getHeightmap");
579 f32 UnlimitedHeightmap::getGroundHeight(v2s16 p, bool generate)
581 v2s16 heightmappos = getNodeHeightmapPos(p);
582 v2s16 relpos = p - heightmappos*m_blocksize;
584 FixedHeightmap * href = getHeightmap(heightmappos, generate);
585 f32 h = href->getGroundHeight(relpos);
586 if(h > GROUNDHEIGHT_VALID_MINVALUE)
589 catch(InvalidPositionException){}
591 If on border or in the (0,0) corner, try to get from
592 overlapping heightmaps
596 FixedHeightmap * href = getHeightmap(
597 heightmappos-v2s16(1,0), false);
598 f32 h = href->getGroundHeight(v2s16(m_blocksize, relpos.Y));
599 if(h > GROUNDHEIGHT_VALID_MINVALUE)
602 catch(InvalidPositionException){}
606 FixedHeightmap * href = getHeightmap(
607 heightmappos-v2s16(0,1), false);
608 f32 h = href->getGroundHeight(v2s16(relpos.X, m_blocksize));
609 if(h > GROUNDHEIGHT_VALID_MINVALUE)
612 catch(InvalidPositionException){}
614 if(relpos.X == 0 && relpos.Y == 0){
616 FixedHeightmap * href = getHeightmap(
617 heightmappos-v2s16(1,1), false);
618 f32 h = href->getGroundHeight(v2s16(m_blocksize, m_blocksize));
619 if(h > GROUNDHEIGHT_VALID_MINVALUE)
622 catch(InvalidPositionException){}
624 return GROUNDHEIGHT_NOTFOUND_SETVALUE;
627 void UnlimitedHeightmap::setGroundHeight(v2s16 p, f32 y, bool generate)
629 bool was_set = false;
631 v2s16 heightmappos = getNodeHeightmapPos(p);
632 v2s16 relpos = p - heightmappos*m_blocksize;
633 /*dstream<<"UnlimitedHeightmap::setGroundHeight(("
634 <<p.X<<","<<p.Y<<"), "<<y<<"): "
635 <<"heightmappos=("<<heightmappos.X<<","
636 <<heightmappos.Y<<") relpos=("
637 <<relpos.X<<","<<relpos.Y<<")"
640 FixedHeightmap * href = getHeightmap(heightmappos, generate);
641 href->setGroundHeight(relpos, y);
643 }catch(InvalidPositionException){}
644 // Update in neighbour heightmap if it's at border
647 FixedHeightmap * href = getHeightmap(
648 heightmappos-v2s16(1,0), generate);
649 href->setGroundHeight(v2s16(m_blocksize, relpos.Y), y);
651 }catch(InvalidPositionException){}
655 FixedHeightmap * href = getHeightmap(
656 heightmappos-v2s16(0,1), generate);
657 href->setGroundHeight(v2s16(relpos.X, m_blocksize), y);
659 }catch(InvalidPositionException){}
661 if(relpos.X == 0 && relpos.Y == 0){
663 FixedHeightmap * href = getHeightmap(
664 heightmappos-v2s16(1,1), generate);
665 href->setGroundHeight(v2s16(m_blocksize, m_blocksize), y);
667 }catch(InvalidPositionException){}
672 throw InvalidPositionException
673 ("UnlimitedHeightmap failed to set height");
678 void UnlimitedHeightmap::serialize(std::ostream &os, u8 version)
680 //dstream<<"UnlimitedHeightmap::serialize()"<<std::endl;
682 if(!ser_ver_supported(version))
683 throw VersionMismatchException
684 ("ERROR: UnlimitedHeightmap format not supported");
688 /*if(m_base_generator->getId() != VALUE_GENERATOR_ID_CONSTANT
689 || m_randmax_generator->getId() != VALUE_GENERATOR_ID_CONSTANT
690 || m_randfactor_generator->getId() != VALUE_GENERATOR_ID_CONSTANT)*/
691 if(std::string(m_base_generator->getName()) != "constant"
692 || std::string(m_randmax_generator->getName()) != "constant"
693 || std::string(m_randfactor_generator->getName()) != "constant")
695 throw SerializationError
696 ("Cannot write UnlimitedHeightmap in old version: "
697 "Generators are not ConstantGenerators.");
700 f32 basevalue = ((ConstantGenerator*)m_base_generator)->m_value;
701 f32 randmax = ((ConstantGenerator*)m_randmax_generator)->m_value;
702 f32 randfactor = ((ConstantGenerator*)m_randfactor_generator)->m_value;
705 os.write((char*)&version, 1);
710 [6] s32 randfactor*1000
711 [10] s32 basevalue*1000
712 [14] u32 heightmap_count
713 [18] X * (v2s16 pos + heightmap)
716 FixedHeightmap::serializedLength(version, m_blocksize);
717 u32 heightmap_count = m_heightmaps.size();
719 //dstream<<"heightmap_size="<<heightmap_size<<std::endl;
721 u32 datasize = 2+4+4+4+4+heightmap_count*(4+heightmap_size);
722 SharedBuffer<u8> data(datasize);
724 writeU16(&data[0], m_blocksize);
725 writeU32(&data[2], (s32)(randmax*1000.0));
726 writeU32(&data[6], (s32)(randfactor*1000.0));
727 writeU32(&data[10], (s32)(basevalue*1000.0));
728 writeU32(&data[14], heightmap_count);
730 core::map<v2s16, FixedHeightmap*>::Iterator j;
731 j = m_heightmaps.getIterator();
733 for(; j.atEnd() == false; j++)
735 FixedHeightmap *hm = j.getNode()->getValue();
736 v2s16 pos = j.getNode()->getKey();
737 writeV2S16(&data[18+i*(4+heightmap_size)], pos);
738 hm->serialize(&data[18+i*(4+heightmap_size)+4], version);
742 os.write((char*)*data, data.getSize());
747 os.write((char*)&version, 1);
751 writeU16(buf, m_blocksize);
752 os.write((char*)buf, 2);
754 /*m_randmax_generator->serialize(os, version);
755 m_randfactor_generator->serialize(os, version);
756 m_base_generator->serialize(os, version);*/
757 m_randmax_generator->serialize(os);
758 m_randfactor_generator->serialize(os);
759 m_base_generator->serialize(os);
761 u32 heightmap_count = m_heightmaps.size();
762 writeU32(buf, heightmap_count);
763 os.write((char*)buf, 4);
766 FixedHeightmap::serializedLength(version, m_blocksize);
768 SharedBuffer<u8> hmdata(heightmap_size);
770 core::map<v2s16, FixedHeightmap*>::Iterator j;
771 j = m_heightmaps.getIterator();
773 for(; j.atEnd() == false; j++)
775 v2s16 pos = j.getNode()->getKey();
776 writeV2S16(buf, pos);
777 os.write((char*)buf, 4);
779 FixedHeightmap *hm = j.getNode()->getValue();
780 hm->serialize(*hmdata, version);
781 os.write((char*)*hmdata, hmdata.getSize());
788 UnlimitedHeightmap * UnlimitedHeightmap::deSerialize(std::istream &is)
791 is.read((char*)&version, 1);
793 if(!ser_ver_supported(version))
794 throw VersionMismatchException("ERROR: UnlimitedHeightmap format not supported");
801 [6] s32 randfactor*1000
802 [10] s32 basevalue*1000
803 [14] u32 heightmap_count
804 [18] X * (v2s16 pos + heightmap)
806 SharedBuffer<u8> data(18);
807 is.read((char*)*data, 18);
808 if(is.gcount() != 18)
809 throw SerializationError
810 ("UnlimitedHeightmap::deSerialize: no enough input data");
811 s16 blocksize = readU16(&data[0]);
812 f32 randmax = (f32)readU32(&data[2]) / 1000.0;
813 f32 randfactor = (f32)readU32(&data[6]) / 1000.0;
814 f32 basevalue = (f32)readU32(&data[10]) / 1000.0;
815 u32 heightmap_count = readU32(&data[14]);
817 /*dstream<<"UnlimitedHeightmap::deSerialize():"
818 <<" blocksize="<<blocksize
819 <<" heightmap_count="<<heightmap_count
823 FixedHeightmap::serializedLength(version, blocksize);
825 //dstream<<"heightmap_size="<<heightmap_size<<std::endl;
827 ValueGenerator *maxgen = new ConstantGenerator(randmax);
828 ValueGenerator *factorgen = new ConstantGenerator(randfactor);
829 ValueGenerator *basegen = new ConstantGenerator(basevalue);
831 UnlimitedHeightmap *hm = new UnlimitedHeightmap
832 (blocksize, maxgen, factorgen, basegen);
834 for(u32 i=0; i<heightmap_count; i++)
836 //dstream<<"i="<<i<<std::endl;
837 SharedBuffer<u8> data(4+heightmap_size);
838 is.read((char*)*data, 4+heightmap_size);
839 if(is.gcount() != (s32)(4+heightmap_size)){
841 throw SerializationError
842 ("UnlimitedHeightmap::deSerialize: no enough input data");
844 v2s16 pos = readV2S16(&data[0]);
845 FixedHeightmap *f = new FixedHeightmap(hm, pos, blocksize);
846 f->deSerialize(&data[4], version);
847 hm->m_heightmaps.insert(pos, f);
855 is.read((char*)buf, 2);
856 s16 blocksize = readU16(buf);
858 ValueGenerator *maxgen = ValueGenerator::deSerialize(is);
859 ValueGenerator *factorgen = ValueGenerator::deSerialize(is);
860 ValueGenerator *basegen = ValueGenerator::deSerialize(is);
862 is.read((char*)buf, 4);
863 u32 heightmap_count = readU32(buf);
866 FixedHeightmap::serializedLength(version, blocksize);
868 UnlimitedHeightmap *hm = new UnlimitedHeightmap
869 (blocksize, maxgen, factorgen, basegen);
871 for(u32 i=0; i<heightmap_count; i++)
873 is.read((char*)buf, 4);
874 v2s16 pos = readV2S16(buf);
876 SharedBuffer<u8> data(heightmap_size);
877 is.read((char*)*data, heightmap_size);
878 if(is.gcount() != (s32)(heightmap_size)){
880 throw SerializationError
881 ("UnlimitedHeightmap::deSerialize: no enough input data");
883 FixedHeightmap *f = new FixedHeightmap(hm, pos, blocksize);
884 f->deSerialize(*data, version);
885 hm->m_heightmaps.insert(pos, f);