SHOW:
|
|
- or go back to the newest paste.
| 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; |
| 16 | + | current.state = CLOSED; |
| 17 | // node list | |
| 18 | node nodes[MAPY*MAPX]; | |
| 19 | bool searching = true; | |
| 20 | - | // start searching |
| 20 | + | // while the open list is not empty |
| 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++) {
|
| 25 | + | if (steps > MAPY*MAPX) { steps = 0; }
|
| 26 | for (int i = 0; i < (width/font_scale)*(height/font_scale); i++) {
| |
| 27 | if ( (nodes[i].f < lowest_f) && (nodes[i].state == OPEN) ) {
| |
| 28 | lowest_f = nodes[i].f; | |
| 29 | tiles[nodes[i].y][nodes[i].x].c[0] = 'x'; | |
| 30 | old_current.set(current.y,current.x); | |
| 31 | current.set(nodes[i].y,nodes[i].x); | |
| 32 | } else {nodes[i].state = CLOSED; }
| |
| 33 | } | |
| 34 | // check if reached destination | |
| 35 | if ( (current.x == dest_node.x) && (current.y == dest_node.y) ) { searching = false; }
| |
| 36 | // check if node has not changed (meaning there is no where to go) | |
| 37 | if ( (current.x == old_current.x) && (current.x == old_current.x) ) { break; }
| |
| 38 | ||
| 39 | // Generate each state node_successor that can come after node_current for each node_successor of node_current | |
| 40 | if (tiles[current.y+1][current.x].obj_solid == false) { // check below
| |
| 41 | nodes[steps].set(current.y+1, current.x); // set node cords | |
| 42 | nodes[steps].state = OPEN; // add to open list | |
| 43 | nodes[steps].h = StepsFrom_To(current.y+1,current.x,dest_node.y,dest_node.x) * 10; // calc histerics | |
| 44 | nodes[steps].g = StepsFrom_To(current.y+1,current.x,start_node.y,start_node.x) + steps; // calc move cost | |
| 45 | nodes[steps].f = nodes[steps].h + nodes[steps].g; | |
| 46 | steps++; | |
| 47 | } | |
| 48 | if (tiles[current.y-1][current.x].obj_solid == false) { // check above
| |
| 49 | nodes[steps].set(current.y-1, current.x); // set node cords | |
| 50 | nodes[steps].state = OPEN; // add to open list | |
| 51 | nodes[steps].h = StepsFrom_To(current.y-1,current.x,dest_node.y,dest_node.x) * 10; // calc histerics | |
| 52 | nodes[steps].g = StepsFrom_To(current.y-1,current.x,start_node.y,start_node.x) + steps; // calc move cost | |
| 53 | nodes[steps].f = nodes[steps].h + nodes[steps].g; | |
| 54 | steps++; | |
| 55 | } | |
| 56 | if (tiles[current.y][current.x+1].obj_solid == false) { // check right
| |
| 57 | nodes[steps].set(current.y, current.x+1); // set node cords | |
| 58 | nodes[steps].state = OPEN; // add to open list | |
| 59 | nodes[steps].h = StepsFrom_To(current.y,current.x+1,dest_node.y,dest_node.x) * 10; // calc histerics | |
| 60 | nodes[steps].g = StepsFrom_To(current.y,current.x+1,start_node.y,start_node.x)+ steps; // calc move cost | |
| 61 | nodes[steps].f = nodes[steps].h + nodes[steps].g; | |
| 62 | steps++; | |
| 63 | } | |
| 64 | if (tiles[current.y][current.x-1].obj_solid == false) { // check left
| |
| 65 | nodes[steps].set(current.y, current.x-1); // set node cords | |
| 66 | nodes[steps].state = OPEN; // add to open list | |
| 67 | nodes[steps].h = StepsFrom_To(current.y,current.x-1,dest_node.y,dest_node.x) * 10; // calc histerics | |
| 68 | nodes[steps].g = StepsFrom_To(current.y,current.x-1,start_node.y,start_node.x) + steps; // calc move cost | |
| 69 | nodes[steps].f = nodes[steps].h + nodes[steps].g; | |
| 70 | steps++; | |
| 71 | } | |
| 72 | ||
| 73 | current.state = CLOSED; | |
| 74 | } | |
| 75 | } |