10
\$\begingroup\$

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?

http://i.stack.imgur.com/lr19c.jpg

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.

\$\endgroup\$
  • \$\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 Nov 3 '12 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\$ – Markus von Broady Nov 4 '12 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\$ – Kooi Nam Ng Nov 4 '12 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\$ – Loren Pechtel Nov 4 '12 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\$ – Markus von Broady Nov 4 '12 at 17:07
8
\$\begingroup\$

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

Further Reading

EDIT : I like @MarkusvonBroady's comment.

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

Resources

From @MarkusvonBroady

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

\$\endgroup\$
  • 1
    \$\begingroup\$ great links, +1 from me \$\endgroup\$ – lhk Nov 3 '12 at 19:00
  • 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\$ – Md Mahbubur Rahman Nov 4 '12 at 14:56
  • \$\begingroup\$ @MarkusvonBroady, would you please share several resource of path smoothing algorithm? \$\endgroup\$ – Md Mahbubur Rahman Nov 4 '12 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\$ – Sean Middleditch Nov 4 '12 at 19:36
  • \$\begingroup\$ I had been using A* and I think I had found the optimal path. \$\endgroup\$ – Kooi Nam Ng Nov 4 '12 at 19:49
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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