Приветствую!
Самое первое - данная тема посвящяется алгоритму поиска путей, схожим с алгоритмом игры Lines.
У меня кое-что получилось, но... ФИГНЯ!
Вобщем суть такая: есть что-то вроде плана квартиры. Стены нарисованы clBlack'ом на clWhite'е
Всё это загружено в простой TImage. Если точнее - TBitmap;
Вот, теперь, есть две точки - А и В. Мне нужно построить алгоритм,
который будет строить ломаную из точки А в точку В, обходящую стены, нарисованые чёрным цветом (напоминаю

Вот мой листинг, код, признаюсь, тупее некуда, но он кое-как работает

Код

var   Form1: TForm1;   Def: TBitmap;   C: Integer=-1;   pA,pB: TPoint;   FirstPoint: Boolean=TRUE;   stopped: boolean;   a,b: array[0..377, 0..225] of TBit; procedure TForm1.Image1MouseUp(Sender: TObject; Button: TMouseButton;   Shift: TShiftState; X, Y: Integer); var   TX, TY, AX, AY, BX, BY, I: Integer;   TheEnd: Boolean;   V: Byte;   DM, DM_I, St: Integer;   Points: array[0..7] of TPoint;  // 111   123                                                  // 101   4X5                                                  // 111   678 procedure DStep(x,y: Integer); begin    Form1.Image1.Canvas.Ellipse(X-5, Y-5, X+5, Y+5); end; procedure DLine(x1,y1,x2,y2: Integer); begin    Form1.Image1.Canvas.MoveTo(x1,y1);    Form1.Image1.Canvas.LineTo(x2,y2); end; function Distance(x1,y1,x2,y2: LongInt): LongInt; begin    Result := Round(Sqrt(Sqr(x1-x2)+Sqr(y1-y2))); end; procedure Find(x,y: Integer); begin end; {           Image1.Canvas.MoveTo(pA.X, pA.Y);           Image1.Canvas.LineTo(pB.X, pB.Y);           Image1.Canvas.Pen.Color := clGreen;           Image1.Canvas.MoveTo(pA.X, pA.Y);           Image1.Canvas.LineTo(pB.X, pA.Y);           Image1.Canvas.LineTo(pB.X, pB.Y); } begin Image1.Canvas.Ellipse(X-5, Y-5, X+5, Y+5); if CheckBox1.Checked then begin inc©; case c of  0: begin pA.X := X; pA.Y := Y; end;  1: begin pB.X := X; pB.Y := Y;  //=====================================        for tx:=0 to 377 do         for ty:=0 to 225 do          if def.canvas.Pixels[tx,ty] = clBlack then           a[tx,ty] := 1          else           a[tx,ty] := 0;        for tx:=0 to 377 do         for ty:=0 to 225 do          b[tx,ty] := 0;        bx := pB.X;        by := pB.Y;        ax := pA.X;        ay := pA.Y;        TX := ax;        TY := ay;        //Form1.Memo1.Lines.Add(format('BX: %d BY: %d AX: %d AY: %d ; Distance: %d', [bx,by,ax,ay,distance(ax,ay,bx,by)]));        I:=0;        DM := 0;        DM_I := 0;        St := 1;        stopped := false;        repeat            for I:=0 to 7 do             begin Points[I].X := -1; Points[I].Y := -1; end;            Points[0].X := TX-St; //1            Points[0].Y := TY-St; //1            Points[1].X := TX;   //2            Points[1].Y := TY-St; //2            Points[2].X := TX+St; //3            Points[2].Y := TY-St; //3            Points[3].X := TX-St; //4            Points[3].Y := TY;   //4            Points[4].X := TX+St; //5            Points[4].Y := TY;   //5            Points[5].X := TX-St; //6            Points[5].Y := TY+St; //6            Points[6].X := TX;   //7            Points[6].Y := TY+St; //7            Points[7].X := TX+St; //8            Points[7].Y := TY+St; //8            DM := 0;            for I:=0 to 7 do             if a[Points[I].X, Points[I].Y] = 1 then             begin              Points[I].X := -1; Points[I].Y := -1;              Inc(DM);             end;            Application.ProcessMessages;            if DM >= 8 then             begin                Form1.Memo1.Lines.Add('Ошибка! Путь не найден!');                Inc(St);                if stopped then break;                if st > 10 then Break;                Continue;             end;            DM := 32767;            for I:=0 to 7 do             if Distance(Points[I].X, Points[I].Y, bx, by) < DM then              begin                 DM := Distance(Points[I].X, Points[I].Y, bx, by);                 DM_I := I;              end;            a[TX,TY] := 1;            TX := Points[DM_I].X;            TY := Points[DM_I].Y;            b[TX,TY] := 1;        until ((tx = bx) and (ty = by)) or stopped;        Form1.Memo1.Lines.Add('ok');  //=====================================           C := -1;        for TX := 0 to 377 do         for TY := 0 to 225 do          if b[tx,ty] = 1 then           Image1.Canvas.Pixels[TX,TY] := clGreen;     end; end; end else begin if FirstPoint then  Image1.Canvas.MoveTo(X,Y) else  Image1.Canvas.LineTo(X,Y); FirstPoint := FALSE; end; end;

В переменную Def загружается картинка из TImage, а в TImage она установлена ещё с Object Inspector'а.
Ломаная - траектория движения.

Я ещё буду мучаться, но незнаю что у меня получится.

Цель всего этого - небольшая часть большой программы, которая должна будет управлять домашним роботом, которого
ещё пока нету

Кто чем может, помогите люди!!! У меня мАзгов на ето не хватает!!!

Цитата

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Vit.

- мне понравилось

Это сообщение отредактировал(а) Girder - 25.4.2005, 01:15

Цитата(vintch @ 24.4.2005, 21:00)

мне понравилось

ну тада регистрируйся! не боись нечего страшного там нет, и

По сабжу:
с твоим листнгом не разбирался - много сильно понаписано, без комментариев... Ты про волновой алгоритм знаешь - почти наилучшее решение твоей задачи. Поисчи в разделе "Алгоритмы" там с месяц назад игра "Сапёр" обсуждалась, там кажись и про волновой агоритм че-то было

Это сообщение отредактировал(а) Girder - 25.4.2005, 01:17

почитай полезно, есть много интересного и на твой вопрос
жми сюда

Цитата

ну тада регистрируйся! не боись нечего страшного там нет

Дык уже зарегился!
За советы спасибо, щас смотреть буду

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

А если по волновому, то могу полуполезный совет предложить. Если формат картинки достаточно большой, то, возможно, есть смысл её уменьшить. Только так, чтобы стены не проподали и не срастались в месте проходов.

Да, я с Вами полностью соглашаюсь!

Я нашёл в инете полное описание этого алгоритма, написал, работает.
НО! Он совершенно не такой эффиктивный, как его разрекламировали!!! Он находит путь примерно в 25-35% случаев!
И при этом, он работает только если координаты начальной точки меньше координат конечной! Но это я кажется знаю как исправить. Мой алгоритм, что весьма интересно, работает раз в 10-20 быстрее, но он также не эффиктивен. Но зато, такой финт: если не работает первый алгоритм, то работает второй, и наоборот. (!!!) Карту уменьшать не собираюсь, мне это просто не подходит по ряду причин. А вот про алгоритмы, у меня появилась ещё идея, попробую реализовать. И плюс к этой идеи, я ещё припишу оба алгоритма, так, чтобы они выполнялись в последовательности от самого быстрого к самому медленному. Итог - если самый быстрый алгоритм не нашёл пути, его найдёт более сложный, и более медленный. Таким образом я постараюсь уменьшить время выполнения уже "обобщённого" алгоритма, и увеличить вероятность правильного ответа до 85-95% Если у меня что-нибудь получится, обязательно расскажу как я это сделал, и выкину полный проект в архиве.

vintch Не правильно пишешь слово "эффективен"