Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
I would use two Besenham's lines at half-tile width. – Jonathan Connell Jul 1 '11 at 12:59

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:

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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