aspose file tools*
The moose likes Java in General and the fly likes Finding the shortest path on a grid Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Finding the shortest path on a grid" Watch "Finding the shortest path on a grid" New topic
Author

Finding the shortest path on a grid

Kasun Athukorala
Greenhorn

Joined: Jun 14, 2011
Posts: 18
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???


[Thumbnail for shortest path.JPG]

Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14114
    
  16

Have you thought about the problem yourself? What do you think yourself would be a good way to approach this?


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
James Sabre
Ranch Hand

Joined: Sep 07, 2004
Posts: 781

Google for "shortest path algorithm"


Retired horse trader.
 Note: double-underline links may be advertisements automatically added by this site and are probably not endorsed by me.
Kasun Athukorala
Greenhorn

Joined: Jun 14, 2011
Posts: 18


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

Joined: Sep 07, 2004
Posts: 781

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

Joined: Jun 14, 2011
Posts: 18
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

Joined: Jun 08, 2011
Posts: 37
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

Joined: Sep 07, 2004
Posts: 781

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
Bartender

Joined: Sep 20, 2010
Posts: 3615
    
  14

You can also try googling for A*-search (or A-star search).
James Sabre
Ranch Hand

Joined: Sep 07, 2004
Posts: 781

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
Bartender

Joined: Sep 20, 2010
Posts: 3615
    
  14

Nevermind then
James Sabre
Ranch Hand

Joined: Sep 07, 2004
Posts: 781

Stephan van Hulst wrote:Nevermind then

Kasun Athukorala
Greenhorn

Joined: Jun 14, 2011
Posts: 18
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.
 
subject: Finding the shortest path on a grid