To find a way between 2 Points in a map with known obstacles following algorithm is a possibility :

Strart:
XXXXXXXXXXXXXX
X                X                 X
X       S       X                 X
X                X                 X
X                X                 X
X                               D  X
XXXXXXXXXXXXXX
Fig. 1

S = Source (Startpoint)
D = Destination
X = Obstacles
 

Step 1:
The program scans the map.
If the startpoint is on the left ,right ,down or upper side , the scanpoint will change the map entrie to 1.
  in C Source :
  if ( o[ x ][ y - 1] == 'S' ) o[x][y] = '1';
  if ( o[ x ][ y + 1] == 'S' ) o[x][y] = '1';
  if ( o[ x  - 1][ y ] == 'S' ) o[x][y] = '1';
  if ( o[ x  + 1][ y ] == 'S' ) o[x][y] = '1';
the howle map is scaned whith 1 Step (Fig. 2)

XXXXXXXXXXXXXX
X       1       X                 X
X     1S1     X                 X
X       1       X                 X
X                X                 X
X                               D  X
XXXXXXXXXXXXXX
Fig. 2
 
 

Step 2:
Now the map will be rescaned again by searching for number "1" and insert at scanpoint "2" (Fig. 3)
XXXXXXXXXXXXXX
X     212     X                 X
X   21S12   X                 X
X     212     X                 X
X       2       X                 X
X                               D  X
XXXXXXXXXXXXXX
Fig. 3
 

Step 3-5:
inserting a value at obstacle ("X") is disabled. (Fig.4)
XXXXXXXXXXXXXX
X54321234X                 X
X4321S123X                 X
X54321234X                 X
X  5432345X                 X
X    54345                 D  X
XXXXXXXXXXXXXX
Fig. 4
 

Step  6-C hex:
mapscan pocedure has arrived at destination in Step C.(Fig 5)
XXXXXXXXXXXXXX
X54321234XC              X
X4321S123XBC           X
X54321234XABC        X
X65432345X9ABC      X
X  65434567 8 9ABD   X
XXXXXXXXXXXXXX
Fig. 5
The mapscan pocedure acts like water.

go Back to Source:
Starting at destinationpoint , following next lower value around , you will come to source ! (Fig. 6)
XXXXXXXXXXXXXX
X54321234XC              X
X4321S+23XBC           X
X54321++4XABC        X
X654323++X9ABC      X
X  654345+++++++D   X
XXXXXXXXXXXXXX
Fig. 6
By following the lower value , the way must be saved in a dataarray:
Entrys of dataarray : (Dest.) go go go go go go go right go left go right go left go right go left go (Source)
For driving from Source to Destination the way must be turn around.
New entrys :                              (Source) : go left go right go left go right go left go right go go go go go go go (Dest.)
Left and right will be changed: (Source) : go right go left go right go left go right go left go go go go go go go (Dest.)
Send this values to the robot.

Joerg Wolf 1999
 
  >