Advertisement
slinky99

Path Finding

Aug 29th, 2013
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.10 KB | None | 0 0
  1. // ============================ PATH FINDING ==========================
  2.     int StepsFrom_To(int start_y, int start_x, int dest_y, int dest_x) {
  3.         int count = 0;
  4.         for (int y = start_y; y < dest_y; y++) { count++; }
  5.         for (int x = start_x; x < dest_x; x++) { count++; }
  6.         return count;
  7.     }
  8.  
  9.     void FindPathFrom_To(int start_y, int start_x, int dest_y, int dest_x) {
  10.         // create nodes for start and desticaion
  11.         node start_node(start_y,start_x);
  12.         node dest_node(dest_y,dest_x);
  13.         node old_current(-1,-1);
  14.         // open current id
  15.         node current(start_y,start_x);
  16.         current.state = OPEN;
  17.         // node list
  18.         node nodes[MAPY*MAPX];
  19.         bool searching = true;
  20.         // start searching
  21.         int steps = 0;
  22.         while (searching) {
  23.             // Get the node off the open list with the lowest f and make it current node
  24.             int lowest_f = 9999; // just so it works :)
  25.             for (int i = 0; i < MAPY*MAPX; i++) {
  26.                 if ( (nodes[i].f < lowest_f) && (nodes[i].state == OPEN) ) {
  27.                     lowest_f = nodes[i].f;
  28.                     tiles[nodes[i].y][nodes[i].x].c[0] = 'x';
  29.                     old_current.set(current.y,current.x);
  30.                     current.set(nodes[i].y,nodes[i].x);
  31.                 } else {nodes[i].state = CLOSED; }
  32.             }
  33.             // check if reached destination
  34.             if ( (current.x == dest_node.x) && (current.y == dest_node.y) ) { searching = false; }
  35.             // check if node has not changed (meaning there is no where to go)
  36.             if ( (current.x == old_current.x) && (current.x == old_current.x) ) { break; }
  37.  
  38.             // Generate each state node_successor that can come after node_current for each node_successor of node_current
  39.             if (tiles[current.y+1][current.x].obj_solid == false) {  // check below
  40.                 nodes[steps].set(current.y+1, current.x); // set node cords
  41.                 nodes[steps].state = OPEN; // add to open list
  42.                 nodes[steps].h = StepsFrom_To(current.y+1,current.x,dest_node.y,dest_node.x) * 10; // calc histerics
  43.                 nodes[steps].g = StepsFrom_To(current.y+1,current.x,start_node.y,start_node.x) + steps; // calc move cost
  44.                 nodes[steps].f = nodes[steps].h + nodes[steps].g;
  45.                 steps++;
  46.             }
  47.             if (tiles[current.y-1][current.x].obj_solid == false) { // check above
  48.                 nodes[steps].set(current.y-1, current.x); // set node cords
  49.                 nodes[steps].state = OPEN; // add to open list
  50.                 nodes[steps].h = StepsFrom_To(current.y-1,current.x,dest_node.y,dest_node.x) * 10; // calc histerics
  51.                 nodes[steps].g = StepsFrom_To(current.y-1,current.x,start_node.y,start_node.x) + steps; // calc move cost
  52.                 nodes[steps].f = nodes[steps].h + nodes[steps].g;
  53.                 steps++;
  54.             }
  55.             if (tiles[current.y][current.x+1].obj_solid == false) { // check right
  56.                 nodes[steps].set(current.y, current.x+1); // set node cords
  57.                 nodes[steps].state = OPEN; // add to open list
  58.                 nodes[steps].h = StepsFrom_To(current.y,current.x+1,dest_node.y,dest_node.x) * 10; // calc histerics
  59.                 nodes[steps].g = StepsFrom_To(current.y,current.x+1,start_node.y,start_node.x)+ steps; // calc move cost
  60.                 nodes[steps].f = nodes[steps].h + nodes[steps].g;
  61.                 steps++;
  62.             }
  63.             if (tiles[current.y][current.x-1].obj_solid == false) { // check left
  64.                 nodes[steps].set(current.y, current.x-1); // set node cords
  65.                 nodes[steps].state = OPEN; // add to open list
  66.                 nodes[steps].h = StepsFrom_To(current.y,current.x-1,dest_node.y,dest_node.x) * 10; // calc histerics
  67.                 nodes[steps].g = StepsFrom_To(current.y,current.x-1,start_node.y,start_node.x) + steps; // calc move cost
  68.                 nodes[steps].f = nodes[steps].h + nodes[steps].g;
  69.                 steps++;
  70.             }
  71.  
  72.             current.state = CLOSED;
  73.         }
  74.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement