алгоритм нахождения пути

[blacktener]

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

вот код:

#include <GL/glut.h>
#include <cstdio>
#include <cstdlib>
#include <ctime>


bool down;
const int screenx = 100;
const int screeny = 100;
int x=40;
int y=50;
int destx = x;
int desty = y;
const int path_length = 300;
int Path[path_length];
const int width = 100;
const int height = 100;
bool havePath = false;        

class Map
{
 public:
        bool map[width][height];     
        Map()
        {
         int rnd;
         for (int i=0;i<width;i++)
         {
          for (int j=0;j<height;j++)
          {
           map[i][j]=false;   
           rnd = rand()%5;
           if (rnd<0) map[i][j]=true;
          };   
         };
         for (int i=0;i<width;i++)
         {
          map[i][0]=true;
          map[i][height-1]=true;   
         };   
         for (int j=0;j<height;j++)
         {
          map[0][j]=true;
          map[width-1][j]=true;   
         };
        };
        void show()
        {
         glColor3f(0.1,0.1,0.1);
         for (int i=0;i<width;i++)
         {
          for (int j=0;j<height;j++)
          {
           if (map[i][j]) glVertex3f(i,j,0);   
          };   
         };    
        };
        void findPath(int start_x,int start_y,int end_x, int end_y,int path[])
        {
         for (int i=0;i<path_length;i++)
         {
          path[i]=0;   
         };
         int current_number = 0;
         int current_x = start_x;
         int current_y = start_y;
         bool made = false;
         int dir = 0;
         int way[width][height];
         bool madeAll = false;
         bool done[width][height];
         while (!madeAll)
         {
          if (made)
          {
           if (dir==1) current_y++;
           if (dir==3) current_y--;
           if (dir==2) current_x++;
           if (dir==4) current_x--;
           path[current_number]=dir;
           current_number++;
           for (int j=0;j<height;j++)
           {
            for (int i=0;i<width;i++)
            {
             way[i][j]=0;   
            };   
           };
           if ((current_x>0) && (!map[current_x-1][current_y])) way[current_x-1][current_y] = 4;
           if ((current_x<width) && (!map[current_x+1][current_y])) way[current_x+1][current_y] = 2;
           if ((current_y<height) && (!map[current_x][current_y+1])) way[current_x][current_y+1] = 1;
           if ((current_y>0) && (!map[current_x][current_y-1])) way[current_x][current_y-1] = 3; 
           if ((current_x != end_x) || (current_y != end_y)) made=false;        
          };
          if ((current_x == end_x) && (current_y == end_y)) madeAll = true;
           
          while ((!made) && (!madeAll))
          {
           for (int i=0;i<width;i++)
           {
            for (int j=0;j<height;j++)
            {
             done[i][j]=false;   
            };   
           };
           for (int j=1;j<height-1;j++)
           {
            for (int i=1;i<width-1;i++)
            {
             if (way[i][j] != 0)
             {              
              if ((!done[i][j+1]) && (way[i][j+1]==0) && (!map[i][j+1])) {way[i][j+1] = way[i][j]; done[i][j+1]=true;};
              if ((!done[i][j-1]) && (way[i][j-1]==0) && (!map[i][j-1])) {way[i][j-1] = way[i][j]; done[i][j-1]=true;};
              if ((!done[i+1][j]) && (way[i+1][j]==0) && (!map[i+1][j])) {way[i+1][j] = way[i][j]; done[i+1][j]=true;};
              if ((!done[i-1][j]) && (way[i-1][j]==0) && (!map[i-1][j])) {way[i-1][j] = way[i][j]; done[i-1][j]=true;};
              if ((i==end_x) && (j==end_y))
              {
              dir = way[end_x][end_y];
              made = true;                   
              };
             };   
            };   
           };     
          };     
         };    
        };
};

Map* l;

это была первая часть кода...

[blacktener]

вот вторая часть кода

//function mouse
void mouse(int b, int state,int ax, int ay)
{
 down = state == GLUT_DOWN; 
 destx = ax/4;
 desty = screeny-1-ay/4;
 if (down) havePath = false;   
 if (destx<1) destx=1;
 if (destx>width-2) destx = width-2;
 if (desty<1) desty = 1;
 if (desty>height-2) desty = height -2;
};



//function DISPLAY!!!
void display()
{
 glClear(GL_COLOR_BUFFER_BIT);
 
 glPointSize(4);
 glBegin(GL_POINTS);
 l->show();
 
 //show path
 glColor3f (0.5,0.5,0);
 int number=0;
 int cx = x;
 int cy = y;
 while (Path[number] != 0)
 {
  glVertex3f(cx,cy,0);
  if (Path[number]==1) cy++;
  if (Path[number]==2) cx++;
  if (Path[number]==3) cy--;
  if (Path[number]==4) cx--;
  number++;     
 };
 glColor3f(0,0.7,0);
 glVertex3f(x,y,0);
 glColor3f(0,0,1);
 glVertex3f(destx,desty,0);
 glEnd();
 
 glutSwapBuffers();     
}


//function TIMER
void timer(int = 0)
{
 if ((!havePath) && ((x != destx) || (y != desty)))
 {
  havePath = true;
  l->findPath(x,y,destx,desty,Path);               
 };   
 
 display();
 glutTimerFunc(10,timer,0);     
};

//MAIN function
int main(int argc, char **argv)
{
 srand(time(0));
 for (int i=0;i<path_length;i++)
 {
  Path[i]=0;   
 };
 l = new Map;
 glutInit(&argc, argv);
 glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);
 glutInitWindowSize(screenx*4, screeny*4);
 glutInitWindowPosition(400, 100);
 glutCreateWindow("PathFinding 2.0");
 glClearColor(0.9, 0.95, 0.9, 1.0);
 glMatrixMode(GL_PROJECTION);
 glLoadIdentity();
 glOrtho(-0.5,screenx-0.5,-0.5,screeny-0.5,-1,1);
 glutDisplayFunc(display);
 timer();
 glutMouseFunc(mouse);
 glutMainLoop();   
}

[Mandrivnyk]

алгоритм нахождения пути.

поленился накидать комментариев

получился тормознутый и непонятный код

Может не поленишься и хотя бы словами опишешь алгоритм?

[blacktener]

короче класс Мап содержит массив map[][]. конструктор по умолчанию заполняет его пустотой(то есть массив булевых значений и им всем присваевается фолс). есть функция findPath(start_x,start_y,end_x,end_ y,path[]) , где старт_х и старт_у - координаты начала, енд_х и енд_у - координаты конца а path - массив циферок, которые отвечают за направление (1 вверх, 2 - вправо, 3 - вниз, 4 - вниз).
внутри самой функции массив создаются координаты current_x и current_y - координаты точки которая как бы двигается по напралвению к концу. каждый раз внутри цикла вокруг начала ставятся соответствующие цифры которые потом равномерно распостраняются по уровню.то есть если сначала в клеточке стояла цифра 1 то вокруг нее на пустых клетках ставятся единички. и когда клетка с координатами конца ставновится заполненой то это значит что найдено начальное направление для current точки. начальное направление записывается в path, точка двигается в этом направлении и опять находится начальное направление для этой же точки находящейся уже в новом месте.