Am I making correct use of pointers in this C implementation of A*?

In order to get a better understanding of C and to try and improve the performance of an app I am building for iOS, I decided to implement the path finding in C.

The code is available here

In the code, I create and use the following structures:

• Node: this is a vertex of the graph, it has coordinates and some other data related to A*
• NodeGraph: a collection of nodes
• NodeHeap: a heap that is used for the open list (priority queue)

The NodeGraph is responsible for managing the node memory; everything else that needs access to the node uses a pointer to the specific node in the NodeGraph. For example, the NodeHeap is just a collection of Node pointers like:

// graph is NodeGraph* created elsewhere
Node* n = &(graph->nodes[x][y]);
// heap is a Nodeheap* created elsewhere
heap[0] = n;

Within the game, I intend to use the same graph structure for multiple path find calls. It is my understanding that there is some performance gain from reusing the same structure as opposed to freeing it and allocating memory for a new one.

Is this the way I should be doing something like this in C? 开发者_开发知识库Are there any C constructs I am not taking advantage of, or anything else that I am completely missing?

On most systems, memory allocation is expensive because your process has to communicate with (and thus wait for) the OS. Typically this is not the case for free however, which will not return the memory to the OS, but will instead store it for you, and use it preferentially for future calls to the *alloc functions.

Whether or not you'll see a big performance gain here is dependent on your system.

I suggest writing your code without optimizations, and then using a profiler (e.g. gprof) to see where you're spending the most time. You can then optimize your code accordingly.