Simple Map Generator Part 2.5 ( Smoothing )

I’m aware this series are coming along pretty slow , apologies for that. One of the main reasons for that , is I’m working on a few different version of this project at the same time. You see this series are based on WPF but actually I switched to XNA some time ago , and it is the main branch for me at the moment. But since WPF and XNA is so different , I just can’t switch to XNA for blogging like that.

That’s pretty much why I decided to make this WPF version , the exact same as Amit’s original work. I will not go into my own implementations of various stuff like elevation distribution , I’ll just convert Amit’s code. I’m doing things my own way in XNA anyway ( and probably I’ll talk about that in future too ).

But before that , there is one last personal thing I want to talk about in this WPF series , so I’ll call this Part 2.5. It’s totally optional and actually I even suggest not use this one in your project but still something cool and good to know.

Remember the island we got at the end of last post? It was looking pretty decent right? Well but in my XNA work , I came to a point where I had to do something about those strong and sharp coast line.

 

WindowClipping (56)

 

So I decided to try smoothing that coast line and see how it looks. After reading a bit about spline smoothing techniques , I decided to use Catmull-Rom interpolation!

 

Catmull-Rom Interpolation

OK so let’s talk a bit about Catmull-Rom , what it is and how to implement it.

It’s an interpolation technique that requires 2 main points ( the ones you want to smooth ) and 2 other for calculating the curve. And of course something like a ratio of the new 3rd point ( between those main 2 ). Bah it’s hard to describe really so check this out;

spline1

So the idea is , creating a new point between P1 and P2 which will make the line smoother. But what if I don’t want to add new points to my map? That would create lots of new problem , just for a simple smoothing test , right? So what about this ,

 

int

 

Well excuse my photoshop skills and let me explain this. Instead of creating a new point which will cause lots of new troubles like creating and processing 2 new edges , safely deleting the old one etc , I’ll just replace the existing points in a way they’ll look smoother.

 

So let’s say black lines are the original coast line and forming a zig-zag which we don’t want. If we put i-2 ,  i-1 ,  i+1 and i+2 in catmull-rom , we’ll end up with a point between i-1 and i+1 right? You can see that blue line would be the smooth line , our interpolation function will create and i* will be the point it will return. So we’ll just replace the I with i* , and do this for all coast corners on the map!

 

I think it’ll be best if we do this in IslandService and CreateIsland method. But first of all , we must order coast corners in a line so we can just iterate through them as I explained above.

 var ordered = new List<Corner>();
 var first = App.AppMap.Corners.Values.First(x => x.Coast && x.Touches.Any(z=>z.Ocean));
 var start = first;
ordered.Add(first);
 var next = first.Adjacents.First(x => x.Coast);

 while (next != start)
{
     var nexte = next.Protrudes.FirstOrDefault(x => x.Coast && (x.VoronoiStart != ordered.Last() && x.VoronoiEnd != ordered.Last()));
    ordered.Add(next);
    next = nexte.VoronoiStart == next ? nexte.VoronoiEnd : nexte.VoronoiStart;
}

I’m not really sure if this is the best way to order them but well it’ll do for now. In the end we’ll have a list of corners ordered as a line. And then comes the iteration for interpolation ;

 for (int a = 0; a < 2; a++)
{
     for (int i = 2; i < ordered.Count 2; i++)
    {
        ordered[i].Point = PointOnCurve(ordered[i 2].Point, ordered[i 1].Point, ordered[i + 1].Point,
                                     ordered[i + 2].Point, 0.5f);
    }
}

So we iterate through each point and relocate it depending on the positions of 4 other points around it.

Oh and you can see the interpolation ratio there , 0.5f. That means , I want the point in the middle of curve between point i-1 and i+1. If I passed 0.9f , the result would be very close to i+1 and obviously if I passed 0.1f , it would be very close to i-1.

And of course the “PointOnCurve” function. I’ll admit I’ve just stolen this from a math forum , although I understand how does the calculation process works , I don’t have a full grasp on the code. You can easily find lots of resources on interpolation calculation and it’s fun really , so I suggest you read it about interpolation from more professional mathematicians. Anyway , here is the implementation I use;

 public Point PointOnCurve(Point p0, Point p1, Point p2, Point p3, float t)
{
     Point ret = new Point();
     
     float t2 = t * t;
     float t3 = t2 * t;

    ret.X = 0.5f * ((2.0f * p1.X) +
    (p0.X + p2.X) * t +
    (2.0f * p0.X 5.0f * p1.X + 4 * p2.X p3.X) * t2 +
    (p0.X + 3.0f * p1.X 3.0f * p2.X + p3.X) * t3);

    ret.Y = 0.5f * ((2.0f * p1.Y) +
    (p0.Y + p2.Y) * t +
    (2.0f * p0.Y 5.0f * p1.Y + 4 * p2.Y p3.Y) * t2 +
    (p0.Y + 3.0f * p1.Y 3.0f * p2.Y + p3.Y) * t3);

    return ret;
}

 

We’re pretty much done eh? So this is what it should look like now ;

 

WindowClipping

 

Much smoother then before right? I’ll admit I personally do not like this new smooth look. I prefer previous hex-like look , no contest. But I believe it was still a nice attempt and it was great to learn about Catmull-Rom so I decided to blog it.

Also I guess it looks a bit better when you remove the edges ,

WindowClipping (2)

 

Anyway , hope you liked it or at least find it somewhat useful. You can find the sample below!

 

Visual Studio 2010 Solution

Simple Map Generator Part 2

Wow , it has been 31 days since that last post? Damn I’m lazy. Ok so in this second part of the series , we’ll create our island and visualize it in 2D with some basic colors.

Remember we had our voronoi diagram and our polygons in previous post? Now we’ll need a logic to decide which polygons will be ocean/water and which part will be land. There are some generic algorithms like perlin noise for these stuff , but I decided to use a sine wave function which I saw in Amit’s example and actually it looks kinda better than perlin noise to me.

It’s a simple function which takes a point ( between 0 and 1 since we’ll use sine wave ) and returns a boolean to set IsLand property of the polygon.

It goes something like this ,

private bool IsLandShape(Point point)
{
    double ISLAND_FACTOR = 1.07;
    int bumps = islandRandom.Next(1, 6);
    double startAngle = islandRandom.NextDouble() * 2 * Math.PI;
    double dipAngle = islandRandom.NextDouble() * 2 * Math.PI;
    double dipWidth = islandRandom.Next(2, 7) / 10;

    double angle = Math.Atan2(point.Y, point.X);
    double length = 0.5 * (Math.Max(Math.Abs(point.X), Math.Abs(point.Y)) + GetPointLength(point));

    double r1 = 0.5 + 0.40 * Math.Sin(startAngle + bumps * angle + Math.Cos((bumps + 3) * angle));
    double r2 = 0.7 - 0.20 * Math.Sin(startAngle + bumps * angle - Math.Sin((bumps + 2) * angle));
    if (Math.Abs(angle - dipAngle) < dipWidth
    || Math.Abs(angle - dipAngle + 2 * Math.PI) < dipWidth
    || Math.Abs(angle - dipAngle - 2 * Math.PI) < dipWidth)
    {
        r1 = r2 = 0.2;
    }
    return (length < r1 || (length > r1 * ISLAND_FACTOR && length < r2));
}

I have to admit I just (shamelessly) converted Amit’s AS3 code to C# for this function and don’t totally understand what’s going on. I’m not really good at math and I didn’t want to waste time on this one. For all I know , it returns a “noisy” boolean series. Yes I’m a terrible person and coder , let’s move on.

Now we’ll just iterate through corners and set water/land values according to results of the function above. Not much to see here ;

foreach (var c in App.AppMap.Corners.Values)
{
     c.Water = !InLand(c.Point); // calculate land&water corners
}

Now that we have set corners’ land/water values , we’ll iterate through polygons ( centers ) and decide if a polygon is water or land according to states of it’s own corners. Also we’ll do some other stuff like fixing edges for polygons at the edge of the map and ordering corners as we’ll need them in order for creating visuals ( WPF Polygons ).

First ;

 

 

foreach (var ct in App.AppMap.Centers.Values)
{
    ct.FixBorders(); //Fix edges at map edge, set "border" and "ocean" values
    ct.OrderCorners(); //Order corners clockwise as we'll need it for polygons and 3d stuff

    //if it touches any water-corner , it's water
    ct.Water = (ct.Corners.Any(x => x.Water)) ? true : false;
}

 

As you can see I decided to set a polygon as water ( or sea , whatever ) if it has even one corner set as water. Of course you can use the exact opposite here ( land if it has one corner set as land ) or something more complex.

Then we’ll floodfill the oceans starting from map edges. Oh I set polygons at map edge as “Ocean” in FixBorders method but that method is pretty ugly and should be rewritten, so I’m not going to talk about it here. You can just go set a polygon as Ocean if it has a corner at map boundaries ( like X = 0 or Y = 0 etc )

 

var Oceans = new Queue<Center>();
    //start with oceans at the borders
foreach (Center c in App.AppMap.Centers.Values.Where(c => c.Ocean))
{
    Oceans.Enqueue(c);
}

//floodfill oceans
while (Oceans.Count > 0)
{
    Center c = Oceans.Dequeue();

    foreach (Center n in c.Neighbours.Where(x => !x.Ocean))
    {
        if (n.Corners.Any(x => x.Water))
        {
            n.Ocean = true;
            if (!Oceans.Contains(n))
            Oceans.Enqueue(n);
        }
        else
        {
            n.Coast = true;
        }
    }
}

I guess it’s pretty clear what’s going on here. We just ahve a queue for Oceans and we floodfill starting from the polygons at the edge of the map. Then we set every polygon , which has at least one corner set as water , as ocean. A nice little touch here, if a polygon we reached by this floodfill , doesn’t have any corners set as water ( all land ) this means that’s the coast! So we set it as coast and later we’ll visualize it as beach.

One last thing , we have to set polygon “biome”. We’ll use biome for template selection at the front end. You know ocean will be blue and land will be brown and stuff like that.

 

 

foreach (Center c in App.AppMap.Centers.Values)
{
    c.SetBiome();
}

Just wanted to clarify what it is.

Hmm we now have our island , created oceans and lands even beaches. Should be enough for this post but of course we need to visualize this all now right?

Since we already set biome for all polygons , we just need to set a visual style for that biome and use a template selector to choose polygon styles according to polygon biomes.

It’s kinda hard to write and explain Xaml stuff but I’ll try ; we’ll use this style for oceans

   

<DataTemplate x:Key="Ocean">
<Polygon Points="{Binding Converter={StaticResource MapPointToPointConverter}}"
Fill="#363661" />
</DataTemplate>

It creates a Polygon , do change corner points according to polygon center and fill the polygon with that probably blue-ish color. You can find all styles ( and even more, old test styles, which I forgot to delete ) in MapResource.xaml in the solution.

And since we’re using a Listbox as item container, we need to give our listbox a function to help him decide how to choose styles for each polygon.

It’s much longer but I’ll just paste a part of it as sample ;

 

public class MapDataTemplateSelector : DataTemplateSelector
{
    public override DataTemplate SelectTemplate(object item, DependencyObject container)
    {
        if (item != null && item is Center)
        {
            var center = item as Center;
            var window = Application.Current.MainWindow;

            return window.FindResource(center.Biome) as DataTemplate; 
        }
    }
}

It’s pretty straight-forward I guess. If the item is a Center ( polygon ) we just get the MainWindow ( which holds all styles , actually I doubt we need to do that but anyway ) and find the style ( FindResource ) according to that Center’s Biome. Listbox will handle the rest , easy peasy.

Now this is how it should look;

In the next episode? Hmm probably some elevation work maybe even rivers!

Hope you enjoy it!

Visual Studio 2010 Solution

Simple Map Generator Part 1

Simple Map Generator – Introduction

OK so now that we have Amit’s blog post as a general guideline and a Voronoi diagram library , we can start coding. In this post , we’ll just create a nice Voronoi diagram and a 2D visualization of it.

First of all , we need a Voronoi diagram. We’ll throw bunch of points in an area and Bendi’s Voronoi library will calculate the edges between those points for us. And then we’ll create a better and more complicated structure so it’ll be easier to play with it in the future.

var rnd = new Random();
var points = new HashSet<BenTools.Mathematics.Vector>();

for (int i = 0; i < DotCount; i++)
{
    points.Add(new BenTools.Mathematics.Vector(rnd.NextDouble() * MapSize,
    rnd.NextDouble() * MapSize));
}

VoronoiGraph voronoiMap = Fortune.ComputeVoronoiGraph(loadMapParams.Points);

VoronoiGraph is a class from Bendi’s library. It inclused edges and vertices of the voronoi diagram.

Edges have all the data we need so we’ll use them but before that , if you have seen any Voronoi diagrams before , you may ahve noticed that area sizes varies a lot. And since extremely small or big areas looks pretty bad in later stages , I use Lloyd’s algorithm to generate a more “balanced” diagram.

I won’t go into details but in general , all you have to do is to

– generate a voronoi diagram ( using random number for first time )
– take the center points of the areas in that diagram
– regenerate the diagram with those points
– Repeat it as much as you want

After like 3-4 times , you’ll have a much better balanced diagram. If you run it too much , you’ll end up with a grid tho , so be careful. ( There is something wrong with my implementation tho , messing up after like 10 iterations. Oh well , I use 3 anyway. )

Now we a VoronoiDiagram object but it’s hardly usefull for anything. Sho now we’ll use that diagram object and create a structure pretty close to the one Amit used. We’ll create Centers ( the points we put in ) , Edges ( edges between those points ) and Corners ( where edges connect each other ) and then set some relations between them. For example , center object will have Neighbours ( centers ) , Borders ( edges ) and Corners.

As I said before , VoronoiEdges in VoronoiDiagram object has all the data we need , so we’Ll just iterate through them and get as much data as we can.

foreach (VoronoiEdge edge in voronoiMap.Edges)
{
    Corner c1 = fact.CornerFactory(edge.VVertexA[0], edge.VVertexA[1]);
    Corner c2 = fact.CornerFactory(edge.VVertexB[0], edge.VVertexB[1]);
    Center cntrLeft = fact.CenterFactory(edge.LeftData[0], edge.LeftData[1]);
    Center cntrRight = fact.CenterFactory(edge.RightData[0], edge.RightData[1]);

    c1.AddAdjacent(c2);
    c2.AddAdjacent(c1);

    cntrRight.AddCorner(c1);
    cntrRight.AddCorner(c2);

    cntrLeft.AddCorner(c1);
    cntrLeft.AddCorner(c2);

    Edge e = fact.EdgeFactory(c1, c2, cntrLeft, cntrRight);

    cntrLeft.AddBorder(e);
    cntrRight.AddBorder(e);

    cntrLeft.AddNeighbour(cntrRight);
    cntrRight.AddNeighbour(cntrLeft);

    c1.AddProtrudes(e);
    c2.AddProtrudes(e);
    c1.AddTouches(cntrLeft);
    c1.AddTouches(cntrRight);
    c2.AddTouches(cntrLeft);
    c2.AddTouches(cntrRight);
}

Pretty straight forward I guess? Create Corners , create centers , add a few relations then create the edge and then add that edges relations etc etc. Actually this is probably a lot more detailed than we need but still , it just makes everything easier in later stages.

Oh and by the way , as I mentioned before ; Bendi’s library doesn’t take map borders into account so you have to take care of it before this part. I won’t go into this here , but I added my fix function to the example solution below. It does a decent job but not perfect ( can mess up map corners etc ) so you may want to rewrite that part.

And also ; I’m skipping most of the small details in this post , like ordering area corners for visualization etc. You can find them all in the solution below.

So now we have our organized voronoi diagram but before moving any further , let’s have a look what we have done right? I’ll use an ObservableCollection to hold map items ( centers , edges , corners ) and then a ListBox ( using a Canvas as ItemConainer ) to view those items.

It seems FunnelWeblog doesn’t support XAML in posts. Whatever , now all we need is to create an ObservableCollection , fill it with our items and bind it to that ListBox.

You can find the sample solution below. It only includes the basics I described above and a 2D presentation.

Next , we’ll create the island and stuff.

Visual Studio 2010 Solution

Slide Transitions in WPF

I have been working on a small media player application on WPF these days. And since I’m going full Metro on it , I needed some good animations and transitions. 

The main idea is to have a one screen for everything and then just slide in/out whole content with the help of a little menu at the top right. This menu should have like 2-3 horizontal layers , one layer for stuff like settings , help , about etc , then another layer for main menu items , and probably a 3rd one for sub menus or player screen etc.

So whenever you click on a menu item ; the main view behind the menu ( whole application surface including that big blue “Management” title ) will slide left/right or top/bottom according to the layer and position of that item. Sounds good?

Being way too lazy to implement it myself , I started searching for a nice transition implementation and came across FluidKit. Althought it’s pretty old and seems abandoned , I decided to give it a shot. So I started playing with it and it was all going fine until I this little bug ; althought LeftToRight and RightToLeft transitions are working properly , there seems to be a problem with BottomToTop and TopToBottom transitions as they don’t work at all. Even when I set direction to BottomToTop by hand , it just ignores the direction and slides LeftToRight!

Only after wasting a few hours , I remembered it’s an open source project and decided to take a look at the code and found this little method , in SlideTransition class , which supposed to , well Prepare Storyboard ;

public override Storyboard PrepareStoryboard()
{
    Storyboard animator = (TransitionResources["SlideAnim"] as Storyboard).Clone();

    DoubleAnimation prevAnim = animator.Children[0] as DoubleAnimation;
    DoubleAnimation nextAnim = animator.Children[1] as DoubleAnimation;
    Storyboard.SetTargetName(prevAnim, "PrevElement");
    Storyboard.SetTargetName(nextAnim, "NextElement");
    prevAnim.Duration = this.Duration;
    nextAnim.Duration = this.Duration;

    // Left <-> Right transition
    if (Direction == Direction.RightToLeft)
    {
        prevAnim.From = 0;
        prevAnim.To = -1 * Owner.ActualWidth;

        nextAnim.From = Owner.ActualWidth;
        nextAnim.To = 0;
    }
    else
    {
        prevAnim.From = 0;
        prevAnim.To = Owner.ActualWidth;

        nextAnim.From = -1 * Owner.ActualWidth;
        nextAnim.To = 0;
    }

    return animator;
}

See the problem? They just totally ignored vertical animations!

Turns out that Direction Enum is used for all transitions supported by FluidKit and vertical transitions are only used in stuff like CubeTransition. So although you get intellisense for BottomToTop and TopToBottom and even set Direction to those , FluidKit doesn’t even care , doesn’t even give an exception and just plays the default LeftToRight animation!

Now that we know what the problem is , it’s pretty easy to fix it. Well just add Top&Bottom support to PrepareStoryboard method and then add a new StoryBoard for vertical animations.

First , the PrepareStoryboard Method ;

 

public override Storyboard PrepareStoryboard()
{
    Storyboard animator = null;
    if (Direction == Direction.RightToLeft || Direction == Direction.LeftToRight)
        animator = (TransitionResources["SlideAnimX"] as Storyboard).Clone();
    else
        animator = (TransitionResources["SlideAnimY"] as Storyboard).Clone();


    DoubleAnimation prevAnim = animator.Children[0] as DoubleAnimation;
    DoubleAnimation nextAnim = animator.Children[1] as DoubleAnimation;
    Storyboard.SetTargetName(prevAnim, "PrevElement");
    Storyboard.SetTargetName(nextAnim, "NextElement");
    prevAnim.Duration = this.Duration;
    nextAnim.Duration = this.Duration;

    // Left <-> Right transition
    if (Direction == Direction.RightToLeft)
    {
        prevAnim.From = 0;
        prevAnim.To = -1 * Owner.ActualWidth;

        nextAnim.From = Owner.ActualWidth;
        nextAnim.To = 0;
    }
    else if (Direction == Direction.LeftToRight)
    {
        prevAnim.From = 0;
        prevAnim.To = Owner.ActualWidth;

        nextAnim.From = -1 * Owner.ActualWidth;
        nextAnim.To = 0;
    }
    else if (Direction == Direction.BottomToTop)
    {
        prevAnim.From = 0;
        prevAnim.To = -1 * Owner.ActualHeight;

        nextAnim.From = Owner.ActualHeight;
        nextAnim.To = 0;
    }
    else if (Direction == Direction.TopToBottom)
    {
        prevAnim.From = 0;
        prevAnim.To = Owner.ActualHeight;

        nextAnim.From = -1 * Owner.ActualHeight;
        nextAnim.To = 0;
    }


    return animator;
}

So instead of ignoring vertical animations , we handle them properly and set the From&Top properties of animation according to the direction ( notice we’re using ActualyHeight instead of Width for vertical animations ).

Oh and it turns out FluidKit uses storyboards from a xaml instead of creating them in code. I played along and didn’t changed that ;

TransitionStoryboards.xaml ;

 

<Storyboard x:Key="SlideAnim">
<DoubleAnimation Duration="0:0:0.5"
Storyboard.TargetProperty="RenderTransform.(TranslateTransform.X)"
DecelerationRatio="1.0"/>
<DoubleAnimation Duration="0:0:0.5"
Storyboard.TargetProperty="RenderTransform.(TranslateTransform.X)"
DecelerationRatio="1.0"/>
</Storyboard>

<Storyboard x:Key="SlideAnimY">
<DoubleAnimation Duration="0:0:0.5"
Storyboard.TargetProperty="RenderTransform.(TranslateTransform.Y)"
DecelerationRatio="1.0"/>
<DoubleAnimation Duration="0:0:0.5"
Storyboard.TargetProperty="RenderTransform.(TranslateTransform.Y)"
DecelerationRatio="1.0"/>
</Storyboard>

I decided to post this as it seems there are still a few people using FluidKit out there. Hope it helps , you can find an example solution file below.

Visual Studio 2010 Solution

Simple Map Generator

So I was thinking about some game concepts last week , stealing ideas from here and there etc. One thing I noticed tho , indie games with random maps really have an advantage over professional games with static content , especially when it comes to replay value of the game. Also random map generation is a must for sandbox games like Minecraft and Terraria right? Noone would like to play same sandbox game over and over again on same map ( unless it’s HUGE ie. Eve Online )

So I decided that I need a good random map generator more than everything else , if I have a good map generator , I can build any game on it right?!

After a little search , I found the awesome blog of Amit. I remember reading his A* algorithm articles a few years ago , but somehow I totally forgot about his blog after that. It seems he just posted a new little series about random map generation a few months ago ( September 2010 ) , based on Voronoi diagrams

After reading his article and a little more about voronoi diagrams , I knew I had to do it myself so yea I have been working on it for a few days now. It’s extremely fun playing with Voronoi diagrams , shaping the land , rivers , mountains etc and create my own little island!

I’ll slowly blog about my process here , and the first step is obviously ;

Voronoi Diagrams

So what is a Voronoi diagram?

Wikipedia says ;
   In mathematics, a Voronoi diagram is a special kind of decomposition of a metric space determined by distances to a specified discrete set    of objects in the space, e.g., by a discrete set of points.

Or we can simply say ; it divides an area based on a set of points. You take a field , then throw some points in it , then create zones around those points in a way that everywhere in that zone is closer to that point than any other. An image worths thousand words right?

Looks nice isn’t it? It’s a great diagram used for lots and lots of different stuff

Now what we will do , is just throw in a few thousand dots , divide the area , then work on it as if it’s a grid. We’ll use areas to decided land type , edges to create rivers and coastline etc etc.

But since I’m more interested in creating a random map more than a basic Voronoi diagram , I decided to use a 3rd party Voronoi Diagram library to take care of that. But it turns out there isn’t many Voronoi implementations for .Net. The best I was able to find , is an implementation by BenDi , posted on CodeProject.

It’s doing a pretty good job , fast and reliable. The only problem I had , is that it only works on points and generated edges between them , there is no way to actually set area boundaries. I had to work it out myself , not a big problem but my temporary fix isn’t good enough so borders of the maps looks a bit silly. ( I’ll redo it later , I’m hardly bothered about the map borders at the moment , our island will be at the center anyway )

As I said I’ll blog more about this in future , and probably even post the project when I’m done with it.

My current process ;