• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Junilu Lacar
  • Martin Vashko
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Scott Selikoff
  • salvin francis
  • Piet Souris

Pathfinding Algorithm - Finding any possible Path

 
Ranch Hand
Posts: 51
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello friends,

Its me again back with another project.

The project is about Path finding and includes a two dimensional array with different fields which have different movement options.
Goals of the program is to show if it is possible to reach a certain field when we start with different two-dimensional arrays and starting positions.

I looked for a few possible ways on different websites and tried to adapt some ideas into my program, but I am quite lost and don't know where to continue or what I need to change.
Below is my code for the moment.

Is my code not working because there is no repetition of the pathFinding? Or are there some other mistakes I need to have a look at?
Output shows 0 ways but there are possible ways....



As always thank you very much for your help!
 
Sheriff
Posts: 6448
172
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recursion and backtracking is hard -- maybe too hard for the Beginning Java forum.

I can only suggested that you put System.out.println() statements into your code or run it through a debugger.
 
Marshal
Posts: 7316
497
Mac OS X VI Editor BSD Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Michael Grünau wrote:I looked for a few possible ways on different websites and tried to adapt some ideas into my program, but I am quite lost and don't know where to continue or what I need to change.


I don't have much time to help now, but could suggest one thing in advance. Delete all that code and start solving it yourself in small steps without any examples took from Internet. That is the main reason probably why you have no idea how to continue.

First, you have lots of duplication which makes your code very hard to understand - mainly for yourself.

Have you learned about object oriented design/approach already?
 
Michael Grünau
Ranch Hand
Posts: 51
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well thank you very much for the replies.
I will try to go through the code again and go line by line to check what is missing or what went wrong but to be honest not sure what was wrong about the approach.

For now, I would highly appreciate it when somebody has a moment to check if they find some mistakes I can note down for the second approach.
Thank you very much!
 
Rancher
Posts: 3623
34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How can the code be compiled and executed for testing and debugging?
 
Liutauras Vilda
Marshal
Posts: 7316
497
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you don't want to start in smaller steps, maybe you want to refactor it a bit. When you remove duplication you may spot the mistake(s).

For instance, you have method isValidCell(int x, int y) (meaning valid step to take), but you are using it only in 1 place, while there are another 12 places where you could/should be using it.

So why you are not doing so?
 
Liutauras Vilda
Marshal
Posts: 7316
497
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What the rules are for:

You have inconsistent blocks inside them, so wondering what's the story about that?
 
Ranch Hand
Posts: 85
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I tried to do this for a game I was making and then  gave up. No need to reinvent the wheel there are already algorithms out their that do this. .  But if you want to  code this yourself look up A-star pathfinding algorithm tutorials. They will be of massive help.
 
Liutauras Vilda
Marshal
Posts: 7316
497
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Jesse Matty wrote:I tried to do this for a game I was making and then  gave up. No need to reinvent the wheel there are already algorithms out their that do this.


I don't think that is about re-inventing the wheel. Such type of an assignment is quite common for the BSc Computer Science students, usually during year 1 or 2. Attempting to solve such problem can help in many ways, i.e. to practice implementing recursive algorithms.

As mentioned, OP is cramming everything to a singular source file with quite a bit of code duplication, which makes this problem to look more difficult than it actually is.
 
Bartender
Posts: 3668
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Michael,

just had a look at your code. I think your method is valid, but there are some bugs in it. For instance, see the code in your opening post, in the snippet that starts at line 42, we see:

Do you spot the mistake here? When I tested your code with N = 2 and int[][] = {{0, 4}, {0, 0}} I got the expected ArrayIndexOutOfBounds.

I corrected this mistake and tested your code with these data:

and I got the correct answer of 11.

I see similar mistakes in the other parts of your code (for instance line 59 and 60).

Well, if you got your code up and running, let us know. And then try what Liutauras advised: try to refactor your code so that it uses far less code repetition.
 
Piet Souris
Bartender
Posts: 3668
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For instance, you can make 'count' a static variable, that you can initialize to 0 just before you invoke the 'findPaths' method. It has the advantage that you can drop the 'count' argumentt in that method, and that you can simplify the
to just

The findPaths method can the be void. There are some minor other adjustments to do, but your IDE will show you these.
 
Piet Souris
Bartender
Posts: 3668
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Did you manage to get the code up and running?
 
All of the following truths are shameless lies. But what about this tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!