• Register
Post news RSS About Organic Tiles and Boolean Operations

Long time no see! This time I am writing about more organic looking tiles, boolean operations on polygons and some distractions.

Posted by on

It's time for another update to show you that the project is still alive. Here are the topics I dealt with this time:

  • Organic Tiles
  • Boolean Operations on Polygons
  • BEPU Physics Integration
  • Some Optimizations
    • Support for meshes with more than 64k vertices
    • Random Number Generator
    • Region Files

Organic Tiles

When I first started this project I aimed at making the whole world look more organic than Minecraft does. Therefore I was in need of a counterpart to the sharp tiles for carpets, laminate or other urban ground texture. I always thought about supporting organic tiles as in Warcraft 3. To cut a long story short: I did just that!

Screenshot of the terrain with organic and inorganic tiles at the same time

Technically, I am just blending four uv sets in a shader but it required me to write code that separates all parts of the terrain using four uv sets from parts that only use one uv set for performance reasons. Additionally, organic tiles will use more space in the texture atlas but it's absolutely worth it.

A pixel art grass tileset

Boolean Operations on Polygons

Placing windows and doors requires the game to cut holes into the walls. My first implementation for this hole cutting mechanism was trivial in that it only allowed simple holes, i.e. only one hole for each wall segment, the holes needed to be rectangular and their edges had to be paraxial. However, I want to be able to place more interesting structures, e.g. garage doors that might overlap two wall segments or circular shaped windows. To do that I started implementing an algorithm described by Martinez et al. It turned out to be not very robust due to floating point issues. Further investigations lead me to a programmer called Sean Connelly who had similar issues and invented a better polygon clipping algorithm. His algorithm isn't robust in a mathmatical sense but robust enough for practical use cases like mine. However, all these clipping algorithms only deal with polygons, so I still have to triangulate them. For that I had to partition the resulting polygon into y-monotone polygons because monotone polygons can be triangulated in linear time. I did just that as you can see in the following video:

The partitioning algorithm has similar floating point issues as the original clipping algorithm by Martinez but I hope that I will be able solve the problem.

BEPU Physics Integration

In one of my old articles I said that I've implemented a dynamic character controller. In turns out that I was wrong: creating a dynamic controller in Unity isn't possible or at least way too difficult to be practical. By looking for a way to deal with this problem I found a physics engine called BEPU. This library already contains an implementation for a dynamic character controller and it works like a charm. The developer Ross Nordby said that he was trying to reach the quality of the character controller of Valve's Source engine and I think he nailed it but it gets even better. Version 2.0 of his engine will support reconstructions of collision meshes over time, i.e. the hickups I am getting now due to reconstructions being expensive will hopefully go away since the work will be spread over several frames. I am really looking forward to it.

Some Optimizations

Some of the additional things I've done worth mentioning are my custom XorShift pseudo random number generator based on the work of George Marsaglia. The random number generator of C# is based on a modified version of Donald E. Knuth's subtractive random number generator algorithm and it has two drawbacks: it's quite slow and you can't change its seed unless you create a new instance.

I've also implemented a mechanism to support meshes in Unity with more than 65535 vertices. Unity uses index buffers based on unsigned shorts therfore the strange limit. It is unlikely to happen often but if a player places too many detailed props, walls, windows etc. in an area this limit might be exceeded and in earlier versions the game might have crashed so that's why I had to support it.

Last but not least, I've implemented a region file format for saving terrain chunks inspired by Minecraft's region system. Previously I've opened one file for each chunk in my world. Now, I'm just opening one file every 1024 chunks which should speed things up a bit at least during loading and saving.


Wait? Another paragraph? Well, there are some more things to tell you: I've got sidetracked! Every now and then I need a break from the work on this project. Some of the problems I have to solve for this game can become really frustrating or cumbersome, so I try to get new motivion by doing something else like programming a game. Wait? What? Yes, that's right. I just wanted to test my skills or I wanted to see if an idea works without the intention of finishing it. So here are some other things I've done since my last update:

By the way, you can find some of the code I've created in my GitHub account. For example, there's a conversation editor I've programmed for Unity that is inspired by the conversation editor of Neverwinter Nights. The source code for my random number generator called XORShiftRNG or the Martinez Polygon Clipping Algorithm can be found there, too.

My GitHub Account: BrightBitGAMES

Thanks for reading and let me know about any questions in the comments!


Post a comment
Sign in or join with:

Only registered members can share their thoughts. So come on! Join the community today (totally free - or sign in with your social account on the right) and join in the conversation.