3 replies to this topic

[IceMetalPunk]

Background
Essentially what I'm trying to do is, given a black surface and an arbitrary list of starting points (and colors), create randomized regions of the surface in the given colors which contain the seed points. So if I gave (100,100,c_red) and (200, 150, c_blue), then it would create a surface with only two regions, both randomized: one red region containing at least (100, 100) and one blue region containing at least (200, 150).

My First Attempt
Originally, I just tried a Breadth-First Search methodology, where the seed positions were initially added to a queue, then all black pixels around it were marked with the current pixel's color and added to the queue, repeating until the queue was empty (and thus no pixels are black). This worked to create the regions, but there was no randomness. It just grew diamonds, basically, in order from one region to the next to the next and back to the first. That's to be expected, of course. I thought it would be easy to then modify this and add in some randomness...but it turns out, it's not. I couldn't figure out how to add randomness while still guaranteeing that every black pixel is visited at least once and that won't result in an infinite loop (i.e. restricting that to "every pixel is visited exactly once").

If you can help from here, then please do; Lord knows it'll be easier for me to implement this! If not, continue reading.

A Different Approach
My friend is a computer science/mathematics dual major. I figured if anyone could help, he could. When I asked about the above problem, he told me he thinks it's impossible to add randomness to the BFS without allowing the possibility of unfilled holes. So instead, he suggested a different method.

Instead of starting at the seeds and filling each pixel, he said, it would be better to simply divide the surface into N regions (where there are N seeds), each containing exactly one seed. This way, the focus is on generating the edges of the region and not filling from the inside.

He pointed me on a path that eventually led me to a mathematical problem (at which point he left, since it was 1:30AM). I haven't been able to figure it out since.

Basically, I have a set of arbitrary but constant seed points (set P). I also have a set of randomly chosen vertices (set V).

Note for below: I use |A| as the symbol for "the size of set A".

I first must guarantee that |V| >= 2 + |P|/2 (this is easy, since the vertices are procedurally generated and |P| is known).

I then need to connect pairs of the vertices in V with edges (set E) in such a way that the following three conditions hold true:

1) No two edges intersect,
2) |E| = |P| + |V| - 2, and
3) Each region created by the edges contains exactly one point from set P.

The restriction on |V|, as well as the first two numbered conditions above, should guarantee that this results in exactly |P| contiguous regions.

How can I guarantee those three properties for any arbitrary (compatible) V and P while choosing edges as randomly as possible?

I first thought of brute-forcing condition 1 by choosing a uniformly random edge and checking if it intersects a previously-chosen edge, trying another random edge if it does. That seems terribly inefficient. I then thought of testing all edges for intersections with previous edges, discarding the ones that intersect, and randomly choosing from the remaining set. This seems more efficient (though still not great), but it could be the case that a previous edge worked but also prevented another edge from being chosen later, which could break condition 2.

And don't even get me started on condition 3. I don't even know where to begin that.

So can anyone point me in the right direction?

-IMP

*EDIT* Oh, and also, the way points are stored doesn't matter. As of now, I'm keeping them in a queue or list in pairs so that, say, if a queue holds points (10, 20) and (35, 40), the queue contents would be {10, 20, 35, 40}. But I can change that to nested lists or such if it helps. The representation is immaterial to the problem, so don't worry about changing that to make things easier.

Edited by IceMetalPunk, 16 February 2012 - 09:41 PM.

[Follomania]

I threw together a script that may do what you'd like. It took 19 seconds to generate a 128x128 grid, but I didn't try optimizing anything. I basically generate two seeds and they expand to random adjacent tiles.

Spoiler

width = 128
height = 128
map = surface_create(width,height)
surface_set_target(map)
draw_clear(c_black)
for (ii = 0; ii < width; ii += 1){
    for (jj = 0; jj < height; jj += 1){
        data[ii,jj] = 0
    }
}
region_one_x = irandom(width-2)+1
region_two_x = irandom(width-2)+1
region_one_y = irandom(height-2)+1
region_two_y = irandom(height-2)+1
data[region_one_x,region_one_y] = 1
data[region_two_x,region_two_y] = 2

should_fill = 1
while (should_fill == 1){
    possible_one = 0
    possible_two = 0
    unfilled = 0
    for (ii = 0; ii < width; ii += 1){
        for (jj = 0; jj < height; jj += 1){
            if (data[ii,jj] == 0){
                unfilled += 1
            }
            if (possible_one < 31998){
                if (data[ii, jj] == 1){
                    if (ii > 0){
                        if (data[ii-1,jj] == 0){
                            pos1_x[possible_one] = ii-1
                            pos1_y[possible_one] = jj
                            possible_one += 1
                        }
                    }
                    if (jj > 0){
                        if (data[ii,jj-1] == 0){
                            pos1_x[possible_one] = ii
                            pos1_y[possible_one] = jj-1
                            possible_one += 1
                        }
                    }
                    if (ii < width-1){
                        if (data[ii+1,jj] == 0){
                            pos1_x[possible_one] = ii+1
                            pos1_y[possible_one] = jj
                            possible_one += 1
                        }
                    }
                    if (jj < height-1){
                        if (data[ii,jj+1] == 0){
                            pos1_x[possible_one] = ii
                            pos1_y[possible_one] = jj+1
                            possible_one += 1
                        }
                    }
                }
            }
            if (possible_two < 31998){
                if (data[ii, jj] == 2){
                    if (ii > 0){
                        if (data[ii-1,jj] == 0){
                            pos2_x[possible_two] = ii-1
                            pos2_y[possible_two] = jj
                            possible_two += 1
                        }
                    }
                    if (jj > 0){    
                        if (data[ii,jj-1] == 0){
                            pos2_x[possible_two] = ii
                            pos2_y[possible_two] = jj-1
                            possible_two += 1
                        }
                    }
                    if (ii < width-1){
                        if (data[ii+1,jj] == 0){
                            pos2_x[possible_two] = ii+1
                            pos2_y[possible_two] = jj
                            possible_two += 1
                        }
                    }
                    if (jj < height-1){
                        if (data[ii,jj+1] == 0){
                            pos2_x[possible_two] = ii
                            pos2_y[possible_two] = jj+1
                            possible_two += 1
                        }
                    }
                }
            }
        }
    }
    repeat (min(possible_one,possible_two)){
        if (possible_one > 0){
            new_pos = irandom(possible_one-1)
            data[pos1_x[new_pos],pos1_y[new_pos]] = 1
            draw_point_color(pos1_x[new_pos],pos1_y[new_pos],c_red)
        }
        if (possible_two > 0){
            new_pos = irandom(possible_two-1)
            data[pos2_x[new_pos],pos2_y[new_pos]] = 2
            draw_point_color(pos2_x[new_pos],pos2_y[new_pos],c_blue)
        }
    }
    if (possible_one + possible_two == 0){
        should_fill = 0
    }
    if (unfilled == 0){
        should_fill = 0
    }
}
surface_reset_target()

[torigara]

Just for an idea, you could replace an adjacent pixel in some chance. Take your first attempt, modify this part (in a pseudo code):

if (the adjacent pixel is black) {
    turn it into my color;
    add it to the queue;
}

into something like this.

if ((the adjacent pixel is black) or ((it is an opponent color) and (random() < threshold))) {
    turn it into my color;
    add it to the queue;
}

To keep it from an infinite loop, you may have to count the number of remaining black pixels, and stop replacing colors when no black one is left.

[IceMetalPunk]

Just for an idea, you could replace an adjacent pixel in some chance. Take your first attempt, modify this part (in a pseudo code):

if (the adjacent pixel is black) {
    turn it into my color;
    add it to the queue;
}

into something like this.

if ((the adjacent pixel is black) or ((it is an opponent color) and (random() < threshold))) {
    turn it into my color;
    add it to the queue;
}

To keep it from an infinite loop, you may have to count the number of remaining black pixels, and stop replacing colors when no black one is left.

It seems so simple! Why didn't I think of it? I'm currently running this version now (on a 640x480 surface, so it's a bit slow, especially as I'm drawing the surface every 100 iterations so I can monitor the progress). So far it looks great! I need to play around with the threshold, though...I'm using 50% and getting very patchy borders.

I'm waiting for this to finish since I don't know if I did the math right for calculating the remaining black pixels. Perhaps you can verify? Initially, the surface is black. Then I put single-pixel seeds into the queue as [x, y] pairs. Thus, the black pixels would be w*h-ds_queue_size(queue)/2, right? And then whenever I replace a black pixel, I just subtract 1? That should work, correct?

-IMP

*EDIT* Woohoo! It worked . Here's the result with a 25% threshold and 4 seeds:



Thanks for the help. Now it's just a matter of optimization, since that was really slow...if I get stuck, would you mind if I PM'ed you for help with the optimizations, tori?

*EDIT2* Optimizations done. The main boost was that instead of manipulating the colors directly from the surface, as I was originally doing, I moved them into an array and only drew the final result to the surface linearly. This drastically improved the performance. It can now generate a 640x480 random mass of lands in an average of 12.5 seconds. That's including the slowdown caused by drawing the percent completion to the screen at regular intervals--without that, it only took 10 seconds.

For those interested in the final code, I'll share it below .

Init()

Spoiler

global.__seedsurf=surface_create(room_width, room_height);
global.__seedqueue=ds_queue_create();

for (xx=0; xx<room_width; xx+=1) {
  for (yy=0; yy<room_height; yy+=1) {
    global.__seedArray[xx, yy]=0;
  }
}

surface_set_target(global.__seedsurf);
draw_clear_alpha(0, 1);
surface_reset_target();

Note: it's designed to fill the room with these regions, but you can easily modify it to take two arguments for the width and height. The other scripts use the surface size anyway.

Seed(x, y, color)

Spoiler

global.__seedArray[argument0, argument1]=argument2;
ds_queue_enqueue(global.__seedqueue, argument0);
ds_queue_enqueue(global.__seedqueue, argument1);

Generate(showprogress?)
Note: the showprogress argument, when set to false, does not display the percent completion, which saves about 2 seconds but leaves you with no indication of progress during generation.

Spoiler

var surf, xx, w, h, showprog, yy, xo, yo, which, n, col, c2, queue, blacks, perc;
surf=global.__seedsurf;
queue=global.__seedqueue;
showprog=argument0;

w=surface_get_width(surf);
h=surface_get_height(surf);
blacks=w*h-ds_queue_size(queue)/2;
n=0;

while (!ds_queue_empty(queue) && blacks>0) {
  io_handle();
  if (keyboard_check(vk_escape)) { game_end(); return false; }
  if (showprog) {
    if ((n mod 3500)==0) {
      perc=(w*h-blacks)/(w*h);
      draw_clear(background_color);
      draw_text(10, 10, "Generating lands..."+string(perc*100)+"%...");
      draw_rectangle_color(10, 12+string_height("G"), 10+perc*100, 22+string_height("G"), c_blue, c_blue, c_blue, c_blue, 0);
      draw_rectangle_color(10, 12+string_height("G"), 110, 22+string_height("G"), 0, 0, 0, 0, 1);
      screen_refresh();
    }
    n+=1;
  }
      
  xx=ds_queue_dequeue(queue);
  yy=ds_queue_dequeue(queue);
  
  col=global.__seedArray[xx, yy];

  if (xx>0) {
    c2=global.__seedArray[xx-1, yy];
    if (c2==0 || (c2!=col && random(1)<0.5)) {
      if (c2==0) { blacks-=1; }
      global.__seedArray[xx-1, yy]=col;
      ds_queue_enqueue(queue, xx-1);
      ds_queue_enqueue(queue, yy);
    }
  }
  
  if (yy>0) {
    c2=global.__seedArray[xx, yy-1];
    if (c2==0 || (c2!=col && random(1)<0.5)) {
      if (c2==0) { blacks-=1; }
      global.__seedArray[xx, yy-1]=col;
      ds_queue_enqueue(queue, xx);
      ds_queue_enqueue(queue, yy-1);
    }
  }
  
  if (yy<h-1) {
    c2=global.__seedArray[xx, yy+1];
    if (c2==0 || (c2!=col && random(1)<0.5)) {
      if (c2==0) { blacks-=1; }
      global.__seedArray[xx, yy+1]=col;
      ds_queue_enqueue(queue, xx);
      ds_queue_enqueue(queue, yy+1);
    }
  }
  
  if (xx<w-1) {
    c2=global.__seedArray[xx+1, yy];
    if (c2==0 || (c2!=col && random(1)<0.25)) {
      if (c2==0) { blacks-=1; }
      global.__seedArray[xx+1, yy]=col;
      ds_queue_enqueue(queue, xx+1);
      ds_queue_enqueue(queue, yy);
    }
  }
}

surface_set_target(global.__seedsurf);
for (xx=0; xx<w; xx+=1) {
  for (yy=0; yy<h; yy+=1) {
    io_handle();
    if (keyboard_check(vk_escape)) { game_end(); return false; }
    
    surface_set_target(global.__seedsurf);
    draw_point_color(xx, yy, global.__seedArray[xx, yy]);
    
    if (showprog) {
      perc=(h*xx+yy)/(w*h);
      if ((xx+yy) mod 500==0) {
        surface_reset_target();
        draw_clear(background_color);
        draw_text(10,10, "Filling Map..."+string(perc*100)+"%...");
        draw_rectangle_color(10, 12+string_height("F"), 10+perc*100, 22+string_height("F"), c_blue, c_blue, c_blue, c_blue, 0);
        draw_rectangle_color(10, 12+string_height("F"), 110, 22+string_height("F"), 0, 0, 0, 0, 1);
        screen_refresh();
      }
    }
  }
}

surface_reset_target();
ds_queue_clear(queue);

And the Deinit() cleanup script simply frees global.__seedsurf and destroys global.__seedqueue.

Thanks, tori, for your help .

Edited by IceMetalPunk, 17 February 2012 - 10:55 PM.