Jump to content
  • Advertisement
Sign in to follow this  
Tigro

Unity Generating simple 2D maps with randomized number of neighbours

This topic is 592 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

What I'm trying to achieve for my current project is a simple 2D map generation (or, being more precise, the screen space tessellation) where not all of the "cells" have the same number of neighbours. So for example I'd be fully content with a Voronoi diagram like this:

v-shaken.jpg

 

But the cells don't have to be convex polygonal (or polygon-like) at all. The may very well look like this:

 

512px-Manhattan_Voronoi_Diagram.svg.png

 

All that matters to me is to be able to easily create such maps programming-wise and also be it efficient enough for mobile devices to handle. Also the cells created with this method will have to be clickable cause I want to bind some actions to them.

 

Does any engine support something like this out of the box or with a well-known library or asset? Normally I work in Unity but frankly, I don't even know where to start if I were to do it in it. There are some open source Voronoi diagram codes for Unity but they're complex, have bugs and don't make the next step, which is making the cells clickable, easy at all as they're geared toward simple line drawings.

 

What tool would you recommend for my needs? How would you go about creating something like this?

Edited by Tigro

Share this post


Link to post
Share on other sites
Advertisement

9iKOVxo.jpg

 

Note that you can generate voroni cells easily from a delauney triangulation (blue) as they are dual to this:

Triangle vertices become a polygon centers, polygon edges cross triangle edges at their centers, triangle centers become polygon vertices.

From that you build a list of neighbours for each voroni cell.

 

To build a colored picture of coroni cells you find the cell the current pixel is inside and set it to a color generated from the voroni cell index (no neighbours needed).

 

The picture you show seems to use manhattan distance or something similar:

 

float ManhattanDistance (vec2 a, vec2 b)

{

return min (fabs(a.x-b.x), fabs(a.y-b.y)); // 45 degree patterns, max would give rectangular patterns, can experiment with rotations for  hexagonal look etc.

}

 

To color a pixel you would first find the voroni cell it is inside and calculate manhattan distance to its center, but also iterate over all neighbouring cells to find the closest final cell.

Edited by JoeJ

Share this post


Link to post
Share on other sites
Thanks for the reply. It doesn't seem to be an easy task at all, though, that's why I was hoping for a little automation :( Are there really no higher level way of achieving this, like some libraries or a given engine features?

Share this post


Link to post
Share on other sites

The only thing not easy here is to generate a delauney triangulation from a set of random points. (I used the wrong word in first post, edited).

If you google for that, dozens of tutorials and libs appear.

 

(I'm no Unity user but i can't imagine they expose things like this to user managed code)

 

If you think this is too hard (believe me it's not), you could start with a simpler method which is called Worley Noise.

 

This is easier and much faster because it uses a simple grid, and each grid cell must contain exactly (or at least) one point.

(The point has a random position only within the grid cell, so the resulting pattern appears more regular than your image.)

 

The advantage is: No voroni / delauney stuff required, because you find neighbours simply from the neighbouring grid cells.

Edited by JoeJ

Share this post


Link to post
Share on other sites

Oh wait, you can implement your picture without dlauney / voroni es well:

 

To color a pixel iterate over ALL random points, find the closest by manhattan distance and that's it.

 

It is just very slow, but maybe this does not matter for you.

Share this post


Link to post
Share on other sites

You can look at this thread on the Unity forums: https://forum.unity3d.com/threads/delaunay-voronoi-diagram-library-for-unity.248962/
(Which I'm surprised you didn't see already.)
The main code link provided is to here: https://github.com/adamgit/Unity-delaunay


Oh, that's one of the codes I referred to as being "buggy" in the first post - I saw it but discarded it after seing someone mentioning bugs but now that I read the whole topic again after you linked to it, I see that the author have actually patched all the bugs. Great, that's just what I needed, thank you :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!