SHARE
TWEET

Untitled

a guest Aug 24th, 2013 117 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdint>
  2. #include <vector>
  3. #include <cstdlib>
  4. #include <iostream>
  5. #include <time.h>
  6. #include <thread>
  7. #include <cassert>
  8.  
  9. const uint32_t TILE_DIM = 50;
  10. const uint32_t WIDMIN = 2;
  11. const uint32_t RESTWIDMAX = 8;
  12. const uint32_t NUM_LEVS = 800;
  13. const uint32_t NUM_THREADS = 4;
  14. const uint32_t NUM_LEVS_PER_THREAD = NUM_LEVS / NUM_THREADS;
  15.  
  16. struct GenRandGenerator {
  17.     uint32_t operator()( uint32_t & gen ) {
  18.         gen += gen;
  19.         gen ^= 1;
  20.         int32_t tgen=gen;
  21.         if ( tgen < 0) {
  22.             gen ^= 0x88888eef;
  23.         }
  24.         return gen;
  25.     }
  26. };
  27.  
  28. struct Tile {
  29.     uint32_t X, Y;
  30.     bool T;
  31. };
  32.  
  33. struct Room {
  34.     Room(uint32_t x, uint32_t y, uint32_t w, uint32_t h, uint32_t roomNum)
  35.         : x(x), y(y), w(w), h(h), roomNum(roomNum) { }
  36.  
  37.     uint32_t x, y, w, h, roomNum;
  38. };
  39.  
  40. struct Level {
  41.     Level() : tiles( 2500 ) {
  42.         for( uint32_t t = 0 ; t < 2500 ; t++ ) {
  43.             tiles[t].X = t % TILE_DIM;
  44.             tiles[t].Y = t / TILE_DIM;
  45.             tiles[t].T = false;
  46.         }
  47.         rooms.reserve( 100 );
  48.     }
  49.  
  50.     void fillTiles() {
  51.         for( const Room & r : rooms ) {
  52.             for( uint32_t yi = r.y ; yi <= ( r.y + r.h ) ; ++yi ) {
  53.                 for( uint32_t xi = r.x ; xi <= ( r.x + r.w ) ; ++xi ) {
  54.                     tiles[ yi * TILE_DIM + xi ].T = true;
  55.                 }
  56.             }
  57.         }
  58.     }
  59.  
  60.     std::vector<Tile> tiles;
  61.     std::vector<Room> rooms;
  62. };
  63.  
  64. class OcclusionBuffer{
  65.     std::vector<uint8_t> buffer;
  66.     int width;
  67.     int height;
  68. public:
  69.     OcclusionBuffer(int w, int h)
  70.     :buffer(w*h), width(w), height(h){
  71.        
  72.     };
  73.    
  74.     bool IsOccluded(int minx, int miny, int maxx, int maxy){
  75.         int      line   = maxx-minx+1;
  76.         int      lines  = maxy-miny+1;
  77.         int      stride = width-line;
  78.         uint8_t* p      = buffer.data()+minx+width*miny;
  79.        
  80.         // test region if any point is marked
  81.         while(lines--){
  82.             int templine = line;
  83.             while(templine--){
  84.                 if (*p)
  85.                     return true;
  86.                 p++;
  87.             }
  88.             p+=stride;
  89.         }
  90.         return false;
  91.     }
  92.    
  93.     void Occlude(int minx, int miny, int maxx, int maxy){
  94.         int      line   = maxx-minx+1;
  95.         int      lines  = maxy-miny+1;
  96.         int      stride = width-line;
  97.         uint8_t* p      = buffer.data()+minx+width*miny;
  98.        
  99.         //mark region
  100.         while(lines--){
  101.             int templine = line;
  102.             while(templine--){
  103.                 *p = 1;
  104.                 p++;
  105.             }
  106.             p+=stride;
  107.         }
  108.     }
  109.    
  110.     void Clear(){
  111.         memset(buffer.data(), 0, width*height);
  112.     }
  113. };
  114.  
  115. template <typename RandomGenerator>
  116. class LevelGenerator {
  117.     bool makeRoomSilentlyFail( Level & level, uint32_t & gen, OcclusionBuffer& occ ) {
  118.         uint32_t x( nextRandomGenerator_( gen ) % TILE_DIM );
  119.         uint32_t y( nextRandomGenerator_( gen ) % TILE_DIM );
  120.         uint32_t w( (nextRandomGenerator_( gen ) % RESTWIDMAX) + WIDMIN );
  121.         uint32_t h( (nextRandomGenerator_( gen ) % RESTWIDMAX) + WIDMIN );
  122.  
  123.         if( (x+w) < TILE_DIM-1 && (y+h) < TILE_DIM-1 && x != 0 && y != 0 &&
  124.             !isCollision( x, y, w, h, occ ) ) {
  125.                 occ.Occlude(x, y, x+w, y+h);
  126.                 level.rooms.emplace_back(x, y, w, h, (uint32_t)(level.rooms.size() + 1));
  127.                 return true;
  128.         }
  129.         return false;
  130.     }
  131.  
  132.     static bool isCollision(const uint32_t x,
  133.                       const uint32_t y, const uint32_t w, const uint32_t h, OcclusionBuffer &occ ) {
  134.         return occ.IsOccluded(x-1, y-1, x+w+1, y+h+1);
  135.     }
  136.     RandomGenerator nextRandomGenerator_;
  137.     std::vector<Level> levels_;
  138.    
  139. public:
  140.     LevelGenerator( RandomGenerator randomGenerator, const uint32_t numLevels ) :
  141.         nextRandomGenerator_( randomGenerator ), levels_( numLevels, Level() ) {}
  142.  
  143.     void partitionedGenerateLevels( uint32_t seed, const uint32_t partitionStartIndex,
  144.                                     const uint32_t partitionEndIndex ) {
  145.         OcclusionBuffer occ(TILE_DIM, TILE_DIM);
  146.         for( uint32_t i = partitionStartIndex ; i < partitionEndIndex ; ++i ) {
  147.             occ.Clear();
  148.             uint32_t roomsAdded = 0;
  149.             for( uint32_t ii = 0 ; ii < 50000 ; ii++ ) {
  150.                 roomsAdded += static_cast<size_t>(makeRoomSilentlyFail( levels_[i], seed, occ ));
  151.                 if (roomsAdded == 99) break;
  152.             }
  153.             levels_[i].fillTiles();
  154.         }
  155.     }
  156.  
  157.     template <typename LevelMetric>
  158.     Level & pickLevelByCriteria( LevelMetric levelMetric ) {
  159.         auto lIter = levels_.begin(), lEnd = levels_.end();
  160.         Level * result( &*lIter++ );
  161.         for( ; lIter != lEnd ; ++lIter ) {
  162.             if( levelMetric.isBetterLevel( *result, *lIter ) ) {
  163.                 result = &*lIter;
  164.             }
  165.         }
  166.         return *result;
  167.     }
  168. };
  169.  
  170. struct NumRoomsMetric {
  171.     bool isBetterLevel( const Level & x, const Level & y ) {
  172.         return y.rooms.size() > x.rooms.size();
  173.     }
  174. };
  175.  
  176. void printLevel( const Level & level ) {
  177.     for( uint32_t i = 0 ; i < 2500 ; i++ ) {
  178.         std::cout <<  (level.tiles[i].T ? 1 : 0 );
  179.         if( i % ( TILE_DIM ) == 49 && i != 0 ) std::cout << std::endl;
  180.     }
  181. }
  182.  
  183. int main(int argc, char* argv[]) {
  184.     clock_t start, stop;
  185.     start = clock();
  186.     //int v = atoi(argv[1]);
  187.     int v = 10; // nicer for IDE/Profiler
  188.     std::cout << "The random seed is: " << v << std::endl;
  189.     srand(v);
  190.  
  191.     GenRandGenerator randGenerator;
  192.     LevelGenerator<GenRandGenerator> levelGenerator( randGenerator, NUM_LEVS );
  193.  
  194.     std::vector<std::thread> threads; threads.reserve( NUM_THREADS );
  195.     for( uint32_t i = 0 ; i < NUM_THREADS ; ++i ) {
  196.         uint32_t threadSeed = v * ((i+1)*(i+1));
  197.         std::cout << "The seed of thread " << i << " is: " << threadSeed << std::endl;
  198.         uint32_t partitionStartIndex( i * NUM_LEVS_PER_THREAD );
  199.         uint32_t partitionEndIndex( partitionStartIndex + NUM_LEVS_PER_THREAD );
  200.         threads.emplace_back(std::bind( &LevelGenerator<GenRandGenerator>::partitionedGenerateLevels,
  201.                            &levelGenerator, threadSeed, partitionStartIndex, partitionEndIndex ));
  202.     }
  203.  
  204.     for( uint32_t i = 0 ; i < NUM_THREADS ; ++i ) {
  205.         threads[i].join();
  206.     }
  207.     NumRoomsMetric numRoomsMetric;
  208.     Level & l( levelGenerator.pickLevelByCriteria( numRoomsMetric ) );
  209.     printLevel( l );
  210.  
  211.     stop = clock();
  212.     long clocks_per_ms = CLOCKS_PER_SEC/1000;
  213.     std::cout << (stop - start)/clocks_per_ms << std::endl;
  214.     return 0;
  215. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top