fork download
copy 
  1. #include <cassert>
  2. #include <cmath>
  3. #include <cstdint>
  4. #include <cstdlib>
  5. #include <map>
  6. #include <cstring>
  7. #include <fstream>
  8. #include <algorithm>
  9. #include <iomanip>
  10. #include <iostream>
  11. #include <memory>
  12. #include <random>
  13. #include <stdexcept>
  14. #include <string>
  15. #include <tuple>
  16. #include <unistd.h>
  17. #include <utility>
  18. #include <vector>
  19. #include <ctime>
  20. #include <string>
  21. #include <vector>
  22. #include <sstream>
  23. #include <iomanip>
  24. #include <ostream>
  25. #include <cstring>
  26.  
  27.  
  28. class stop_watch
  29. {
  30. private:
  31. public:
  32. 	struct timespec ts1_r;
  33. 	struct timespec ts2_r;
  34.  
  35. public:
  36. 	stop_watch()
  37. 	{
  38. 		memset(&ts1_r,0,sizeof(ts1_r));
  39. 		memset(&ts2_r,0,sizeof(ts2_r));
  40. 	}
  41.  
  42. 	void start()
  43. 	{
  44. 		clock_gettime(CLOCK_REALTIME,&ts1_r);
  45. 	}
  46.  
  47. 	void stop()
  48. 	{
  49. 		clock_gettime(CLOCK_REALTIME,&ts2_r);
  50. 	}
  51.  
  52. 	long double get_micro_r() const
  53. 	{
  54. 		long double ret = (ts2_r.tv_sec - ts1_r.tv_sec) * 1000000.0L + (ts2_r.tv_nsec - ts1_r.tv_nsec) / 1000.0L;
  55. 		return ret;
  56. 	}
  57.  
  58. 	long double get_seconds_r() const { return get_micro_r() / 1000000.0L; }
  59. };
  60.  
  61.  
  62.  
  63. template<class C>
  64. const typename C::value_type& random_element( C& container )
  65. {
  66. 	static std::random_device rnd;
  67. 	auto it = container.begin();
  68. 	size_t num = rnd() % container.size();
  69. 	std::advance( it, num );
  70.  
  71. 	return *it;
  72. }
  73.  
  74. class bmp_stream
  75. {
  76. private:
  77. 	std::vector<char> buffer;
  78. 	std::ofstream out;
  79. 	size_t xres;
  80. 	size_t yres;
  81. 	size_t rowpos;
  82. 	size_t pixels;
  83.  
  84. 	template<class T>
  85. 	void write( const T& t )
  86. 	{
  87. 		size_t spos = buffer.size();
  88. 		buffer.resize(buffer.size()+sizeof(t));
  89. 		char* dst = &buffer[spos];
  90. 		memcpy(dst,&t,sizeof(t));
  91. 	}
  92.  
  93. 	template<class T>
  94. 	void write( const T& t, size_t num )
  95. 	{
  96. 		size_t spos = buffer.size();
  97. 		buffer.resize(buffer.size()+num);
  98. 		char* dst = &buffer[spos];
  99. 		memcpy(dst,&t,num);
  100. 	}
  101.  
  102. 	void create_header( size_t _x, size_t _y, int bpp );
  103.  
  104. public:
  105. 	bmp_stream( size_t x, size_t y, const std::string& fname );
  106.  
  107. 	~bmp_stream( );
  108.  
  109. 	void flush( )
  110. 	{
  111. 		out.write(&buffer[0],buffer.size());
  112. 		buffer.resize(0);
  113. 		out.flush();
  114. 	}
  115.  
  116. 	void add_pixel( int r, int g, int b );
  117. };
  118.  
  119. template<size_t N>
  120. struct rgb_pixel
  121. {
  122. 	uint32_t r : N;
  123. 	uint32_t g : N;
  124. 	uint32_t b : N;
  125.  
  126. 	rgb_pixel( uint32_t r_, uint32_t g_, uint32_t b_ ) :
  127. 		r(r_),
  128. 		g(g_),
  129. 		b(b_)
  130. 	{
  131. 	}
  132. };
  133.  
  134.  
  135.  
  136. template<size_t N, class T>
  137. rgb_pixel<N>& operator/=( rgb_pixel<N>& l, const T& t )
  138. {
  139. 	l.r /= t;
  140. 	l.g /= t;
  141. 	l.b /= t;
  142. 	return l;
  143. }
  144.  
  145. template<size_t N, class T>
  146. rgb_pixel<N>& operator*=( rgb_pixel<N>& l, const T& t )
  147. {
  148. 	l.r *= t;
  149. 	l.g *= t;
  150. 	l.b *= t;
  151. 	return l;
  152. }
  153.  
  154.  
  155.  
  156. template<size_t N>
  157. rgb_pixel<N>& operator-=( rgb_pixel<N>& l, const rgb_pixel<N>& r )
  158. {
  159. 	if( l.r > r.r )
  160. 	{
  161. 		l.r -= r.r;
  162. 	}
  163. 	else
  164. 	{
  165. 		l.r = 0;
  166. 	}
  167.  
  168. 	if( l.g > r.g )
  169. 	{
  170. 		l.g -= r.g;
  171. 	}
  172. 	else
  173. 	{
  174. 		l.g = 0;
  175. 	}
  176.  
  177. 	if( l.b > r.b )
  178. 	{
  179. 		l.b -= r.b;
  180. 	}
  181. 	else
  182. 	{
  183. 		l.b = 0;
  184. 	}
  185.  
  186. 	return l;
  187. }
  188.  
  189. template<size_t N>
  190. rgb_pixel<N>& operator+=( rgb_pixel<N>& l, const rgb_pixel<N>& r )
  191. {
  192. 	if( l.r + r.r >= (1<<N) )
  193. 	{
  194. 		l.r = (1<<N)-1;
  195. 	}
  196. 	else
  197. 	{
  198. 		l.r += r.r;
  199. 	}
  200.  
  201. 	if( l.g + r.g >= (1<<N) )
  202. 	{
  203. 		l.g = (1<<N)-1;
  204. 	}
  205. 	else
  206. 	{
  207. 		l.g += r.g;
  208. 	}
  209.  
  210. 	if( l.b + r.b >= (1<<N) )
  211. 	{
  212. 		l.b = (1<<N)-1;
  213. 	}
  214. 	else
  215. 	{
  216. 		l.b += r.b;
  217. 	}
  218.  
  219. 	return l;
  220. }
  221.  
  222. class bmp
  223. {
  224. public:
  225. 	typedef rgb_pixel<8> pixel_type;
  226. private:
  227. 	std::vector<pixel_type> pixels;
  228. 	size_t xdim;
  229. 	size_t ydim;
  230. protected:
  231. public:
  232. 	bmp ( size_t xs, size_t ys, const pixel_type& proto = pixel_type(0,0,0) );
  233.  
  234. 	/**
  235. 	 * Writes the bmp image to a file
  236. 	 * @param fname is the name of the file to write
  237. 	 */
  238. 	void write( const std::string& fname ) const;
  239.  
  240. 	void fill( const pixel_type& col )
  241. 	{
  242. 		for (size_t x = 0; x < xdim; ++x)
  243. 		{
  244. 			for (size_t y = 0; y < ydim; ++y)
  245. 			{
  246. 				this->raw(x,y) = col;
  247. 			}
  248. 		}
  249. 	}
  250.  
  251. 	pixel_type& raw( size_t x, size_t y )
  252. 	{
  253. 		assert(x < xdim);
  254. 		assert(y < ydim);
  255. 		return pixels[x + xdim*y];
  256. 	}
  257.  
  258. 	const pixel_type& raw( size_t x, size_t y ) const
  259. 	{
  260. 		return pixels[x + xdim*y];
  261. 	}
  262.  
  263. 	void raw_line_add( int32_t x0, int32_t y0, int32_t x1, int32_t y1, const pixel_type& col )
  264. 	{
  265. 		const int32_t dx = std::abs(x1-x0);
  266. 		const int32_t dy = std::abs(y1-y0);
  267.  
  268. 		const int32_t sx = (x0<x1) ? 1 : -1;
  269. 		const int32_t sy = (y0<y1) ? 1 : -1;
  270.  
  271. 		int32_t err = dx-dy;
  272.  
  273. 		while(true)
  274. 		{
  275. 			raw(x0,y0) += col;
  276. 			if( x0 == x1 && y0 == y1 ) break;
  277. 			int32_t e2 = 2*err;
  278.  
  279. 			if( e2 > -dy )
  280. 			{
  281. 				err -= dy;
  282. 				x0 += sx;
  283. 			}
  284. 			if( e2 < dx )
  285. 			{
  286. 				err += dx;
  287. 				y0 += sy;
  288. 			}
  289. 		}
  290. 	}
  291.  
  292. 	void raw_line( int32_t x0, int32_t y0, int32_t x1, int32_t y1, const pixel_type& col )
  293. 	{
  294. 		const int32_t dx = std::abs(x1-x0);
  295. 		const int32_t dy = std::abs(y1-y0);
  296.  
  297. 		const int32_t sx = (x0<x1) ? 1 : -1;
  298. 		const int32_t sy = (y0<y1) ? 1 : -1;
  299.  
  300. 		int32_t err = dx-dy;
  301.  
  302. 		while(true)
  303. 		{
  304. 			raw(x0,y0) = col;
  305. 			if( x0 == x1 && y0 == y1 ) break;
  306. 			int32_t e2 = 2*err;
  307.  
  308. 			if( e2 > -dy )
  309. 			{
  310. 				err -= dy;
  311. 				x0 += sx;
  312. 			}
  313. 			if( e2 < dx )
  314. 			{
  315. 				err += dx;
  316. 				y0 += sy;
  317. 			}
  318. 		}
  319. 	}
  320.  
  321. 	void max_contrast_all( )
  322. 	{
  323. 		uint32_t min = std::numeric_limits<uint32_t>::max();
  324. 		uint32_t max = 0;
  325.  
  326. 		for( auto& p : pixels )
  327. 		{
  328. 			min = std::min(min,uint32_t(p.r));
  329. 			min = std::min(min,uint32_t(p.g));
  330. 			min = std::min(min,uint32_t(p.b));
  331.  
  332. 			max = std::max(max,uint32_t(p.r));
  333. 			max = std::max(max,uint32_t(p.g));
  334. 			max = std::max(max,uint32_t(p.b));
  335. 		}
  336.  
  337. 		uint32_t range = max - min;
  338. 		double factor = 255.0 / range;
  339. 		for( auto& p : pixels )
  340. 		{
  341. 			p.r -= min;
  342. 			p.g -= min;
  343. 			p.b -= min;
  344.  
  345. 			p *= factor;
  346. 		}
  347. 	}
  348.  
  349. 	std::vector<std::pair<int32_t,int32_t>> raw_line_pixels( int32_t x0, int32_t y0, int32_t x1, int32_t y1 ) const
  350. 	{
  351. 		std::vector<std::pair<int32_t,int32_t>> ret;
  352. 		const int32_t dx = std::abs(x1-x0);
  353. 		const int32_t dy = std::abs(y1-y0);
  354.  
  355. 		const int32_t sx = (x0<x1) ? 1 : -1;
  356. 		const int32_t sy = (y0<y1) ? 1 : -1;
  357.  
  358. 		int32_t err = dx-dy;
  359.  
  360. 		while(true)
  361. 		{
  362. 			ret.push_back({x0,y0});
  363. 			if( x0 == x1 && y0 == y1 ) break;
  364. 			int32_t e2 = 2*err;
  365.  
  366. 			if( e2 > -dy )
  367. 			{
  368. 				err -= dy;
  369. 				x0 += sx;
  370. 			}
  371. 			if( e2 < dx )
  372. 			{
  373. 				err += dx;
  374. 				y0 += sy;
  375. 			}
  376. 		}
  377. 		return ret;
  378. 	}
  379.  
  380. 	std::vector<pixel_type>& get_pixels( ) { return pixels; }
  381. 	const std::vector<pixel_type>& get_pixels( ) const { return pixels; }
  382. };
  383.  
  384. std::pair<size_t, size_t> load_bmp( const std::string& fname, bmp& bmap )
  385. {
  386. 	std::cout << "Loading " << fname << "..." << std::flush;
  387. 	std::ifstream in(fname);
  388. 	std::string p6;
  389. 	uint32_t xs;
  390. 	uint32_t ys;
  391. 	std::string cpp;
  392.  
  393. 	in >> p6;
  394. 	in >> ys;
  395. 	in >> xs;
  396. 	in >> cpp;
  397.  
  398. 	bmap = bmp(ys,xs);
  399.  
  400. 	char dummy;
  401. 	in.read(&dummy,1);
  402.  
  403. 	for (size_t i = 0; i < xs; ++i)
  404. 	{
  405. 		for (size_t j = 0; j < ys; ++j)
  406. 		{
  407. 			unsigned char r,g,b;
  408. 			in.read(reinterpret_cast<char*>(&r),1);
  409. 			in.read(reinterpret_cast<char*>(&g),1);
  410. 			in.read(reinterpret_cast<char*>(&b),1);
  411. 			bmap.raw(j,i) = {r,g,b};
  412. 		}
  413. 	}
  414.  
  415. 	std::cout << "done" << std::endl;
  416. 	return { ys, xs };
  417. }
  418.  
  419. size_t distance( ssize_t x0, ssize_t x1, ssize_t y0, ssize_t y1 )
  420. {
  421. 	ssize_t dx = x0-x1;
  422. 	ssize_t dy = y0-y1;
  423.  
  424. 	return dx*dx+dy*dy;
  425. }
  426.  
  427. ssize_t rgb_distance( ssize_t r0, ssize_t r1, ssize_t g0, ssize_t g1, ssize_t b0, ssize_t b1 )
  428. {
  429. 	ssize_t dr = r0-r1;
  430. 	ssize_t dg = g0-g1;
  431. 	ssize_t db = b0-b1;
  432.  
  433. 	return dr*dr+dg*dg+db*db;
  434. }
  435.  
  436.  
  437. struct environment
  438. {
  439. 	ssize_t x = 0;
  440. 	ssize_t y = 0;
  441.  
  442. 	size_t lines = 0;
  443.  
  444. 	// minimal line length (pixels squared)
  445. 	ssize_t m = 0;
  446. 	// maximum line length (pixels squared)
  447. 	ssize_t M = 1'000'000;
  448. };
  449.  
  450. struct line
  451. {
  452. 	int16_t x0 = 0;
  453. 	int16_t y0 = 0;
  454. 	int16_t x1 = 0;
  455. 	int16_t y1 = 0;
  456.  
  457. 	uint8_t r;
  458. 	uint8_t g;
  459. 	uint8_t b;
  460. 	uint8_t skip_next = 0;
  461. 	bool active = true;
  462. 	bool auto_deactivate = false;
  463.  
  464. 	static uint64_t count;
  465.  
  466. 	line( int x0_, int y0_, int x1_, int y1_, int r_, int g_, int b_ ) :
  467. 		x0(x0_),
  468. 		y0(y0_),
  469. 		x1(x1_),
  470. 		y1(y1_),
  471. 		r(r_),
  472. 		g(g_),
  473. 		b(b_)
  474. 	{
  475. 		count++;
  476. 	}
  477.  
  478. 	line( ) 
  479. 	{
  480. 		++count;
  481. 	}
  482.  
  483. 	line( const line& other ) :
  484. 		x0(other.x0),
  485. 		y0(other.y0),
  486. 		x1(other.x1),
  487. 		y1(other.y1),
  488. 		r(other.r),
  489. 		g(other.g),
  490. 		b(other.b),
  491. 		skip_next(other.skip_next),
  492. 		active(other.active),
  493. 		auto_deactivate(other.auto_deactivate)
  494. 	{
  495. 		++count;
  496. 	}
  497.  
  498. 	line( line&& other ) :
  499. 		x0(other.x0),
  500. 		y0(other.y0),
  501. 		x1(other.x1),
  502. 		y1(other.y1),
  503. 		r(other.r),
  504. 		g(other.g),
  505. 		b(other.b),
  506. 		skip_next(other.skip_next),
  507. 		active(other.active),
  508. 		auto_deactivate(other.auto_deactivate)
  509. 	{
  510. 		++count;
  511. 	}
  512.  
  513.  
  514. 	line& operator=( const line& other )
  515. 	{
  516. 		x0 = other.x0;
  517. 		y0 = other.y0;
  518. 		x1 = other.x1;
  519. 		y1 = other.y1;
  520. 		r = other.r;
  521. 		g = other.g;
  522. 		b = other.b;
  523. 		skip_next = other.skip_next;
  524. 		active = other.active;
  525. 		auto_deactivate = other.auto_deactivate;
  526. 		return *this;
  527. 	}
  528.  
  529. 	~line( )
  530. 	{
  531. 		--count;
  532. 	}
  533.  
  534. 	void randomize( const environment& env, const bmp& orig  )
  535. 	{
  536. 		static std::random_device rnd;
  537. 		static std::uniform_int_distribution<ssize_t> dist(0,255);
  538.  
  539. 		ssize_t d = 0;
  540.  
  541. //		r = g = b = 128;
  542. //		r = dist(rnd);
  543. //		g = dist(rnd);
  544. //		b = dist(rnd);
  545.  
  546. 		do
  547. 		{
  548.  
  549. 			x0 = rnd() % env.x;
  550. 			x1 = rnd() % env.x;
  551.  
  552. 			y0 = rnd() % env.y;
  553. 			y1 = rnd() % env.y;
  554.  
  555. 			d = distance( x0,x1,y0,y1);
  556. 		}
  557. 		while( d < env.m || d > env.M );
  558.  
  559. 		auto pixels = orig.raw_line_pixels( x0,y0,x1,y1 );
  560. 		size_t pr = 0;
  561. 		size_t pg = 0;
  562. 		size_t pb = 0;
  563.  
  564. 		for (size_t i = 0; i < pixels.size(); ++i)
  565. 		{
  566. 			pr += orig.raw(pixels[0].first,pixels[0].second).r;
  567. 			pg += orig.raw(pixels[0].first,pixels[0].second).g;
  568. 			pb += orig.raw(pixels[0].first,pixels[0].second).b;
  569. 		}
  570.  
  571. 		r = pr / pixels.size();
  572. 		g = pg / pixels.size();
  573. 		b = pb / pixels.size();
  574. 	}
  575.  
  576. 	void mutate( const environment& env )
  577. 	{
  578. 		static std::random_device rnd;
  579. 		static std::uniform_real_distribution<double> prob_dist(0,1);
  580. 		static std::uniform_int_distribution<ssize_t> dist(-10,10);
  581.  
  582. 		x0 += dist(rnd);
  583. 		x1 += dist(rnd);
  584. 		y0 += dist(rnd);
  585. 		y1 += dist(rnd);
  586.  
  587. 		x0 = std::max(int16_t(0),std::min(x0,int16_t(env.x-1)));
  588. 		x1 = std::max(int16_t(0),std::min(x1,int16_t(env.x-1)));
  589. 		y0 = std::max(int16_t(0),std::min(y0,int16_t(env.y-1)));
  590. 		y1 = std::max(int16_t(0),std::min(y1,int16_t(env.y-1)));
  591.  
  592. 		if( prob_dist(rnd) < 0.1 )
  593. 		{
  594. 			active = !active;
  595. 		}
  596. 		if( prob_dist(rnd) < 0.1 )
  597. 		{
  598. 			skip_next += dist(rnd);
  599. 		}
  600.  
  601. 		// let them do some wraparound
  602. 		r += dist(rnd);
  603. 		g += dist(rnd);
  604. 		b += dist(rnd);
  605.  
  606. 		ssize_t d = distance( x0, x1, y0, y1 );
  607.  
  608. 		auto_deactivate = ( d < env.m || d > env.M );
  609. 	}
  610.  
  611. 	bool is_active( ) const { return !auto_deactivate && active; }
  612. };
  613.  
  614. uint64_t line::count = 0;
  615.  
  616. struct chromo
  617. {
  618. 	std::vector<line> lines;
  619. 	// per line (and one for the probability itself)
  620. 	double mutation_probability = 0.00005;
  621.  
  622. 	// = 0 means "never calculated"
  623. 	size_t score = 0;
  624.  
  625. 	std::unique_ptr<chromo> mate( const chromo& other, const environment& env, bool clone )
  626. 	{
  627. 		static std::random_device rnd;
  628. 		static std::uniform_int_distribution<size_t> block_dist(1,5);
  629. 		static std::uniform_real_distribution<double> mut_dist(0,1);
  630. 		static std::uniform_real_distribution<double> mut_mut_dist(0.5,2);
  631.  
  632. 		std::unique_ptr<chromo> ret(new chromo);
  633. 		ret->mutation_probability = (other.mutation_probability + mutation_probability)/2.0;
  634. 		ret->lines.reserve(other.lines.size());
  635.  
  636. 		const std::vector<line>* src = &other.lines;
  637. 		for( size_t i = 0; i < src->size(); )
  638. 		{
  639. 			if( mut_dist(rnd) > 0.5 && !clone )
  640. 			{
  641. 				src = &other.lines;
  642. 			}
  643. 			else
  644. 			{
  645. 				src = &lines;
  646. 			}
  647. 			ssize_t block = block_dist(rnd);
  648. 			block = std::min( block, ssize_t(src->size()) - ssize_t(i) );
  649.  
  650. 			size_t copies = 1;
  651. 			double dr = mut_dist(rnd);
  652. 			if( dr < mutation_probability )
  653. 			{
  654. 				copies = 0;
  655. 			}
  656. 			else if( dr > (1-mutation_probability) )
  657. 			{
  658. 				copies = block_dist(rnd);
  659. 			}
  660.  
  661. 			for (size_t k = 0; k < copies; ++k)
  662. 			{
  663. 				for (ssize_t j = 0; j < block; ++j)
  664. 				{
  665. 					ret->lines.push_back( (*src)[i+j] );
  666. 					if( mut_dist(rnd) < mutation_probability )
  667. 					{
  668. 						ret->lines.back().mutate(env);
  669. 					}
  670. 				}
  671. 			}
  672. 			i += block;
  673. 		}
  674. 		ret->lines.resize(env.lines * ( 1 + (.2 * mut_dist(rnd))));
  675. 		if( mut_dist(rnd) < mutation_probability )
  676. 		{
  677. 			ret->mutation_probability *= mut_mut_dist(rnd);
  678. 		}
  679. 		return ret;
  680. 	}
  681. };
  682.  
  683.  
  684. void paint_remaining( const std::vector<line>& lines, bmp& bmap, size_t start )
  685. {
  686. 	for (size_t i = start; i < lines.size(); ++i)
  687. 	{
  688. 		if( lines[i].is_active() )
  689. 		{
  690. 			if( lines[i].skip_next > 0 )
  691. 			{
  692. 				i+= lines[i].skip_next;
  693. 				continue;
  694. 			}
  695. 			const auto& l = lines[i];
  696. 			bmap.raw_line(l.x0,l.y0,l.x1,l.y1,{l.r,l.g,l.b});
  697. 		}
  698. 	}
  699. }
  700.  
  701. void paint( const std::vector<line>& lines, bmp& bmap )
  702. {
  703. 	bmap.fill({255,255,255});
  704.  
  705. 	for (size_t i = 0; i < lines.size(); ++i)
  706. 	{
  707. 		if( lines[i].is_active() )
  708. 		{
  709. 			if( lines[i].skip_next > 0 )
  710. 			{
  711. 				i+= lines[i].skip_next;
  712. 				continue;
  713. 			}
  714. 			const auto& l = lines[i];
  715. 			bmap.raw_line(l.x0,l.y0,l.x1,l.y1,{l.r,l.g,l.b});
  716. 		}
  717. 	}
  718. }
  719.  
  720.  
  721. void paint( const chromo& chr, bmp& bmap )
  722. {
  723. 	paint(chr.lines,bmap);
  724. }
  725.  
  726. void paint_layers( const std::vector<line>& lines, bmp& bmap )
  727. {
  728. 	bmap.fill({0,0,0});
  729.  
  730. 	for (size_t i = 0; i < lines.size(); ++i)
  731. 	{
  732. 		if( lines[i].is_active() )
  733. 		{
  734. 			if( lines[i].skip_next > 0 )
  735. 			{
  736. 				i+= lines[i].skip_next;
  737. 				continue;
  738. 			}
  739. 			const auto& l = lines[i];
  740. 			auto pixels = bmap.raw_line_pixels(l.x0,l.y0,l.x1,l.y1);
  741. 			for( auto& p : pixels )
  742. 			{
  743. 				bmap.raw(p.first,p.second) += bmp::pixel_type(2,2,2);
  744.  
  745. 			}
  746. 		}
  747. 	}
  748. }
  749.  
  750. void paint_layers( const chromo& chr, bmp& bmap )
  751. {
  752. 	paint_layers( chr.lines, bmap );
  753. }
  754.  
  755. template<class PX>
  756. ssize_t generate_score( const std::vector<PX>& a, const std::vector<PX>& b )
  757. {
  758. 	ssize_t score = 0;
  759. 	for (size_t i = 0; i < a.size(); ++i)
  760. 	{
  761. 		score += rgb_distance( a[i].r, b[i].r, a[i].g, b[i].g, a[i].b, b[i].b );
  762. 	}
  763. 	return score;
  764. }
  765.  
  766. ssize_t evaluate( const std::vector<line>& lines, const bmp& orig )
  767. {
  768. 	ssize_t score = 0;
  769.  
  770. 	bmp bmap(orig);
  771.  
  772. 	const auto& op = orig.get_pixels();
  773. 	const auto& np = bmap.get_pixels();
  774.  
  775. 	paint(lines,bmap);
  776.  
  777. 	for (size_t i = 0; i < op.size(); ++i)
  778. 	{
  779. 		score += rgb_distance( op[i].r, np[i].r, op[i].g, np[i].g, op[i].b, np[i].b );
  780. 	}
  781. 	return score;
  782. }
  783.  
  784. ssize_t evaluate( const chromo& chr, const bmp& orig )
  785. {
  786. 	if( chr.score != 0 ) return chr.score;
  787. 	ssize_t score = evaluate(chr.lines,orig);
  788. 	return score;
  789. }
  790.  
  791. void seed( const bmp& /*orig*/, const std::vector<line>& proto_lines, std::vector<std::unique_ptr<chromo>>& population, size_t individuals, size_t /*linelength*/, const environment& env )
  792. {
  793. 	std::cout << "Start seeding out of " << proto_lines.size() << " proto lines ..." << std::flush;
  794. 	population.reserve(individuals);
  795.  
  796. 	std::unique_ptr<chromo> ni( new chromo);
  797. 	ni->lines.reserve(proto_lines.size());
  798. 	for (size_t i = 0; i < proto_lines.size(); ++i)
  799. 	{
  800. 		ni->lines.push_back(proto_lines[i]);
  801. 	}
  802.  
  803. 	population.emplace_back( new chromo(*ni) );
  804. 	for (size_t i = 1; i < individuals; ++i)
  805. 	{
  806. 		// some bad clones
  807. 		population.emplace_back(  ni->mate(*population[i-1],env,true) );
  808. 	}
  809. 	std::cout << "done" << std::endl;
  810. }
  811.  
  812.  
  813. void evolve( const std::string& fname, const std::vector<line>& proto_lines )
  814. {
  815. 	bmp orig(1,1);
  816. 	size_t x;
  817. 	size_t y;
  818. 	std::tie(x,y) = load_bmp( fname, orig );
  819.  
  820. 	environment env;
  821. 	env.x = x;
  822. 	env.y = y;
  823.  
  824. //	env.lines = 0.25*x*y;
  825. 	env.lines = 0.3*x*y;
  826.  
  827. 	env.m = 10*10;
  828. 	env.M = 50*50;
  829.  
  830. 	std::vector<std::unique_ptr<chromo>> population;
  831. 	const size_t individuals = 400;
  832.  
  833. 	seed(orig, proto_lines, population,10,env.lines,env);
  834.  
  835. 	const size_t generations = 100000;
  836. 	const size_t reproducers = 10;
  837. 	const size_t kidnum = 10;
  838. 	const size_t clones = 10;
  839.  
  840. 	std::cout << "Target line amount is " << env.lines << "\n";
  841. 	for (size_t j = 0; j < generations; ++j)
  842. 	{
  843. 		std::cout << "Evaluating up to " << population.size() << " individuals..." << std::flush;
  844. 		double score = 0.0;
  845. 		for (size_t i = 0; i < population.size(); ++i)
  846. 		{
  847. 			population[i]->score = evaluate(*population[i],orig);
  848. 			score += population[i]->score;
  849. 		}
  850. 		score /= population.size();
  851. 		std::cout << "done\n";
  852. 		std::cout << "Average score "<< score << "\n",
  853. 		std::cout << "Sorting them..." << std::flush;
  854. 		std::sort(population.begin(), population.end(), []( auto& l, auto& r ) { return l->score < r->score; } );
  855.  
  856. 		population.resize(std::min(population.size(),individuals));
  857. 		std::cout << "done" << std::endl;
  858.  
  859. 		static chromo* last_painted = nullptr;
  860.  
  861. 		if( last_painted != population[0].get() )
  862. 		{
  863. 			last_painted = population[0].get();
  864. 			std::ostringstream on;
  865. 			on << "generation_" << std::setw(5) << std::setfill('0') << j << ".bmp";
  866.  
  867. 			bmp b(x,y);
  868. 			paint(*population[0],b);
  869. 			b.write(on.str());
  870. 			paint_layers(*population[0],b);
  871. 			b.max_contrast_all();
  872. 			b.write("layers_" + on.str());
  873. 		}
  874. 		std::cout << "At generation " << j << " we have " << line::count << " lines (" << double(line::count)/population.size() << " per chromo)\n";
  875.  
  876. 		std::vector<std::unique_ptr<chromo>> kids;
  877. 		std::cout << "Running " << reproducers << " reproduction cycles..." << std::flush;
  878.  
  879. 		for (size_t i = 0; i < reproducers; ++i )
  880. 		{
  881. 			for (size_t k = 0; k < kidnum; ++k)
  882. 			{
  883. 				kids.push_back( population[i]->mate(*random_element(population),env,false ));
  884. 			}
  885. 			for (size_t k = 0; k < clones; ++k)
  886. 			{
  887. 				kids.push_back( population[i]->mate(*population[0],env,true ));
  888. 			}
  889. 		}
  890. 		std::cout << "done\n";
  891. 		std::cout << "Merging " << kids.size() << " offsprings..." << std::flush;
  892. 		population.reserve( population.size() + kids.size() );
  893. 		for (size_t i = 0; i < kids.size(); ++i)
  894. 		{
  895. 			population.push_back( std::move(kids[i]));
  896. 		}
  897. 		std::cout << "done" << std::endl;
  898. 	}
  899. }
  900.  
  901.  
  902. std::pair<bmp,std::vector<line>>  paint_useful( const bmp& orig, bmp& clone, std::vector<line>& retlines, bmp& layer, const std::string& outprefix, size_t x, size_t y )
  903. {
  904. 	const size_t pixels = (x*y);
  905. 	const size_t lines = 0.3*pixels;
  906. //	const size_t lines = 10000;
  907.  
  908. //	const size_t start_accurate_color = lines/4;
  909.  
  910. 	std::random_device rnd;
  911.  
  912. 	std::uniform_int_distribution<size_t> distx(0,x-1);
  913. 	std::uniform_int_distribution<size_t> disty(0,y-1);
  914. 	std::uniform_int_distribution<size_t> col(-15,15);
  915. 	std::uniform_int_distribution<size_t> acol(0,255);
  916.  
  917. 	const ssize_t m = 1*1;
  918. 	const ssize_t M = 50*50;
  919.  
  920. 	retlines.reserve( lines );
  921.  
  922. 	for (size_t i = retlines.size(); i < lines; ++i)
  923. 	{
  924. 		size_t x0;
  925. 		size_t x1;
  926.  
  927. 		size_t y0;
  928. 		size_t y1;
  929.  
  930. 		size_t dist = 0;
  931. 		do
  932. 		{
  933. 			x0 = distx(rnd);
  934. 			x1 = distx(rnd);
  935.  
  936. 			y0 = disty(rnd);
  937. 			y1 = disty(rnd);
  938.  
  939. 			dist = distance(x0,x1,y0,y1);
  940. 		}
  941. 		while( dist > M || dist < m );
  942.  
  943. 		std::vector<std::pair<int32_t,int32_t>> points = clone.raw_line_pixels(x0,y0,x1,y1);
  944.  
  945. 		ssize_t r = 0;
  946. 		ssize_t g = 0;
  947. 		ssize_t b = 0;
  948.  
  949. 		for (size_t i = 0; i < points.size(); ++i)
  950. 		{
  951. 			r += orig.raw(points[i].first,points[i].second).r;
  952. 			g += orig.raw(points[i].first,points[i].second).g;
  953. 			b += orig.raw(points[i].first,points[i].second).b;
  954. 		}
  955.  
  956. 		r += col(rnd);
  957. 		g += col(rnd);
  958. 		b += col(rnd);
  959.  
  960. 		r /= points.size();
  961. 		g /= points.size();
  962. 		b /= points.size();
  963.  
  964. 		r %= 255;
  965. 		g %= 255;
  966. 		b %= 255;
  967.  
  968. 		r = std::max(ssize_t(0),r);
  969. 		g = std::max(ssize_t(0),g);
  970. 		b = std::max(ssize_t(0),b);
  971.  
  972. //		r = acol(rnd);
  973. //		g = acol(rnd);
  974. //		b = acol(rnd);
  975.  
  976. //		if( i > start_accurate_color )
  977. 		{
  978. 			ssize_t dp = 0; // accumulated distance of new color to original
  979. 			ssize_t dn = 0; // accumulated distance of current reproduced to original
  980. 			for (size_t i = 0; i < points.size(); ++i)
  981. 			{
  982. 				dp += rgb_distance(
  983. 										orig.raw(points[i].first,points[i].second).r,r,
  984. 										orig.raw(points[i].first,points[i].second).g,g,
  985. 										orig.raw(points[i].first,points[i].second).b,b
  986. 									);
  987.  
  988. 				dn += rgb_distance(
  989. 										clone.raw(points[i].first,points[i].second).r,orig.raw(points[i].first,points[i].second).r,
  990. 										clone.raw(points[i].first,points[i].second).g,orig.raw(points[i].first,points[i].second).g,
  991. 										clone.raw(points[i].first,points[i].second).b,orig.raw(points[i].first,points[i].second).b
  992. 									);
  993.  
  994. 			}
  995.  
  996. 			if( dp > dn ) // the distance to original is bigger, use the new one
  997. 			{
  998. 				--i;
  999. 				continue;
  1000. 			}
  1001. 			// also abandon if already too bad
  1002. //			if( dp > 100000 )
  1003. //			{
  1004. //				--i;
  1005. //				continue;
  1006. //			}
  1007. 		}
  1008.  
  1009. 		layer.raw_line_add(x0,y0,x1,y1,{1u,1u,1u});
  1010. 		clone.raw_line(x0,y0,x1,y1,{(uint32_t)r,(uint32_t)g,(uint32_t)b});
  1011. 		retlines.push_back({ (int)x0,(int)y0,(int)x1,(int)y1,(int)r,(int)g,(int)b});
  1012.  
  1013. 		static time_t last = 0;
  1014. 		time_t now = time(0);
  1015. 		if( i % (lines/100) == 0 )
  1016. 		{
  1017. 			std::ostringstream fn;
  1018. 			fn << outprefix + "perc_" << std::setw(3) << std::setfill('0') << (i/(lines/100)) << ".bmp"; 
  1019. 			clone.write(fn.str());
  1020. 			bmp lc(layer);
  1021. 			lc.max_contrast_all();
  1022. 			lc.write(outprefix + "layer_" + fn.str());
  1023. 		}
  1024.  
  1025. 		if( (now-last) > 10 )
  1026. 		{
  1027. 			last = now;
  1028. 			static int st = 0;
  1029. 			std::ostringstream fn;
  1030. 			fn << outprefix + "inter_" << std::setw(8) << std::setfill('0') << i << ".bmp";
  1031. 			clone.write(fn.str());
  1032.  
  1033. 			++st;
  1034. 		}
  1035. 	}
  1036. 	clone.write(outprefix + "clone.bmp");
  1037. 	return { clone, retlines };
  1038. }
  1039.  
  1040.  
  1041. void erase_bad( std::vector<line>& lines, const bmp& orig )
  1042. {
  1043. 	ssize_t current_score = evaluate(lines,orig);
  1044.  
  1045. 	std::vector<line> newlines(lines);
  1046.  
  1047. 	uint32_t deactivated = 0;
  1048. 	std::cout << "current_score = " << current_score << "\n";
  1049. 	for (size_t i = 0; i < newlines.size(); ++i)
  1050. 	{
  1051. 		newlines[i].active = false;
  1052. 		ssize_t score = evaluate(newlines,orig);
  1053. 		if( score > current_score )
  1054. 		{
  1055. 			newlines[i].active = true;
  1056. 		}
  1057. 		else
  1058. 		{
  1059. 			current_score = score;
  1060. 			++deactivated;
  1061. 		}
  1062. 		if( i % 1000 == 0 )
  1063. 		{
  1064. 			std::ostringstream fn;
  1065. 			fn << "erase_" << std::setw(6) << std::setfill('0') << i << ".bmp";
  1066. 			bmp tmp(orig);
  1067. 			paint(newlines,tmp);
  1068. 			tmp.write(fn.str());
  1069. 			paint_layers(newlines,tmp);
  1070. 			tmp.max_contrast_all();
  1071. 			tmp.write("layers_" + fn.str());
  1072. 			std::cout << "\r i = " << i << std::flush;
  1073. 		}
  1074. 	}
  1075. 	std::cout << "\n";
  1076. 	std::cout << "current_score = " << current_score << "\n";
  1077. 	std::cout << "deactivated = " << deactivated << "\n";
  1078.  
  1079.  
  1080. 	bmp tmp(orig);
  1081.  
  1082. 	paint(newlines,tmp);
  1083. 	tmp.write("newlines.bmp");
  1084. 	lines.clear();
  1085. 	for (size_t i = 0; i < newlines.size(); ++i)
  1086. 	{
  1087. 		if( newlines[i].is_active() )
  1088. 		{
  1089. 			lines.push_back(newlines[i]);
  1090. 		}
  1091. 	}
  1092. }
  1093.  
  1094. std::pair<bmp,std::vector<line>>  try_ggate( const std::string& fname )
  1095. {
  1096. 	bmp orig(100,100);
  1097. 	size_t x,y;
  1098.  
  1099. 	std::tie(x,y) = load_bmp(fname,orig);
  1100. 	orig.write("orig.bmp");
  1101.  
  1102. 	size_t ir = 0;
  1103. 	size_t ig = 0;
  1104. 	size_t ib = 0;
  1105. 	for( auto& p : orig.get_pixels() )
  1106. 	{
  1107. 		ir += p.r;
  1108. 		ig += p.g;
  1109. 		ib += p.b;
  1110. 	}
  1111. 	ir /= orig.get_pixels().size();
  1112. 	ig /= orig.get_pixels().size();
  1113. 	ib /= orig.get_pixels().size();
  1114.  
  1115. 	bmp clone(orig);
  1116. //	clone.fill({255,255,255});
  1117. 	clone.fill({(uint32_t)ir,(uint32_t)ig,(uint32_t)ib});
  1118.  
  1119. 	bmp layer(x,y);
  1120. 	layer.fill({0,0,0});
  1121. 	std::vector<line> retlines;
  1122. 	stop_watch sw;
  1123.  
  1124. 	sw.start();
  1125. 	paint_useful( orig, clone, retlines, layer, "standard_", x, y );
  1126. 	sw.stop();
  1127. 	std::cout << "Initial distribution took " << sw.get_seconds_r() << "s to write " << retlines.size() << " lines \n";
  1128. 	sw.start();
  1129. 	erase_bad(retlines,orig);
  1130. 	sw.stop();
  1131. 	std::cout << "Removing unnecessary took " << sw.get_seconds_r() << " and left us with " << retlines.size() <<" lines \n";
  1132.  
  1133. 	sw.start();
  1134. 	paint_useful( orig, clone, retlines, layer, "second_", x, y );
  1135. 	sw.stop();
  1136. 	std::cout << "Second layer of useful lines took " << sw.get_seconds_r() << " and we now have " << retlines.size() <<" lines \n";
  1137.  
  1138. 	return { clone, retlines };
  1139. }
  1140.  
  1141. int main(int argc, const char *argv[])
  1142. {
  1143. 	std::string f = "ggate.ppm";
  1144.  
  1145. 	if( argc > 1 )
  1146. 	{
  1147. 		f = argv[1];
  1148. 	}
  1149.  
  1150. 	stop_watch sw;
  1151.  
  1152. 	std::vector<std::tuple<double,double,double>> allpixels;
  1153.  
  1154. 	const size_t num = 1;
  1155. 	bmp b(1,1);
  1156. 	std::vector<line> lines;
  1157. 	for (size_t i = 0; i < num; ++i)
  1158. 	{
  1159. 		std::tie( b, lines ) = try_ggate(f);
  1160.  
  1161. 		if( allpixels.empty() )
  1162. 		{
  1163. 			allpixels.resize(b.get_pixels().size(),std::make_tuple(0.0,0.0,0.0));
  1164. 		}
  1165. 		for (size_t j = 0; j < b.get_pixels().size(); ++j)
  1166. 		{
  1167. 			std::get<0>(allpixels[j]) += b.get_pixels()[j].r;
  1168. 			std::get<1>(allpixels[j]) += b.get_pixels()[j].g;
  1169. 			std::get<2>(allpixels[j]) += b.get_pixels()[j].b;
  1170. 		}
  1171. 		evolve(f,lines);
  1172. 	}
  1173. 	for (size_t i = 0; i < allpixels.size(); ++i)
  1174. 	{
  1175. 		b.get_pixels()[i].r = std::get<0>(allpixels[i]) / num;
  1176. 		b.get_pixels()[i].g = std::get<1>(allpixels[i]) / num;
  1177. 		b.get_pixels()[i].b = std::get<2>(allpixels[i]) / num;
  1178. 	}
  1179. 	b.write("merged.bmp");
  1180. }
  1181.  
  1182.  
  1183. bmp_stream::bmp_stream( size_t x, size_t y, const std::string& fname ) :
  1184. 	xres(x),
  1185. 	yres(y),
  1186. 	rowpos(0),
  1187. 	pixels(0)
  1188. {
  1189. 	out.open(fname.c_str());
  1190. 	if(!out)
  1191. 	{
  1192. 		throw std::runtime_error("Could not open " + fname);
  1193. 	}
  1194. 	create_header(x,y,24); // 8 bit per pixel per color
  1195. }
  1196.  
  1197. bmp_stream::~bmp_stream( )
  1198. {
  1199. 	// pad the rest of the file with black pixels
  1200. 	while( pixels < (xres*yres) )
  1201. 	{
  1202. 		add_pixel(0,0,0);
  1203. 	}
  1204. 	flush();
  1205. //	out.write(&buffer[0],buffer.size());
  1206. }
  1207.  
  1208. void bmp_stream::add_pixel( int r, int g, int b )
  1209. {
  1210. 	++pixels;
  1211. 	++rowpos;
  1212.  
  1213. 	unsigned char col[3];
  1214. 	col[0] = b;
  1215. 	col[1] = g;
  1216. 	col[2] = r;
  1217. 	buffer.insert(buffer.end(),{ (char)col[0], (char)col[1], (char)col[2] });
  1218. //	out.write(reinterpret_cast<const char*>(col),3);
  1219.  
  1220. 	if( rowpos == xres )
  1221. 	{
  1222. 		// the position in the row means we are finished with the row. Close it
  1223. 		// by rounding its bytes up to 4-byte boundary and start with the next
  1224. 		// row
  1225. 		rowpos = 0;
  1226. 		char dummy = 0xcc;
  1227. 		switch( xres*3 % 4 )
  1228. 		{
  1229. 			case 1:
  1230. 				buffer.push_back(dummy);
  1231. //				write(dummy);
  1232. 			case 2:
  1233. 				buffer.push_back(dummy);
  1234. //				write(dummy);
  1235. 			case 3:
  1236. 				buffer.push_back(dummy);
  1237. //				write(dummy);
  1238. 			case 0:
  1239. 			default:
  1240. 				break;
  1241. 		}
  1242. 	}
  1243. }
  1244.  
  1245. void bmp_stream::create_header( size_t _x, size_t _y, int bpp )
  1246. {
  1247. 	// BMP Header
  1248. 	const char magic[] = { 'B', 'M' };
  1249. 	write(magic,2);
  1250. 	// XXX (#31) approximation, must be corrected by header and stuff
  1251. 	uint32_t fsize = _x*_y*(bpp/8) + 0x100;
  1252. 	write(fsize);
  1253. 	// write 2 times 2 implementation defined bytes
  1254. 	write(magic,2);
  1255. 	write(magic,2);
  1256.  
  1257. 	// beginning of the actual bitmap data...
  1258. 	uint32_t start = 0x100;
  1259. 	write(start);
  1260.  
  1261. 	// DIB Header
  1262. 	uint32_t hsize = 40; // as defined by the format
  1263. 	write(hsize);
  1264.  
  1265. 	int32_t x = _x;
  1266. 	int32_t y = - _y;
  1267. 	write(x);
  1268. 	write(y);
  1269. 	int16_t colplanes = 1; // fixed by the format
  1270. 	write(colplanes);
  1271. 	uint16_t bitdepth = bpp;
  1272. 	write(bitdepth);
  1273. 	uint32_t compmethod = 0; // no compression
  1274. 	write(compmethod);
  1275. 	uint32_t rawbmpsize = (x+1)*y*3;
  1276. 	write(rawbmpsize);
  1277. 	int32_t hres = 240;
  1278. 	int32_t vres = 240;
  1279. 	write(hres);
  1280. 	write(vres);
  1281. 	int32_t colpal = 0;
  1282. 	write(colpal);
  1283. 	write(colpal);
  1284. 	char dummy[0x100] = { 0 };
  1285. 	size_t padbytes = 0x100 - buffer.size();//out.tellp();
  1286. //	out.write(dummy,padbytes);
  1287. 	write(dummy,padbytes);
  1288. 	buffer.reserve(1.1*_x*_y+buffer.size());
  1289. }
  1290.  
  1291. bmp::bmp ( size_t xs, size_t ys, const pixel_type& proto ) :
  1292. 	xdim(xs),
  1293. 	ydim(ys)
  1294. {
  1295. 	pixels.resize(xdim*ydim,proto);
  1296. }
  1297.  
  1298. void bmp::write( const std::string& fname ) const
  1299. {
  1300. 	bmp_stream bs(xdim,ydim,fname);
  1301. 	for( size_t i = 0; i < pixels.size(); i++)
  1302. 	{
  1303. 		const pixel_type& pix = pixels[i];
  1304. 		bs.add_pixel( pix.r, pix.g, pix.b );
  1305. 	}
  1306. }
  1307.  
  1308. // vim: tabstop=4 shiftwidth=4 noexpandtab
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Z2P6Ls
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!