I am developing a game that involves pathfinding on terrain where different surfaces have different movement costs (e.g., snow, mud, etc.). I need an any-angle pathfinding algorithm that works efficiently on an infinite weighted grid with these varying terrain costs. The goal is to find the shortest path that accounts for the weights of each type of terrain.

I’ve tried implementing a cost function for Theta* that consideres the weight of each node under the line between each waypoint into account, but that didn’t work. It was very inefficient and didn’t find an optimal path. It often searched in the opposite direction.

function cost(node1, node2)
    initialize totalCost to 0

    points = supercover(node1, node2)

    for each point in points except the last one do
        node = getNode(point.x, point.y)
        nextPoint = next point in points
        nextNode = getNode(nextPoint.x, nextPoint.y)
        
        if nextNode is not found then
            exit loop
        end

        distance = euclidean_distance(node, nextNode)

        if nextNode.material exists in costs then
            multiplier = costs[nextNode.material]
        else
            multiplier = 1
        end

        totalCost = totalCost + (distance * multiplier)
    end

    return totalCost
end function