Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Layne Nov 3 '12 at 16:20
2  
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

1 Answer 1

up vote 8 down vote accepted

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)

share|improve this answer
1  
great links, +1 from me –  lhk Nov 3 '12 at 19:00
2  
@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. :) –  Md. Mahbubur R. Aaman Nov 4 '12 at 14:56
    
@MarkusvonBroady, would you please share several resource of path smoothing algorithm? –  Md. Mahbubur R. Aaman Nov 4 '12 at 15:08
    
@MarkusvonBroady, Thanks for sharing :) –  Md. Mahbubur R. Aaman Nov 4 '12 at 15:16
    
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. –  Sean Middleditch Nov 4 '12 at 19:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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