Detect obstacles in path on a tile-based map

Question

I'm creating a 2d game with a tile-based map, but smooth movement. I currently use A* in combination with some other tricks for pathfinding, and one issue what I've been dealing with is getting the units to move smoothly despite tile-based pathfinding.

My solution at the moment is the use raycasting to determine if there is an obstacle between a unit and its target. If there is, it uses A*. Otherwise, it just sets its next move directly as the coordinates of its target. In the case that it uses A*, I also use raycasting to determine which point in the path the unit should move to next, by finding the nearest point in the path that is not obstructed from the units current location, and setting that as the next move. This is necessary so the unit doesn't have to move in a jerky fashion based on the tile-based path that the A* found.

Raycasting is faster than A* every time, but it still has some overhead with a large number of units since it checks every point on the line in small increments. (More so since I'm doing double raycasting each time to account for the size bounds of the unit)

My question is: Is there a better algorithm than raycasting to determine if there is an obstacle between two points (independent of the tiles structure) on a tile-based map? My thought is that there is some way to take advantage of the tiled nature of the map.

Answer 1

By using continuous agent positions on a tiled map, the translation from a tile-list path to a points-list path is best served by a Funnel Algorithm. Basically doing what you have been, but only checking intermediate tile-vertices on the path that are next to an obstacle (which will naturally be where the tile-path has a bend).

I see ray-tracing as fundamental to discovering unobstructed path segments on your polygonal map, but one can use broad phase checks to potentially speed it up. Its sorta like having bounding boxes for the obstacles, if the tile stores yes/no/maybe clearance then the ray can return a result from intersecting the tiles (which are cheap to find due to regular pattern) and not need to check the contained (arbitrary polygon) obstacles.