@3run
As a recursive function, it seems like it must be. I saw your function stats leap some ms on the video. Too bad. You will probably need to cut it in some frames or somehow enshort the process.

Do you use pointer offsets instead of array coordinates? It can speed up things a lot.

There is a way of speeding up short paths but unfortunatelly it is more expensive on long paths. It consists on a list of candidates, where you include new candidates as last member in the list and you take the first in the list, one by one, in order to analyze and add its neighborhood to the candidates list. This way the algorithm checks the cells sorted by the count of steps to the end, so it only runs until it finds the ending point, flooding up only the cells closer than the shortest path length. All this stuff can perfectly fit in a single function.

Another way of saving some cycles is to save the direction of the incoming neighbor into the cell struct, so with an offset array like the following:
Code:
int cellOffsets[7] = {1, ARRAY_WIDTH, -1, -ARRAY_WIDTH, 1, ARRAY_WIDTH, -1};

you can totally avoid the cell the flood came from. Same for the subsequent path-finding process. It is just a little bost but every cycle takes into account on hard processes.
Code:
void recursive(CELL *_c){
   int _i = _c->incomingDirection + 1;
   int _iLast = _i + 3;
   for(; _i<_iLast; _i+=1) {
      CELL *_cT = _c + *(cellOffsets + _i);
      ...