I have implemented A* pathfinding on a hexagonal grid in C# that nicely smooths paths like so in the HexGridUtilitiesForGames project (in an opensource project underunder 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 IntVector2DIntVector2D 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.
