Quickest path through a Maze (Dungeon) Dijstkra

Question

UPDATE:

the output of some random paths is caused here I believe:

if(openlist[x][y]!=1){

            if(min>copy[x][y]){
            min=copy[x][y];
            holdx = x;    
            holdy = y;
            }
        }

I believe that at certain points, it will make it test every path (and output it) when my shortest path is bigger then the other path. How would I go about fixing this?

Answer 1

All I can see from looking at your code is that you're not mainlining your state properly. You have a method called moveToPosition() but it's called for every node - and you end up adding every x/y combination to the paths List.

To be honest a lot of this doesn't make sense, and I think you've got more than one problem. There are also a lot of poor programming techniques you'll lose marks for:

• not being OO - you're using static everywhere.
• no use of proper scope - everything is public
• no comments
• names of variables that don't explain what they contain.
• use of the same variable for different uses (holdx)

If I were you I would attempt to complete your profs example. It will teach you some decent transferable skills in OO design. I'd ignore the whole reading and writing from a file. Just mock up a quick Node[3][3] maze in a method and pass that into the initial method. You'll also need to track whether you've already visited a node, but that should be easy.

Sorry I can't help more - my solution would be very similar to your profs which you'd find equally difficult to understand, and I'm against doing homework for someone - one cant learn that way, and programming is very enjoyable once you get past the initial difficulties.

All the best

---

As a solution to your StackOverflowError when setting your size > 100, you'll need to increase the size of your stack.

To increase the stack size, use the Java VM argument -Xss and set it to something bigger than the default.

-Xss64M should do the trick.

As an explanation, as your increase the size param, you're also increasing the amount of recursion you're doing which means putting more and more method calls onto your stack (as seen by the very long stack printed when the error is thrown). To continue using your app with this much recursion requires you to increase the size of your stack.

See this SO question for details.

Answer 2

When you get a "real" StackOverflow error, it means that your stack has too many nested frames for the JVM to feel like it is making progress.

To solve the issue, you can tune your JVM, but that's a losing game. There will always be something that will require more tuning, and the tuning will de-tune the JVM for smaller mazes.

To really solve the problem, you need to keep a collection of states, effectively pushing the information that would have been stored on the stack into the heap. Unlike the stack, the heap doesn't have stack frames, and so you can't nest them too deeply. You still will run the risk of an out-of-memory exception (if you fill your heap) but that will likely happen much later (and with much larger mazes).