Pathfinding with 2D, non-grid based movement over uniform terrain

Question

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.

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*

   

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.

   

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.