index 99e0dcd1a27c47dfa296992b85f967f156d115e4..320c450a78a1b1149e8c73fa5b2113f504728aa7 100644 (file)
@@ -1,6 +1,4 @@
/*
/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
*
* The Original Code is Copyright (C) 2014 Blender Foundation.
* All rights reserved.
*
* The Original Code is Copyright (C) 2014 Blender Foundation.
* All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): Bastien Montagne.
- *
- * ***** END GPL LICENSE BLOCK *****
*/

#ifndef __BLI_ASTAR_H__
#define __BLI_ASTAR_H__

*/

#ifndef __BLI_ASTAR_H__
#define __BLI_ASTAR_H__

-/** \file BLI_astar.h
- *  \ingroup bli
- *  \brief An implementation of the A* (AStar) algorithm to solve shortest path problem.
+/** \file
+ * \ingroup bli
+ * \brief An implementation of the A* (AStar) algorithm to solve shortest path problem.
*/

#include "BLI_utildefines.h"
*/

#include "BLI_utildefines.h"
/* -------------------------------------------------------------------- */

typedef struct BLI_AStarGNLink {
/* -------------------------------------------------------------------- */

typedef struct BLI_AStarGNLink {
-       int nodes;
-       float cost;
+  int nodes;
+  float cost;

-       void *custom_data;
+  void *custom_data;
} BLI_AStarGNLink;

typedef struct BLI_AStarGNode {
} BLI_AStarGNLink;

typedef struct BLI_AStarGNode {
-       struct ListBase neighbor_links;
+  struct ListBase neighbor_links;

-       void *custom_data;
+  void *custom_data;
} BLI_AStarGNode;

typedef struct BLI_AStarSolution {
} BLI_AStarGNode;

typedef struct BLI_AStarSolution {
-       /* Final 'most useful' data. */
-       int steps;  /* Number of steps (i.e. walked links) in path (nodes num, including start and end, is steps + 1). */
-       int *prev_nodes;  /* Store the path, in reversed order (from destination to source node), as indices. */
-       BLI_AStarGNLink **prev_links;  /* Indices are nodes' ones, as prev_nodes, but they map to relevant link. */
-
-       void *custom_data;
-
-       /* Mostly runtime data. */
-       BLI_bitmap *done_nodes;
-       float *g_costs;
-       int *g_steps;
-
-       struct MemArena *mem;  /* Memory arena. */
+  /* Final 'most useful' data. */
+  /** Number of steps (i.e. walked links) in path
+   * (nodes num, including start and end, is steps + 1). */
+  int steps;
+  /** Store the path, in reversed order (from destination to source node), as indices. */
+  int *prev_nodes;
+  /** Indices are nodes' ones, as prev_nodes, but they map to relevant link. */
+  BLI_AStarGNLink **prev_links;
+
+  void *custom_data;
+
+  /* Mostly runtime data. */
+  BLI_bitmap *done_nodes;
+  float *g_costs;
+  int *g_steps;
+
+  struct MemArena *mem; /* Memory arena. */
} BLI_AStarSolution;

typedef struct BLI_AStarGraph {
} BLI_AStarSolution;

typedef struct BLI_AStarGraph {
-       int node_num;
-       BLI_AStarGNode *nodes;
+  int node_num;
+  BLI_AStarGNode *nodes;

-       void *custom_data;
+  void *custom_data;

-       struct MemArena *mem;  /* Memory arena. */
+  struct MemArena *mem; /* Memory arena. */
} BLI_AStarGraph;

void BLI_astar_node_init(BLI_AStarGraph *as_graph, const int node_index, void *custom_data);
} BLI_AStarGraph;

void BLI_astar_node_init(BLI_AStarGraph *as_graph, const int node_index, void *custom_data);
-void BLI_astar_node_link_add(
-        BLI_AStarGraph *as_graph, const int node1_index, const int node2_index, const float cost, void *custom_data);
+void BLI_astar_node_link_add(BLI_AStarGraph *as_graph,
+                             const int node1_index,
+                             const int node2_index,
+                             const float cost,
+                             void *custom_data);
int BLI_astar_node_link_other_node(BLI_AStarGNLink *lnk, const int idx);

int BLI_astar_node_link_other_node(BLI_AStarGNLink *lnk, const int idx);

-void BLI_astar_solution_init(BLI_AStarGraph *as_graph, BLI_AStarSolution *as_solution, void *custom_data);
+void BLI_astar_solution_init(BLI_AStarGraph *as_graph,
+                             BLI_AStarSolution *as_solution,
+                             void *custom_data);
void BLI_astar_solution_clear(BLI_AStarSolution *as_solution);
void BLI_astar_solution_free(BLI_AStarSolution *as_solution);

void BLI_astar_solution_clear(BLI_AStarSolution *as_solution);
void BLI_astar_solution_free(BLI_AStarSolution *as_solution);

@@ -95,13 +96,20 @@ void BLI_astar_solution_free(BLI_AStarSolution *as_solution);
* \param node_idx_next: next node index.
* \param node_idx_dst: destination node index.
*/
* \param node_idx_next: next node index.
* \param node_idx_dst: destination node index.
*/
-typedef float (*astar_f_cost)(BLI_AStarGraph *as_graph, BLI_AStarSolution *as_solution, BLI_AStarGNLink *link,
-                              const int node_idx_curr, const int node_idx_next, const int node_idx_dst);
+typedef float (*astar_f_cost)(BLI_AStarGraph *as_graph,
+                              BLI_AStarSolution *as_solution,
+                              BLI_AStarGNLink *link,
+                              const int node_idx_curr,
+                              const int node_idx_next,
+                              const int node_idx_dst);

void BLI_astar_graph_init(BLI_AStarGraph *as_graph, const int node_num, void *custom_data);
void BLI_astar_graph_free(BLI_AStarGraph *as_graph);

void BLI_astar_graph_init(BLI_AStarGraph *as_graph, const int node_num, void *custom_data);
void BLI_astar_graph_free(BLI_AStarGraph *as_graph);
-bool BLI_astar_graph_solve(
-        BLI_AStarGraph *as_graph, const int node_index_src, const int node_index_dst, astar_f_cost f_cost_cb,
-        BLI_AStarSolution *r_solution, const int max_steps);
-
-#endif  /* __BLI_ASTAR_H__ */
+bool BLI_astar_graph_solve(BLI_AStarGraph *as_graph,
+                           const int node_index_src,
+                           const int node_index_dst,
+                           astar_f_cost f_cost_cb,
+                           BLI_AStarSolution *r_solution,
+                           const int max_steps);
+
+#endif /* __BLI_ASTAR_H__ */