Finding the shortest path on a grid

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

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

Google for "shortest path algorithm"

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

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 !

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.

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:

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.

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

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.

Nevermind then

Stephan van Hulst wrote:Nevermind then

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.