Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Pathfinding function problem
New Posts  All Forums:Forum Nav:

Pathfinding function problem

post #1 of 3
Thread Starter 
Hey, I am having some trouble getting a function to work properly. The code works when it is directly in the my statement but as soon as I try to call a function that does the exact same thing it breaks. I am pretty sure it has to do with the call but I am obviously overlooking something. Warning: Spoiler! (Click to show)
Code:
#include <iostream>
#include <string>
#include "tile.h"

using namespace std;
//node
struct nodeType
{
        Tile *tile;
        nodeType *link;
        nodeType *prevLink;
        nodeType();
        ~nodeType();
};
//size of map
const int SIZE = 10;
//prototypes
void findPath(char map[SIZE][SIZE]);
void findStartAndEnd(int&, int&, int&, int&, char map[SIZE][SIZE]);
void printMap(char map[SIZE][SIZE]);
void deleteList(nodeType *list);
void searchOpenList(nodeType *list, nodeType *&lowestNode);
bool notInList(nodeType *list, int x, int y);
void mapOutPath(char map[SIZE][SIZE], Tile *tile);
void newTileCreation(Tile *&newTile, nodeType *&newNode, int &currX, int &currY, int &endX, int &endY, nodeType *&currentNode, nodeType *&openListTail);

int main()
{
        char end;
        string blank;
        char map1[SIZE][SIZE] = {{' ','S',' ',' ',' ',' ',' ',' ',' ',' '},
                                                        {'B','B','B',' ','B','B','B','B','B',' '},
                                                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
                                                        {'B','B','B','B','B','B','B','B',' ','B'},
                                                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
                                                        {' ',' ',' ',' ',' ',' ','B','B','B','B'},
                                                        {' ',' ',' ',' ',' ','B','B',' ',' ',' '},
                                                        {' ',' ',' ',' ','B',' ','B',' ',' ',' '},
                                                        {' ',' ',' ',' ',' ',' ','B',' ',' ',' '},
                                                        {' ',' ',' ',' ',' ',' ',' ',' ',' ','E'}};
        char map2[SIZE][SIZE] = {{' ','S',' ',' ',' ',' ',' ',' ',' ',' '},
                                                        {'B','B','B','B','B','B','B','B','B',' '},
                                                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
                                                        {'B','B','B','B','B','B','B','B',' ','B'},
                                                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
                                                        {' ','B','B','B','B','B',' ',' ',' ',' '},
                                                        {' ',' ',' ',' ',' ','B',' ',' ',' ',' '},
                                                        {' ',' ',' ','B',' ','B','B','B','B','B'},
                                                        {' ',' ',' ','B',' ',' ',' ',' ',' ',' '},
                                                        {' ',' ',' ','B','B','B',' ',' ',' ','E'}};
        char map3[SIZE][SIZE] = {{' ','S',' ',' ',' ',' ',' ',' ',' ',' '},
                                                        {'B','B','B','B','B','B','B','B','B',' '},
                                                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
                                                        {'B','B','B','B','B','B','B','B',' ','B'},
                                                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
                                                        {' ','B','B','B','B','B',' ',' ',' ',' '},
                                                        {' ',' ',' ',' ',' ','B',' ',' ',' ',' '},
                                                        {' ',' ',' ','B',' ','B','B','B','B','B'},
                                                        {' ',' ',' ','B',' ','B',' ',' ',' ',' '},
                                                        {' ',' ',' ','B','B','B',' ',' ',' ','E'}};
        //------------------------------------------------------
        cout << "\n\t---------------"
                 << "\n\t     MAP 1"
                 << "\n\t---------------";
        printMap(map1);
        cout << "Press enter to find path...";
        getline(cin, blank);
        findPath(map1);
        //------------------------------------------------------
        cout << "\n\t---------------"
                 << "\n\t     MAP 2"
                 << "\n\t---------------";
        printMap(map2);
        cout << "Press enter to find path...";
        getline(cin, blank);
        findPath(map2);
        //------------------------------------------------------
        cout << "\n\t---------------"
                 << "\n\t     MAP 3"
                 << "\n\t---------------";
        printMap(map3);
        cout << "Press enter to find path...";
        getline(cin, blank);
        findPath(map3);
        //------------------------------------------------------
        cout << "Enter a character and press enter: ";
        cin >> end;
        return 0;
}
//###########################################################
void findPath(char map[SIZE][SIZE])
{
        // Coordinate Variables
        int startX, startY;
        int endX, endY;
        int currX, currY; 
        // Other Variables
        bool foundDestination = false;
        // New and Current Pointers
        Tile *newTile;
        Tile *currentTile;
        nodeType *newNode;
        nodeType *currentNode;
        // List Pointers
        nodeType *openListHead = NULL;
        nodeType *openListTail = NULL;
        nodeType *closedListHead = NULL;
        nodeType *closedListTail = NULL;
        //-----------------------------------------------
        findStartAndEnd(startX, startY, endX, endY, map);

        //Staring tile and node
        newTile = new Tile(startX, startY, endX, endY);
        newNode = new nodeType;
        newNode->tile = newTile;

        //set openlist head and tail to starting node
        openListHead = openListTail = newNode;
        openListHead->prevLink = NULL;

        //search nodes
        do
        {
                //determine open list head
                searchOpenList(openListHead, currentNode);
                currentNode->tile->getCoords(currX, currY);

                //determine if space is searchable, if useable, create new tile and set links
                if (currX+1 < SIZE && map[currY][currX+1] != 'B' && notInList(openListHead, currX+1, currY) && notInList(closedListHead, currX+1, currY))
                {
breaks program
Code:
                     newTileCreation(newTile, newNode, currX, currY, endX, endY, currentNode, openListTail);

                      [B]This works[/B]
                        /*
                        newTile = new Tile(currX+1, currY, endX, endY, currentNode->tile->getScore() + 1, currentNode->tile);
                        newNode = new nodeType;
                        newNode->tile = newTile;
                        openListTail->link = newNode;
                        openListTail->link->prevLink = openListTail;
                        openListTail = openListTail->link;
                        */
                        
                }
                else if (currY+1 < SIZE && map[currY+1][currX] != 'B' && notInList(openListHead, currX, currY+1) && notInList(closedListHead, currX, currY+1))
                {
                        newTileCreation(newTile, newNode, currX, currY, endX, endY, currentNode, openListTail);
                        /*
                        newTile = new Tile(currX+1, currY, endX, endY, currentNode->tile->getScore() + 1, currentNode->tile);
                        newNode = new nodeType;
                        newNode->tile = newTile;
                        openListTail->link = newNode;
                        openListTail->link->prevLink = openListTail;
                        openListTail = openListTail->link;
                        */
                        
                }
                else if (currX-1 >= 0 && map[currY][currX-1] != 'B' && notInList(openListHead, currX-1, currY) && notInList(closedListHead, currX-1, currY))
                {
                        newTileCreation(newTile, newNode, currX, currY, endX, endY, currentNode, openListTail);
                        /*
                        newTile = new Tile(currX+1, currY, endX, endY, currentNode->tile->getScore() + 1, currentNode->tile);
                        newNode = new nodeType;
                        newNode->tile = newTile;
                        openListTail->link = newNode;
                        openListTail->link->prevLink = openListTail;
                        openListTail = openListTail->link;
                        */
                        
                }
                else if (currY-1 >= 0 && map[currY-1][currX] != 'B' && notInList(openListHead, currX, currY-1) && notInList(closedListHead, currX, currY-1))
                {
                        newTileCreation(newTile, newNode, currX, currY, endX, endY, currentNode, openListTail);
                        /*
                        newTile = new Tile(currX+1, currY, endX, endY, currentNode->tile->getScore() + 1, currentNode->tile);
                        newNode = new nodeType;
                        newNode->tile = newTile;
                        openListTail->link = newNode;
                        openListTail->link->prevLink = openListTail;
                        openListTail = openListTail->link;
                        */
                        
                }
                else
                {
                        if (currentNode == openListHead)
                        {
                                openListHead = openListHead->link;
                                if (openListHead != NULL)
                                        openListHead->prevLink = NULL;
                        }
                        else if (currentNode == openListTail)
                        {
                                openListTail = openListTail->prevLink;
                                openListTail->link = NULL;
                        }
                        else
                        {
                                currentNode->prevLink->link = currentNode->link;
                                currentNode->link->prevLink = currentNode->prevLink;
                        }
                        currentNode->link = NULL;
                        currentNode->prevLink = NULL;

                        if (closedListHead == NULL)
                                closedListHead = closedListTail = currentNode;
                        else
                        {
                                closedListTail->link = currentNode;
                                closedListTail = closedListTail->link;
                        }
                }

                newTile->getCoords(currX, currY);
                if (currX == endX && currY == endY)
                {
                        currentTile = newTile;
                        foundDestination = true;
                        break;
                }
        } while (openListHead != NULL);

        if (foundDestination)
        {
                mapOutPath(map, currentTile);
                printMap(map);
        }
        else
                cout << "\n\t\t\t------------------"
                         << "\n\t\t\t  No Path Exists"
                         << "\n\t\t\t------------------\n\n";

        deleteList(openListHead);
        deleteList(closedListHead);
}
//###########################################################
void findStartAndEnd(int &xStart, int &yStart, int &xEnd, int &yEnd, char map[SIZE][SIZE])
{
        for (int i = 0; i < SIZE; i++)
        {
                for (int j = 0; j < SIZE; j++)
                {
                        if (map[i][j] == 'S')
                        {
                                xStart = j;
                                yStart = i;
                        }
                        else if (map[i][j] == 'E')
                        {
                                xEnd = j;
                                yEnd = i;
                        }
                }
        }
}
//###########################################################
void printMap(char map[SIZE][SIZE])
{
        cout << "\n\t\t-";
        for (int k = 0; k < SIZE; k++)
                cout << "----";
        cout << endl;
        
        for (int i = 0; i < SIZE; i++)
        {
                cout << "\t\t|";
                for (int j = 0; j < SIZE; j++)
                {
                        cout << " " << map[i][j] << " |";
                }
                cout << "\n\t\t";
                if (i == (SIZE - 1))
                {
                        cout << "-";
                        for (int k = 0; k < SIZE; k++)
                                cout << "----";
                }
                else
                {
                        cout << "|";
                        for (int k = 0; k < SIZE; k++)
                                cout << "---|";
                }

                cout << endl;
        }
}
//###########################################################
void deleteList(nodeType *list)
{
        nodeType *currNode;

        while (list != NULL)
        {
                currNode = list;
                list = list->link;
                delete currNode;
        }
}
//###########################################################
void searchOpenList(nodeType *list, nodeType *&lowestNode)
{
        lowestNode = list;
        int lowestCost = list->tile->getCost();
        int tempCost;

        list = list->link;
        while (list != NULL)
        {
                tempCost = list->tile->getCost();
                if (tempCost <= lowestCost)
                {
                        lowestNode = list;
                        lowestCost = tempCost;
                }
                list = list->link;
        }
}
//###########################################################
bool notInList(nodeType *list, int x, int y)
{
        int tempX;
        int tempY;
        while (list != NULL)
        {
                list->tile->getCoords(tempX, tempY);
                if (tempX == x && tempY == y)
                        return false;
                else
                        list = list->link;
        }
        return true;
}
//###########################################################
void mapOutPath(char map[SIZE][SIZE], Tile *tile)
{
        int x, y;
        tile->getParent(tile);
        do
        {
                tile->getCoords(x, y);
                if (map[y][x] != 'S')
                        map[y][x] = 'X';
                tile->getParent(tile);
        } while (tile != NULL);
}
//##########################################################
//new Tile function
void newTileCreation(Tile *&newTile, nodeType *&newNode, int &currX, int &currY, int &endX, int &endY, nodeType *&currentNode, nodeType *&openListTail)
{
        newTile = new Tile(currX+1, currY, endX, endY, currentNode->tile->getScore() + 1, currentNode->tile);
        newNode = new nodeType;
        newNode->tile = newTile;
        openListTail->link = newNode;
        openListTail->link->prevLink = openListTail;
        openListTail = openListTail->link;
}
//##########################################################
// nodeType constructor
nodeType::nodeType()
{
        tile = NULL;
        link = NULL;
        prevLink = NULL;
}
//##########################################################
// nodeType destructor
nodeType::~nodeType()
{       delete tile;    }
Any help would be appreciated, Thanks.
Edited by Tk7331 - 6/28/13 at 1:34pm
My System
(13 items)
 
  
CPUMotherboardGraphicsRAM
Intel i7 950 Asus P6X58D-E Gigabyte GTX 770  12 GB GSkill 
Hard DriveOptical DriveOSMonitor
Seagate 1TB, Samsung 2TB TSSTcorp Windows 7 home Premium x64 Asus 24" 1920*1080 x 2 
KeyboardPowerCaseMouse
WASD XFX 650 watt Cooler Master HAF 932 Logitech G500 
  hide details  
Reply
My System
(13 items)
 
  
CPUMotherboardGraphicsRAM
Intel i7 950 Asus P6X58D-E Gigabyte GTX 770  12 GB GSkill 
Hard DriveOptical DriveOSMonitor
Seagate 1TB, Samsung 2TB TSSTcorp Windows 7 home Premium x64 Asus 24" 1920*1080 x 2 
KeyboardPowerCaseMouse
WASD XFX 650 watt Cooler Master HAF 932 Logitech G500 
  hide details  
Reply
post #2 of 3

First, you should use spoiler tags to wrap your code so your post isn't so huge. Second, this seems a lot like a school assignment... I'm not sure I should be offering too much assistance.

post #3 of 3
Thread Starter 
This is not for homework, the original project was but I am now modifying it for my own purposes not school. I am on summer break. It is probably a simple fix because it works completely like its supposed too, except in the function. I just wanted to have it in a function now rather than being in the code like it is.
My System
(13 items)
 
  
CPUMotherboardGraphicsRAM
Intel i7 950 Asus P6X58D-E Gigabyte GTX 770  12 GB GSkill 
Hard DriveOptical DriveOSMonitor
Seagate 1TB, Samsung 2TB TSSTcorp Windows 7 home Premium x64 Asus 24" 1920*1080 x 2 
KeyboardPowerCaseMouse
WASD XFX 650 watt Cooler Master HAF 932 Logitech G500 
  hide details  
Reply
My System
(13 items)
 
  
CPUMotherboardGraphicsRAM
Intel i7 950 Asus P6X58D-E Gigabyte GTX 770  12 GB GSkill 
Hard DriveOptical DriveOSMonitor
Seagate 1TB, Samsung 2TB TSSTcorp Windows 7 home Premium x64 Asus 24" 1920*1080 x 2 
KeyboardPowerCaseMouse
WASD XFX 650 watt Cooler Master HAF 932 Logitech G500 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Pathfinding function problem