L3DT users' community
Large 3D terrain generator

Wang Tiling Generator

Correspondence concerning plugins and scripts; development, use, bugs and ideas.

Wang Tiling Generator

Postby David Walters » Thu Apr 30, 2009 12:20 am

I've spent the last few hours experimenting with ZeoScript. My goal was to implement a Wang tiling generator as per this paper:
http://research.microsoft.com/en-us/um/people/cohen/WangFinal.pdf

I was successful and you can download it from here. I learned a lot about ZeoScript and it's not a bad little language 8)
The script takes the dimensions of the design map and generates a grid of tiles as per the 8-tile system described in the paper. It then writes out the data to disk as a stream of bytes.

One really big problem emerged from doing this though: There doesn't appear to be any kind of 'random' function - so at the moment the script will always generate the same tiling - and it's slow and messy to generate such a number in script anyway. Please can you expose some kind of 'rand' native call!

Hope this comes in handy for someone :)
David Walters
Doyen
 
Posts: 128
Joined: Fri Apr 24, 2009 1:10 pm

Postby Aaron » Thu Apr 30, 2009 10:40 pm

Hi David,

Bravo. That's one impressive script. I'd also like to thank you for introducing me to Wang tiling. Having just skim-read this and a few other papers on the subject, I'm already getting ideas about implementing this in L3DT's texture generator to reduce texture periodicity artefacts. Can I ask what your intended application is for the output?

Anyway, as per your request, I've added some random number functions to ZeoScript, including the usual 'rand' and 'srand'*, plus 'frand' for floating point random numbers between -1 and 1, and 'absrand' for floating point numbers between 0 and 1.

You can download the updated plugin from here:

http://www.bundysoft.com/wiki/doku.php? ... :zeoscript

To install, simply extract the extension from the zip archive, and copy it over the existing ZeoScript plugin in the 'extensions' directory in L3DT's install path.

Best regards,
Aaron.

* You don't generally need to call srand to seed the random number generator, as L3DT does this on initialisation. However, it may be of use if you want a reproducible pseudorandom sequence.
User avatar
Aaron
Site Admin
 
Posts: 3691
Joined: Sun Nov 20, 2005 2:41 pm
Location: Melbourne, Australia

Postby David Walters » Fri May 01, 2009 2:54 pm

aaron wrote:Bravo. That's one impressive script

Thank you very much, and also thanks for adding the 'rand' function so quickly! I've uploaded a new version of my script which uses this function - and also I've added a ton of comments to the code which hopefully makes it all a bit clearer what the tables are for, etc.

http://hidden.asbestos.googlepages.com/WangTiles.zs

I think I'd improve this script a little more by basing the tile area on the size of the heightmap - and asking for a Wang:HM ratio. Not sure how best to solve this problem, but using the design map ratio doesn't seem like a natural correspondence. I guess with a script you can edit it locally to suit your needs :)

aaron wrote:Can I ask what your intended application is for the output?

Well it's a bit backwards in a way as I've worked with this algorithmn before. At work, we were making a terrain based racing game for PSP (unreleased) and wanted a way to texture a terrain with a small memory overhead on the low res display. The algorithm offered a good solution to both limitations because the aperiodic tiling made it quick to mark an area of tiles as "grass" without having to spend any more time on it. Additionally at long distances, where mipmapping reduced tiles to very small visible pixel counts, the tiling helped to reduce any Moire patterns a little bit.

Our code generated terrain patches for the surrounding area from a low frequency height map and some real-time noise applied from a small set of displacement maps to add a bit of local detail (rock textures had bumpy ones and grass had flater ones). An attribute for each patch picked a texture set and the Wang data, which we calculated offline, was used to pick the right texture from it. The PSP only does a single texture fetch, and we didn't get around to adding multiple passes for blending -- but I imagine we would have put blend values on the vertices for some kind of texture splatting.

So, to answer your question - I don't really have a specific plan for what to do with this data :). It's a nice simple algorithm and I wanted to try out the language a bit and as I'd not long written a generator in C++. I thought I'd port it over to ZeoScript as a challenge! .. seeing it in L3DT would be nice though :wink:

aaron wrote:I'm already getting ideas about implementing this in L3DT's texture generator to reduce texture periodicity artefacts.

I should tell you how we generated the texture sets for this job then! Firstly our artists made a 4x2 texture (we used 1024px x 512px) and stamped down eight copies of the same grass texture. We then made a guide layer for them to drop into Photoshop which had the same coloured edges as the PDF I linked to before. The artists then used this layer to help them apply clone-stamping and other standard seam removing techniques across the edges that were required to match. It didn't seem to take them long and the beauty of the system is that you only really need a few sets for each environment anyway.

For better integration with L3DT, I guess it wouldn't take more than a bunch of assets (not sure how this would integrate with the existing climates though - maybe as 'enhanced' data side-by-side?), a built-in 'Wang Tile map' generator with a combo box to set the Wang:HM ratio, and a check-box to use it at TM generation time. Hmm.. actually the ratio isn't really necessary as you already have TM:HM ratio which would do the same thing.

Generation would sure be a lot faster as native code for the sorts of terrain sizes you can go up to in the Pro version 8) and visualising it with an arbitrary set of primary/secondary colours can look quite crazy too! I would definitely want the ability to save this data off seperately though -- packing it into nibbles would be pretty efficent, or embedding attributes into it to fill in the remaining 5 bits on a byte. Perhaps that's better left as a game specific post process though.

FWIW, here's my generation code in C++ ... hope it comes in useful, but it's pretty simple :) Extending the algorithm to do lookup across mozaic edges wouldn't be too hard, I think.

Code: Select all
enum e8WangTile { WANG_A, WANG_B, WANG_C, WANG_D, WANG_E, WANG_F, WANG_G, WANG_H };

// West Tiles
e8WangTile west[ 2 ][ 4 ] =
{
   { WANG_A, WANG_B, WANG_G, WANG_H },
   { WANG_C, WANG_D, WANG_E, WANG_F }
};

// Does a tile have an east value of one?
bool is_east_one[ 8 ] = { true, false, true, false, false, true, false, true };

// North Tiles
e8WangTile north[ 2 ][ 4 ] =
{
   { WANG_A, WANG_C, WANG_E, WANG_G },
   { WANG_B, WANG_D, WANG_F, WANG_H }
};

// Does a tile have a south value of one?
bool is_south_one[ 8 ] = { true, true, false, false, true, true, false, false };

// Lookup table for main cells
e8WangTile wang_table[ 2 ][ 2 ][ 2 ] =
{
   { { WANG_A, WANG_G }, { WANG_B, WANG_H } },
   { { WANG_C, WANG_E }, { WANG_D, WANG_F } }
};

Generate8WangPlane( e8WangTile* p_tiles, const uint_t size_x, const uint_t size_y )
{
   e8WangTile above, current;

   // Pick a random starting tile
   current = static_cast< e8WangTile >( rand() & 7 );
   p_tiles[ 0 ] = current;
   
   // Tile the first row
   for ( uint_t x = 1; x < size_x; ++x )
   {
      // Is the east edge of the previous tile '1'?
      current = west[ is_east_one[ current ] ][ rand() & 3 ];

      // Store
      p_tiles[ x ] = current;
   }

   // For each remaining row
   for ( uint_t y = 1; y < size_y; ++y )
   {
      // Create a random value
      const uint_t r = rand() & 3;

      // Index of the first element of the row, and the one above
      const uint_t row_base = y * size_x;
      const uint_t above_base = ( y - 1 ) * size_x;

      // Start the row: Pick from north tiles using south edge of the above tile
      current = north[ is_south_one[ p_tiles[ above_base ] ] ][ r ];
      p_tiles[ row_base ] = current;
         
      // Tile the rest of this row
      for ( uint_t x = 1; x < size_x; ++x )
      {
         // Create a random value
         const uint_t r = rand() & 1;

         // Get the tile above this one.
         above = p_tiles[ above_base + x ];

         // Lookup a tile given the above and previous tiles, along with a random coin flip
         current = wang_table[ is_east_one[ current ] ][ is_south_one[ above ] ][ r ];
         p_tiles[ row_base + x ] = current;
      }
   
   }; // for each row
}


sorry for the massive post!
David Walters
Doyen
 
Posts: 128
Joined: Fri Apr 24, 2009 1:10 pm

Postby David Walters » Wed May 06, 2009 7:09 am

I've updated my script to the latest version of ZeoScript. It now uses the new variable declaration syntax, the SetValue2 for compact table generation and I've added a call to "EditUI" (which I've just discovered) to allow for manual adjustments to the size of the map after it has been populated with the design map size.

http://hidden.asbestos.googlepages.com/WangTiles.zs

Thanks Aaron for your support and interest in this micro-project!
David Walters
Doyen
 
Posts: 128
Joined: Fri Apr 24, 2009 1:10 pm

Re: Wang Tiling Generator

Postby hogjonny » Mon May 20, 2013 4:25 pm

Hello,

I've been trying to get this Wang Tile script to run, using the latest standard release. and when I execute it, I am getting a compile error:
ZeoScript error: Unrecognised command 'zs:map.GetWidth'.
- Line 52: 'set ls.size_x <zs:map.GetWidth <map:DM>>'

ZeoScript compilation aborted on line 52 following errors.

ZeoScript error: Unrecognised command 'zs:map.GetWidth'.
- Line 52: 'set ls.size_x <zs:map.GetWidth <map:DM>>'

ZeoScript compilation aborted on line 52 following errors.

ZeoScript error: Unrecognised command 'zs:map.GetWidth'.
- Line 52: 'set ls.size_x <zs:map.GetWidth <map:DM>>'

ZeoScript compilation aborted on line 52 following errors.


I am pretty much a noob to L3DT, but it seems pretty straightforward ... I am hoping this is more of an issue of a simple oversight on my part, then say something like the script syntax being out of date?

Any help would be appreciated.

- jonny
hogjonny
Newbie
 
Posts: 1
Joined: Mon May 20, 2013 4:20 pm

Re: Wang Tiling Generator

Postby Aaron » Tue May 21, 2013 2:11 pm

Hi Jonny,

Alas, the syntax of the scripting language changed slightly in 2010 with L3DT v2.9. I've updated the script to the new scripting language syntax, and uploaded it here:

http://www.bundysoft.com/wiki/doku.php? ... wang_tiles

Please let me know if you find any problems.

Best regards,
Aaron.
User avatar
Aaron
Site Admin
 
Posts: 3691
Joined: Sun Nov 20, 2005 2:41 pm
Location: Melbourne, Australia


Return to Plugins and scripts

Who is online

Users browsing this forum: No registered users and 4 guests

cron