2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can have a look at one of my older answer, if it is what you are looking for. \$\endgroup\$ – wondra Aug 31 '14 at 12:01
5
\$\begingroup\$

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. Output of my painfully-hacky C++ implementation

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Is your implementation (while buggy) available for review? Did you implement the basic form, or the lazy Theta*? Theta* is on my list to try implementing in my pathfinding engine. \$\endgroup\$ – Steven Dec 5 '14 at 6:25
  • \$\begingroup\$ Not currently, but there's no particular reason for that beyond its hideousness. I might tidy it up a bit this weekend and post it. It's only the basic form. :-) \$\endgroup\$ – FLHerne Dec 5 '14 at 17:47
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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

enter image description here

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.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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