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.

  • \$\begingroup\$ 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. \$\endgroup\$
    – user22553
    Commented Nov 3, 2012 at 16:20
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ Commented Nov 4, 2012 at 15:18
  • \$\begingroup\$ You are right.My path was flawed, but it was more for an illustration purpose.Thanks for pointing the better way to look into. \$\endgroup\$ Commented Nov 4, 2012 at 15:52
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Nov 4, 2012 at 16:52
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Nov 4, 2012 at 17:07

2 Answers 2


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.


Further Reading

EDIT : I like @MarkusvonBroady's comment.

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


From @MarkusvonBroady

I have made a search, find the followings (those may help you)

  • 2
    \$\begingroup\$ @MarkusvonBroady, Thanks for -1. I have learned from you. I don't want point, rather I am willing to learn and share the right one. I believe by discussing we can find the right one. :) \$\endgroup\$ Commented Nov 4, 2012 at 14:56
  • \$\begingroup\$ @MarkusvonBroady, would you please share several resource of path smoothing algorithm? \$\endgroup\$ Commented Nov 4, 2012 at 15:08
  • \$\begingroup\$ Actually, I think this answer does help the OP. I don't think the OP was asking for actual smoothing (spline interpolation or the like) but rather that his algorithm is currently finding a horribly non-optimal path and needs to be "smoothed" into a straighter line. Which A* would naturally have found for him without any additional smoothing. \$\endgroup\$ Commented Nov 4, 2012 at 19:36
  • \$\begingroup\$ I had been using A* and I think I had found the optimal path. \$\endgroup\$ Commented Nov 4, 2012 at 19:49
  • 1
    \$\begingroup\$ Half of the links are dead now. That is why SO (and GDSE) recommend to include essential details the into the answer, rather than linking. \$\endgroup\$
    – Kromster
    Commented Sep 19, 2015 at 9:55

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.

This will not only smooth the path but also remove some useless points, like fire example, 3 consecutive segments of a straight line.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .