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;


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 ,




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;
 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()));
    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 ;




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

Leave a Reply