new map generator

[Gandalf Parker]

Ahhh...
I had on my projects list (my super overloaded projects list) an idea to do a webpage tiling of the maps I randomly generate just to see if one accidentally comes close to being wrappable. That way I could spot one that was at least possible with slight effort.

[paradoxharbinger]

hmmm... maybe i am doing the voronoi calculation wrong. the tringulation is delaunay, other triangles were removed from around the edges, so the borders do not appear so, but they are. i thought that to get the voronoi tesselation you drew a line from the center of a triangle to its neighbor's center. working from memory here, so would not be suprised if that isnt quite right.

edit: so hard to find good computational geom stuff on the internets, bu i think i figured the difference out, should be from the centers of the triangle's circumcircles. i think the triangle centers will suit my purpose fine though.

[BandarLover]

Woa...suddenly had a flash back to high school geometry after reading that. And it still makes no sense now like it did then.

[llamabeast]

Hey paradox, just to let you know I'm lurking here, and I'm really impressed by what you've got done! The latest demo is really good looking I think. Seems like an excellent system you're using. I'm impressed you managed to get the wraparound working too - it's not obvious after a brief think how you'd do that.

I like how the province borders are defined by the midpoints of the triangles. Cunning. One thing - the coastline goes along the edges of the triangles, which means that all the coastal provinces are half in the sea and half on land. Is that deliberate?

[paradoxharbinger]

@ich

oh there are plenty of links to applets and half assed descriptions of how to do it, but go looking for a detailed description and all i've ever gotten is cryptic source code, if that

i dont like the very short edges that you get with voronoi, so im sticking to the segments between the triangle centers

@llamabeast

those regions are not necessarily provinces, they are meant to be the building blocks of the provinces. im thinking that province edges could be either the gray or red lines, depending on the terrain that has been placed. but im pretty sure that im sticking to rivers on the triangle edges, using the others would make it too chaotic. and yes, getting the delaunay triangulation to wrap was rough.

[lch]

Oh, you don't want the cells to be the finished provinces, okay, you're free to do that. Otherwise I'd assume that you get strange effects because I'd assume that the game interprets the provinces as being voronoi cells, so that mouse-clicks on the map can be efficiently calculated to the province they're meant for, by only saving and using one point per province instead of a whole polygon.

I still guess there's quite alot of good software around, but either you'll have to program the stuff yourself or use some library which does tons of other algorithmic geometry stuff aswell (like CGAL), yeah.

[paradoxharbinger]

actually i think the game just gets the closest point. otherwise youd have to calculate the voronoi every time the map is loaded and store all the vertexes in addition to the province centers.

[lch]

paradoxharbinger said:
hmmm... maybe i am doing the voronoi calculation wrong. the tringulation is delaunay, other triangles were removed from around the edges, so the borders do not appear so, but they are. i thought that to get the voronoi tesselation you drew a line from the center of a triangle to its neighbor's center. working from memory here, so would not be suprised if that isnt quite right.

That's right, the question is whether you used the incircles or circumcircles for that. I just judged by my eyesight and most cells look quite fine, but you can spot that some are a little bit off, some are even so far off that it can't come from rounding errors / computer precision. (see Attachment)

paradoxharbinger said:
edit: so hard to find good computational geom stuff on the internets, bu i think i figured the difference out, should be from the centers of the triangle's circumcircles. i think the triangle centers will suit my purpose fine though.

Yep. The vertices of the Voronoi cells are the centers of the circumcircles from the triangles of the Delaunay triangulation: you get the Voronoi cells if you draw in the perpendicular bisectors of the sides of the triangle towards their collective intersection point. This point could even be outside of the triangle surface, if it is obtuse angled. In the same way, the vertices from the Delaunay triangulation are the intersection points of the perpendicular bisectors from the Voronoi cells.

There is quite some information about it on Wikipedia, and they got lots of links regarding Voronoi diagrams and Delaunay triangulation, too.