Show Posts
1
Programming / Path Finding Problem
« on: August 30, 2013, 02:56:05 AM »
Sorry if this is the wrong section to post this in..
This is the first time I've EVER plaid about with path finding, attempted to implement it and I'm having so much trouble getting it to work!
I've literally been at it for hours, tweaking and scanning through it trying to figure out what I'm doing wrong.
The problem is I'm not completely sure the math is correct and I'm not sure what the problem is, but I'm going to go out on a limb here and guess It's all wrong..
If you prefer syntax (http://pastebin.com/jF7VGd1v)
Snippits:
The node class:
This is the first time I've EVER plaid about with path finding, attempted to implement it and I'm having so much trouble getting it to work!
I've literally been at it for hours, tweaking and scanning through it trying to figure out what I'm doing wrong.
The problem is I'm not completely sure the math is correct and I'm not sure what the problem is, but I'm going to go out on a limb here and guess It's all wrong..
If you prefer syntax (http://pastebin.com/jF7VGd1v)
Snippits:
The node class:
Code: [Select]
struct node {
int y,x,g,h,f;
bool state;
node() { y,x,g,h,f = 0; }
node(int y0, int x0) { y = y0; x = x0; h = 0; f = 0; g = 0; };
void set(int y0, int x0) { y = y0; x = x0; };
};
Code: [Select]
// ============================ PATH FINDING ==========================
int StepsFrom_To(int start_y, int start_x, int dest_y, int dest_x) {
int count = 0;
for (int y = start_y; y < dest_y; y++) { count++; }
for (int x = start_x; x < dest_x; x++) { count++; }
return count;
}
void FindPathFrom_To(int start_y, int start_x, int dest_y, int dest_x) {
// create nodes for start and desticaion
node start_node(start_y,start_x);
node dest_node(dest_y,dest_x);
node old_current(-1,-1);
// open current id
node current(start_y,start_x);
current.state = OPEN;
// node list
node nodes[MAPY*MAPX];
bool searching = true;
// start searching
int steps = 0;
while (searching) {
// Get the node off the open list with the lowest f and make it current node
int lowest_f = 9999; // just so it works :)
for (int i = 0; i < MAPY*MAPX; i++) {
if ( (nodes[i].f < lowest_f) && (nodes[i].state == OPEN) ) {
lowest_f = nodes[i].f;
tiles[nodes[i].y][nodes[i].x].c[0] = 'x';
old_current.set(current.y,current.x);
current.set(nodes[i].y,nodes[i].x);
} else {nodes[i].state = CLOSED; }
}
// check if reached destination
if ( (current.x == dest_node.x) && (current.y == dest_node.y) ) { searching = false; }
// check if node has not changed (meaning there is no where to go)
if ( (current.x == old_current.x) && (current.x == old_current.x) ) { break; }
// Generate each state node_successor that can come after node_current for each node_successor of node_current
if (tiles[current.y+1][current.x].obj_solid == false) { // check below
nodes[steps].set(current.y+1, current.x); // set node cords
nodes[steps].state = OPEN; // add to open list
nodes[steps].h = StepsFrom_To(current.y+1,current.x,dest_node.y,dest_node.x) * 10; // calc histerics
nodes[steps].g = StepsFrom_To(current.y+1,current.x,start_node.y,start_node.x) + steps; // calc move cost
nodes[steps].f = nodes[steps].h + nodes[steps].g;
steps++;
}
if (tiles[current.y-1][current.x].obj_solid == false) { // check above
nodes[steps].set(current.y-1, current.x); // set node cords
nodes[steps].state = OPEN; // add to open list
nodes[steps].h = StepsFrom_To(current.y-1,current.x,dest_node.y,dest_node.x) * 10; // calc histerics
nodes[steps].g = StepsFrom_To(current.y-1,current.x,start_node.y,start_node.x) + steps; // calc move cost
nodes[steps].f = nodes[steps].h + nodes[steps].g;
steps++;
}
if (tiles[current.y][current.x+1].obj_solid == false) { // check right
nodes[steps].set(current.y, current.x+1); // set node cords
nodes[steps].state = OPEN; // add to open list
nodes[steps].h = StepsFrom_To(current.y,current.x+1,dest_node.y,dest_node.x) * 10; // calc histerics
nodes[steps].g = StepsFrom_To(current.y,current.x+1,start_node.y,start_node.x)+ steps; // calc move cost
nodes[steps].f = nodes[steps].h + nodes[steps].g;
steps++;
}
if (tiles[current.y][current.x-1].obj_solid == false) { // check left
nodes[steps].set(current.y, current.x-1); // set node cords
nodes[steps].state = OPEN; // add to open list
nodes[steps].h = StepsFrom_To(current.y,current.x-1,dest_node.y,dest_node.x) * 10; // calc histerics
nodes[steps].g = StepsFrom_To(current.y,current.x-1,start_node.y,start_node.x) + steps; // calc move cost
nodes[steps].f = nodes[steps].h + nodes[steps].g;
steps++;
}
current.state = CLOSED;
}
}
