What Algorithm are they using?

[Sean Doherty]

I have been looking at Weird Worlds and I was wondering how they are calculating the polygons around each of the territories? The map is randon so they must be calculating it?

http://www.shrapnelgames.com/digital_eel/weird_worlds/2.htm

Thanks

[Pyabo]

Interesting... hard to tell from the screenshots, but it looks like it would be pretty simple to build a weighted graph of the stars and their neighbors. That graph lets you find the contiguous sets. Then drop your points at the midway marks between sets and neighboring sets, and you've got your points for a polygon.

Making assumptions about the gameplay here though... haven't really seen it. Also, that seems like it would break if you had a set of 4 interconnected nodes where the opposite "corners" were two sets.

[Sean Doherty]

Interesting... hard to tell from the screenshots, but it looks like it would be pretty simple to build a weighted graph of the stars and their neighbors. That graph lets you find the contiguous sets. Then drop your points at the midway marks between sets and neighboring sets, and you've got your points for a polygon.

Making assumptions about the gameplay here though... haven't really seen it. Also, that seems like it would break if you had a set of 4 interconnected nodes where the opposite "corners" were two sets.

Hmmm, a weighted graph might work. I was trying to think of a way of doing it without providing the weights. Is there a way to calculate the weights just from points?

[merovingian]

Looks like a slightly transmogrified Voronoi Diagram (http://en.wikipedia.org/wiki/Voronoi_tessellation) to me.

[Pyabo]

Looks like a slightly transmogrified Voronoi Diagram (http://en.wikipedia.org/wiki/Voronoi_tessellation) to me.

Bingo.. that's gotta be it. Then two neighboring polygons get the same color when they belong to the same race/player.

Ya learn something new every day...

[Sean Doherty]

Voronoi Diagrams are pixel based; so there really isn't any polygons being generated. However, it does a good job of calculating color of each region. And you could probably calculate a polygon based on the results.

[mr n00b]

Voronoi Diagrams are pixel based; so there really isn't any polygons being generated

Yes there is, a voronoi decomposition can most definitely generate polygons.

/mr n00b

[Sean Doherty]

Yes there is, a voronoi decomposition can most definitely generate polygons.

Do you no where I can find a sample code for voronoi decomposition?

Thanks

[mr n00b]

Do you no where I can find a sample code for voronoi decomposition?

Thanks

Excellent voronoi generation code (plus other useful stuff):

http://www.cs.cmu.edu/%7Equake/triangle.html

/mr n00b

[Sean Doherty]

Excellent voronoi generation code (plus other useful stuff):
http://www.cs.cmu.edu/%7Equake/triangle.html


Can you point me at the source code? I have been looking at the site and there seems to be a lot of different diagrams with complex source? Which one are you talking about?

Thanks

[mr n00b]

Can you point me at the source code? I have been looking at the site and there seems to be a lot of different diagrams with complex source? Which one are you talking about?

Thanks

The code is in:

http://cm.bell-labs.com/netlib/voronoi/triangle.zip

Unfortunately it uses a somewhat clunky c-interface, instructions on how to use it is in the file 'triangle.h'.

/mr n00b