линия

[supernewbie]

вообщем есть функция рисующая линию

procedure TLinePainter.PaintLine;
var
i,path:integer;
v:real;
x,y:integer;

begin
i:=abs(Start.X - Finish.X);
path:=abs(Start.Y - Finish.Y);
if path<i then path:=i;
if path=0 then exit;
for i:=0 to path do
begin
v:=(i / path);
x:=Start.x + Round((Finish.x - Start.x) * v);
y:=Start.y + Round((Finish.y - Start.y) * v);
Form.Scene.Canvas.Pixels[x,y]:=clBlack;
end;
end;

первая линия на рисунке - нарисованая этой функцией, а вторая - так как надо нарисовать.
проще гря надо рисовать линию которая не может по-диагонали двигатся

[Xa4ik]

так заарисовуются углы: (исправлено)

if (x<>x1) and (y<y1) then Form.Scene.Canvas.Pixels[x-1,y]:=clBlack;
if (x<>x1) and (y>y1) then Form.Scene.Canvas.Pixels[x+1,y]:=clBlack;
if (y<>y1) and (x<x1) then Form.Scene.Canvas.Pixels[x,y+1]:=clBlack;
if (y<>y1) and (x>x1) then Form.Scene.Canvas.Pixels[x,y-1]:=clBlack;
Form.Scene.Canvas.Pixels[x,y]:=clBlack;
x1:=x;
y1:=y;

[xkor]

надо рисовать линию которая не может по-диагонали двигатсячто бы это могло означать :confused:

[Aries]

Тебе это именно для рисования, или все таки имеет отношение к поиску пути?)))

Вторая в 2 пикселя толищиной, первая в 1.
думаю так:

Form.Scene.Canvas.Pixels[x,y]:=clBlack;
Form.Scene.Canvas.Pixels[x+1,y+1]:=clBlack;

сомнительно... Внимательно посмотри на рисунок, если именно 1 в 1 как у него... то на втором рисунке точка(3,5) должна быть в (4,4), если толщиной в 2 пикселя строить...

Если это тупо рисование пути (и ничего больше), то там только попиксельно (или извратиться с поиском прямых отрезков параллельно осям коодинат)

[supernewbie]

Тебе это именно для рисования, или все таки имеет отношение к поиску пути?)))


сомнительно... Внимательно посмотри на рисунок, если именно 1 в 1 как у него... то на втором рисунке точка(3,5) должна быть в (4,4), если толщиной в 2 пикселя строить...

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

[Nickers]

supernewbie, а что ты конструируешь такое? А то у тебя постоянно геометрические впросы, аж интересно...
(Если ответ: "Иди ёбни ломату дерьма убейся", то я пойму)

[supernewbie]

дык алгоритм пути по геодате, сам путь есть в виду координат, надо отрезать лишние точки, чтобы посылать мув то локейшен только в точки в которые можно провести прямую линию и на ней не будет препятствий, для этого сначала эту прямую линию надо провести)

Добавлено через 2 минуты
памагите пасаны

[mira]

он боитса что диагональная линия пути проскочит между двумя такимиже диагональным пикселами геодаты как я понимаю) и получитса типа как итти можно.

а ты попробуй рисавать еще 1 линию вплотную к этой со сдвигом в один пиксель. если обе линии проходят то вперед, пока в мою светлую голову не приходит ничего другова ))

[Aries]

дык алгоритм пути по геодате, сам путь есть в виду координат, надо отрезать лишние точки, чтобы посылать мув то локейшен только в точки в которые можно провести прямую линию и на ней не будет препятствий, для этого сначала эту прямую линию надо провести)

Добавлено через 2 минуты
памагите пасаны

Так тут все более чем просто... Путь не является прямой линией, поэтому мысль с построением линии без диагональных переходов - как-то бредова))

Суть такая:

coord A = CurrentCoord();
coord B = CurrentCoord();
while (A != EndPoint) {
bool Flag = false, ShiftX=false, ShiftY=false;
while (!Flag) {
if(A.x != B.x) ShiftX=true;
if(A.y != B.y) ShiftY=true;
if(B == EndPoint) Flag = true;
if (ShiftX && ShiftY) {
Flag = true;
B = PrevPoint();
}
else B = NextPoint();
}
moveto(B);
A = B;
}


эт если я правильно понял что тебе надо)
Т.е. мы строим прямую линии до ближайшего диагонального перехода, идем к нему, от него начинаем строить дальше и т.д.... Если нужно изначально все точки просто пробить, то вместо moveto(B) записывай себе куда-нить эту координату и все

Добавлено через 6 минут
он боитса что диагональная линия пути проскочит между двумя такимиже диагональным пикселами геодаты как я понимаю) и получитса типа как итти можно.

нет, как я понял, у него путь готовый есть уже) просто ему нужно сделать координаты контрольных точек, чтоб не писать MoveTo на каждую точку пути)))

хотя мб я как всегда не допонял что-то))
А если ты прав, то это говорит о том, что выбранный алгоритм для поиска пути заведомо неверный, раз ищет не в 4 направления, а в 8)))

[xkor]

mira, значит голова твоя ещё не вся на стороне света)

[supernewbie]

у него путь готовый есть уже) просто ему нужно сделать координаты контрольных точек, чтоб не писать MoveTo на каждую точку пути)))

вот именно так, есть массив точек xyz пути, надо удалить лишние посредством провода прямых линий, а в геодате по диагонали нельзя двигатса

Добавлено через 1 минуту
а ты попробуй рисавать еще 1 линию вплотную к этой со сдвигом в один пиксель. если обе линии проходят то вперед, пока в мою светлую голову не приходит ничего другова ))
но это хренова :\ так лишние точки будут задействованы и тупить всё будет

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

[Aries]

вот именно так, есть массив точек xyz пути, надо удалить лишние посредством провода прямых линий, а в геодате по диагонали нельзя двигатса


ну так идею вычисления нужных точек я тебе написал... Проверка на Z координату там походу и не нужна вообще будет.

Добавлено через 2 минуты
эм... Эт как же ты эти бордовые точки выбрал? по какой логике?))

[supernewbie]

ну так идею вычисления нужных точек я тебе написал... Проверка на Z координату там походу и не нужна вообще будет.

Добавлено через 2 минуты
эм... Эт как же ты эти бордовые точки выбрал? по какой логике?))
по логике от каждой бордовой точки можно провести к другой бордовой линию и не будет препятствия, примерно так

[Aries]

по логике от каждой бордовой точки можно провести к другой бордовой линию и не будет препятствия, примерно так

не, ну стоп...
Путь у тебя синим показан, не?
Как мы можем выбрать точки, которые буду соединены в обход пути?

ЗЫ сейчас кстати конечно вижу, что я тупо разделил на прямые отрезки, но которые по сути излишни местами... А раньше так путь и прокладывал, и ток глядя на твой рисунок осознал, что в случае клиента линейки, там путь во многих случаях и без доп обхода норм должен проложиться (надо будет по этому поводу подумать как следует)....

[supernewbie]

не, ну стоп...
Путь у тебя синим показан, не?
Как мы можем выбрать точки, которые буду соединены в обход пути?

ЗЫ сейчас кстати конечно вижу, что я тупо разделил на прямые отрезки, но которые по сути излишни местами... А раньше так путь и прокладывал, и ток глядя на твой рисунок осознал, что в случае клиента линейки, там путь во многих случаях и без доп обхода норм должен проложиться (надо будет по этому поводу подумать как следует)....
путь синим, по факту каждый пиксель=координата, надо оставить тока бордовые т.к. по ним буду посылать мув то локейшек епт) для этого надо провести *бучую линию и каждую координату линии проверить на наличие препятствий, если их нет - удаляем координату и так все координаты пока не останутся только одни бордовые, че тупишь))

короче, не напрягайся, просто скажи как нарисовать линию без диагональных точек *ля

и если примеры будут - пиши на дельфе их плз

[Aries]

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

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

А если это не кратчайший путь, то зачем он нам нужен вообще?))

[supernewbie]

так всё, забей

[Aries]

так всё, забей

мне просто интересно, это я так туплю или ты так тупишь?)

[supernewbie]

и то и другое

[Aries]

Похоже на то
Напоследок выскажу свое мнение и убегаю по делам)))
Короче тут 3 варианта:
1) Синим показан кратчайший путь. Т.е. мы не должны с него отклоняться, т.к. один хрен больше уже не сократишь. И тогда твои фиолетовые точки не в тему.
2) Синий путь - какой-то путь, не пойми зачем показанный, и мы ориентируемся по фиолетовым точкам => (см. *)
3) Синий - якобы кратчайший путь, но судя по зеленой линии он таковым не является и => (см. *)
* необходимо переделывать/писать заново алгоритм поиска пути

ЗЫ пример 1 - показаны точки, которые при идеальном раскладе должны использоваться при прохождении, учитывая, что синий путь - кратчайший.
Пример 2 - то как это делается в моем способе, но есть идея как привести к примеру 1... Вечером могу набросать, если понадобится.

[Xa4ik]

как я понял, если нада чтоб квадратики граничили между собой боками а не углами в линии, то алгоритм во 2 посте темы.

[mira]

можно вообще сделать тупо. первичный путь у тебя типа массиваю начинаеш с 1го элемента проводить отрезки сначало до 2го потом до 3го итд пока отрезок не пересечет препятствие. если пересек на элементе 10 преграду то то проводиш новый отрезок от 1 до 9 и начинаеш с 9го проводить отрезки в 10, 11 итд.
тупо но действенно если объемы не столь огромны и вызывать не часто =)

[mira]

както так если упрощено

[supernewbie]

дак да, но линию надо проводить не обычную, а ещё боковые пиксели считать, т.к. по диагонали нельзя ходить в геодате

[supernewbie]

уф, ну че-то типо альфа бета версии вышло пока

алгоритм удаления точек даёт смертельные висяки раз на раз, но в 6 часов утра ниче лучше сделать физически нереально, я спать..

[Aries]

Народ, вправьте мне мозг))) Мне уже чисто для себя интересно)))))
Ну объясните суть синей линии и суть всех этих извращений))
Ведь по факту обычный поиск кратчайшего пути и так даст координаты, через которые нереально уже провести линии для сокращения)

А если это тупо намеченный путь, то нам нужна только его начальная и конечная координаты для рассчета пути, а не вся линия...

[mira]

А я непонял почему нельзя ходить по диагонали. Персы же ходят) да и боты тоже

[Aries]

Они ходят не по диагноали, а как бы по 3 точкам, которые получаются типо диагонального соединения...

[mira]

Тоесть проходимость проверяетса тока вверх вниз вбока. Ах ну да логично, теперь понял что значит NWSE. Это типа норд, вест, сауз, ист..

просто не заморачивалса неразу геодатой

[xkor]

вы блин меня заинтриговали, аж захотелось свой алгоритм поиска пути допилить, ток вот когда его открыл и увидел 100 строк кода без комментариев понял что день уйдёт только чтоб понять/вспомнить что уже реализовал(

[mira]

Так зачем его менять. Написал новую функцию и перешол на нее. Если луше робит удалил старую если хуже убрал) я както так делаю стараясь не корежить ранше времени старый код

[destructor]

а я гуглить умею http://www.dtf.ru/articles/read.php?id=46788

[supernewbie]

ыыы

[mira]

чето похожее на то что нужно вроде

[supernewbie]

он ходит, он ходит!!!!!!!11111

[Aries]

Грац))))

[mira]

тоже когданить займусь, как разберусь с ХФ. тут мне чето никто подсказать непожелал и удалили тему) придетса разбирать пакеты самому.
благо там немного изменений =/

[supernewbie]

почти ничего на самом деле

Добавлено через 1 час 29 минут
*ля короче нужен алгоритм рисования прямой линии какой я описал в начале, а то бот иногда сквозь стены ломится или застрявает на углах

[Aries]

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

[supernewbie]

всем спасибо за помощь

function GetVector : integer;
begin
result:=0;
if (dx>0) and (dy>0) then result:=1 else
if (dx<0) and (dy>0) then result:=2 else
if (dx>0) and (dy<0) then result:=3 else
if (dx<0) and (dy<0) then result:=4 else exit;
end;

if (dx<>0) and (dy<>0) then
begin
case GetVector of
1: Dec(y);
2: Dec(y);
3: Inc(y);
4: Inc(y);
end;
Form.Scene.Canvas.Pixels[x,y]:=clBlack;
end;

[Breadfan]

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

[xkor]

так будет быстрее)
function GetVector: Integer; inline;
begin
result := Integer(dx<0) or (Integer(dy<0) shl 1) + 1;
end;

[Hint]

проще гря надо рисовать линию которая не может по-диагонали двигатся
Такой отрезок называется 4-х связным :) На картинке 8-ми связный.

[Aries]

Такой отрезок называется 4-х связным :) На картинке 8-ми связный.

я думаю, тут это и так все поняли)))
А вообще по логике правильно построенный стандартный волновой алгоритм построит кратчайший путь причем без диагональных переходов) Поэтому-то мне и так сложно понять смысл всех этих жестоких манипуляций))))

[xkor]

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

[Aries]

только вот они по точкам путь построит, и всё равно надо их потом группировать в отрезки...

Ну как это разбивать, я уже предложил на 1 странице
Добавить там еще пару условий и количество точек можно сократить будет

Добавлено через 29 минут
Че-т ща сам решил на будущее себе набросать алгоритм, и понял, какой бред на первой страницу мну накотал))

[supernewbie]

ето, про линию, у кого-нить есть формула которая узнает пересекаюца ли два отрезка и говорит где именно, а то все функции что в нете нашёл тока булеан возвращают

[червь]

http://programmersforum.ru/showthread.php?t=41041 здесь вроде понятно написано

[Aries]

или вот
http://programmersforum.ru/showthread.php?t=50402 - по-моему, первая же ссылка в гугле))

Добавлено через 14 минут
Если тебе надо в 3-х мерном пространстве, тогда надо дополнительно функцию вначале накатать, которая определяет, что отрезки в одной плоскости лежат, а потом уже дальнейшие проверки... Хотя алгоритмы немного усложнятся тогда.