MathJax example

A* Pathfinding

This project includes an implementation of an A* pathfinding algorithm on 3D meshes. The pathfinder includes parametrized cost function that allows users to adjust weights based on the edge slopes, vertical step distance, and turning angle. For efficiency, the algorithm is implemented in C++ using Houdini's "inlinecpp" Python module. It works similar to Houdini's native "Shortest Path" node and both solutions have provided similar results. Users are free to extend and customize the cost function based on their project needs.

As always, project files are available for download on Patreon.


A_Star(Graph, StartNode, EndNode):
  //all Graph nodes except StartNode are
  //initialized with fScore and gScore of infinity
  StartNode.fScore = 0
  StartNode.gScore = 0
  //pq - priority queue based on Node's f score
  priorityQueue = {}
  while priorityQueue.size() > 0 do:

    currentNode =

    if currentNode == EndNode do:
      path = {}
      nextNode = currentNode->parent

      while nextNode do:
          nextNode = nextNode->parent

      return path

    for each neighbour of currentNode do:
      gScore = currentNode.gScore + stepCost

      if gScore < current gScore of neighbour do:
        newNode = neighbour
        newNode.gScore = gScore
        newNode.fScore = h(neighbour) + gScore
        newNode.parent = currentNode


The A* algorithm paths through an input graph from a starting node to an end node. At each step, it evaluates a function \(f(n) = h(n) + g(n)\)

Here, \(h(n)\) is a distance estimate from current node to the end node, often computed as Euclidean distance.

\(g(n)\) represents the cost to reach a given node from the start node.

The nodes with the lowest f-score will be explored first. The algorithm stops when the end node is reached or when the priority queue is empty.

Users can adjust parametrized cost functions to change the pathfinding output based on factors like terrain slopes or turning angles.