• Post Reply Bookmark Topic Watch Topic
  • New Topic

Finding the shortest path on a grid  RSS feed

 
Kasun Athukorala
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can anyone suggest me a suitable code to find a shortest path between 2 objects??

if i describe the senario,

1.there is a GUI which is displaying a grid
2.and there are few obstacles at some of the junctions, which are generated randomly.
3. Three are another 2 special objects colored in red and blue at two other junctions which are also generated randomly and i need to find shortest path between them.

image of my GUI is attach here with........

can anyone gv me a suitable algo rythem???
shortest-path.JPG
[Thumbnail for shortest-path.JPG]
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16028
87
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Have you thought about the problem yourself? What do you think yourself would be a good way to approach this?
 
James Sabre
Ranch Hand
Posts: 781
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Google for "shortest path algorithm"
 
Kasun Athukorala
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


Well since i know where the obstacles are i thought of using a 2 dimensional matrix where there will be '1' for obstacles and '0' for free junctions. But still i couldn't think of a suitable way to connect the zeros between the two objects that i want.

If i can do that then i can count the number of zeros and find the path which is having the minimum zeroes.

I am out of ideas. If you can help, it would be really great!!!
 
James Sabre
Ranch Hand
Posts: 781
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kasun Athukorala wrote:
I am out of ideas. If you can help, it would be really great!!!


So you don't class my idea of using a search engine as helpful !
 
Kasun Athukorala
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
James Sabre wrote:
Kasun Athukorala wrote:
I am out of ideas. If you can help, it would be really great!!!


So you don't class my idea of using a search engine as helpful !



i googled it long before i post this question. But i couldn't find a suitable one for my application.
That is why i post this man.
 
Daniel Marti
Ranch Hand
Posts: 37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I will not give you the answer, but i will give you the topics to search for:

Recursion
2-dimensional array or (even better) graph

That is all you need.
You should have a stop condition to know when to stop doing recursive calls. If you want an improved performance, you should check all paths for the shortest path (that would mean 2 stop conditions: 1 for reaching the goal/meeting a dead end and another for having checked all paths possible).

Hope that helped.

@James Sabre: I think it would be a lot better to find an answer by yourself (himself in this case) and then give the dijkstra algorithm as a possible solution.
 
James Sabre
Ranch Hand
Posts: 781
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kasun Athukorala wrote:
James Sabre wrote:
Kasun Athukorala wrote:
I am out of ideas. If you can help, it would be really great!!!


So you don't class my idea of using a search engine as helpful !



i googled it long before i post this question. But i couldn't find a suitable one for my application.
That is why i post this man.


Come off it! Google quickly finds http://en.wikipedia.org/wiki/Shortest_path_problem which gives a short list of appropriate algorithms. I have used the Djikstra and Floyd algorithms for finding shortest paths in a graph/network and your grid is a network/grid of nodes that are the intersection points with links from all nodes to all neighbouring nodes unless there is a black spot on the node. The weighting for each link is the same so can be made = 1. Djikstra is probably the best algorithm for you to use but that is your decision.
 
Stephan van Hulst
Saloon Keeper
Posts: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can also try googling for A*-search (or A-star search).
 
James Sabre
Ranch Hand
Posts: 781
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:You can also try googling for A*-search (or A-star search).


That's third on the list in the Wikipedia reference.
 
Stephan van Hulst
Saloon Keeper
Posts: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nevermind then
 
James Sabre
Ranch Hand
Posts: 781
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:Nevermind then

 
Kasun Athukorala
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Daniel Marti wrote:I will not give you the answer, but i will give you the topics to search for:

Recursion
2-dimensional array or (even better) graph

That is all you need.
You should have a stop condition to know when to stop doing recursive calls. If you want an improved performance, you should check all paths for the shortest path (that would mean 2 stop conditions: 1 for reaching the goal/meeting a dead end and another for having checked all paths possible).

Hope that helped.

@James Sabre: I think it would be a lot better to find an answer by yourself (himself in this case) and then give the dijkstra algorithm as a possible solution.


I knew i could use recursion. But the problem is i cant use it. I created this to model a robot behavior. So i have to put this algorithm into a 18F452 micro-controller. But micro-controller wont be able to handle more than two or three recursion as i was told. The real arena is about 13x6 junctions. So i also don't think micro-controller will handle it.

I'll look in to others solutions and tell you people what i found. I will need at least one day to read and think about those articles you people have mentioned.

Thanks for for your support guys.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!