8
\$\begingroup\$

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!

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.

\$\endgroup\$
  • \$\begingroup\$ I would use two Besenham's lines at half-tile width. \$\endgroup\$ – Jonathan Connell Jul 1 '11 at 12:59
1
\$\begingroup\$

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:

\$\endgroup\$
0
\$\begingroup\$

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:

enter image description here

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.

\$\endgroup\$
0
\$\begingroup\$

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

tracing a tile-sized line over a grid

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;
      }
    }
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.