Voronoi diagrams

ID:265835
 
Apr 29 2008, 7:57 am (Edited on Apr 29 2008, 8:04 am)
Continuing discussion from here, but in a place where we can post code.

This is a little something I whipped up to quickly find the closest seeds in a Voronoi diagram.

var/minx=0,miny=0,maxx=width-1,maxy=height-1,maxd=width+height
var/bestn=0,end=seeds.len

while(end > bestn)
  var/index = rand(bestn+1, end)
  var/seed/S = seeds[index]
  var/d = sqrt((x-S.x)*(x-S.x)+(y-S.y)*(y-S.y))
  if(d > maxd)
    seeds.Swap(index, end--)
  else if(d == maxd)
    seeds.Swap(index, ++bestn)
  else
    maxd = d
    var/ceil = -round(-d)
    bestn = 1
    seeds.Swap(index, 1)
    minx = max(minx, x-ceil)
    maxx = min(maxx, x+ceil)
    miny = max(miny, y-ceil)
    maxy = min(maxy, y+ceil)
    for(index=end, index>bestn, --index)
      S = seeds[index]
      if(S.x < minx || S.x > maxx || S.y < miny || S.y > maxy)
        seeds.Swap(index, end--)


You start the algorithm with a list of seeds, and x and y coordinates for your target point. At the end, seeds[1] through seeds[bestn] are your closest seeds.

Taking the algorithm apart, you see that at each step, a random point from part of the list is chosen. At the head of the list there are the best points, the closest ones found. At the tail is everything that has been discarded. Every point in the active portion of the list should be within the square bounded by minx/maxx and miny/maxy.

Each iteration of the main loop is looking inside the "active square" to find points within a circle with center x,y and radius maxd. Anything that's in the square but not the circle is discarded. Whenever a new best seed is found, the max distance is recalculated and the active square is narrowed down to an even smaller square. During this process, more seeds are pushed over to the tail of the list if they don't fit the square.

This algorithm should be fairly efficient because the "rejection sort" done as the square shrinks is only O(n) complexity, where n in this case is getting smaller each time, so the overall process is roughly O(n log n) in an average case. At any given step, you have about a π/4 chance of picking a seed inside the circle--a chance that grows larger as seeds are found and discarded, so eventually you'll either find a seed inside the circle or run out of seeds to test. Depending on the new seed you find, the circle could get a little smaller or a lot smaller, but anything you've already rejected stays rejected.

Lummox JR
#1 Apr 29 2008, 8:12 am
Looks nice, but what is the purpose of this?
#2 Apr 29 2008, 8:16 am
In response to Ripiz (#1)
Ripiz wrote:
Looks nice, but what is the purpose of this?

It's a secret, so whatever you do, don't follow the link in the post and read the relevant article.

Lummox JR
#3 Apr 29 2008, 8:21 am
In response to Lummox JR (#2)
Very funny...
I downloaded that example, clicking testland works fine, creates some.. Don't know what, but clicking it again creates infinite loop :)
As MapMaker I don't find it really good :) Not sure about others
#4 Apr 29 2008, 8:58 am
In response to Ripiz (#3)
The grid version would be useful for generating random city maps, so each street would be a line and each block would be a square. The other version would be for generating things like Risk board game maps (have a look at the wiki article (http://en.wikipedia.org/wiki/Voronoi) for an example).
#5 Apr 29 2008, 11:57 am
Possibly off-topic, since this is a problem that has been plaguing me for a while outside of BYOND; say I had a map full of solar systems and I want to draw borders along the points separating those solar systems. Would your routine be the best way of finding which systems should have border lines drawn along a front?



This is a mock-up of what I'd want a border to look like (the yellow lines would not appear in the final product, of course). The end points leading off of the map are arbitrary, and the mid-points were "eyeballed" so they might not be totally correct.
#6 Apr 29 2008, 8:56 pm
In response to Jtgibson (#5)
Your problem is basically related to the Voronoi diagram. For this, I'd think a slightly different algorithm would be in order. What you need to find is not which cell a given point goes to, but which lines define the cell borders--in terms of which nodes are their neighbors. So you're not as concerned with finding the nearest point, but actually knowing the lines involved.

From reading up on this (it aroused my interest), I found out there's an algorithm called Fortune's Algorithm you can use to find the edges of a Voronoi diagram. I also discovered there is a related structure called the Delaunay Triangulation, which is closely related to Voronoi and can give you the nearest neighbors that way. Fortune's Algorithm looks a bit complicated, so I'd have to study some code implementing it; right now I only vaguely understand the algorithm itself, but not as well how that would translate into code.

Without knowing offhand how to implement this, my first approach would be to do something more along the lines of the code I presented here. First, for a target seed, exclude it from the list; then find its closest seed. The closest seed is the first neighbor. Now, take the list of all known seeds minus the target and its first neighbor, and exclude anything that lies on the neighbor's side of the line bisecting them. From this smaller list, now calculate the closest seed again; this is the second neighbor. Again exclude anything on its half of the bisecting line. Repeat until the list of neighbor candidates is empty. Obvious downside to this approach: Doing it for one cell may be easy, but doing it for every cell is probably idiotic, and without doing this you can't tell which stars are on the border. So Fortune's Algorithm is really the best way to go.

Once you know the nearest neighbors for any given seed, stars in your case, drawing a border between them should be fairly easy; in fact you can even smoothly interpolate a curve for them, since at each point you have a tangent.

Lummox JR
#7 Apr 30 2008, 4:41 pm
I tried to make my own, but keeping it non mathimatical as possible, its no way as good as gughunter's or your's, Lummox JR and its kinda square-ish but I'll show you anyway.
obj/Point
    icon = 'Icons.dmi'
    icon_state = "P"
    var/list/Dis = list()
    Click()
        ..()
        for(var/obj/Point/P in world)
            P.icon_state = null
            for(var/turf/T in world)
                for(var/S in src.Dis)
                    if(isnum(S) == get_dist(T,P))
                        T.icon_state = "Grass"
        for(var/turf/X in world)
            for(var/obj/O in X.contents)
                if(istype(O,/obj/Point))
                    X.icon_state = "Grass"
                else
                    X.icon_state = "Water"
                    X.name = "Water"
        for(var/turf/F in world)
            if(F.icon_state == initial(F.icon_state))
                F.icon_state = "Water"
                F.name = "Water"
    New()
        ..()
        spawn(20)
            for(var/obj/Point/P in oview(10,src))
                src.Dis += get_dist(src,P)
proc/Voronoi()
    for(var/turf/Grass/G in world)
        if(prob(10)) //Works best for 5-10 smaller the thicker water
            var/obj/Point/P = new
            P.loc = locate(G.x,G.y,G.z)

Here were the results:
http://img337.imageshack.us/my.php?image=scrnshot1bf8.png
http://img516.imageshack.us/my.php?image=scrnshot2lq6.png
#8 Apr 30 2008, 6:54 pm
In response to Chibi-Gohan0 (#7)
Hate to break it to you, but that's not actually any kind of Voronoi algorithm, and it has errors. The most noticeable is that you're using isnum() where you must be expecting an actual number, but that will only give you 1 or 0. get_dist() gives you a square distance (the max of the x and y differences), not actual distance.

Lummox JR
#9 May 1 2008, 11:04 am (Edited on May 1 2008, 11:13 am)
In response to Lummox JR (#8)
Well, i figured you'd say the isnum part, but when i removed the isnum it wouldn't work properly to my surprise, so i kept it.

[edit] also, get_dist() gives you the number of tiles between two locations so if there are two squares between point 1 and 2 you get a result of two
From the DM Guide:
"The distance between Loc1 and Loc2. This is the number of movements (disregarding any obstacles and allowing diagonal moves) required to go from one to the other."
#10 May 1 2008, 1:56 pm
In response to Chibi-Gohan0 (#9)
Thing is, it isn't actually working properly anyway. The whole algorithm really needs redoing. I see it's got the seeds of the diagram being planted (although you may want to go with a lower density than 10%), but the rest of it isn't consistent with a Voronoi diagram.

Lummox JR
#11 May 1 2008, 2:33 pm
In response to Lummox JR (#10)
I see where you're going with it not being an algorithm, but once i change the rate to 5% and fixed one line, i got more realistic results. I still think it works fine as a map generator(and i know now i'm stating something off topic) but..

if(isnum(S) == get_dist(T,P))
//To:
if(isnum(S) == get_dist(T,P)||isnum(S) == get_dist(T,P)-1)


Results:
Its a lot more realistic, and less square-ish.
http://img509.imageshack.us/my.php?image=scrnshot3vb4.png
#12 May 1 2008, 4:13 pm
In response to Chibi-Gohan0 (#11)
Once again, you're misusing isnum(S). S is always going to be a number, so isnum(S) is always going to be 1.
#13 May 1 2008, 4:15 pm
In response to Garthor (#12)
Garthor wrote:
Once again, you're misusing isnum(S). S is always going to be a number, so isnum(S) is always going to be 1.

i allready stated in a previous post, the results came out differently without it to my surprise, which is why i kept it.
If i remove the isnum() it turns the whole map into grass instead of the expected results.
#14 May 1 2008, 8:08 pm
In response to Chibi-Gohan0 (#13)
Chibi-Gohan0 wrote:
Garthor wrote:
Once again, you're misusing isnum(S). S is always going to be a number, so isnum(S) is always going to be 1.

i allready stated in a previous post, the results came out differently without it to my surprise, which is why i kept it.
If i remove the isnum() it turns the whole map into grass instead of the expected results.

And as I said, this is merely covering one error with another. get_dist() is the wrong proc to be using for this, and isnum() is useless to you because it will always be 1 in this situation. 5% seeding will give you better results with a proper Voronoi algorithm, which is why I suggested it; but this algorithm is not giving you a Voronoi graph.

Of course I'm not sure you're even clear on what you're trying to accomplish, since the point of using a Voronoi graph here would be to specify that some seeds are water, some are grass, etc. You've got all the seeds as grass, so filling in each cell with like turfs would give you all grass.

Lummox JR
#15 May 2 2008, 7:31 am
In response to Lummox JR (#14)
I see what you guys mean now, thanks anyway.