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'm looking for the best solution to pathfinding in my game. The map is ultimately grid-based, but entities are positioned using floats, and can move in any direction to any point on the map. The 'ground' in my game has a uniform movement cost, but of course there can be obstacles that block the way. The majority of obstacles will be static, and although there will be other animate entities in the game, I may get away with not considering them - it's an isometric Theme Hospital style strategy game, so no fighting.

Most of the path-finding articles I've seen cover 3D or grid-based 2D movement. Any suggestions for something that might cover my use-case? Many thanks.

share|improve this question
    
Don't have time for a proper answer right now, but you might want to look at this question: stackoverflow.com/questions/4054701/…. –  Christian Jul 11 '13 at 15:40

1 Answer 1

up vote 8 down vote accepted

This is called the "any-angle pathfinding problem." You basically have two choices:

  1. Generate a navigation mesh for your map and search over that using A*

    Navigation mesh

  2. Search over a grid using an algorithm meant specifically for any-angle pathfinding. Traditionally, the way to do this was A* + path-smoothing (linear interpolation, etc), but these days a more popular alternative is Theta*, which is easier to implement, runs faster, and produces better results than path-smoothing.

    Theta* vs. path smoothing

All of the above methods generate near optimal results. If for some reason you need optimal results, this paper was released a few weeks ago. I haven't had a chance to read it yet, though, so I don't know how efficient it is, or how difficult it is to implement.

share|improve this answer
    
Great, thanks! I have no need for totally optimal results, as long as it's close. –  tommaisey Jul 11 '13 at 16:34
1  
Just thought I'd add this article to the ones you listed. It seems like a more succinct version of the paper you linked, by one of the original paper's authors. I think I'm gonna go with Theta*, cheers. –  tommaisey Jul 11 '13 at 16:52

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.