DeAllocating Resources in A*

Title: Releasing Allocated Resources in A*
Difficulty: Easy
By: Maj.Bitch
Email: peblair@frontiernet.com
Date: 10-03-99
Note: Please give credit where credit is due.
======================================================

I noticed when I was generating paths using my A* algorithm
that eventually my Quake2 engine shutdown. After some tests,
I determined that it was because the OS ran out of memory.
This could only have been caused by (and was actually caused by)
the failure of the FreeStack() routine to actually free ALL of
the allocated nodes. So, in my A* source, everywhere there was
an malloc() of type NODE I put a nodesallocated++ and everytime
I did a free NODE it put a nodefreed++. I printed the values of
these to the HUD so I could see the allocation and free'ing of the
resources consumed by A*. Interestingly, that in alot of instances
the A* algorithm allocated thousands of nodes and freed only
a few hundred of them. So, I was slowly running out of resources
as I requested path after path until the computer shutdown the
game.

So, I put together this functionality which GUARANTEES that ALL
allocated resources are freed. Feast upon this souce...

Define an array of pointers to pointers to type struct NODE and set
the NUMPTRS to some really high number like so..

#define NUMPTRS 5048
struct NODE **LIST=NULL;
int nodes_allocated=0;

Add this function to the top of your A* source...

//=========================================
struct NODE *NodeAlloc(int size) {
LIST[nodes_allocated]=(struct NODE *)malloc(size);
if (nodes_allocated+1>=NUMPTRS)
gi.error("NODE LIST SIZE EXCEEDED\n");
return LIST[nodes_allocated++];
}

Change your FreeStack() to this function...

//=========================================
void FreeStack(void) {
int i;

gi.dprintf("Nodes Allocated=%d\n",nodes_allocated);

for (i=0;i<nodes_allocated;i++)
if (LIST[i]) free(LIST[i]);

free(LIST);

nodes_allocated=0;

OPEN=NULL;
CLOSED=NULL;
Stack=NULL; // Should already be empty.
}

At the very top of your FindPath() function put these 2 lines
like so:

LIST=(struct NODE **)malloc(NUMPTRS*sizeof(struct Node *));
memset(LIST,0,NUMPTRS*sizeof(struct Node *));

This will allocate the array of pointers to pointers.

Lastly, everywhere in your A* algorithm where you are doing
an malloc() change the malloc() to NodeAlloc() so that you
are using your new function defined above for your allocations.

Examples are:

OPEN=NodeAlloc(sizeof(struct NODE));
OPEN->NextNode=NULL;

CLOSED=NodeAlloc(sizeof(struct NODE));
CLOSED->NextNode=NULL;

Now, a copy of a pointer to ALL structs of type NODE allocated during
the execution of the A* pathing will be stored in the LIST array
of pointers to pointers. When you are done with FindPath, you
make a call to FreeStack() which steps thru the LIST array and
frees the memory pointed to by the array of pointers (no matter
where they are at present).

This works great and no more running out of resources problems...

That'll put this problem to bed!

Make the change to your A* source..

Maj.Bitch