Jump to content


Photo

Finding the nearest tile of one type in a ds_grid?


  • Please log in to reply
8 replies to this topic

#1 ariugh

ariugh

    GMC Member

  • GMC Member
  • 140 posts

Posted 27 April 2012 - 09:04 PM

A bit of background first. My game is tile-based, and uses a ds_grid to keep track of all the tiles. I want my game to find a spawn point for my player that's open, so I was thinking of ways to make him spawn in the closest open point to the center of the grid.
This is what I arrived at:

x = global.width/2;
y = global.height/2;
move_snap(global.gridsize,global.gridsize);
i = 1;
count = 0;
found = false;
while(found == false) {
    if ds_grid_get(global.dungeon,x,y) == dt_air then found = true;
    if(count == i) {
        direction += 90;
        count = 0;
        i += 1;
    }
    else {
        x += lengthdir_x(global.gridsize,direction);
        y += lengthdir_y(global.gridsize,direction);
    }
    count += 1;
}

posx = x;
posy = y;

but for some reason, it refuses to work, and just spawns me outside of the room.
Any ideas?
  • 0

#2 Spikehead777

Spikehead777

    GMC Member

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

Posted 27 April 2012 - 09:30 PM

First, you might want to round the x and y values in case you get fractional values.

Next, you might be spawning outside of the room because of your incrementing expressions:
x += lengthdir_x(global.gridsize,direction);
y += lengthdir_y(global.gridsize,direction);

More specifically, if your global.gridsize variable is too large, you'll quickly find your respawn code spawns your player outside of the room. You might consider leaving the global.gridsize variable as a multiplier for your x and y values at the end of your code.
  • 0

#3 IceMetalPunk

IceMetalPunk

    InfiniteIMPerfection

  • Retired Staff
  • 9322 posts
  • Version:Unknown

Posted 27 April 2012 - 09:54 PM

All you need to do is a breadth-first search. Essentially Dijkstra's Algorithm, but with the modification that when it adds a node to the visited set, if it's an air space, the algorithm can terminate right there since it knows it's found the nearest free space. (So it's Dijkstra's goal-path algorithm, only where any and all open spaces are valid goals).

In my implementation, I'll be using a temporary ds_grid to contain the distances of each cell from the center. I'm also using a ds_map to store the visited nodes since that will make it faster when checking if a node has been visited or not (O(log n) instead of O(n) like a list would be).

var visited, dists, Q, xx, yy, found, tdist, dist, cdist, tx, ty, cx, cy;
Q=ds_queue_create();
visited=ds_map_create();
dists=ds_grid_create(global.width, global.height);
ds_grid_clear(dists, -1);

ds_queue_enqueue(Q, global.width/2);
ds_queue_enqueue(Q, global.height/2);
ds_grid_set(dists, global.width/2, global.height/2, 0);

found=false;
while (!ds_queue_empty(Q)) {
  xx=ds_queue_dequeue(Q);
  yy=ds_queue_dequeue(Q);

  dist=ds_grid_get(dists, xx, yy);
  cdist=global.width*global.height+128;
  cx=-1;
  cy=-1;

  if (ds_grid_get(global.dungeon, xx, yy)==dt_air) {
    found=true;
    cx=xx;
    cy=yy;
    break;
  }
  
  for (tx=-1; tx<=1; tx+=1) {
    for (ty=-1; ty<=1; ty+=1) {
      if (ty==0 && tx==0) { continue; }
      if (xx+tx<0 || yy+ty<0 || xx+tx>=global.width || yy+ty>=global.height) { continue; }
      if (ds_map_exists(visited, string(xx+tx)+"|"+string(yy+ty))) {
        tdist=ds_grid_get(dists, xx+tx, yy+ty);
        tdist=min(tdist, cdist+1);
        if (tdist<0 || tdist==cdist+1) {
          ds_grid_set(dists, xx+tx, yy+ty, tdist);
        }
        if (tdist<cdist) {
          cdist=tdist;
          cx=xx+tx;
          cy=yy+ty;
        }
      }
    }
  }
  
  ds_map_add(visited, string(xx)+"|"+string(yy), 0);
  
  if (cx!=-1 && cy!=-1) {
    ds_queue_enqueue(Q, cx);
    ds_queue_enqueue(Q, cy);
  }
}

ds_queue_destroy(Q);
ds_map_destroy(visited);
ds_grid_destroy(dists);

if (found) {
  ret=ds_list_create();
  ds_list_add(ret, cx);
  ds_list_add(ret, cy);
  return ret;
}
else { return -1; }

It returns -1 if no air spaces were found or a 2-element ds_list containing the (x, y) position in the ds_grid of the nearest air space.

-IMP
  • 2

#4 xot

xot

    GMC Dismember

  • Retired Staff
  • 4772 posts
  • Version:GM:Studio

Posted 28 April 2012 - 12:47 AM

My approach would be a bit simpler.

  • set radius to 1 or another low value
  • use ds_grid_value_disk_exists() to check for dt_air
  • if it returned true, find the coordinates of dt_air with ds_grid_value_disk_x() and ds_grid_value_disk_y() and stop searching
  • if it returned false, increase radius by one (or another low value) and go to step 2

It might not be as technically sophisticated or efficient as Dijkstra's algorithm, but since the hard work is being done by the built-in compiled functions, it is easier to implement and I suspect it is also faster. Try both. I'm curious to see which works better for you.
  • 1

#5 IceMetalPunk

IceMetalPunk

    InfiniteIMPerfection

  • Retired Staff
  • 9322 posts
  • Version:Unknown

Posted 28 April 2012 - 09:00 AM

You know, I completely forgot about the disk functions. Yeah, that's probably a much better solution.

-IMP
  • 0

#6 DanRedux

DanRedux

    GMC Member

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

Posted 01 May 2012 - 07:40 PM

Even though Xot's idea is better as it's all pre-compiled functions (it was my solution to this problem, too), I have to commend IMP on implementing DJikstra's algorithm especially given that this is just a question. Good job, +1'd.
  • 0

#7 Gamer3D

Gamer3D

    Human* me = this;

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

Posted 02 May 2012 - 01:03 AM

I propose a revision to xot's method (should perform better on average):

  • Set radius_inner to 0 and radius_outer to some power of 2 that is close to your guess about how far away the nearest cell is (round up to nearest power of 2).
  • Use ds_grid_value_disk_exists() with radius radius_outer to check for dt_air
  • If it returned false, set radius_inner to radius_outer, then double radius_outer and go to step 2. Otherwise, go to step 4
  • Use ds_grid_value_disk_exists() with radius (radius_inner + radius_outer) / 2 to check for dt_air
  • If it returned true, set radius_outer to (radius_inner + radius_outer) / 2. Otherwise, set radius_inner to (radius_inner + radius_outer) / 2.
  • If (radius_outer - radius_inner) >= 1, go to step 4. Otherwise, return a point with value dt_air in the disk with radius radius_outer.

  • 0

#8 xot

xot

    GMC Dismember

  • Retired Staff
  • 4772 posts
  • Version:GM:Studio

Posted 02 May 2012 - 06:28 AM

Ah, yeah. Applying a binary search to that method is a good idea, Gamer3D. If finding the absolute nearest cell with value dt_air is unimportant, you could raise the threshold level in step six by a few spaces to speed things up even more. (ie. (radius_outer - radius-inner) >= threshold)
  • 0

#9 Gamer3D

Gamer3D

    Human* me = this;

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

Posted 02 May 2012 - 07:49 AM

Ah, yeah. Applying a binary search to that method is a good idea, Gamer3D. If finding the absolute nearest cell with value dt_air is unimportant, you could raise the threshold level in step six by a few spaces to speed things up even more. (ie. (radius_outer - radius-inner) >= threshold)

The thing I'm wondering most about is if, at some point, it will be better to use a custom function. I'm not particularly fond of repeatedly calling O(n^2) functions, and worst-case for our method is going to be O(n^2 log n) or so.

EDIT: To explain it better, a custom function could be O(n^2) and have a potential early exit, so for a sufficiently large search radius the custom function will be faster, no matter how slow the pixel-checking is. I'm wondering if the radius beyond which the custom function is better might reasonably occur in a game.

Edited by Gamer3D, 02 May 2012 - 07:59 AM.

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users