//	Реализация алгоритма навигации путника "Разделяй и влавствуй"
//	Анисимов С.Ю. 1996 г.

/*
 ┌─────────────────────────────────╖
 │ Алгоритм разделяй и влавствуй ? ║
 └═════════════════════════════════╝

Это алгоритм прислан мне sillywiz@wardrobe.demon.co.uk.

Возьмите начальную позицию и конечную. Нарисуйте между ними прямую
линию. Возьмите точку посередине линии. Если она попала на
препятствие перемещайте ее каким-нибудь образом ( по спирали,
например ) до тех пор пока она будет не на препятствии. Установите
эту точку как конечную и продолжайте до тех пор пока не достигните
начальной позиции, или одной двух секции карты от начальной.

Этот алгоритм не будет работать на пересеченной местности, но от
ухода от деревьев/болот ( мелких препятствий ) возможно он подойдет.
У этого алгоритма есть еще преймущество в том, что вы игнорируете
дальние препятствия, которые могут изменится до того как путник до
них дойдет.
*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

typedef unsigned int word;
typedef unsigned char byte;

#define X_MAP 60
#define Y_MAP 50

char map[Y_MAP][X_MAP]={
"                                                           ",
"            oooo                                           ",
"             ooo              ooooooo ooooo                ",
"             ooo                          o                ",
"              ooo                         o                ",
"             ooo              ooooooooooooo                ",
"   A         ooo                                           ",
"                                                           ",
"                                                           ",
"                                                           ",
"                    o ooooooooooo   oo ooooo      o        ",
"                    oooooooooooooo   oooo                  ",
"                   ooooooooooooooo     oo                  ",
"                  ooooooooooooooooo    o                   ",
"                  ooooooooooooooooo                        ",
"                 oooooooooooooooooo                        ",
"                oooooooooooooooooooo                       ",
"               oooooooooooooooooo                          ",
"               oooooooooooooooo                            ",
"              oooooooooooooooo                             ",
"             ooo                                           ",
"            oooooo      o                   oo             ",
"             oooooo     oo                oooo   o         ",
"   o        oooo oo      o o              oooo o oooo      ",
"  oooo       oo  o       o oooo            o   ooooooo     ",
"  ooooo       o          o oooo                  ooo       ",
"  ooooo       o         oo oooo         o o       o        ",
"   oo oo      oo        ooooooooo      oooo oo    o        ",
"       oooooo  oo      oooooooooo       oooooooo  o        ",
"                o     ooooooooooo  oo   oo oooo   o        ",
"                    o ooooooooooo   oo ooooo      o        ",
"                    oooooooooooooo   oooo                  ",
"                   ooooooooooooooo     oo                  ",
"                  ooooooooooooooooo    o                   ",
"                  ooooooooooooooooo                        ",
"                 oooooooooooooooooo                        ",
"                oooooooooooooooooooo                       ",
"               ooooooooooooooooooooo                       ",
"               ooooooooooooooooooooo                       ",
"              ooooooooooooooooooooooo                      ",
"                oo  o ooooooooooo  ooo ooooo      o        ",
"                    oooooooooooooo   oooo                  ",
"                  oooooooooooooooo  oo oo                  ",
"                  oooooooooooooooooooo o           B       ",
"                  oooooooooooooooooooo                     ",
"                 oooooooooooooooooo                        ",
"                oooooooooooooooooooo                       ",
"               ooooooooooooooooooooo                       ",
"               ooooooooooooooooooooo                       ",
"               ooooooooooooooooooooo                       ",
};

struct
{
	int x;
	int y;
} DirMove[8]= // Массив направлений просмотра вокруг точки,
	      // по часовой стрелке
	{{1,-1},{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},};

int	FindPath // найдем весь путь
	( void ) ;
int	FindMoveUnit // найдем следующий шаг
	( int * xptr, int * yptr, int xe, int ye );
int	checkPoint // Проверка попала ли точка на препятствие
	( int x, int y );
int	findPoint // Поиск ближайшей точки к начальной
	( int * x, int * y, int delta );

#define MAX_STORE 7
struct
{
	int x;
	int y;
} Store[MAX_STORE]; // массив пройденных точек

void 	main
	( void )
{
int i, j;

textmode(C4350);
clrscr();
textattr(0x1E);
for ( i=0; i<Y_MAP; i++ ) // Вывод карты
{
	gotoxy(1,i+1);
	cprintf("%s",map[i]);
}
textattr(0x7);
if ( FindPath()==0 )
{
	textattr(0x7);
	gotoxy(60,3);
	cputs("Решения нет.");
	goto FIN;
}
textattr(0x7);
gotoxy(60,3);
cputs("Решения готово.");

FIN:
getch();
textmode(C80);

}

	// найдем весь путь

int	FindPath
	( void )
{
int i, j, xb, yb, xe, ye, max_i, xptr, yptr;
xb=yb=xe=ye=-1;
// поиск начальной и конечной точки
for ( j=0; j<Y_MAP; j++ )
for ( i=0; i<X_MAP; i++ )
{
	if ( map[j][i]=='A' ) { xb=i; yb=j; }
	if ( map[j][i]=='B' ) { xe=i; ye=j; }
}
if ( xb==-1 || xe==-1 ) return 0;
if ( abs(xb-xe)<2 && abs(yb-ye)<2 ) return 1;

i=0; max_i=X_MAP*Y_MAP; xptr=xb; yptr=yb; // начальные условия
for ( j=0; j<MAX_STORE; j++ )
	{ Store[j].x=xb; Store[j].y=yb; } // массив пройденных точек
while ( 1 )
{
	if ( i>=max_i ) return 0; // явно ничего не нашли
	if ( FindMoveUnit(&xptr,&yptr,xe,ye)==0 ) // найдем следующий шаг
		return 0;
	textattr(0x30);
	gotoxy(xptr+1,yptr+1);// поставим текущую точку
	cputs("+");
	// запомним текущую точку
	memmove(&Store[0],&Store[1],sizeof(Store)-4);
	Store[MAX_STORE-1].x=xptr; Store[MAX_STORE-1].y=yptr;
	if ( abs(xptr-xe)<2 && abs(yptr-ye)<2 ) return 1; // дошли таки
	i++;
}
}


	// найдем следующий шаг

int	FindMoveUnit
	( int * xptr, int * yptr, int xe, int ye )
{
int x, y, d, j=0, max_j;
int x_old, y_old;
max_j=(X_MAP+Y_MAP)*2;
x=xe; y=ye;
while ( 1 )
{
  x=((*xptr-x)>>1)+x; // точка посередине
  y=((*yptr-y)>>1)+y;
  d=1;
  if ( checkPoint(x,y)==1 )
  while ( 1 ) // ищем вокруг точки
  {
	if ( findPoint(&x,&y,d)==1 ) break;
	d++;
	if ( d>max_j ) return 0; // вышли за пределы карты
  }
  if ( x_old==x && y_old==y ) // ВОТ ЗДЕСЬ ПРОИСХОДИТ ЗАЦИКЛИВАНИЕ
  {
    	x=*xptr; y=*yptr;
  }
  if ( x==*xptr && y==*yptr) // ничего не нашли, тогда ...
  {
	if ( findPoint(&x,&y,1)==0 )
		return 0;
	else	break;
  }
  x_old=x; y_old=y;
  if ( abs(x-*xptr)<2 && abs(y-*yptr)<2 ) break; // нашли решение
  if ( j>max_j )
  	return 0;
  j++;
}
*xptr=x; *yptr=y;
return 1;
}


	// Проверка попала ли точка на препятствие

int	checkPoint
	( int x, int y )
{
int i;
if ( x<0 || x>=X_MAP ) return 1; // вылезли за карту
if ( y<0 || y>=Y_MAP ) return 1;
for ( i=0; i<MAX_STORE; i++ ) // оказалась уже пройденной
	if ( Store[i].x==x && Store[i].y==y ) return 1;
switch ( map[y][x] )
{
case 'o': return 1; // есть препятствие
default: return 0; // нет препятствия
}
}


	// Поиск ближайшей точки к начальной

int	findPoint
	( int * x, int * y, int delta )
{
int i, x_new, y_new;
for ( i=0; i<8; i++ )
{
	x_new=*x+DirMove[i].x*delta;
	y_new=*y+DirMove[i].y*delta;
	if ( checkPoint(x_new,y_new)==1 ) continue;
	*x=x_new; *y=y_new;
	return 1;
}
return 0;
}