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
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: 14345
    
  22

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 8 API documentation
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: 3649
    
  17

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: 3649
    
  17

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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Finding the shortest path on a grid