Jump to content


Photo

Finding the furthest location from a collection of points.


Best Answer webber17, 18 February 2016 - 07:29 PM

Since you are using ds_grid, here's an idea outside the box:
1. Clear the grid to 0.
2. Any blocked spaces add 10000.
3. With each point to avoid, find the furthest corner and save the distance (in grid cells) as that point's radius.
4. With each point, while radius is greater than 0, ds_grid_add_disk(id,gridx,gridy,radius,1) and radius -= 1.
5. Find the grid cell with smallest value.

Not sure how fast that will run but it should give the best value. I would think it would be faster than using the distance formula.

Your method seems to work the fastest. 

 

Here is a video of it in action:

///scr_safe_space_grid(avoid);
var avoid = argument0;
var focus = 32;
var width = room_width div focus;
var height = room_height div focus;
var fp_grid = ds_grid_create(width, height);
var mp_grid = mp_grid_create(0,0,width, height,focus,focus);
var safe_x = 0;
var safe_y = 0;
ds_grid_clear(fp_grid,0);

mp_grid_add_instances(mp_grid,obj_wall,1);
mp_grid_to_ds_grid(mp_grid,fp_grid);
mp_grid_destroy(mp_grid);

ds_grid_multiply_region(fp_grid,0,0,width,height,-1000);
var r = max(width,height);
//var safe_x = 0;
//var safe_y = 0;
var r = -1;
var i = 0;
with(avoid)
{
    var corn_x = 0;
    var corn_y = 0;
    var xx = x div focus;
    var yy = y div focus;
    if xx<width/2 then corn_x = width;
    if yy<height/2 then corn_y = height;
    r[i] = scr_diagDist(xx,yy,corn_x,corn_y);
    ds_grid_set(fp_grid,xx,yy,10000);
i++;
}
var loop = true;
while(loop)
{
    loop = false;
    var i = 0;
    with(avoid)
    {
        ds_grid_add_disk(fp_grid,x div focus, y div focus,r[i],1);

        if r[i]>=0 then 
        {
            loop = true;
            r[i]-=1;
        }
i++;
    }
}
r=-1;
var min_val = ds_grid_get_min(fp_grid,0,0,width,height);
safe_x=ds_grid_value_x(fp_grid,0,0,width,height,min_val)*focus;
safe_y=ds_grid_value_y(fp_grid,0,0,width,height,min_val)*focus;
safe_x+=focus/2;
safe_y+=focus/2;
ds_grid_destroy(fp_grid);//var rtn = -1;
rtn[0] = safe_x;
rtn[1] = safe_y;
return rtn;

Thanks for the help,

Trevor

Go to the full post


  • This topic is locked This topic is locked
12 replies to this topic

#1 webber17

webber17

    GMC Member

  • GMC Member
  • 497 posts
  • Version:GM:Studio

Posted 16 February 2016 - 05:11 PM

I am trying to find the furthest point from a collection of given points on a grid with the plan on using it to find a safe spawn position on level. I have tried various methods that have returned different results. 

 

Please feel free to use any of these scripts in your game.

 

Method 1: Distance checking

For each cell on grid, record the total distance to every point on grid. Return cell with highest value.

Pros:

  • Can return the most correct answer'
  • Fast when there are few points to check.

Cons:

  • Slow when checking large amounts of points.
  • Slow when checking large grid.

Code:

///scr_safe_space_grid(avoid);
var avoid = argument0;
var focus = 8;
var fp_grid = ds_grid_create(room_width div focus, room_height div focus);
for (var ix=0; ix<ds_grid_width(fp_grid); ix+=1)
{
    for (var iy=0; iy<ds_grid_height(fp_grid); iy+=1)
    {
        var d = 100000000;
        with(avoid)
        {
            d += scr_diagDist( ix, iy, x div focus, y div focus )
        }
        fp_grid[# ix,iy] = d;
    };
};
return fp_grid;

Method 2: Quadrant Search

Divide the search area into 4 quadrants. Narrow the search area to the quadrants with the least amount of points. Repeat until the search area is small enough.

Pros: 

  • Extremely fast.
  • Can be executed in step

Cons:

  • Favors top left.
  • Often is inaccurate when the search area no longer has points in it.

Video:

Spoiler

Code:

///scr_safePlace_quad();
var ww =room_width div 64;
var hh = room_height div 64;
var grid = ds_grid_create(ww, hh);
ww-=1;
hh-=1;
ds_grid_clear(grid,0);
with(obj_player)
{
    var px,py;
    px = x div 64;
    py = y div 64;
    if point_in_rectangle(px,py,0,0,ww,hh) then grid[# px, py] = 1;
}

var xx = 0;
var yy = 0;
var sizew = room_width*0.5;
var sizeh = room_height*0.5;
var safe_x = -sizew;
var safe_y = -sizeh;

while(sizew>4) 
{
    var tl,tr,bl,br;
    tl = 0;
    tr = 0;
    bl = 0;
    br = 0;

    tl+=ds_grid_get_sum(grid,xx div 64,yy div 64,(xx+sizew) div 64,(yy+sizeh) div 64);
    tr+=ds_grid_get_sum(grid,(xx+sizew) div 64,yy div 64,(xx+sizew+sizew) div 64,(yy+sizeh) div 64);
    bl+=ds_grid_get_sum(grid,xx div 64,(yy+sizeh)  div 64,(xx+sizew) div 64,(yy+sizeh+sizeh) div 64);
    br+=ds_grid_get_sum(grid,(xx+sizew) div 64,(yy+sizeh) div 64,(xx+sizew+sizew) div 64,(yy+sizeh+sizeh) div 64);
    var t,b,l,r;
    t = tl+tr;
    b = bl+br;
    l = tl+bl;
    r = tr+br;
    if l>r then xx = xx+sizew;
    if t>b then yy = yy+sizeh;

    if l==r then xx = xx+(sizew/2);
    if t==b then yy = yy+(sizeh/2);
    sizew*=0.5;
    sizeh*=0.5;
}
ds_grid_destroy(grid);



var rtn = -1;

rtn[0] = safe_x;
rtn[1] = safe_y;

return rtn;

Method 3: Flood Fill

Record all points to a grid. Loop through grid, check if value is greater than 0. Increase the value of adjacent cells. Store the x and y of any cells that are set to 0. Loop until there is no longer a 0 on the grid. Return the x and y of the last 0 found.

 

Pros: 

  • Faster with more points.
  • Can be executed in step

Cons:

  • Very slow when there is not a lot of points to check.
  • Does not always return the best answers.

Video:

Spoiler

Code:

///scr_safe_space_grid_flood(avoid);
var avoid = argument0;
var focus = 32;
var ww,hh;
ww = room_width div focus;
hh = room_height div focus;
var fp_grid = ds_grid_create(ww, hh);
with(avoid){
var px,py;
px = x div focus;
py = y div focus;
if point_in_rectangle(px,py,0,0,ww,hh) then fp_grid[# x div focus,y div focus]=1
}
while(ds_grid_value_exists(fp_grid,0,0,ds_grid_width(fp_grid),ds_grid_height(fp_grid),1))
{
    for (var ix=0; ix<ds_grid_width(fp_grid); ix+=1)
    {
        for (var iy=0; iy<ds_grid_height(fp_grid); iy+=1)
        {
            if mp_grid_get_cell(ai_grid, ix,iy)==-1 then 
            {
                fp_grid[# ix,iy]=0;
                continue;
            }
            if fp_grid[# ix,iy]==1 then
            {
                for (var iix=-1; iix<=1; iix+=1)
                {
                    if ix+iix<0 then continue;
                    if ix<0 then continue;
                    if ix+iix>=ds_grid_width(fp_grid) then continue;
                    for (var iiy=-1; iiy<=1; iiy+=1)
                    {
                        if iy+iiy<0 then continue;
                        if iy<0 then continue;
                        if iy+iiy>=ds_grid_height(fp_grid) then continue;
                        if fp_grid[# ix+iix,iy+iiy] == 0 then 
                        {
                        fp_grid[# ix+iix,iy+iiy]-=1;
                        }
                    }
                }
                fp_grid[# ix,iy] += 1;
            }
            if fp_grid[# ix,iy]==0 then 
            {
                safe_x = (ix*focus)+(focus/2);
                safe_y = (iy*focus)+(focus/2);
            };
        };
    };
    for (var ix=0; ix<ds_grid_width(fp_grid); ix+=1)
    {
        for (var iy=0; iy<ds_grid_height(fp_grid); iy+=1)
        {
            if fp_grid[# ix,iy]<0 then fp_grid[# ix,iy]*=-1;
        }
    }
}
ds_grid_destroy(fp_grid);

Here is a video of the script run at real time

 

If anyone knows of a better way of finding the answer please let me know.

 

Thank you,

Trevor


Edited by webber17, 16 February 2016 - 06:37 PM.

  • 1

X8fburi.png

 


#2 Juju

Juju

    GMC Member

  • GMC Member
  • 1109 posts
  • Version:Unknown

Posted 16 February 2016 - 05:56 PM

Quick note: scr_diagDist mentioned in the first method is this function:

///scr_diagDist( x1, y1, x2, y2 )
var dx = abs( argument2 - argument0 );
var dy = abs( argument3 - argument1 );
return max( dx, dy ) + 0.41421356 * min( dx, dy );

This is the shortest distance between two points on a grid that permits 8-direction movement. It's a fast approximation for point_distance.


  • 2

Come find me @jujuadams

 

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.


#3 Strawbry_Jam

Strawbry_Jam

    Likes Toast

  • GMC Member
  • 345 posts
  • Version:Unknown

Posted 18 February 2016 - 04:42 AM

Since you are using ds_grid, here's an idea outside the box:
1. Clear the grid to 0.
2. Any blocked spaces add 10000.
3. With each point to avoid, find the furthest corner and save the distance (in grid cells) as that point's radius.
4. With each point, while radius is greater than 0, ds_grid_add_disk(id,gridx,gridy,radius,1) and radius -= 1.
5. Find the grid cell with smallest value.

Not sure how fast that will run but it should give the best value. I would think it would be faster than using the distance formula.
  • 2
Spoiler

#4 webber17

webber17

    GMC Member

  • GMC Member
  • 497 posts
  • Version:GM:Studio

Posted 18 February 2016 - 07:29 PM   Best Answer

Since you are using ds_grid, here's an idea outside the box:
1. Clear the grid to 0.
2. Any blocked spaces add 10000.
3. With each point to avoid, find the furthest corner and save the distance (in grid cells) as that point's radius.
4. With each point, while radius is greater than 0, ds_grid_add_disk(id,gridx,gridy,radius,1) and radius -= 1.
5. Find the grid cell with smallest value.

Not sure how fast that will run but it should give the best value. I would think it would be faster than using the distance formula.

Your method seems to work the fastest. 

 

Here is a video of it in action:

///scr_safe_space_grid(avoid);
var avoid = argument0;
var focus = 32;
var width = room_width div focus;
var height = room_height div focus;
var fp_grid = ds_grid_create(width, height);
var mp_grid = mp_grid_create(0,0,width, height,focus,focus);
var safe_x = 0;
var safe_y = 0;
ds_grid_clear(fp_grid,0);

mp_grid_add_instances(mp_grid,obj_wall,1);
mp_grid_to_ds_grid(mp_grid,fp_grid);
mp_grid_destroy(mp_grid);

ds_grid_multiply_region(fp_grid,0,0,width,height,-1000);
var r = max(width,height);
//var safe_x = 0;
//var safe_y = 0;
var r = -1;
var i = 0;
with(avoid)
{
    var corn_x = 0;
    var corn_y = 0;
    var xx = x div focus;
    var yy = y div focus;
    if xx<width/2 then corn_x = width;
    if yy<height/2 then corn_y = height;
    r[i] = scr_diagDist(xx,yy,corn_x,corn_y);
    ds_grid_set(fp_grid,xx,yy,10000);
i++;
}
var loop = true;
while(loop)
{
    loop = false;
    var i = 0;
    with(avoid)
    {
        ds_grid_add_disk(fp_grid,x div focus, y div focus,r[i],1);

        if r[i]>=0 then 
        {
            loop = true;
            r[i]-=1;
        }
i++;
    }
}
r=-1;
var min_val = ds_grid_get_min(fp_grid,0,0,width,height);
safe_x=ds_grid_value_x(fp_grid,0,0,width,height,min_val)*focus;
safe_y=ds_grid_value_y(fp_grid,0,0,width,height,min_val)*focus;
safe_x+=focus/2;
safe_y+=focus/2;
ds_grid_destroy(fp_grid);//var rtn = -1;
rtn[0] = safe_x;
rtn[1] = safe_y;
return rtn;

Thanks for the help,

Trevor


Edited by webber17, 18 February 2016 - 09:17 PM.

  • 1

X8fburi.png

 


#5 Juju

Juju

    GMC Member

  • GMC Member
  • 1109 posts
  • Version:Unknown

Posted 18 February 2016 - 07:35 PM

I find it hard to believe that s.jam's method is the fastest. Surely ds_grid_add_disk is slower than a distance approximation.

 

Edit: Mmmyep, my own tests have confirmed that ds_grid_add_disk just is that fast. Either this is down to better CPU support for square roots (support for square root on the metal), some kind of lookup table trickery with ds_grid_add_disk (unlikely), or me underestimating how slow GML is even under YYC.

 

...still doesn't sit right. Oh well.


Edited by Juju, 18 February 2016 - 08:51 PM.

  • 1

Come find me @jujuadams

 

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.


#6 Strawbry_Jam

Strawbry_Jam

    Likes Toast

  • GMC Member
  • 345 posts
  • Version:Unknown

Posted 19 February 2016 - 03:36 AM

I find it hard to believe that s.jam's method is the fastest. Surely ds_grid_add_disk is slower than a distance approximation.
 
Edit: Mmmyep, my own tests have confirmed that ds_grid_add_disk just is that fast. Either this is down to better CPU support for square roots (support for square root on the metal), some kind of lookup table trickery with ds_grid_add_disk (unlikely), or me underestimating how slow GML is even under YYC.
 
...still doesn't sit right. Oh well.

I'd assume that they were using some algorithm for the disk that would be way faster than the distance formula. Something like the midpoint circle algorithm. Grid cells can be treated as int positions to run through the algorithm really fast. My other assumption was ds grids are already extremely fast.

Edited by Strawbry_Jam, 19 February 2016 - 03:39 AM.

  • 2
Spoiler

#7 Juju

Juju

    GMC Member

  • GMC Member
  • 1109 posts
  • Version:Unknown

Posted 19 February 2016 - 04:48 AM

The thing that baffles me is the scale of the difference. For an enemy/avoid-point right in the middle of a 32x24 cell grid (a 1024x768 room divided into 32x32 cells), which is 768 cells total, it's faster to use concentric disks than to calculate a distance for each cell.

 

The disk method ends up writing about 6,620 times to the grid, which requires thousands of distance calculations of some kind, and then has to do a full pass to find the minimum point as well.

 

The per-cell method doesn't even need to write data to the grid to get an answer nor does it need to do a pass at the end to work out the best point (it can do that calculation as it's going along). The per-cell method doesn't even need read data from every point on the grid! It's literally just doing 768 fast distance calculations and 768 comparisons.

 

The difference between the (supposed) efficiency of both methods should be highlighted by this specific situation. This is a scenario where a concentric disk model should perform worse than the per-cell model... but it's not, it's 10% faster under YYC and much, much faster under the Runner (we're talking 80us versus 1000us here).

 

Edit: For kicks, I bumped it up to a 64x48 grid and one enemy right in the centre. The disk method is finally shown to be slower here under YYC but, yep, sure enough when you use the Runner, the disk method comes out on top again (this is kind of to be expected given how the Runner works). You have to try to find cases where the disk method is slower in YYC which is a pretty good indication it's going to be faster in the real world.

 

Anywho, the search continues for a geometric solution.


Edited by Juju, 19 February 2016 - 05:00 AM.

  • 2

Come find me @jujuadams

 

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.


#8 RujiK

RujiK

    GMC Member

  • GMC Member
  • 841 posts
  • Version:GM:Studio

Posted 23 February 2016 - 02:46 PM

This was a fun read. Props to webber for making such a thorough topic. I wish we had more discussions like this.

 

Possible idea:

     1. Make a surface (1 pixel = 1 tile would be fastest)

     2. Use a voronoi shader/script using your objects as points

     3. Dump the surface to a buffer using buffer_get_surface

     4. Find highest value in the buffer

 

Voronoi links:


  • 1

#9 Strawbry_Jam

Strawbry_Jam

    Likes Toast

  • GMC Member
  • 345 posts
  • Version:Unknown

Posted 23 February 2016 - 04:05 PM

I looked into voronoi diagrams. I think there could be slightly longer load times for this but that would allow a lot faster processing. Maintaining the diagram wouldn't be too hard or expensive. Of course this depends on how it's implemented too. The links you gave show it done through drawing. Could it be faster if it was done in a way to preserve processed data and make minor edits frame by frame? Btw never thought about cones to find voronoi diagram. Thats pretty cool.

Edited by Strawbry_Jam, 23 February 2016 - 04:12 PM.

  • 0
Spoiler

#10 Juju

Juju

    GMC Member

  • GMC Member
  • 1109 posts
  • Version:Unknown

Posted 23 February 2016 - 05:46 PM

webber's original use was for a respawning system in an action game; every avoidance point is moving all the time and use of the voronoi would be infrequent.

 

Don't let that stop you, mind.


  • 0

Come find me @jujuadams

 

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.


#11 Strawbry_Jam

Strawbry_Jam

    Likes Toast

  • GMC Member
  • 345 posts
  • Version:Unknown

Posted 23 February 2016 - 06:36 PM

True but think similar to a collision system and the optimizations included. One method is to sort aabbs of instances and keep the list ready for possible collisions. While most instances aren't colliding each step, it does speed up the process when they do. Moving objects rarely pass other objects every step so minor changes to the stored list are easy and cheap. Update the voronoi diagram in a similar way and the respawn system would be able to stay fast for when it is needed. All of this is theory though. But yeah probably over kill. :)
  • 0
Spoiler

#12 RujiK

RujiK

    GMC Member

  • GMC Member
  • 841 posts
  • Version:GM:Studio

Posted 23 February 2016 - 07:24 PM

I believe a shader based voronoi would be almost instantaneous. The slow part would be searching the buffer for the highest point.

 

A voronoi shader ALONE I would estimate to be several hundred fps on a decent rig. Maybe I will try making/converting a voronoi shader in game maker, but shaders aren't exactly my strong suit.


  • 1

#13 Strawbry_Jam

Strawbry_Jam

    Likes Toast

  • GMC Member
  • 345 posts
  • Version:Unknown

Posted 23 February 2016 - 08:21 PM

The best part about the voronoi diagram is that each polygon represents all the points closest to a particular point in a group of points. Take that polygon and cycle through the points that make it up and you can find the furthest point. Compare that furthest point of all the polygons and you find your winner. If you do this in a shader, you run through all the texels in the draw call that you could possibly skip.
  • 1
Spoiler