Now that my debugger works, I need help!

clsCorwin

I've got a function that is supposed to recursively find a path from beginning (0,0) to end (9,9). He does it, just very slow right now. Within my findPath function, I'm passing it a 2d boolean array, which is just there so it knows which tiles its been on, and not to go on them again.

Right now, its making changes to the original table I instantiated, rather than the one I passed in my functions, so instead of getting a different table for each recursive movement, I've got one table for all of them, and hes lucky that hes funding his way across right now.

According to my debugger, once my table gets passed to the function, it goes from being bool[10][10] to bool[10]*, causing everything to crap out.

Anyone got any ideas, or do ya wanna see the code?

Bama

Arrays are pointers, the index operator just shifts the address by a given amount to get to sub-indexes. That is why the first element of an array is index zero - you aren't shifting anywhere.

I have to admit that I can't remember off the top of my head what C++ will and will not pass by copy. You may have to manually copy the array before passing it to the function. Just be sure to de-allocate the memory once the function is done with it!

edit: quick thought - since this array is fixed size, you could just declare an array at the beginning of the function and do the copying there. That should be easier, especially if you aren't comfortable with memory management.

Smasher

c++ passes arrays by reference instead of value. Passing by value copies the value to a new variable while reference just passes the address, which means the table you're passing recursively is the original table. Hence, it gets modified.

Out of curiosity, what's your algorithm? It sounds like your program is doing a depth-first search, which means it's not guaranteed to return the shortest path. Is that a concern?

jclast

It's more work to set up, but declare your array as a bool bArray** instead of bool bArray[10][10]. This will let you pass bArray without worrying about pass by copy or pass by reference; you'll just always access the data through the pointer.

Something like this:

int main() {
    bool bArray**;

    bArray = new bool *[10];
    for (int i = 0; i < 10; i++) {
        bArray[i] = new bool[10];
    }

    // your code and whatnot here

    for (int i = 0; i < 10; i++) {
        delete[] bArray[i];
    }
    delete[] bArray;

    return (0);
}

Now you can pass bArray to your function and be able to access it as bArray[0][0].

DISCLAIMER: This code has not been compiled, but gcc should take it. VC++ 6.0 probably won't though as it doesn't do variable scope correctly. To fix that just declare i at the same time as bArray and it should work. I don't know about VC++ .net; never used it.

Bama

But why do all of that plus the copy if he can just declare the array at the beginning of the function and copy the values over?

ecco the dolphin

jclast wrote: »

It's more work to set up, but declare your array as a bool bArray** instead of bool bArray[10][10]. This will let you pass bArray without worrying about pass by copy or pass by reference; you'll just always access the data through the pointer.

Something like this:

int main() {
    bool bArray**;

    bArray = new bool *[10];
    for (int i = 0; i < 10; i++) {
        bArray[i] = new bool[10];
    }

    // your code and whatnot here

    for (int i = 0; i < 10; i++) {
        delete[] bArray[i];
    }
    delete[] bArray;

    return (0);
}

Now you can pass bArray to your function and be able to access it as bArray[0][0].

DISCLAIMER: This code has not been compiled, but gcc should take it. VC++ 6.0 probably won't though as it doesn't do variable scope correctly. To fix that just declare i at the same time as bArray and it should work. I don't know about VC++ .net; never used it.

Also, this code creates 10 individual arrays that do not necessarily follow each other in memory. Declaring bool someArray[10][10] on the other hand, guarantees that all elements follow each other in memory, and allows a single memcpy() from the original if needed.

jclast

Bama wrote: »

But why do all of that plus the copy if he can just declare the array at the beginning of the function and copy the values over?

To be honest, I do it that way because I think it's easier. When I'm passing a pointer, I never have to remember if I passed by value or reference or any of that. I know that when I pass a pointer, I can access the same data in the called function that I accessed in the calling function.

Besides, it sounds like OP is in a C++ programming class, and good memory management is going to be handy to know when these arrays are no longer [10][10] but [x][y].

Bama

Oh I agree, and it's why I think people should learn in languages like C/C++ instead of ones like Java. However, it doesn't sound like the purpose of this assignment is to teach memory management.

clsCorwin

Smasher wrote: »

Out of curiosity, what's your algorithm? It sounds like your program is doing a depth-first search, which means it's not guaranteed to return the shortest path. Is that a concern?

Right now my algorithm finds ALL paths, and I have a functions to tell me what the best path is.