Most efficient search?

[Mats]

If I have a set up like this: (this will copy + paste compile and run just fine)

#include <iostream>
#include <ctime>
#include <cstdlib>
int main()
{
    char grid[25][25];
    int x = 0, y = 0; //Purely used to iterate loops.
    int xrandom[80], yrandom[80]; //Random obsticle positions.
    int destination[1][2], startposition[1][2];
    for(x = 0; x < 25;++x) //Make the grid
    {
        for(y = 0; y < 25; ++y)
        {
            grid[x][y] = '-';
        }
    }
    srand(time(NULL));
    for(x = 0;x < 80;++x) //Put in some random obsticles.
    {
            xrandom[x] = rand() % 25;
            yrandom[x] = rand() % 25;
            grid[xrandom[x]][yrandom[x]] = 'x';
    }
    destination[0][0] = rand() % 25; //Make a random destination.
    destination[0][1] = rand() % 25;
    startposition[0][0] = rand() % 25; //And a random start position.
    startposition[0][1] = rand() % 25;
    grid[startposition[0][0]][startposition[0][1]] = 'S';
    grid[destination[0][0]][destination[0][1]] = 'D';
    for(x = 0; x < 25;++x) //Display grid.
    {
        for(y = 0; y < 25; ++y)
        {
            std::cout << grid[x][y] << " ";
        }
        std::cout << "\n";
    }
    return 0;
}

What is the best algorithm to find a short path from start position to destination? Speed of search is most important. i.e. It doesn't need to find the absolute minimum path, as long as it find a reasonable path quickly.

I've been trying first of all to set up a kind of wave front. First calculating where the destination is in relation to S and then doing this:

1st iteration: -> Destination is somewhere this way ->

  n1
S n2         
  n3

2nd
     h11
  n1 n12 
S n2 n22
  n3 n31
     n32

And deleting paths which hit obstacles. This seems to be a very expensive search though. :S

[tntxtnt]

perhaps A* algorithm: http://en.wikipedia.org/wiki/A*_search_algorithm#Example

pseudocode : http://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode

[Mats]

Efficiency is very important though. A* does a lot of checks to find the shortest solution. However, I am willing to sacrifice definitely finding the fastest route to improve efficiency.

[tntxtnt]

then perhaps union-find
http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionUF.java.html

you have to connect open cells together, and modify the find() function so that find(start) pushs the route to queue A, and find(end) pushs the route to stack B, and if they are connected then join the route from queue B and stack A together.

[Script Coder]

I would like to suggest a type of Dijkstra's algorithm.
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Also, AFAIK A* is just Dijkstra with heuristics.
Also, you will need to remember that there may not be a path between your start and destination.

[Mats]

This was just a quick example code. The real situation will always have a possible path (usually several). Never seen union-find before. Will have to read up on that!