c++ - Path-finding algorithm for a game -

i have assigment in university i'm given code of c++ game involving pathfinding. pathfinding made using wave function , assigment requires me make change way pathfinding works.

the assigment requires pathfinding choose path farthest away object other clear space. shown here:

and here's result i've gotten far:

below i've posted part of update function concerning pathfinding i'm pretty sure that's i'll have make change.

for (int y = 0, o = 0; y < level_height; y++) {     (int x = 0; x < level_width; x++, o++) {         int ncost = !bricks[o].type;         if (ncost) {             (int j = 0; j < 4; j++)             {                 int dx = s_directions[j][0], dy = s_directions[j][1];                 if ((y == 0 && dy < 0)                     || (y == level_height - 1 && dy > 0)                     || (x == 0 && dx < 0)                     || (x == level_width - 1 && dx > 0)                     || bricks[o + dy * level_width + dx].type)                 {                     ncost = 2;                     break;                 }             }         }         pfwaycost[o] = (float)ncost;     } } 

also here wave function if needed further clarity on problem.

i'd grateful ideas on how proceed, since i've been struggling quite time now.

your problem can reduced problem known minimum-bottle-neck-spanning-tree.

for reduction following:

1. calculate costs every point/cell in space minimal distance object.
2. make graph edges correspond points in space , weights of edges costs calculated in prior step. vertices of graph corresponds boundaries between cell.

for 1 dimensional space 4 cells costs 10, 20, 3, 5:

|10|20|3|5| 

the graph like:

 a--(w=10)--b--(w=20)--c--(w=3)--d--(w=5)--e 

with nodes a-e corresponding boundaries of cells.

3. run example prim's algorithm find mst. looking direct way entry point (in example above a) exit point (e) in resulting tree.