# Path Finding

Aug 29th, 2013
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.     }