Pathfinding

Functions
C_INTERFACE	CreatePath (const HF::SpatialStructures::Graph *g, int start, int end, const char *cost_type, int *out_size, HF::SpatialStructures::Path **out_path, HF::SpatialStructures::PathMember **out_data)
	Find the shortest path from start to end. More...
C_INTERFACE	CreatePaths (const HF::SpatialStructures::Graph *g, const int *start, const int *end, const char *cost_type, HF::SpatialStructures::Path **out_path_ptr_holder, HF::SpatialStructures::PathMember **out_path_member_ptr_holder, int *out_sizes, int num_paths)
	Find multiple shortest paths in paralllel. More...
C_INTERFACE	GetPathInfo (HF::SpatialStructures::Path *p, HF::SpatialStructures::PathMember **out_member_ptr, int *out_size)
	Get the size of a path and a pointer to its path members. More...
C_INTERFACE	DestroyPath (HF::SpatialStructures::Path *path_to_destroy)
	Delete a path. More...
C_INTERFACE	CreateAllToAllPaths (const HF::SpatialStructures::Graph *g, const char *cost_type, HF::SpatialStructures::Path **out_path_ptr_holder, HF::SpatialStructures::PathMember **out_path_member_ptr_holder, int *out_sizes, int num_paths)
	Find a path from every node in a graph to every other node. More...
C_INTERFACE	CalculateDistanceAndPredecessor (const HF::SpatialStructures::Graph *g, const char *cost_name, std::vector< float > **out_dist_vector, float **out_dist_data, std::vector< int > **out_pred_vector, int **out_pred_data)
	Calculate the distance and predecessor matricies for a graph. More...

Detailed Description

Find paths between different points in a graph.

Mesh setup (energy blob)

Begin by loading an .obj file:

// Status code variable, value returned by C Interface functions
// See documentation for HF::Exceptions::HF_STATUS for error code definitions.
int status = 0;
 
// Get model path
// This is a relative path to your obj file.
const std::string obj_path_str = "energy_blob_zup.obj";
 
// Size of obj file string (character count)
const int obj_length = static_cast<int>(obj_path_str.size());
 
// This will point to memory on free store.
// The memory will be allocated inside the LoadOBJ function,
// and it must be freed using DestroyMeshInfo.
std::vector<HF::Geometry::MeshInfo>* loaded_obj = nullptr;
 
// Load mesh.
// Notice that we pass the address of the loaded_obj pointer
// to LoadOBJ. We do not want to pass loaded_obj by value, but by address --
// so that we can dereference it and assign it to the address of (pointer to)
// the free store memory allocated within LoadOBJ.
const std::array<float, 3> rot { 0.0f, 0.0f, 0.0f };    // No rotation.
status = LoadOBJ(obj_path_str.c_str(), obj_length, rot[0], rot[1], rot[2], &loaded_obj);
 
if (status != 1) {
    // All C Interface functions return a status code.
    // Error!
    std::cerr << "Error at LoadOBJ, code: " << status << std::endl;
}
else {
    std::cout << "LoadOBJ loaded mesh successfully into loaded_obj at address " << loaded_obj << ", code: " << status << std::endl;
}

Then, review the example at Raytracer setup (how to create a BVH).

Graph generation

You will then generate a graph, using the BVH:

// Define start point.
// These are Cartesian coordinates.
// If not above solid ground, no nodes will be generated.
const std::array<float, 3> start_point{ -30.0f, 0.0f, 20.0f };
 
// Define spacing.
// This is the spacing between nodes, with respect to each axis.
// Lower values create more nodes, yielding a higher resolution graph.
const std::array<float, 3> spacing{ 2.0f, 2.0f, 180.0f };
 
// Value of - 1 will generate infinitely many nodes.
// Final node count may be greater than this value.
const int max_nodes = 5000;
 
const int up_step = 30;                 // Maximum step height the graph can traverse.
                                        // Steps steeper than this are considered to be inaccessible.
 
const int down_step = 70;               // Maximum step down the graph can traverse.
                                        // Steps steeper than this are considered to be inaccessible.
 
const int up_slope = 60;                // Maximum upward slope the graph can traverse (in degrees).
                                        // Slopes steeper than this are considered to be inaccessible.
 
const int down_slope = 60;              // Maximum downward slope the graph can traverse (in degrees).
                                        // Slopes steeper than this are considered to be inaccessible.
 
const int max_step_connections = 1;     // Multiplier for number of children to generate for each node.
                                        // Increasing this value increases the number of edges in the graph,
                                        // therefore increasing the memory footprint of the algorithm overall.
    
const int min_connections = 1;          // The required out-degree for a node to be valid and stored.
                                        // This must be greater than 0 and equal or less than the total connections created from max_step_connections.
                                        // Default is 1. A value of 8 when max_step_connections=1 would be a grid.
 
const int core_count = -1;              // CPU core count. A value of (-1) will use all available cores.
 
// Generate graph.
// Notice that we pass the address of the graph pointer into GenerateGraph.
//
// GenerateGraph will assign the deferenced address to a pointer that points
// to memory on the free store. We will call DestroyGraph to release the memory resources later on.
HF::SpatialStructures::Graph* graph = nullptr;
 
status = GenerateGraph(bvh, start_point.data(), spacing.data(), max_nodes,
    up_step, down_step, up_slope, down_slope,
    max_step_connections, min_connections, core_count, &graph);
 
if (status != 1) {
    std::cerr << "Error at GenerateGraph, code: " << status << std::endl;
}
else {
    std::cout << "Generate graph ran successfully - graph stored at address " << graph << ", code: " << status << std::endl;
}
 
// Always compress the graph after generating a graph/adding new edges
status = Compress(graph);
 
if (status != 1) {
    // Error!
    std::cerr << "Error at Compress, code: " << status << std::endl;
}

Get nodes from graph

You can retrieve the nodes from the generated graph like this:

// Get nodes.
//
// The address of the local variable node_vector will be passed to GetAllNodesFromGraph;
// it will be dereferenced inside that function and assigned memory via operator new.
//
// We will have to call DestroyNodes on node_vector to properly release this memory.
// node_vector_data points to the internal buffer that resides within *(node_vector).
//
// When we call DestroyNodes, node_vector_data's memory will also be released.
std::vector<HF::SpatialStructures::Node>* node_vector = nullptr;
HF::SpatialStructures::Node* node_vector_data = nullptr;
 
status = GetAllNodesFromGraph(graph, &node_vector, &node_vector_data);
 
if (status != 1) {
    // Error!
    std::cerr << "Error at GetAllNodesFromGraph, code: " << status << std::endl;
}
 
// Get size of node vector
int node_vector_size = -1;
status = GetSizeOfNodeVector(node_vector, &node_vector_size);
 
if (status != 1) {
    // Error!
    std::cerr << "Error at GetSizeOfNodeVector code: " << status << std::endl;
}
 
// Print number of nodes in the graph
const int max_node = node_vector_size - 1;  // This is the max index of *node_vector
std::cout << "Graph Generated with " << node_vector_size << " nodes" << std::endl;

Destroy nodes from graph

When you are finished with the graph node container, you must destroy it:

// destroy vector<Node>
status = DestroyNodes(node_vector);
 
if (status != 1) {
    std::cerr << "Error at DestroyNodes, code: " << status << std::endl;
}

Destroy graph

When you are finished with the graph, you must destroy it:

// destroy graph
status = DestroyGraph(graph);
 
if (status != 1) {
    std::cerr << "Error at DestroyGraph, code: " << status << std::endl;
}

Function Documentation

CalculateDistanceAndPredecessor()

C_INTERFACE CalculateDistanceAndPredecessor	(	const HF::SpatialStructures::Graph *	g,
		const char *	cost_name,
		std::vector< float > **	out_dist_vector,
		float **	out_dist_data,
		std::vector< int > **	out_pred_vector,
		int **	out_pred_data
	)

#include <Cinterface/pathfinder_C.h>

Calculate the distance and predecessor matricies for a graph.

Parameters

g	The graph calculate the distance and predecessor matricies for
cost_name	The name of the cost type to use for generating paths. Leaving as an empty string will use the default cost of g.
out_dist_vector	Pointer to be updated with a vector containing the distance matrix
out_dist_data	Pointer to be updated with a pointer to the data contained by out_dist_vector
out_pred_vector	Pointer to be updated with the vector containing the predecessor matrix.
out_pred_data	Pointer to be updated with the data of out_pred_vector

Returns

HF_STATUS::OK If the function completed successfully.

HF_STATUS::NO_COST If cost type was not the key of any existing cost type in the graph.

Postcondition

1) out_dist_vector is updated to contain a pointer to the newly created distance matrix

2) out_dist_data is updated to contain a pointer to the data of out_dist_vector

3) out_pred_vector is updated to contain a pointer to the newly created predecessor matrix

4) out_pred_data is updated to contain a pointer to the data of out_pred_vector

Warning

It is the caller's responsibility to deallocate the distance and predecessor matricies by calling DestroyIntVector and DestroyFloatVector. Failing to do so WILL leak memory. Do NOT attempt to delete the data arrays, they will automatically be deleted when their vectors are deleted.

See also

Raytracer setup (how to create a BVH), Raytracer teardown (how to destroy a BVH)

DestroyFloatVector

DestroyIntVector

DestroyPath for information on deleting the path after usage.

Begin by reviewing the example at Raytracer setup to load an .obj file (mesh), and create a BVH from the mesh.
Then generate a graph (Graph generation) from the BVH – see Get nodes from graph on how to retrieve nodes from the graph.

Example

Create a graph, add some edges – then invoke CalculateDistanceAndPredecessor

    // Create a graph
    Graph * g;
    CreateGraph(NULL, -1, &g);
 
    // Create some nodes and add edges to the graph
    vector<vector<float>> nodes = {
        {1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 1, 2}
    };
    AddEdgeFromNodes(g, nodes[0].data(), nodes[1].data(), 10, "");
    AddEdgeFromNodes(g, nodes[1].data(), nodes[2].data(), 20, "");
    AddEdgeFromNodes(g, nodes[0].data(), nodes[2].data(), 5, "");
    AddEdgeFromNodes(g, nodes[1].data(), nodes[0].data(), 10, "");
    Compress(g);
    
    // Create output parameters
    std::vector<float>* dist_vector; std::vector<int>* pred_vector;
    float* dist_data; int* pred_data;
 
    // Call into the new function
    auto status = CalculateDistanceAndPredecessor(g,"", &dist_vector, &dist_data, &pred_vector, &pred_data);
        

Print the result:

    
    // Print both matricies
    const int array_length = dist_vector->size();
    std::cout << "Distance Matrix: [";
    for (int i = 0; i < array_length; i++)
        std::cout << dist_vector->at(i) << (i ==  array_length - 1 ? "]\r\nPredecessor Mattrix: [" : ", ");
    for (int i = 0; i < array_length; i++)
        std::cout << pred_vector->at(i) << (i == array_length - 1 ? "]\r\n" : ", ");
 
    // Cleanup memory
    DestroyIntVector(pred_vector);
    DestroyFloatVector(dist_vector);
 

>>> Distance Matrix: [0.000000, 10.000000, 5.000000, 10.000000, 0.000000, 15.000000, -1.000000, -1.000000, 0.000000]
>>> Predecessor Matrix: [0, 0, 0, 1, 1, 0, -1, -1, 2]\n

Definition at line 171 of file pathfinder_C.cpp.

References HF::Pathfinding::CreateBoostGraph(), HF::Pathfinding::DistanceAndPredecessor::dist, HF::Pathfinding::GenerateDistanceAndPred(), and HF::Pathfinding::DistanceAndPredecessor::pred.

Here is the call graph for this function:

CreateAllToAllPaths()

C_INTERFACE CreateAllToAllPaths	(	const HF::SpatialStructures::Graph *	g,
		const char *	cost_type,
		HF::SpatialStructures::Path **	out_path_ptr_holder,
		HF::SpatialStructures::PathMember **	out_path_member_ptr_holder,
		int *	out_sizes,
		int	num_paths
	)

#include <Cinterface/pathfinder_C.h>

Find a path from every node in a graph to every other node.

Parameters

g	The graph to conduct the search on nodes that already exist within the graph.
cost_name	The name of the cost type to use for generating paths. Leaving as an empty string will use the default cost of g.
out_size	An empty array of integers that will be updated to contain the length of every path in path_members. Paths that could not be generated will be left with a length of zero.
out_path	Location for the the path pointer array to be created. Paths that could not be generated will be left as null pointers.
out_data	Location for the pathmember pointer array to be created. All path member pointers will point to the PathMembers of the Path in paths at the same index. Paths that could not be generated will be left as null pointers.

Returns

HF_STATUS::OK The completed successfully and all postconditions were fulfilled.

HF_STATUS::NO_COST cost_name is not a valid cost type name

Precondition

If cost_type is specified, cost_type must be the the key of an already existing cost in g

Postcondition

1) out_path_members will point to a vector of pointers to vectors of PathMembers with an element for every path. Paths that could not be generated will be set to null pointers.

2) out_paths will point to a vector of pointers to paths with an element for every path. Paths that could not be generated will be set to null pointers.

3) out_sizes will point to an array of integers containing the size of every path in out_paths. Paths that could not be generated will have a size of 0.

Warning

The caller is responsible for freeing all of the memory allocated in out_pathsand out_sizes. The contents of out_path_members will automatically be deleted when the path they belong to is deleted. Do not try to manually delete out_path_members or the path that owns it will throw a null pointer exception when it is deleted.

See also

Mesh setup (how to load an .OBJ file/create a mesh)

Raytracer setup (how to create a BVH)

Graph generation (how to generate a graph from a BVH)

Get nodes from graph (how to retrieve nodes from a graph)

DestroyPath for information on deleting the path after usage.

Destroy nodes from graph (how to destroy nodes from a graph)

Destroy graph (how to destroy a graph)

Raytracer teardown (how to destroy a BVH)

Mesh teardown (how to destroy a mesh)

Now we are ready to invoke CreateAllToAllPaths .

        HF::SpatialStructures::Graph g;
 
        // Add the edges
        g.addEdge(0, 1, 1);
        g.addEdge(0, 2, 2);
        g.addEdge(1, 3, 3);
        g.addEdge(1, 4, 4);
        g.addEdge(2, 4, 4);
        g.addEdge(3, 5, 5);
        g.addEdge(4, 6, 3);
        g.addEdge(5, 6, 1);
 
        // Always compress the graph after adding edges
        g.Compress();
 
        // Create a BoostGraph (std::unique_ptr)
        auto bg = CreateBoostGraph(g);
 
        // Total paths is node_count ^ 2
        const size_t node_count = g.Nodes().size();
        const size_t path_count = node_count * node_count;
 
        // Buffer of (Path *). Each Path * must be freed using DestroyPath.
        std::vector<Path*> out_paths(path_count);
 
        // Buffer of (PathMember *). These pointers address the vector<PathMember> buffers in all *p in out_paths. 
        std::vector<PathMember*> out_path_member(path_count);
 
        // Pointer to buffer of (int)
        std::vector<int> sizes(path_count);
 
        //
        // The two loops for start_points and end_points
        // are just for the output.
        //
        int curr_id = 0;
        std::vector<int> start_points(path_count);
 
        // Populate the start points,
        // size will be (node_count)^2
        for (int i = 0; i < node_count; i++) {
            for (int k = 0; k < node_count; k++) {
                start_points[curr_id++] = i;
            }
        }
 
        curr_id = 0;
 
        std::vector<int> end_points(path_count);
        // Populate the end points,
        // size will be (node_count)^2
        for (int i = 0; i < node_count; i++) {
            for (int k = 0; k < node_count; k++) {
                end_points[curr_id++] = k;
            }
        }
 
        CreateAllToAllPaths(&g, "", out_paths.data(), out_path_member.data(), sizes.data(), path_count);
 
        auto start_points_it = start_points.begin();
        auto end_points_it = end_points.begin();
 
        for (auto p : out_paths) {
            if (p) {
                // Always check if out_paths[i] is nonnull!
                int total_cost = 0;
                std::cout << "Path from " << *(start_points_it++) << " to " << *(end_points_it++) << std::endl;
 
                for (auto m : p->members) {
                    total_cost += m.cost;
                    std::cout << "node ID: " << m.node << "\tcost " << m.cost << std::endl;
                }
 
                std::cout << "Total cost: " << total_cost << std::endl;
                std::cout << "--------------------------" << std::endl;
            }
        }
 
        //
        // Resource cleanup
        //
        for (auto& p : out_paths) {
            DestroyPath(p);
            p = nullptr;
        }

        Path from 0 to 1
        node ID : 0      cost 1
        node ID : 1      cost 0
        Total cost : 1
        --------------------------
        Path from 0 to 2
        node ID : 0      cost 2
        node ID : 2      cost 0
        Total cost : 2
        --------------------------
        Path from 0 to 3
        node ID : 0      cost 1
        node ID : 1      cost 3
        node ID : 3      cost 0
        Total cost : 4
        --------------------------
        Path from 0 to 4
        node ID : 0      cost 1
        node ID : 1      cost 4
        node ID : 4      cost 0
        Total cost : 5
        --------------------------
        Path from 0 to 5
        node ID : 0      cost 1
        node ID : 1      cost 3
        node ID : 3      cost 5
        node ID : 5      cost 0
        Total cost : 9
        --------------------------
        Path from 0 to 6
        node ID : 0      cost 1
        node ID : 1      cost 4
        node ID : 4      cost 3
        node ID : 6      cost 0
        Total cost : 8
        --------------------------
        Path from 1 to 3
        node ID : 1      cost 3
        node ID : 3      cost 0
        Total cost : 3
        --------------------------
        Path from 1 to 4
        node ID : 1      cost 4
        node ID : 4      cost 0
        Total cost : 4
        --------------------------
        Path from 1 to 5
        node ID : 1      cost 3
        node ID : 3      cost 5
        node ID : 5      cost 0
        Total cost : 8
        --------------------------
        Path from 1 to 6
        node ID : 1      cost 4
        node ID : 4      cost 3
        node ID : 6      cost 0
        Total cost : 7
        --------------------------
        Path from 2 to 4
        node ID : 2      cost 4
        node ID : 4      cost 0
        Total cost : 4
        --------------------------
        Path from 2 to 6
        node ID : 2      cost 4
        node ID : 4      cost 3
        node ID : 6      cost 0
        Total cost : 7
        --------------------------
        Path from 3 to 5
        node ID : 3      cost 5
        node ID : 5      cost 0
        Total cost : 5
        --------------------------
        Path from 3 to 6
        node ID : 3      cost 5
        node ID : 5      cost 1
        node ID : 6      cost 0
        Total cost : 6
        --------------------------
        Path from 4 to 6
        node ID : 4      cost 3
        node ID : 6      cost 0
        Total cost : 3
        --------------------------
        Path from 5 to 6
        node ID : 5      cost 1
        node ID : 6      cost 0
        Total cost : 1
        --------------------------

Definition at line 138 of file pathfinder_C.cpp.

References HF::Pathfinding::CreateBoostGraph(), and HF::Pathfinding::InsertAllToAllPathsIntoArray().

Here is the call graph for this function:

CreatePath()

C_INTERFACE CreatePath	(	const HF::SpatialStructures::Graph *	g,
		int	start,
		int	end,
		const char *	cost_type,
		int *	out_size,
		HF::SpatialStructures::Path **	out_path,
		HF::SpatialStructures::PathMember **	out_data
	)

#include <Cinterface/pathfinder_C.h>

Find the shortest path from start to end.

Parameters

g	The graph to conduct the search on.
start	Start node of the path.
end	End node of the path.
cost_name	The name of the cost in g to use for shortest path calculations. Set to an empty string to use the cost g was constructed with.
out_size	Updated to the length of the found path on success. Set to 0 if no path could be found.
out_path	Output parameter for a pointer to the generated path. Will be null if no path could be found
out_data	Output parameter for a pointer to the data of the generated path. Will be null if no path could be found.

Returns

HF_STATUS::OK The function completed successfully.

HF_STATUS::NO_PATH No path could be found

HF_STATUS::NO_COST cost_name is not an empty string or the key of a cost that already exists in G

Precondition

1) start and end contain both contain the Ids of nodes already in the graph

2) If not set to the empty string, cost_name is the key to a valid cost type already defined in g.

Postcondition

If OK is returned, a path between start and end was found and out_size, out_path, and out_data, are updated to contain the number of nodes in the path, a pointer to the path itself, and a pointer to the PathMembers it holds respectively.

Warning

The caller is responsible for deleting the path returned by out_path by calling DestroyPath if this function completes successfully. Freeing the memory for a path will also free the memory for its path members, so do not attempt to access its members after deletion.

See also

Mesh setup (how to load an .OBJ file/create a mesh)

Raytracer setup (how to create a BVH)

Graph generation (how to generate a graph from a BVH)

Get nodes from graph (how to retrieve nodes from a graph)

DestroyPath for information on deleting the path after usage.

Destroy nodes from graph (how to destroy nodes from a graph)

Destroy graph (how to destroy a graph)

Raytracer teardown (how to destroy a BVH)

Mesh teardown (how to destroy a mesh)

Begin by reviewing the example at Raytracer setup to load an .obj file (mesh), and create a BVH from the mesh.
Then generate a graph (Graph generation) from the BVH – see Get nodes from graph on how to retrieve nodes from the graph.

Now we are ready to create a path. We will find the path from the first node to the last indexed node.

        //
        // Call Dijkstra's Shortest Path Algorithm
        //
 
        // Retrieve the first ID and the last ID indexed in *node_vector.
        const int start_id = 0;
        const int end_id = node_vector->size() - 1;
 
        // empty string means to use the cost type that the graph was constructed with
        const char* cost_type = "";
 
        // Will be set to the size of the found path. Output value of 0 means no path was constructed.
        int path_size = -1;
 
        // If a path is found, path will address memory for a Path.
        // DestroyPath must be called on path when finished with use.
        HF::SpatialStructures::Path* path = nullptr;
 
        // Will address the underlying buffer of a member container within *path.
        // When DestroyPath is called on path, path_data will no longer be valid.
        // Likewise, if path remains null after attempting to create a path,
        // path_data will also be null.
        HF::SpatialStructures::PathMember* path_data = nullptr;
 
        // Create a path.
        status = CreatePath(graph, start_id, end_id, cost_type, &path_size, &path, &path_data);
 
        if (status != 1) {
            std::cerr << "Error at CreatePath, code: " << status << std::endl;
        }
        else {
            if (path) {
                std::cout << "CreatePath stored path successfully - path stored at address " << path << ", code: " << status << std::endl;
 
                // Get total path cost & output the result.
                auto path_sum = 0.0f;
                for (auto& member : path->members) { path_sum += member.cost; }
                std::cout << "Total path cost: " << path_sum << std::endl;
            }
        }

From here, please review the examples on how to destroy a path (DestroyPath),
as well as how to destroy a vector<HF::SpatialStructures::Node> (Destroy nodes from graph),
how to destroy a HF::SpatialStructures::Graph (Destroy graph),
how to destroy a HF::RayTracer::EmbreeRayTracer (Raytracer teardown),
and how to destroy a vector<HF::Geometry::MeshInfo> (Mesh teardown).

>>> LoadOBJ loaded mesh successfully into loaded_obj at address 000001DF01EB9470, code: 1
>>> CreateRaytracer created EmbreeRayTracer successfully into bvh at address 000001DF01EB5100, code: 1
>>> Generate graph ran successfully - graph stored at address 000001DF0BCEDDA0, code: 1
>>> Graph Generated with 886 nodes
>>> CreatePath stored path successfully - path stored at address 000001DF01EB9590, code: 1
>>> Total path cost: 77.6772

Definition at line 23 of file pathfinder_C.cpp.

References HF::Pathfinding::CreateBoostGraph(), HF::SpatialStructures::Path::empty(), HF::Pathfinding::FindPath(), HF::Exceptions::GENERIC_ERROR, HF::SpatialStructures::Path::GetPMPointer(), HF::Exceptions::NO_COST, HF::Exceptions::NO_PATH, HF::Exceptions::OK, and HF::SpatialStructures::Path::size().

Here is the call graph for this function:

CreatePaths()

C_INTERFACE CreatePaths	(	const HF::SpatialStructures::Graph *	g,
		const int *	start,
		const int *	end,
		const char *	cost_type,
		HF::SpatialStructures::Path **	out_path_ptr_holder,
		HF::SpatialStructures::PathMember **	out_path_member_ptr_holder,
		int *	out_sizes,
		int	num_paths
	)

#include <Cinterface/pathfinder_C.h>

Find multiple shortest paths in paralllel.

Parameters

g	The graph to conduct the search on
start	An array of ids for starting nodes. Length must match that of end and all the IDS must belong to nodes that already exist within the graph.
end	An array of ids for ending nodes. Length must match that of start and all the IDS must belong to nodes that already exist within the graph.
cost_name	The name of the cost type to use for generating paths. Leaving as an empty string will use the default cost of g.
out_size	An empty array of integers that will be updated to contain the length of every path in path_members. Paths that could not be generated will be left with a length of zero.
out_path	Location for the the path pointer array to be created. Paths that could not be generated will be left as null pointers.
out_data	Location for the pathmember pointer array to be created. All path member pointers will point to the PathMembers of the Path in paths at the same index. Paths that could not be generated will be left as null pointers.

Returns

HF_STATUS::OK if the function completes successfully

HF_STATUS::NO_COST is cost_name is not a valid cost type name

Precondition

1) The length of start_ids, end_ids, and out_size must be equal.

2) If cost_type is specified, cost_type must be the the key of an already existing cost in g

Postcondition

1) out_path_members will point to a vector of pointers to vectors of PathMembers with an element for every path. paths that could not be generated will be set to null pointers.

2) out_paths will point to a vector of pointers to paths with an element for every path. Paths that could not be generated will be set to null pointers.

3) out_sizes will point to an array of integers containing the size of every path in out_paths. Paths that could not be generated will have a size of 0.

Warning

The caller is responsible for freeing all of the memory allocated in out_paths and out_sizes. The contents of out_path_members will automatically be deleted when the path they belong to is deleted. Do not try to manually delete out_path_members or the path that owns it will throw a null pointer exception when it is deleted.

See also

Mesh setup (how to load an .OBJ file/create a mesh)

Raytracer setup (how to create a BVH)

Graph generation (how to generate a graph from a BVH)

Get nodes from graph (how to retrieve nodes from a graph)

DestroyPath for information on deleting the path after usage.

Destroy nodes from graph (how to destroy nodes from a graph)

Destroy graph (how to destroy a graph)

Raytracer teardown (how to destroy a BVH)

Mesh teardown (how to destroy a mesh)

No cost type:

        // Requires #include "pathfinder_C.h", #include "graph.h", #include "path.h", #include "path_finder.h"
 
        // for brevity
        using HF::SpatialStructures::Graph;
        using HF::SpatialStructures::Path;
        using HF::SpatialStructures::PathMember;
 
        Graph g;
        g.addEdge(0, 1, 1);
        g.addEdge(0, 2, 2);
        g.addEdge(1, 3, 3);
        g.addEdge(2, 4, 1);
        g.addEdge(3, 4, 5);
        g.Compress();
 
        // Maximum amount of paths to search
        const int MAX_PATHS = 2;
        const int MAX_PATHMEMBERS = 2;
 
        // Create a Graph g, and compress it
        auto boostGraph = HF::Pathfinding::CreateBoostGraph(g);
 
        // We want to find the shortest paths from 0 to 3, and 0 to 4.
        std::array<int, 2> start_nodes{ 0, 0 };
        std::array<int, 2> end_nodes{ 3, 4 };
 
        // Create arrays of pointers to Path. We have MAX_PATHS total paths to assess.
        // Create arrays of pointers to PathMember. The anticipated maximum amount of "hops" per path is MAX_PATHMEMBERS.
        std::array<Path*, MAX_PATHS> out_path;
        std::array<PathMember*, MAX_PATHMEMBERS> out_path_member;
 
        // Sizes of paths generated by CreatePaths. Sizes of 0 mean that a path was unable to be generated.
        // Should be the same as
        std::array<int, MAX_PATHS> out_sizes;
 
        // Use CreatePaths
        CreatePaths(&g, start_nodes.data(), end_nodes.data(), "\0", out_path.data(), out_path_member.data(), out_sizes.data(), MAX_PATHS);
 
        //
        // Resource cleanup.
        //
        for (auto& p : out_path) {
            DestroyPath(p);
            p = nullptr;
        }

With a cost type:

        // Requires #include "pathfinder_C.h", #include "graph.h", #include "path.h", #include "path_finder.h"
 
        // for brevity
        using HF::SpatialStructures::Node;
        using HF::SpatialStructures::Graph;
        using HF::Pathfinding::BoostGraph;
        using HF::SpatialStructures::CostAlgorithms::CalculateEnergyExpenditure;
 
        // Create the nodes
        Node node_0(1.0f, 1.0f, 2.0f);
        Node node_1(2.0f, 3.0f, 4.0f);
        Node node_2(11.0f, 22.0f, 14.0f);
        Node node_3(62.9f, 39.1f, 18.0f);
        Node node_4(99.5f, 47.1f, 29.9f);
 
        // Create a graph. No nodes/edges for now.
        Graph graph;
 
        // Add edges. These will have the default edge values, forming the default graph.
        graph.addEdge(node_0, node_1, 1);
        graph.addEdge(node_0, node_2, 2.5);
        graph.addEdge(node_1, node_3, 54.0);
        graph.addEdge(node_2, node_4, 39.0);
        graph.addEdge(node_3, node_4, 1.2);
 
        // Always compress the graph after adding edges!
        graph.Compress();
 
        // Retrieve a Subgraph, parent node ID 0 -- of alternate edge costs.
        // Add these alternate edges to graph.
        std::string desired_cost_type = AlgorithmCostTitle(COST_ALG_KEY::CROSS_SLOPE);
        auto edge_set = CalculateEnergyExpenditure(graph);
        graph.AddEdges(edge_set, desired_cost_type);
 
        // Maximum amount of paths to search
        const int MAX_PATHS = 2;
        const int MAX_PATHMEMBERS = 2;
 
        // Create a Graph g, and compress it
        auto boostGraph = HF::Pathfinding::CreateBoostGraph(graph);
 
        // We want to find the shortest paths from 0 to 3, and 0 to 4.
        std::array<int, 2> start_nodes{ 0, 0 };
        std::array<int, 2> end_nodes{ 3, 4 };
 
        // Create arrays of pointers to Path. We have MAX_PATHS total paths to assess.
        // Create arrays of pointers to PathMember. The anticipated maximum amount of "hops" per path is MAX_PATHMEMBERS.
        std::array<Path*, MAX_PATHS> out_path;
        std::array<PathMember*, MAX_PATHMEMBERS> out_path_member;
 
        // Sizes of paths generated by CreatePaths. Sizes of 0 mean that a path was unable to be generated.
        // Should be the same as
        std::array<int, MAX_PATHS> out_sizes;
 
        // Use CreatePathsCostType, be sure to use the .c_str() method if using a std::string for desired_cost_type
        CreatePaths(&graph, start_nodes.data(), end_nodes.data(), desired_cost_type.c_str(), out_path.data(), out_path_member.data(), out_sizes.data(), MAX_PATHS);
 
        //
        // Use out_path, out_path_member
        //
 
        //
        // Resource cleanup
        //
        for (auto& p : out_path) {
            DestroyPath(p);
            p = nullptr;
        }

>>> TODO output

Definition at line 70 of file pathfinder_C.cpp.

References HF::Pathfinding::CreateBoostGraph(), HF::Exceptions::GENERIC_ERROR, HF::Pathfinding::InsertPathsIntoArray(), HF::Exceptions::NO_COST, and HF::Exceptions::OK.

Here is the call graph for this function:

DestroyPath()

C_INTERFACE DestroyPath

(

HF::SpatialStructures::Path *

path_to_destroy

)

#include <Cinterface/pathfinder_C.h>

Delete a path.

Parameters

path_to_destroy

Pointer to the path to delete.

Returns

HF_STATUS::OK on return.

See also

Mesh setup (how to load an .OBJ file/create a mesh)

Raytracer setup (how to create a BVH)

Graph generation (how to generate a graph from a BVH)

Get nodes from graph (how to retrieve nodes from a graph)

DestroyPath for information on deleting the path after usage.

Destroy nodes from graph (how to destroy nodes from a graph)

Destroy graph (how to destroy a graph)

Raytracer teardown (how to destroy a BVH)

Mesh teardown (how to destroy a mesh)

        // Requires #include "pathfinder_C.h", #include "graph.h", #include "path.h", #include "path_finder.h"
 
        // Create a Graph g, and compress it.
        HF::SpatialStructures::Graph g;
        g.addEdge(0, 1, 1);
        g.addEdge(0, 2, 2);
        g.addEdge(1, 3, 3);
        g.addEdge(2, 4, 1);
        g.addEdge(3, 4, 5);
        g.Compress();
 
        // Create a boostGraph from g
        auto boostGraph = HF::Pathfinding::CreateBoostGraph(g);
 
        HF::SpatialStructures::Path* out_path = nullptr;
        HF::SpatialStructures::PathMember* out_path_member = nullptr;
        int out_size = -1;
 
        CreatePath(&g, 0, 4, "\0", &out_size, &out_path, &out_path_member);
 
        // Use out_path, out_path_member
 
        // Remember to free resources when finished
        DestroyPath(out_path);
 
        // At this point, out_path_member has also been destroyed, so we set this to nullptr
        out_path_member = nullptr;

>>> TODO output

Definition at line 133 of file pathfinder_C.cpp.

References DeleteRawPtr(), and HF::Exceptions::OK.

Here is the call graph for this function:

GetPathInfo()

C_INTERFACE GetPathInfo	(	HF::SpatialStructures::Path *	p,
		PathMember **	out_member_ptr,
		int *	out_size
	)

#include <Cinterface/pathfinder_C.h>

Get the size of a path and a pointer to its path members.

Parameters

p	Pointer to the path to get information from. This can handle null values.
out_member_ptr	Pointer to the path to get information from. Should not be null.
out_size	The number of path members in the path. (PathMember count within *p)

Returns

HF_STATUS::OK on success, HF_STATUS::NO_PATH if the path *p is invalid

See also

Mesh setup (how to load an .OBJ file/create a mesh)

Raytracer setup (how to create a BVH)

Graph generation (how to generate a graph from a BVH)

Get nodes from graph (how to retrieve nodes from a graph)

DestroyPath for information on deleting the path after usage.

Destroy nodes from graph (how to destroy nodes from a graph)

Destroy graph (how to destroy a graph)

Raytracer teardown (how to destroy a BVH)

Mesh teardown (how to destroy a mesh)

        // Requires #include "pathfinder_C.h", #include "graph.h", #include "path.h", #include "path_finder.h"
 
        // Create a Graph g, and compress it.
        HF::SpatialStructures::Graph g;
        g.addEdge(0, 1, 1);
        g.addEdge(0, 2, 2);
        g.addEdge(1, 3, 3);
        g.addEdge(2, 4, 1);
        g.addEdge(3, 4, 5);
        g.Compress();
 
        // Create a boostGraph from g
        auto boostGraph = HF::Pathfinding::CreateBoostGraph(g);
 
        HF::SpatialStructures::Path* out_path = nullptr;
        HF::SpatialStructures::PathMember* out_path_member = nullptr;
        int out_size = -1;
 
        CreatePath(&g, 0, 4, "\0", &out_size, &out_path, &out_path_member);
 
        // Get out_path's info, store results in out_path_member and out_size
        GetPathInfo(out_path, &out_path_member, &out_size);
 
        // Remember to free resources when finished
        DestroyPath(out_path);
 
        // At this point, out_path_member has also been destroyed, so we set this to nullptr
        out_path_member = nullptr;

>>> TODO output
Get the size of a path and a pointer to its path members.

Definition at line 115 of file pathfinder_C.cpp.

References HF::SpatialStructures::Path::GetPMPointer(), HF::Exceptions::NO_PATH, HF::Exceptions::OK, and HF::SpatialStructures::Path::size().

Here is the call graph for this function: