Smooth path/direct movement

Question

I have a tile based isometric map and an A* algorithm that returns a path. I am looking to smooth this path efficiently but with good aesthetics. Basically i am using my grid for building the map and pathfinding but i want the player, enemies and certain types of objects to be detached from this grid.

I can think of a line of sight implementation where i start at the first tile of the path, from there check each further tile if i have a clear path straight to it. And repeat from there.

Answer 1

You could look at Theta* - it's invented for exactly that purpose.

Pretty much like A*, except when adding a node it tests if the new node can be reached directly from the active node's parent, and if so from that node's parent, and so on. It produces very-nearly-perfect paths in most conditions.

Image is the output of my very, vey buggy C++ implementation.

Answer 2

I have implemented A* pathfinding on a hexagonal grid in C# that nicely smooths paths like so in the HexGridUtilitiesForGames project (under the MIT License):

Key portions of the code are reproduced here.

void ExpandNeighbour(IDirectedPath path, NeighbourHex neighbour) {
  if ( ! OpenSet.Contains(neighbour.Hex.Coords)) {
    var cost = StepCost(neighbour.Hex, neighbour.HexsideExit);
    if (cost > 0) {
      var newPath = path.AddStep(neighbour, cost);
      var key     = Estimate(Heuristic, VectorGoal, Source.Coords, 
                             neighbour.Hex.Coords, newPath.TotalCost);

      TraceFindPathEnqueue(neighbour.Hex.Coords, key>>16, (int)(key & 0xFFFFu));

      Queue.Enqueue(key, newPath);
    }
  }
}

static int Estimate(Func<int,int> heuristic, IntVector2D vectorGoal, HexCoords start, 
        HexCoords hex, int totalCost) {
  var estimate   = heuristic(start.Range(hex)) + totalCost;
  var preference = Preference(vectorGoal, start.Canon - hex.Canon);
  return (estimate << 16) + preference;
}

static int Preference(IntVector2D vectorGoal, IntVector2D vectorHex) {
  return (0xFFFF & Math.Abs(vectorGoal ^ vectorHex ));
}

/// <summary>Z component of the 'Vector'- or Cross-Product of two IntVector2Ds</summary>
/// <returns>A pseudo-scalar (it reverses sign on exchange of its arguments).</returns>
public static int operator ^ (IntVector2D v1, IntVector2D v2) {
  return v1.X*v2.Y - v1.Y*v2.X;
}

The ^ operator above on the IntVector2D objects is overloaded to perform a 2D cross-product (as shown), which measures the orthogonality of the two vector factors. The A* heuristic is shifted 16 bits right and the absolute value of the cross product is added to the heuristic value, causing paths which are more visually direct to be favored.

Answer 3

What you're looking for might be more of a steering technique than a path finding technique.

There is a simple steering technique that you can use when there are no dynamic obstacles. Since you already use A* you have the skeleton of a path (regions connected by straight lines). By having your agent move directly towards the furtherst point on the path it can see the path is automatically smoothened and shortened.

This approach creates smooth paths since each frame the agent will be able to look a tiny bit further, which will lead to tiny adjustments to its rotation.

This approach creates short paths since each frame it will move a bit closer on a straight line to the furthest visible point. There is no shorter path between two points than a straight line.

Of course when you add dynamic obstacles such as other agents path following becomes a lot more difficult but as a basis this is a very nice way to do it. You might want to look up papers which mention velocity obstacles and force and velocity based steering.