A* shortest path algorithm optimization

Question

I had this programming exercise of mine where I had to find the shortest path to an exit in an NxM -grid maze in under a second (both N and M would be anywhere between 3 and 1000). The program would be tested with 10 different inputs (mazes), all of which includes a very different amount of exits.

The input goes as follows:

7 10
##########
#.....#... <- exit
#.#.###.##
#..X..#..#
#.#.#.#.##
#......... <- exit
###.######
   ^exit

Where the first number is height and the second width. The rest is the maze itself, and X marks the (starting) spot.

Well, I solved the problem using the A* algorithm and at the same time keeping track of the nearest exit (simple Manhattan distance). Now what's bugging me is that my fellow programmers have come to a lot faster and more memory-friendly solutions than I. My request is that you guys point out anything that comes to your mind, were it to be a completely different algorithm or just a stupid memory leak.

Here's the code:

#include <iostream>
#include <vector>
#include <algorithm>

typedef std::vector<int> monovector;
typedef std::vector< std::vector<int> > bivector;

int _abs(int num);
int* get_nearest_goal(int y, int x, bivector &goals_t);
int goals = 0;

void appendClosedList(int y, int x, bivector &openList, bivector &closedList) {
    for(size_t i = 0; i < openList.size(); i++)
        if(openList[i][0] == y && openList[i][1] == x) closedList.push_back(openList[i]);
}

void dropOpenList(int y, int x, bivector &openList) {
    for(size_t i = 0; i < openList.size(); i++)
        if(openList[i][0] == y && openList[i][1] == x) openList.erase(openList.begin()+i);
}

int* get_coords(bivector &openList)
{
    int* coords = new int[2];
    int min_element = 1000000;
    for(size_t i = 0; i < openList.size(); i++) {
        if(openList[i][2] < min_element) {
            min_element = openList[i][2];
            coords[0] = openList[i][0];
            coords[1] = openList[i][1];
        }
    }
    return coords;
}

struct laby_t {
    int h, w, s_y, s_x;
    char **m_layout;
    int ***m_attr, ***_m_attr;
    int ***m_parent, ***_m_parent;

    laby_t() {
        std::cin >> h >> w;

        m_layout  = new char *[h+1];
        for (int i = 0; i < h+1; i++)
            m_layout[i]  = new char[w+1];

        m_parent = new int **[h];
        m_attr  = new int **[h];
        for (int i = 0; i < h; i++) {
            m_attr[i]  = new int *[w];
            m_parent[i] = new int *[w];

            std::cin >> m_layout[i];

            for (int j = 0; j < w; j++) {
                m_attr[i][j] = new int[4];
                m_parent[i][j] = new int[2];

                m_attr[i][j][0] = 0;
                m_attr[i][j][1] = 0;
                m_parent[i][j][0] = 0;
                m_parent[i][j][1] = 0;
                if(m_layout[i][j] == '#') m_attr[i][j][0] = 2;
                if(m_layout[i][j] == 'X') { s_y = i; s_x = j; }
            }
        }

    }

    int get_visited (int y, int x) { return this->m_attr[y][x][0]; }
    int get_depth(int y, int x)    {
        if(this->m_attr[y][x][1]) return this->m_attr[y][x][1];
        else return 0;
    }
    int get_estimate(int y, int x) { return this->m_attr[y][x][2]; }
    int get_priority(int y, int x) { return this->m_attr[y][x][3]; }

    void set_visited(int py, int px, int y, int x, int f_y, int f_x, int depth)  {
        this->m_attr[y][x][0] = 1; 
        this->m_attr[y][x][1] = depth;
        this->m_attr[y][x][2] = _abs(f_y - y) + _abs(f_x - x);
        this->m_attr[y][x][3] = this->m_attr[y][x][1] + this->m_attr[y][x][2];
        this->m_parent[y][x][0] = py;
        this->m_parent[y][x][1] = px;
    }

    void reset()
    {
        delete this->m_attr;
        delete this->m_parent;
        delete this->m_layout;
    }
};

void dropGoals(int f_y, int f_x, bivector &goals_t, laby_t &laby)
{
    for(size_t i = 0; i < goals_t.size(); i++)
        if(goals_t[i][0] == f_y && goals_t[i][1] == f_x) {
            goals_t.erase(goals_t.begin()+i);
            laby.m_layout[goals_t[i][0]][goals_t[i][i]] = '#';
            laby.m_attr[goals_t[i][0]][goals_t[i][i]][0] = 2;
        }
}

int wander(int y, int x, int f_y, int f_x, laby_t &laby, bivector goals_t)
{
    int depth = 1;
    laby.set_visited(y, x, y, x, f_y, f_x, depth);
    monovector r; r.push_back(y); r.push_back(x); r.push_back(laby.get_priority(y, x)); r.push_back(0);
    bivector openList, closedList;
    openList.push_back(r);
    r.clear();

    int dir[4][2] = {
                        { 1, 0},
                        {-1, 0},
                        { 0, 1},
                        { 0,-1}
                    };

    while(!(y == f_y && x == f_x))
    {
        for(int i = 0; i < 4; i++)
        {
            int _y = y + dir[i][0];
            int _x = x + dir[i][1];
            if(y > 0 && y < laby.h-1 && x > 0 && x < laby.w-1) {
                if(
                    (
                        (laby.get_visited(_y, _x) == 0) ||
                        (laby.get_visited(_y, _x) == 1 && laby.get_depth(y, x)+1 < laby.get_depth(_y, _x))
                    )
                  )
                {
                    laby.set_visited(y, x, _y, _x, f_y, f_x, laby.get_depth(y, x)+1);
                    monovector r; r.push_back(_y); r.push_back(_x); r.push_back(laby.get_priority(_y, _x));
                    openList.push_back(r);
                    r.clear();

                    if((_y == 0 || _y == laby.h-1 || _x == 0 || _x == laby.w-1) && (_y != f_y || _x != f_x)) {
                        int d = laby.get_depth(_y, _x);
                        openList.clear();
                        closedList.clear();
                        laby.reset();
                        return d;
                    }
                }
            }
            else { return laby.get_depth(y, x); };
        }

        appendClosedList(y, x, openList, closedList);
        dropOpenList(y, x, openList);

        int *yx = get_coords(openList);
        y = yx[0];
        x = yx[1];

        yx = get_nearest_goal(y, x, goals_t);
        f_y = yx[0];
        f_x = yx[1];

        delete yx;

    }
    int d = laby.get_depth(y, x);
    openList.clear();
    closedList.clear();
    laby.reset();
    return d;
}

int _abs(int num)
{
    if(num <= 0) return -num;
    else return num;
}

int* get_nearest_goal(int y, int x, bivector &goals_t)
{
    int min_dist = 1000000;
    int *f_coords = new int[2];
    for(size_t i = 1; i < goals_t.size(); i++) {
        if(_abs(y - goals_t[i][0]) + _abs(x - goals_t[i][1]) < min_dist) {
            min_dist = _abs(y - goals_t[i][0]) + _abs(x - goals_t[i][1]);
            f_coords[0] = goals_t[i][0];
            f_coords[1] = goals_t[i][1];
        }
    }

    return f_coords;
}

int* get_goals(int &goals, bivector &goals_t, laby_t &laby)
{
    for(int i = 1; i < laby.h - 1; i++) {
        if(laby.m_layout[i][0] == '.') {
            goals++;
            monovector t; t.push_back(i); t.push_back(0); goals_t.push_back(t);
            t.clear();
        }
        if(laby.m_layout[i][laby.w - 1] == '.') {
            goals++;
            monovector t; t.push_back(i); t.push_back(laby.w - 1); goals_t.push_back(t);
            t.clear();
        }
    }

    for(int i = 1; i < laby.w - 1; i++) {
        if(laby.m_layout[0][i] == '.') {
            goals++;
            monovector t; t.push_back(0); t.push_back(i); goals_t.push_back(t);
            t.clear();
        }
        if(laby.m_layout[laby.h - 1][i] == '.') {
            goals++;
            monovector t; t.push_back(laby.h - 1); t.push_back(i); goals_t.push_back(t);
            t.clear();
        }
    }

    return get_nearest_goal(laby.s_y, laby.s_x, goals_t);
}

int main()
{
    int *f_coords = new int[2];
    bivector goals_t;
    laby_t laby;

    f_coords = get_goals(goals, goals_t, laby);

    int min_path = wander(laby.s_y, laby.s_x, f_coords[0], f_coords[1], laby, goals_t);

    delete f_coords;

    std::cout << min_path << std::endl;
    //system("pause");
    return 0;
}

I was too lazy to add comments, so tell me if they are needed.

Answer 1

Reviewing all of this is a fairly big task, so let me start with a few ideas and come back later if I have the time.

Algorithmic considerations

As Sylvain pointed out in his answer to your question on Stackoverflow, your heuristic is too simple and will underestimate the distance repeatedly and by substantial amounts. This will affect the running time of your algorithm to the point where something like a Dijkstra search may easily be better. For educational purposes, I think it would be best if you took Sylvain's other suggestion of implementing a reverse search from the exits to your startin location.

Style

• Don't be a three star programmer. In this case in particular, hiding the additional information contained in your nodes in m[][][0] to m[][][4] makes it extremely difficult to read for anyone who hasn't spent hours writing it (i.e. you). Use a structured way of implementing your nodes like a class or a struct.
• Use standard names. 'monovector' and 'bivector' make sense only in your brain. Your 'monovector' is a 2D coordinate vector (it is NOT a good idea to make it an std::vector, more on that later!) - why not call it vector2d or coordinate? Your 'bivector' is a list of coordinates.

Choice of data structures

Everything is a vector in your implementation. That's far from ideal

• A 2D coordinate vector always has exactly two elements. A C++ std::vector is designed to have a variable and arbitrary number of elements and is therefore not a good fit (I do agree that the name is confusing for someone coming to coding from a mathematical point of view).
• In the A* algorithm, you repeatedly need to take the cheapest (in terms of estimated remaining distance) element from the open list. It may be sensible to choose a data structure which is kept sorted automatically.

Implementation issues

• If you were consistently working with a proper datatype for your nodes, you could easily get rid of the inefficient implementations of appendClosedList and dropOpenList. Both of those currently scan the entire lists, and all that while your program knows which node they have to remove/add - it's working on them at the very moment you call those functions!

Memory management

As Loki Astari mentioned in the comments, most of these issues will automagically disappear with correct use of containers and other relevant techniques. It may still be worthwhile to know how to do things correctly 'your way', even if it isn't advisable to actually write code like that.

Now, it is not really a case of finding "just a stupid memory leak" in your code, practically everything in there leaks or does error-prone things. Just consider, as an example,

    int *yx = get_coords(openList);
    y = yx[0];
    x = yx[1];

    yx = get_nearest_goal(y, x, goals_t);
    f_y = yx[0];
    f_x = yx[1];

    delete yx;

First of all, allocation is handled by the callee and deallocation by the caller, which is (imho) intransparent and error-prone. Then, you're reusing yx, the memory allocated in get_coords always leaks. Additionally, you allocate memory in get_nearest_goal with new[], then deallocate it with delete. Furthermore, your reset() function is completely broken.

Answer 2

I remember two optimization from my own implementation of the A* algorithm.

• Use only one list and give an Closed/Opened flag to your item. Then instead of removing/adding items from one list to another, simply toggle the flag.

• Use a map / multimap instead of vector. Sort them with a custom comparator. Then instead of doing linear searches in vectors, the map will quickly find what you need it its sorted tree.