Приветствую!
Самое первое - данная тема посвящяется алгоритму поиска путей, схожим с алгоритмом игры 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. |
- мне понравилось |
Ты про волновой алгоритм знаешь - почти наилучшее решение твоей задачи. Поисчи в разделе "Алгоритмы" там с месяц назад игра "Сапёр" обсуждалась, там кажись и про волновой агоритм че-то было 
попробую реализовать. 
И плюс к этой идеи, я ещё припишу оба алгоритма, так, чтобы они выполнялись в последовательности от самого быстрого к самому медленному. Итог - если самый быстрый алгоритм не нашёл пути, его найдёт более сложный, и более медленный. Таким образом я постараюсь уменьшить время выполнения уже "обобщённого" алгоритма, и увеличить вероятность правильного ответа до 85-95% 
Если у меня что-нибудь получится, обязательно расскажу как я это сделал, и выкину полный проект в архиве. 