Smoothing found path on grid

Question

I implemented several approaches such as A* and Potential fields for my tower defense game. But I want smooth paths, first I tried to find path on very small grid ( 5x5 pixels per tile) but it is extremly slow. I found nice video showing an RTS demo where paths are found on big grid but units dont move from each cell's center to center. How do I implement such behavior? Some examples would be great.

Answer 1

There's actually a pretty nice article about this at Gamasutra (7 pages!). While Beizer curves will smooth a path, it won't cut across grid spaces like in your video example.

For example (from the article):

• (a) is the result of a standard A* search, while
• (b) shows the results of a postprocess smoothing operation.
• (c) shows the application of a turning radius for curved turns.
• (d) illustrates an A* modification that will enable searches to include curved turns that avoid collisions.

Answer 2

Try finding a normal path using A* or BFS or Dijkstra on the grid. Later use a beizer curve and make units move on it. This will generate a smoother path.

Answer 3

Note that while the Bezier curve answer given by Gajet will smooth the individual links on the path, it won't result in the smoothest or simplest path on its own.

You will need to remove unnecessary nodes from the path first, simplifying the overall path, and then build a curve from that.

Simplifying the path can be done several different ways. The naive way is to just do a line of sight between nodes and remove any needs between them of the line of sight passes. However, this can and will cause the generated paths to occasionally run too close to the corners of walls, causing agents to run into or clip through them.

You can use the line of sight tests from the outer edges of the nodes based on the agent's radius. That is, take the vector between the two nodes, then take the positive and negative normals to that vector, normalized, and add the agent's radius. Add those vectors to the original two nodes' positions, and ray cast between those modified points.

Another option that will fail in more cases but can be cheaper is to just take the box formed by the two nodes and check to see if any walls are in that area.

After you have the simplified path, you can smooth it with a curve if you want. You may not need to, depending on how you want the agents' movement to look.

Answer 4

In addition to approaches mentioned above answers to smooth out paths with some post-proccessing, another approach is to use a grid geometry other than square tiles to get a closer approximation of the optimal path to begin with. Picture below shows the path approximated using square Tiles, Hex, Octal(means Tile+diagonal) in comparison to actual optimal path (linear distance).

You can see that Hex and Oct grids give better approximations than square tiles. The picture was take from this paper Grid-based Path Finding. Note that the paper actually recommends Hex over Oct because of performance reasons. The paper also addresses the difficulty of implementing Hex grids (since they can't be treated like simple AABBs), by proposing a new scheme called Tex grids. Tex grids are topologically equivalent to Hex grids ( meaning they generate the same 6 degrees per node graph), and thus give same performance in terms accuracy in representing optimal path. Shown below is a typical Tex grid:

Note that the main focus of that paper was actually to improve performance of IDA (Iterative Deepening A*) search, which will definitely be important in an RTS game I'm sure. It was shown in the paper both from empirical results and math using Hex grids makes IDA exponentially faster than Tiles (square grid).

Downside is, like many papers I've read, it does not give you implementation details : (