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.


1 Answer 1


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.

  • \$\begingroup\$ Great, thanks! I have no need for totally optimal results, as long as it's close. \$\endgroup\$
    – tommaisey
    Commented Jul 11, 2013 at 16:34
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – tommaisey
    Commented Jul 11, 2013 at 16:52
  • \$\begingroup\$ Link does not work. Please update answer. \$\endgroup\$
    – firelynx
    Commented Sep 23, 2016 at 9:49
  • 1
    \$\begingroup\$ For anyone reading this in the modern era, there's a really nice "Empirical Comparison of Any-Angle Path-Planning Algorithms" from 2015, here: idm-lab.org/bib/abstracts/papers/socs15a.pdf Specifically, Sub-2, Block A*, and ANYA are interesting contenders, depending on your needs. \$\endgroup\$
    – Dan
    Commented Mar 11 at 4:32

You must log in to answer this question.

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