2

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?

James Doe
  • 77
  • 7
  • "Minimizes danger". Does that mean that a path through one level-9 monster is preferable to ten level-1s? If the level of monsters are equals (nine level-1s vs. one level-9), is there a preferred path? – heptadecagram May 12 '14 at 20:23
  • Probably best if you post your stacktrace from the StackOverflowError – Will May 12 '14 at 20:24
  • @heptadecagram the point of the assignment is to go through the grid with the least dangerous path. meaning if a path contains five lvl 1 monsters and one lvl 9, it would be more optimal than say a path that contains five lvl 2 monsters and one lvl 6 monster (first path has total danger level of 14 and the second has a total of 16) – James Doe May 12 '14 at 20:29
  • @Will I get for anything larger than size 62: Exception in thread "main" java.lang.StackOverflowError at java.lang.AbstractStringBuilder.(AbstractStringBuilder.java:63) at java.lang.StringBuilder.(StringBuilder.java:85) – James Doe May 12 '14 at 20:31
  • @JamesDoe - FYI -The really important part of your error was the lines that were part of your code as opposed to core JDK stuff. Not to worry ran a quick test in my IDE to find your error. – Will May 12 '14 at 20:46
  • Have posted the SO error I got for others so they may benefit from this. – Will May 12 '14 at 20:52
  • @JamesDoe You would make it easier for the community to help if you commented you code. Trying to work out what a random variable is supposed to hold, or some piece of logic is doing is difficult for someone not fully aware of the subject matter. I haven't done path finding algorithms since I was in Uni! :) – Will May 13 '14 at 06:18
  • @Will yeah i know and I usually do comment as I go. I was just in a rush with this one – James Doe May 13 '14 at 16:39
  • @Will My professor just gave us a shell of the assignment. He used a priority que, something that wasn't even in the same direction as me. can you do anything with that? – James Doe May 13 '14 at 17:19
  • @JamesDoe well yes I could just do it - this is nice OO design with comments, but you should have a stab at it first and I can help with specifics. I would start by first reading the javadoc for PriorityQueue so you understand how it works and completing the getConnectedNodes() method. Let me know how you get on. You'll also want to create the 2d array of nodes to pass to the mySearchMethod() - you've already done this in a simpler form so shouldn't be too hard. – Will May 13 '14 at 17:54
  • @will yeah I just hate the fact that I got to ditch my entire project and start over when I felt that I was so close(It's due at midnight tonight etc time). Anyway you can help me on the coding if I take care of the main? I have to read and write to a file which I can do fairly easily. – James Doe May 13 '14 at 18:04
  • @JamesDoe Such is learning to program - it's worth it in the end. You should find this way a lot easier as you don't have to deal with lots of 2d arrays which is hard work. I can help with specific questions but I'm in the UK so it's evening now. – Will May 13 '14 at 18:36
  • @will yeah i understand, I will just try and fix what i have in my code. I'm running out of time and have other projects to do. Wish i got his shell earlier. Thanks for your help anyway though. – James Doe May 13 '14 at 18:39
  • @will also if you somehow figure out what is causing it to print out another path once it finds a better one, please let me know because I can't figure out how to fix it for the life of me. – James Doe May 13 '14 at 18:48

2 Answers2

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.

Community
  • 1
  • 1
Will
  • 6,561
  • 3
  • 30
  • 41
  • This still only fixes one of my problems and not the major problem I am having. Appreciate the help, I'll edit my code shortly to adjust for your fix. – James Doe May 12 '14 at 20:52
  • Yeah, might look later, but it's late now, and I can fix SO errors easily. :) – Will May 12 '14 at 20:53
  • Appreciate you taking a look – James Doe May 12 '14 at 20:54
  • no I understand. I understand my professors example, just didn't feel like implementing all the methods; mainly because I am on a time crunch and have other assignments to do (that's what I get for putting everything off to the last minute). The coding I did was poor and I understand that, but it was a mixture of different elements that I grabbed from different powerpoints and examples and modified them. – James Doe May 14 '14 at 00:13
  • So yeah it's poor even for my standards. I was able to get it that close without too much effort and the difficulties for me where trying to understand it as well. Unfortunately if I had more time i would of attempted this in a much cleaner way; but I didn't and that's what I get. I appreciate your help and understand your unwillingness to do it for me. Thank you for helping all you did though. – James Doe May 14 '14 at 00:14
0

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).

Edwin Buck
  • 69,361
  • 7
  • 100
  • 138