Path Finding Problem

[madmarky1222]

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:

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;
        }
    }


[miki151]

Hi madmarky, I'm not sure if I caught the bug, but line 31 looks suspicious to me, you shouldn't close all the nodes that are not examined at the moment. I have the impression that the algorithm will stop after one iteration, but it's hard to be sure just looking at the code. I think you should use a debugger and a piece of paper and go through what the program is doing.

An extra hint: you can collapse all the repeated code from line 39 down like this (and it will also make it easier to add diagonal movement if needed):

Code: [Select]

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
for (int i = 0; i < 4; ++i)
if (tiles[current.y + dy[i]][current.x + dx[i]].obj_solid == false) {
// and so on

[guest509]

http://roguebasin.roguelikedevelopment.org/index.php?title=The_Incredible_Power_of_Dijkstra_Maps

I've tried and failed to do it with this. I hear it's the best way...

[Endorya]

Hi madmark. I'm not a bright mind but I did manage to implement the A* pathfinding algorithm just by using this website:
http://www.policyalmanac.org/games/aStarTutorial.htm

The above link also includes a code sample. I hope this helps.

[JohnK]

StepsFrom_To looks like it's broken to me. Do you not just want the Manhattan distance from start to dest? ?Iterating over all the steps doesn't seem to make sense and it won't work if dest_y < start_y or dest_x < start_x.

Code: [Select]

int StepsFrom_To(int start_y, int start_x, int dest_y, int dest_x) {
        return abs(start_y - dest_y) + abs(start_x - dest_x);
    }

Looking through the rest of the code you may actually be right that it is all wrong but hopefully we can fix that for you. Unless you really know what you're doing with pathfinding (and usually even if you do) this is the algorithm to use: http://en.wikipedia.org/wiki/A*_search_algorithm

EDIT: Endorya's link looks like a better way to learn how it works.

[JohnK]

Assuming you're using C++ and the standard libraries, maybe something like this...

Code: [Select]

struct node {
    node() : x(0), y(0), g(0), h(0), f(0), state(UNDISCOVERED), previous_step(NULL), tile(NULL) { }

void ResetForDestination( node* destination )
{
// initialises node for new path
h = std::abs(x - destination->y) + std::abs(y - destination->y);
g = f = INT_MAX;
state = UNDISCOVERED;
previous_step = NULL;
}
void Open( node* previous, std::multiset<node*>& open_set )
{
// adds node to the open list, records where it came from and how long the path is
previous_step = previous;
g = previous_step ? previous_step->g + 1 : 0;
f = g + h;
state = OPEN;
open_set.insert( this );
}

    int x,y;
int g,h,f;
    enum { UNDISCOVERED, OPEN, CLOSED } state;
node* previous_step;
node* neighbours[4];
tile* tile;
};

struct nodeCompare {
    bool operator()(const node* lhs, const node* rhs)
{
if(!lhs) return true;
if(!rhs) return false;
        return lhs->f < rhs->f;
    }
};

bool initialised = false;
std::vector< std::vector<node> > nodes;

void Initialise( int max_X, int max_Y )
{
nodes.resize(max_X);
for (int x = 0; x < max_X; ++x)
{
nodes[x].resize(max_Y);
for (int y = 0; y < max_Y; ++y)
{
nodes[x][y].x = x;
nodes[x][y].y = y;
nodes[x][y].tile = &tiles[x][y];
nodes[x][y].neighbours[0] = x > 0 ? &nodes[x-1][y] : NULL;
nodes[x][y].neighbours[1] = x < max_X-1 ? &nodes[x+1][y] : NULL;
nodes[x][y].neighbours[2] = y > 0 ? &nodes[x][y-1] : NULL;
nodes[x][y].neighbours[3] = y < max_Y-1 ? &nodes[x][y+1] : NULL;
}
}
initialised = true;
}

bool FindPathFrom_To( int start_X, int start_Y, int dest_X, int dest_Y, std::list<tile*>& path )
{
if( !initialised )
{
Initialise( MAPX, MAPY );
}
// reinitialise node map
node* start_node = &nodes[start_X][start_Y];
node* destination_node = &nodes[dest_X][dest_Y];
for (int x = 0; x < max_X; ++x)
for (int y = 0; y < max_Y; ++y)
nodes[x][y].ResetForDestination(destination_node);

// open list, automatically sorts by f
std::multiset<node*, nodeCompare> open;
start_node->Open( NULL, open );

// search
while( !open.empty() )
{
// find the current cheapest node (which will be at the start of the set)
node* current_node = *open.begin();
if( current_node == destination_node )
{
break;
}
// open all adjacent nodes
for( int i = 0; i < 4; i++ )
{
if( current_node->neighbours[i] && current_node->neighbours[i]->state == node::UNDISCOVERED )
{
current_node->neighbours[i]->Open( current_node, open );
}
}
// remove current node from the open list
current_node->state = node::CLOSED;
open_set.erase( open.begin() );
}

// calculate the final path
path.clear();
node* current_step = destination_node;
while( current_step )
{
path.push_front( current_step->tile );
if( current_step == start_node )
{
return true;
}
current_step = current_step->previous_step;
}
return false;
}

I haven't compiled it, let alone tested it but all the basics are there (even if it's rather messy).

You call 'Initialise' to create your pathfinding map and then 'FindPathFrom_To' to get a list of tiles you need to traverse. It returns false if no path was found.

[Quendus]

http://paleoludic.com/writing/category/pathfinding/

[IBOL]

as jo mentioned above,
dijkstra is an awesome way to go, and I have gotten them to work,
just by reading the description here:
http://roguebasin.roguelikedevelopment.org/index.php?title=The_Incredible_Power_of_Dijkstra_Maps

[madmarky1222]

Okay, so reading all your post, i decided to scrap that and attempt it again, after having a look at the Dijkstra algorithm this is what I came up with:

Code: (PathFinder.h) [Select]

#ifndef PATHFINDER_H_INCLUDED
#define PATHFINDER_H_INCLUDED
#define EMPTY -1
#define MAPY 200
#define MAPX 200
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

enum node_states { UNVISITED, OPEN, CLOSED };
enum searching_states { FOUND, NON_EXIST, SEARCHING, NOT_SEARCHING };

/*
;===================================================================
;                          NODE CLASS
;===================================================================
*/

struct node {
    node() : x(0), y(0), f(0), previous_step(NULL), state(UNVISITED) { }
    int x,y,state,f;
node* neighbours[8];
node* previous_step;

    // sort by f value
static bool compareNode(node lhs, node rhs) { return (lhs.f < rhs.f); }
};

/*
;===================================================================
;                         PATHFINDER CLASS
;===================================================================
*/

class obj_pathfinder {
    public:
    vector <node> list;
    int xPath[];
    int yPath[];
    node start, cur, dest;
    int state,steps;

    int dist(int start_y, int start_x, int dest_y, int dest_x) {
        return abs(start_y - dest_y) + abs(start_x - dest_x);
    }

    // search list for existing node
    bool checkNeighbour(vector <node> nodes, node* look) {
        return false;
        for (int i = 0; i < nodes.size(); i++) {
            if ( (nodes[i].x == look->x) && (nodes[i].y == look->y) && (look->state == OPEN) ) {
                return true;
                break;
            }
        }
    }

    // search list for existing node
    bool check(vector <node> nodes, node look) {
        return false;
        for (int i = 0; i < nodes.size(); i++) {
            if ( (nodes[i].x == look.x) && (nodes[i].y == look.y) && (look.state == OPEN) ) {
                return true;
                break;
            }
        }
    }

    // find path and record it to a cord list
    void FindPath(int str_y, int str_x, int dest_y, int dest_x, int walkable[MAPY][MAPX]) {
        // reset
        steps = 0;
        list.clear();
        // 1. Put the starting square on the open-list.
        start.y = str_y; start.x = str_x; start.state = OPEN;
        dest.y = dest_y; dest.x = dest.x;
        list.push_back(start);
        state = SEARCHING;
        //2. Repeat the following steps:
        while (state == SEARCHING){
            // a) Find the square with the lowest G value from the open-list, this square is the new current square.
            sort(list.begin(), list.end(), node::compareNode);
            for (int i = 0; i < list.size(); i++) {
                if (list[i].state != CLOSED) {
                    cur = list[i];
                    // b) Put the current square on the closed list.
                    list[i].state = CLOSED;
                    break;
                }
                else { /* do nothing */ }
            }

            // c) For each of the 4 adjacent squares to the current square the following steps are executed:
            int dy[] = {1,  0, -1,  0, -1,  1, -1,  1};
            int dx[] = {0, -1,  0, -1, -1,  1,  1, -1};
            int dc[] = {10, 10, 10, 10, 14, 14, 14, 14};
            for (int i = 0; i < 8; i++) {
                // If the square is a wall than we ignore that square.
                if ( walkable[cur.y+dy[i]][cur.x+dx[i]] == 0 ) {
                    // If the square is not yet on the open-list it will be put on it.
                    // The current square is the parent square for this square.
                    cur.neighbours[i]->y = cur.y+dy[i];
                    cur.neighbours[i]->x = cur.x+dx[i];
                    if( checkNeighbour(list,cur.neighbours[i]) == false) {
                        //Calculate the G value for this square and add it to the open list.
                        cur.neighbours[i]->f = dist(cur.neighbours[i]->y,cur.neighbours[i]->x,start.y,start.x);
                        cur.neighbours[i]->state = OPEN;
                    } else {
                        /* If the square was already on the open-list then there must be check if the
                        /  current path is a shorter path than the neighbour path.
                        /  A lower G value means a shorter path.
                        /  If this is the case than this square should change it’s parent square and it should be given the new G value. */
                        int lowest_f = 9999999;
                        int lowest_id = 0;
                        for (int o = 0; o < 8; o++) {
                            if (cur.neighbours[o]->state == OPEN) {
                                if (cur.neighbours[o]->f < lowest_f) {
                                    lowest_f = cur.neighbours[o]->f;
                                    lowest_id = i;
                                }
                            }
                        }
                        // set lowest G value neighbour to current
                        if (cur.f <= lowest_f) {
                            cur.x, xPath[steps] = cur.neighbours[lowest_id]->x;
                            cur.y, yPath[steps] = cur.neighbours[lowest_id]->y;
                            cur.state = cur.neighbours[lowest_id]->state;
                            list.push_back(cur);
                            for (int o = 0; o < 8; o++) { cur.neighbours[lowest_id] = NULL; }
                            steps++;
                        }

                    }
                }
            }

            // d) Stop the calculation if the ending point is put on the open-list.
            // (in this case the shortest path has been found)
            if ( check(list,dest) ) { state = FOUND; }
            // unable to find path
            if ( list.empty() ) { state = NON_EXIST; }
        }
    }
};

#endif // PATHFINDER_H_INCLUDED

Activate on mouse click:

Code: [Select]

if (MouseClicked() == LEFT) {
                for (int y = 0; y < MAPY; y++) {
                    for (int x = 0; x < MAPX; x++) {
                        if (board.tiles[y][x].obj_solid == true) {
                            solidmap[y][x] = 1;
                        } else { solidmap[y][x] = 0; }
                    }
                }
                pathfinder.FindPath(p1.y,p1.x,board.GetMouseY_OnMap(),board.GetMouseX_OnMap(),solidmap);
            }

As soon as I click the program crashes.. This baffles me, I've been at it for 3 days now

[madmarky1222]

SOLVED IT! 

I never figured out the math sadly.. but I solved it!

Modified AStar* version:

Code: ("pathfinder.h") [Select]

#include <allegro.h>
/*
;===================================================================
;A* Pathfinder (Version 1.71a) by Patrick Lester. Used by permission.
;===================================================================
;Last updated 06/16/03 -- Visual C++ version
 */

//Declare constants
const int mapWidth = 200, mapHeight = 200, numberPeople = 1;
int onClosedList = 10;
const int notfinished = 0, notStarted = 0;// path-related constants
const int found = 1, nonexistent = 2;
const int walkable = 0, unwalkable = 1;// walkability array constants

//Create needed arrays
char walkability [mapWidth][mapHeight];
int openList[mapWidth*mapHeight+2]; //1 dimensional array holding ID# of open list items
int whichList[mapWidth+1][mapHeight+1];  //2 dimensional array used to record
// whether a cell is on the open list or on the closed list.
int openX[mapWidth*mapHeight+2]; //1d array stores the x location of an item on the open list
int openY[mapWidth*mapHeight+2]; //1d array stores the y location of an item on the open list
int parentX[mapWidth+1][mapHeight+1]; //2d array to store parent of each cell (x)
int parentY[mapWidth+1][mapHeight+1]; //2d array to store parent of each cell (y)
int Fcost[mapWidth*mapHeight+2]; //1d array to store F cost of a cell on the open list
int Gcost[mapWidth+1][mapHeight+1]; //2d array to store G cost for each cell.
int Hcost[mapWidth*mapHeight+2]; //1d array to store H cost of a cell on the open list
int pathLength[numberPeople+1];     //stores length of the found path for critter
int pathLocation[numberPeople+1];   //stores current position along the chosen path for critter
int* pathBank [numberPeople+1];

//Path reading variables
int pathStatus[numberPeople+1];
int xPath[numberPeople+1];
int yPath[numberPeople+1];

//-----------------------------------------------------------------------------
// Function Prototypes: where needed
//-----------------------------------------------------------------------------
void ReadPath(int pathfinderID,int currentX,int currentY);
int ReadPathX(int pathfinderID,int pathLocation);
int ReadPathY(int pathfinderID,int pathLocation);


//-----------------------------------------------------------------------------
// Name: InitializePathfinder
// Desc: Allocates memory for the pathfinder.
//-----------------------------------------------------------------------------
void InitializePathfinder (void)
{
for (int x = 0; x < numberPeople+1; x++)
pathBank [x] = (int*) malloc(4);
}


//-----------------------------------------------------------------------------
// Name: EndPathfinder
// Desc: Frees memory used by the pathfinder.
//-----------------------------------------------------------------------------
void EndPathfinder (void)
{
for (int x = 0; x < numberPeople+1; x++)
{
free (pathBank [x]);
}
}


//-----------------------------------------------------------------------------
// Name: FindPath
// Desc: Finds a path using A*
//-----------------------------------------------------------------------------
int FindPath (int pathfinderID,int startingX, int startingY,
  int targetX, int targetY)
{
int onOpenList=0, parentXval=0, parentYval=0,
a=0, b=0, m=0, u=0, v=0, temp=0, corner=0, numberOfOpenListItems=0,
addedGCost=0, tempGcost = 0, path = 0,
tempx, pathX, pathY, cellPosition,
newOpenListItemID=0;

//1. Convert location data (in pixels) to coordinates in the walkability array.
int startX = startingX;
int startY = startingY;
targetX = targetX;
targetY = targetY;

//2.Quick Path Checks: Under the some circumstances no path needs to
// be generated ...

// If starting location and target are in the same location...
if (startX == targetX && startY == targetY && pathLocation[pathfinderID] > 0)
return found;
if (startX == targetX && startY == targetY && pathLocation[pathfinderID] == 0)
return nonexistent;

// If target square is unwalkable, return that it's a nonexistent path.
if (walkability[targetX][targetY] == unwalkable)
goto noPath;

//3.Reset some variables that need to be cleared
if (onClosedList > 1000000) //reset whichList occasionally
{
for (int x = 0; x < mapWidth;x++) {
for (int y = 0; y < mapHeight;y++)
whichList [x][y] = 0;
}
onClosedList = 10;
}
onClosedList = onClosedList+2; //changing the values of onOpenList and onClosed list is faster than redimming whichList() array
onOpenList = onClosedList-1;
pathLength [pathfinderID] = notStarted;//i.e, = 0
pathLocation [pathfinderID] = notStarted;//i.e, = 0
Gcost[startX][startY] = 0; //reset starting square's G value to 0

//4.Add the starting location to the open list of squares to be checked.
numberOfOpenListItems = 1;
openList[1] = 1;//assign it as the top (and currently only) item in the open list, which is maintained as a binary heap (explained below)
openX[1] = startX ; openY[1] = startY;

//5.Do the following until a path is found or deemed nonexistent.
do
{

//6.If the open list is not empty, take the first cell off of the list.
// This is the lowest F cost cell on the open list.
if (numberOfOpenListItems != 0)
{

//7. Pop the first item off the open list.
parentXval = openX[openList[1]];
parentYval = openY[openList[1]]; //record cell coordinates of the item
whichList[parentXval][parentYval] = onClosedList;//add the item to the closed list

// Open List = Binary Heap: Delete this item from the open list, which
//  is maintained as a binary heap. For more information on binary heaps, see:
// http://www.policyalmanac.org/games/binaryHeaps.htm
numberOfOpenListItems = numberOfOpenListItems - 1;//reduce number of open list items by 1

// Delete the top item in binary heap and reorder the heap, with the lowest F cost item rising to the top.
openList[1] = openList[numberOfOpenListItems+1];//move the last item in the heap up to slot #1
v = 1;

// Repeat the following until the new item in slot #1 sinks to its proper spot in the heap.
do
{
u = v;
if (2*u+1 <= numberOfOpenListItems) //if both children exist
{
//Check if the F cost of the parent is greater than each child.
//Select the lowest of the two children.
if (Fcost[openList[u]] >= Fcost[openList[2*u]])
v = 2*u;
if (Fcost[openList[v]] >= Fcost[openList[2*u+1]])
v = 2*u+1;
}
else
{
if (2*u <= numberOfOpenListItems) //if only child #1 exists
{
//Check if the F cost of the parent is greater than child #1
if (Fcost[openList[u]] >= Fcost[openList[2*u]])
v = 2*u;
}
}

if (u != v) //if parent's F is > one of its children, swap them
{
temp = openList[u];
openList[u] = openList[v];
openList[v] = temp;
}
else
break; //otherwise, exit loop

}
while (!key[KEY_ESC]);//reorder the binary heap


//7.Check the adjacent squares. (Its "children" -- these path children
// are similar, conceptually, to the binary heap children mentioned
// above, but don't confuse them. They are different. Path children
// are portrayed in Demo 1 with grey pointers pointing toward
// their parents.) Add these adjacent child squares to the open list
// for later consideration if appropriate (see various if statements
// below).
for (b = parentYval-1; b <= parentYval+1; b++){
for (a = parentXval-1; a <= parentXval+1; a++){

// If not off the map (do this first to avoid array out-of-bounds errors)
if (a != -1 && b != -1 && a != mapWidth && b != mapHeight){

// If not already on the closed list (items on the closed list have
// already been considered and can now be ignored).
if (whichList[a][b] != onClosedList) {

// If not a wall/obstacle square.
if (walkability [a][b] != unwalkable) {

// Don't cut across corners
corner = walkable;
if (a == parentXval-1)
{
if (b == parentYval-1)
{
if (walkability[parentXval-1][parentYval] == unwalkable
|| walkability[parentXval][parentYval-1] == unwalkable) \
corner = unwalkable;
}
else if (b == parentYval+1)
{
if (walkability[parentXval][parentYval+1] == unwalkable
|| walkability[parentXval-1][parentYval] == unwalkable)
corner = unwalkable;
}
}
else if (a == parentXval+1)
{
if (b == parentYval-1)
{
if (walkability[parentXval][parentYval-1] == unwalkable
|| walkability[parentXval+1][parentYval] == unwalkable)
corner = unwalkable;
}
else if (b == parentYval+1)
{
if (walkability[parentXval+1][parentYval] == unwalkable
|| walkability[parentXval][parentYval+1] == unwalkable)
corner = unwalkable;
}
}
if (corner == walkable) {

// If not already on the open list, add it to the open list.
if (whichList[a][b] != onOpenList)
{

//Create a new open list item in the binary heap.
newOpenListItemID = newOpenListItemID + 1; //each new item has a unique ID #
m = numberOfOpenListItems+1;
openList[m] = newOpenListItemID;//place the new open list item (actually, its ID#) at the bottom of the heap
openX[newOpenListItemID] = a;
openY[newOpenListItemID] = b;//record the x and y coordinates of the new item

//Figure out its G cost
if (abs(a-parentXval) == 1 && abs(b-parentYval) == 1)
addedGCost = 14;//cost of going to diagonal squares
else
addedGCost = 10;//cost of going to non-diagonal squares
Gcost[a][b] = Gcost[parentXval][parentYval] + addedGCost;

//Figure out its H and F costs and parent
Hcost[openList[m]] = 10*(abs(a - targetX) + abs(b - targetY));
Fcost[openList[m]] = Gcost[a][b] + Hcost[openList[m]];
parentX[a][b] = parentXval ; parentY[a][b] = parentYval;

//Move the new open list item to the proper place in the binary heap.
//Starting at the bottom, successively compare to parent items,
//swapping as needed until the item finds its place in the heap
//or bubbles all the way to the top (if it has the lowest F cost).
while (m != 1) //While item hasn't bubbled to the top (m=1)
{
//Check if child's F cost is < parent's F cost. If so, swap them.
if (Fcost[openList[m]] <= Fcost[openList[m/2]])
{
temp = openList[m/2];
openList[m/2] = openList[m];
openList[m] = temp;
m = m/2;
}
else
break;
}
numberOfOpenListItems = numberOfOpenListItems+1;//add one to the number of items in the heap

//Change whichList to show that the new item is on the open list.
whichList[a][b] = onOpenList;
}

//8.If adjacent cell is already on the open list, check to see if this
// path to that cell from the starting location is a better one.
// If so, change the parent of the cell and its G and F costs.
else //If whichList(a,b) = onOpenList
{

//Figure out the G cost of this possible new path
if (abs(a-parentXval) == 1 && abs(b-parentYval) == 1)
addedGCost = 14;//cost of going to diagonal tiles
else
addedGCost = 10;//cost of going to non-diagonal tiles
tempGcost = Gcost[parentXval][parentYval] + addedGCost;

//If this path is shorter (G cost is lower) then change
//the parent cell, G cost and F cost.
if (tempGcost < Gcost[a][b]) //if G cost is less,
{
parentX[a][b] = parentXval; //change the square's parent
parentY[a][b] = parentYval;
Gcost[a][b] = tempGcost;//change the G cost

//Because changing the G cost also changes the F cost, if
//the item is on the open list we need to change the item's
//recorded F cost and its position on the open list to make
//sure that we maintain a properly ordered open list.
for (int x = 1; x <= numberOfOpenListItems; x++) //look for the item in the heap
{
if (openX[openList[x]] == a && openY[openList[x]] == b) //item found
{
Fcost[openList[x]] = Gcost[a][b] + Hcost[openList[x]];//change the F cost

//See if changing the F score bubbles the item up from it's current location in the heap
m = x;
while (m != 1) //While item hasn't bubbled to the top (m=1)
{
//Check if child is < parent. If so, swap them.
if (Fcost[openList[m]] < Fcost[openList[m/2]])
{
temp = openList[m/2];
openList[m/2] = openList[m];
openList[m] = temp;
m = m/2;
}
else
break;
}
break; //exit for x = loop
} //If openX(openList(x)) = a
} //For x = 1 To numberOfOpenListItems
}//If tempGcost < Gcost(a,b)

}//else If whichList(a,b) = onOpenList
}//If not cutting a corner
}//If not a wall/obstacle square.
}//If not already on the closed list
}//If not off the map
}//for (a = parentXval-1; a <= parentXval+1; a++){
}//for (b = parentYval-1; b <= parentYval+1; b++){

}//if (numberOfOpenListItems != 0)

//9.If open list is empty then there is no path.
else
{
path = nonexistent; break;
}

//If target is added to open list then path has been found.
if (whichList[targetX][targetY] == onOpenList)
{
path = found; break;
}

}
while (1);//Do until path is found or deemed nonexistent

//10.Save the path if it exists.
if (path == found)
{

//a.Working backwards from the target to the starting location by checking
// each cell's parent, figure out the length of the path.
pathX = targetX; pathY = targetY;
do
{
//Look up the parent of the current cell.
tempx = parentX[pathX][pathY];
pathY = parentY[pathX][pathY];
pathX = tempx;

//Figure out the path length
pathLength[pathfinderID] = pathLength[pathfinderID] + 1;
}
while (pathX != startX || pathY != startY);

//b.Resize the data bank to the right size in bytes
pathBank[pathfinderID] = (int*) realloc (pathBank[pathfinderID],
pathLength[pathfinderID]*8);

//c. Now copy the path information over to the databank. Since we are
// working backwards from the target to the start location, we copy
// the information to the data bank in reverse order. The result is
// a properly ordered set of path data, from the first step to the
// last.
pathX = targetX ; pathY = targetY;
cellPosition = pathLength[pathfinderID]*2;//start at the end
do
{
cellPosition = cellPosition - 2;//work backwards 2 integers
pathBank[pathfinderID] [cellPosition] = pathX;
pathBank[pathfinderID] [cellPosition+1] = pathY;

//d.Look up the parent of the current cell.
tempx = parentX[pathX][pathY];
pathY = parentY[pathX][pathY];
pathX = tempx;

//e.If we have reached the starting square, exit the loop.
}
while (pathX != startX || pathY != startY);

//11.Read the first path step into xPath/yPath arrays
ReadPath(pathfinderID,startingX,startingY);

}
return path;


//13.If there is no path to the selected target, set the pathfinder's
// xPath and yPath equal to its current location and return that the
// path is nonexistent.
noPath:
xPath[pathfinderID] = startingX;
yPath[pathfinderID] = startingY;
return nonexistent;
}




//==========================================================
//READ PATH DATA: These functions read the path data and convert
//it to screen pixel coordinates.
void ReadPath(int pathfinderID,int currentX,int currentY)
{
/*
; Note on PixelsPerFrame: The need for this parameter probably isn't
; that obvious, so a little explanation is in order. This
; parameter is used to determine if the pathfinder has gotten close
; enough to the center of a given path square to warrant looking up
; the next step on the path.
;
; This is needed because the speed of certain sprites can
; make reaching the exact center of a path square impossible.
; In Demo #2, the chaser has a velocity of 3 pixels per frame. Our
; tile size is 50 pixels, so the center of a tile will be at location
; 25, 75, 125, etc. Some of these are not evenly divisible by 3, so
; our pathfinder has to know how close is close enough to the center.
; It calculates this by seeing if the pathfinder is less than
; pixelsPerFrame # of pixels from the center of the square.

; This could conceivably cause problems if you have a *really* fast
; sprite and/or really small tiles, in which case you may need to
; adjust the formula a bit. But this should almost never be a problem
; for games with standard sized tiles and normal speeds. Our smiley
; in Demo #4 moves at a pretty fast clip and it isn't even close
; to being a problem.
*/

int ID = pathfinderID; //redundant, but makes the following easier to read

//If a path has been found for the pathfinder ...
if (pathStatus[ID] == found)
{

//If path finder is just starting a new path or has reached the
//center of the current path square (and the end of the path
//hasn't been reached), look up the next path square.
if (pathLocation[ID] < pathLength[ID])
{
//if just starting or if close enough to center of square
if (pathLocation[ID] == 0 ||(abs(currentX - xPath[ID]) < 1 && abs(currentY - yPath[ID]) < 1))
pathLocation[ID] = pathLocation[ID] + 1;
}

//Read the path data.
xPath[ID] = ReadPathX(ID,pathLocation[ID]);
yPath[ID] = ReadPathY(ID,pathLocation[ID]);

//If the center of the last path square on the path has been
//reached then reset.
if (pathLocation[ID] == pathLength[ID])
{
if (abs(currentX - xPath[ID]) < 1
&& abs(currentY - yPath[ID]) < 1) //if close enough to center of square
pathStatus[ID] = notStarted;
}
}

//If there is no path for this pathfinder, simply stay in the current
  //location.
else
{
xPath[ID] = currentX;
yPath[ID] = currentY;
}
}


//The following two functions read the raw path data from the pathBank.
//You can call these functions directly and skip the readPath function
//above if you want. Make sure you know what your current pathLocation
//is.

//-----------------------------------------------------------------------------
// Name: ReadPathX
// Desc: Reads the x coordinate of the next path step
//-----------------------------------------------------------------------------
int ReadPathX(int pathfinderID,int pathLocation)
{
int x;
if (pathLocation <= pathLength[pathfinderID])
{

//Read coordinate from bank
x = pathBank[pathfinderID] [pathLocation*2-2];
x = x;

}
return x;
}


//-----------------------------------------------------------------------------
// Name: ReadPathY
// Desc: Reads the y coordinate of the next path step
//-----------------------------------------------------------------------------
int ReadPathY(int pathfinderID,int pathLocation)
{
int y;
if (pathLocation <= pathLength[pathfinderID])
{

//Read coordinate from bank
y = pathBank[pathfinderID] [pathLocation*2-1];
}
return y;
}

Thank you all for your time and help

[guest509]

Yay!

Glad we were able to help. That Dijkstra map rundown is a real go to for many people. I swear as soon as I get it to work in a turn based fashion in Gamemaker I'm going to post a tutorial (my first).

Don't worry about not understanding it fully. If you are learning to program maybe that stuff is important, but if you are wanting to make a game it's not. Does that make sense? You only need to know as much as you need to make the kick ass game you want to make, unless you want to go pro and work for someone else...

For example my dumb ass is HORRIBLE at coding. I'm better than the average person maybe, but even among hobbyists I'm pretty fail. One of the major community figures is Darren Grey who uses Dark God's T-Engine (ToME4 Engine) to make his games, but I think he might be pretty proficient at other tools and languages. I'm not sure really.

My point is...that the point is...MAKE GAMES. :-)