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.

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

posted

0

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!!!

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.

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.

You can also try googling for A*-search (or A-star search).

The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.

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.