# 2D pathfinding - finding smooth paths

I was trying to implement a simple pathfinding, but the outcome is less satisfactory than what I intended to achieve. The thing is units in games like Starcraft 2 move in all directions whereas units in my case only move in at most 8 directions (Warcraft 1 style) as these 8 directions direct to next available nodes (they move from a tile to next neighboring tile). What should I do in order to achieve the result as in Starcraft 2? Shrink the tile size?

On the picture you can see a horizontal line of rock tiles being obstacles, and the found path marked as green tiles. The red line is the path I want to achieve.

• I'm a huge fan of jump point search although I haven't found the time to implement it yet. But the documentation was interesting and has a good performance. – user22553 Nov 3 '12 at 16:20
• Are you sure that's your desired path? Units using it will partially go through walls. I made it more visible in another example: i.imgur.com/eh4ZR.png And here's what you probably really want to achieve: i.imgur.com/vFQg4.png – Markus von Broady Nov 4 '12 at 15:18
• You are right.My path was flawed, but it was more for an illustration purpose.Thanks for pointing the better way to look into. – Kooi Nam Ng Nov 4 '12 at 15:52
• You'll have to have fractional coordinates within a tile to get what you want. No possible path without this would work--carrying the fractions but not displaying them would make your unit move straight/diagonal/straight/diagonal. – Loren Pechtel Nov 4 '12 at 16:52
• @LorenPechtel you are wrong, you can smooth the path after finding one. It's quite easy as you create two lines based on unit's dimensions, and check if they intersect with tiles between tile0 and tileN, where tile1-tile(N-1) are tiles you want to remove from path. – Markus von Broady Nov 4 '12 at 17:07

For a good pathfinding algorithm, using A* would probably be a good idea, however, for a simple game that doesn't require sophisticated, efficient, nor effective path searching, simply having the characters move toward a target by finding out the direction of the target should be sufficient.

You can do is generate a 'visibility graph'(what other points are visible from each point) from the vertices and then perform A* on the graph. This works because the shortest path will always lie on the visibility graph.

Shrink the tile size may help you.

Resources

EDIT : I like @MarkusvonBroady's comment.

"it is actually about path smoothing, not finding. The path found on the picture looks OK."

Resources

Starting from one end of the raw path, say path[0], you can remove path[1] if the segment formed by joining the points of path[0] and path[2] does NOT intersect any wall. Going further until the last segment will provide a simpler path.