Tile-wide extent tracing on a grid

Question

I'm currently working on A* pathfinding on a grid and I'm looking to smooth the generated path, while also considering the extent of the character moving along it. I'm using a grid for the pathfinding, however character movement is free roaming, not strict tile to tile movement.

To achieve a smoother, more efficient path, I'm doing line traces on a grid to determine if there is unwalkable tiles between tiles to shave off unecessary corners.

However, because a line trace is zero extent, it doesn't consider the extent of the character and gives bad results (not returning unwalkable tiles just missed by the line, causing unwanted collisions).

So what I'm looking for is rather than a line algorithm that determines the tiles under it, I'm looking for one that determines the tiles under a tile-wide extent line. Here is an image to help visualize my problem!

Does anyone have any ideas? I've been working with Bresenham's line and other alternatives but I haven't yet figured out how to nail this specific problem.

Answer 1

How about if you draw a line from every corner of the 'tile' you are on to every corner of the tile you want to go to. You can probably even optimize this to 3 lines instead of four. Wouldn't this correctly detect all the tiles on the path?

As for smoother paths, check articles about 'steering behaviour' especially those combining it with A* for example these links:

• http://rocketmandevelopment.com/2010/11/10/a-star-and-pathfollowing-steering-behavior/
• http://www.red3d.com/cwr/steer/

Answer 2

I've just implemented this algorithm for a game of mine a couple of days ago! (-8

Here's my idea in a picture form:

Note that the algorithm works with rectangles of any size. it's based on the fact that one corner of the rectangle always collides first with any grid line. This means that you can only trace one ray, and get all intersections you need.

Here's the algorithm step-by-step:

1. Choose the "forward" corner of your rectangle. For example, in the picture the tracing direction lies in the upper-right quadrant, so we choose upper-right corner.
2. Trace the (zero-width) ray from this corner to your destination. You would need to iterate over all intersections of your ray with grid lines.
3. For all intersections of the ray with grid lines, place your rectangle at the intersection point. Its side would lie exactly along a grid line, touching a number of grid cells. These are the tiles that your rectangle collides with at this point!

There are some edge cases here, like when the ray is exactly vertical/horizontal, or when it hits a corner exactly, but they're not difficult.

Answer 3

This procedure is an adaption of bresenham, which solves origial question.

final int cols = 64;
final int rows = 64;
color tiles = new color[cols*rows];

void squaretrace(int x1, int y1, int x2, int y2, color c) {
  if (x1==x2 && y1==y2) {
    tiles[x1+y1*cols] += c;
  } else {
    // make sure y1 is less or equal to y2
    if (y2 < y1) {
      int t = x1;
      x1 = x2;
      x2 = t;
      t = y1;
      y1 = y2;
      y2 = t;
    }
    // along y-axis
    if (x1==x2) {
      for(int y = y1; y <= y2; y++){
        tiles[x1 + y * cols] += c;
      }
    }
    // along x-axis
    else if (y1==y2) {
      int xLo, xHi;
      if(x1 < x2){
        xLo = x1;
        xHi = x2;
      }
      else{
        xLo = x2;
        xHi = x1;
      }
      for(int x = xLo; x <= xHi; x++){
        tiles[x + y1 * cols] += c;
      }
    }
    // northeast
    else if (x1 < x2) { 
      // NW and SE corner
      int dx = x2 - x1;
      int dy = y2 - y1;
      int m = 8;
      int k = (1<<m) * dx / dy;

      int minx = x1 << m;
      int maxx = (x1+1) << m;

      for (int y = y1; y <= y2; y++) {
        int xLo = minx >> m;
        if (y!=y1) minx += k;
        if (y<y2) maxx += k;
        int xHi = (maxx-1) >> m;
        for (int x = xLo; x <= xHi; x++) {
          tiles[x+y*cols] += c;
        }
        tiles[xLo+y*cols] += c;
        tiles[xHi+y*cols] += c;
      }
    }
    // northwest
    else {
      // NW and SE corner
      int dx = x2 - x1;
      int dy = y2 - y1;
      int m = 8;
      int k = (1<<m) * dx / dy;

      int minx = x1 << m;
      int maxx = (x1+1) << m;

      for (int y = y1; y <= y2; y++) {

        if (y<y2) minx += k;
        int xLo = minx >> m;
        int xHi = (maxx-1) >> m;
        if (y!=y1) maxx += k;

        for (int x = xLo; x <= xHi; x++) {
          tiles[x+y*cols] += c;
        }
        tiles[xLo+y*cols] += c;
        tiles[xHi+y*cols] += c;
      }
    }
  }
}