8 replies to this topic

[ariugh]

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?

[Spikehead777]

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.

[IceMetalPunk]

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

[xot]

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.

[IceMetalPunk]

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

-IMP

[DanRedux]

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.

[Gamer3D]

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.

[xot]

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)

[Gamer3D]

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.