Page 3 of 6

Re: Проверка на проходимость

Posted: 2011-06-20 23:04:59
by ZeroDX
Можно расширить, если по очереди прибавлять к двум последним числам в строке по 1

Code: Select all

If IsInRange(A * x + B * y + C, -3, 3) then

То есть так

Code: Select all

If IsInRange(A * x + B * y + C, -3, 4) then
или так

Code: Select all

If IsInRange(A * x + B * y + C, -4, 3) then
выдаст более адекватную линию. Думаю, что зависит от угла отрезка относительно одной из осей. При ровном диагональном отрезке, подойдет 9.


Попробовал ЦДА (цифровой дифференциальный анализатор). Тоже узко на углах...

Code: Select all

Sub VectorPoints2(startx, starty, endx, endy)
  If startx <> endx or starty <> endy then
    var Coordinates = ' ' + str(startx) + ' ' + str(starty) + ' ', Lenght = GetVectorLenght(startx, starty, endx, endy)
    var dx = (endx - startx) / Lenght, dy = (endy - starty) / Lenght
    var x = startx + 0.5 * Sign(dx), y = starty + 0.5 * Sign(dy), i
    For i = 1 to Lenght
      Coordinates = (Coordinates + str(Integer(x)) + ' ' + str(Integer(y)) + ' ')
      x = x + dx
      y = y + dy
    Next
    Return (str(Lenght) + Coordinates)
   else
    Return 0
  Endif
Endsub

Sub GetVectorLenght(startx, starty, endx, endy)
  If Absolute(endx - startx) >= Absolute(endy - starty) then
    Return Absolute(endx - startx)
   else
    Return Absolute(endy - starty)
  Endif
Endsub

Sub Integer(val)
  If int(val + 0.4) > int(val) then
    Return int(val) + 1
   else
    Return int(val)
  Endif
Endsub   

Sub Absolute(val)
  If val > 0 then
    Return val
   else
    Return -val
  Endif
Endsub

Sub Sign(val)
  If val > 0 then
    Return 1
   else
    If val < 0 then
      Return -1
     else
      Return 0
    Endif
  Endif
Endsub



Grin wrote:Основная задача построить список затронутых кубов (у нас же все таки трех мерное пространство:) ).

Именно в этом и проблемма... Но думаю опустить 3d, так как дело будет в лесу и там без лестниц, горок и прочее.
Grin wrote:Строится вектор по двум заданным точкам, длинна этого вектора - длинна диагонали параллелепипеда, это очевидно:)

Ок! Точки А(1;1;0) и В(4;3;0), вектор АВ с координатами (3;2;0) и длиной 5 (определено по точкам начала и конца)(С точки А до точки В идти всего 3 шага!!!)
Grin wrote:Приращение по каждой координате считается как координата вектора деленная на его длину.

то есть .x = дельтаX/5
Grin wrote: Ну а дальше все очень просто, с погрешностью в 0.5 выбираются все кубы через которые проходит вектор, в образованном им параллелепипеде:)Координаты кубов - целые числа.

Вот тут как раз все совсем не просто. Куда в ЦДА воткнуть эту погрешность? И как воткнуть так, чтобы указывать там реальную длину вектора, а не через

Code: Select all

Sub GetVectorLenght(startx, starty, endx, endy)
  If Absolute(endx - startx) >= Absolute(endy - starty) then
    Return Absolute(endx - startx)
   else
    Return Absolute(endy - starty)
  Endif
Endsub

Re: Проверка на проходимость

Posted: 2011-06-21 09:59:41
by Grin
Не путайте декартовую плоскость (длина вектора в декартовой плоскости) с тем что мы имеем в уо, в первом приближении она конечно декартова, но ввиду особенности перемещения в ней это становится не так, так приращение по диагоналям |1|, |1| отсюда вывод о кратчайшем расстоянии между двух точек, что это есть линейная комбинация векторов (|1|,|1|), (0, 1), (1, 0) - с минимальным включением каждого. Очевидно, что в минимальной линейной комбинации наибольший приоритет будут иметь вектора (|1|, |1|).

Отклонились от темы:)

Ну а дальше все очень просто, с погрешностью в 0.5 выбираются все кубы через которые проходит вектор, в образованном им параллелепипеде:)Координаты кубов - целые числа.


В RunUO в частности делается приближение к декартовой плоскости через длину вектора.

От сюда имеем итерацию с приращением dx = (x0-x1)/d, dy = (y0-y1)/d пока x += dx < x1 + 0.5 && y += dy < y1 + 0.5
координаты квадратов выбираются как qx = round(x), qy = round(y) (round - округление до ближайшего целого)
Соответственно квадрат добавляется если его еще не было.

Так же очевидный вывод что координаты начала и конца лучше отсортировать что бы вектор имел положительные координаты.

Re: Проверка на проходимость

Posted: 2011-06-21 14:15:15
by ZeroDX
Если я понял все как надо, то это будет выглядеть вот так

Code: Select all

Sub VectorPoints3(startx, starty, endx, endy)
  If startx <> endx or starty <> endy then ;если не нулевой вектор
    var Coordinates = ' ', Lenght = GetVectorLenght2(startx, starty, endx, endy) ; длина вектора = квадратному корню из суммы квадратов координат вектора
    var dx = (endx - startx) / Lenght, dy = (endy - starty) / Lenght   ;приращение = дельтаХ / длину
    var x = startx * Sign(dx), y = starty * Sign(dy) ; Sign() вернёт -1 при отрицательном параматре, 1 при положительном, 0 при 0(чтобы работать и с отрицателиными координатами вектора, и с положительными)
    While x <= endx + 0.5 and y <= endy + 0.5 ;условие окончания итерации
      Coordinates = (Coordinates + str(Integer(x)) + ' ' + str(Integer(y)) + ' ') ;Integer() - округляет (1.5 округлится до 1)
      x = x + dx
      y = y + dy
    Wend
    Return (str(Lenght) + Coordinates) ;вывод результата
   else
    Return 0
  Endif
Endsub


Вот что выдаёт
Image

А вот что выдаёт ЦДА
Image

Результаты почти одинаковые. Делаю вывод, что я что-то не так понял.

Вот что выдаст

Code: Select all

Sub IsOnVector(x, y, startx, starty, endx, endy)
   var A = starty - endy, B = endx - startx, C = startx * endy - starty * endx
   If IsInRange(A * x + B * y + C, -5, 5) then
      If IsInRange(x, startx, endx) then
         If IsInRange(y, starty, endy) then
            Return 1
         Endif
      Endif
   Endif
   Return 0
Endsub

Image

Это желаемый результат. Но очень капризный скрипт зависит от длины и угла вектора

Re: Проверка на проходимость

Posted: 2011-06-21 16:12:41
by Grin
округление до ближайшего целого - правило 4\5
1.5 -> 2
1.4 -> 1
-1.5 -> -2

Опять повторяю, это алгоритм RunUO, на сфере он может быть другим...

Re: Проверка на проходимость

Posted: 2011-06-21 17:14:49
by ZeroDX
Ну тогда алгоритм для ранки найден =) Это ЦДА (спасибо Грину)
Поломаю голову над формулой для сферы

Re: Проверка на проходимость

Posted: 2011-06-22 00:40:03
by ZeroDX
Провёл небольшие тесты формулы (x1 - x0) * (py - y0) - (y1 - y0) * (px - x0), где px и py - координаты проверяемой точки. Если всё это безобразие равно 0, то точка лежит на прямой. Далее идёт проверка принадлежности точки отрезку If px >= x0 and px <= x1 then аналогично с у координатой.

Но в уо только целые координаты, пожтому скрипт отметит лишь те тайлы, через центр которых проходит отрезок. Решение - допустить погрешность вычислений.

Code: Select all

IsInRange((endx - startx) * (y - starty) - (endy - starty) * (x - startx) , -3, 3)
Функция IsInRange(val, min, max) вернёт 1, если число, переданное функции в первом параметре, принадлежит интервалу, ограниченному вторым и третьим параметрами.

Результаты тестов:

Интервал в таком случае не нужен, но стоял -3 3
Image

Интервал -3 3
Image

Интервал -3 4
Image

Интервал -4 3 (координаты концов отрезака аналогичны преддущему)
Image

Интервал -4 4
Image

Интервал -4 5
Image

Интервал -5 4 (координаты концов отрезака аналогичны преддущему)
Image

Интервал -3 3
Image

Интервал -3 4
Image

Интервал -4 3 (координаты концов отрезака аналогичны преддущему)
Image

Интервал -4 4
Image

Интервал -5 5
Image

Интервал -5 5
Image

Интервал -5 6
Image

Интервал -6 5 (координаты концов отрезака аналогичны преддущему)
Image

Интервал -6 6 (координаты концов отрезака аналогичны преддущему)
Image

Интервал -6 6
Image

Интервал -5 6
Image

Интервал -6 5 (координаты концов отрезака аналогичны преддущему)
Image

Все отрезки строились в положительную сторону по осям x и y. Видно, что чем ближе угол к 45, тем больше погрешность.
Угол можно апределить как sin alfa = a/c, где а - противолежащий катет, с - гипотенуза.

Так вот. Есть у кого функция синуса?

Re: Проверка на проходимость

Posted: 2011-06-22 00:55:29
by ZeroDX
Нашёл вроде как функцию на с++, которая возвращает угол в радианной мере

Code: Select all

#include <iostream>
using namespace std;
const int N = 100;
int main() {
   double x, q, s = 0;
      int n;
   cout << "Enter x = ";
   cin >> x;
   q = x;
   for (n = 1; n <= N; n++) {
      s += q;
      q *= (-1) * x * x/(2 * n)/(2 * n + 1);}
   cout << "sin("<<x<<") = "<< s << endl;
   return 0;
}


У кого есть свободное время, знание и желание помочь, попрошу переконвертировать на инжу. Тем же, у кого есть первое и второе, но нет третьего - горите в аду :twisted:

Re: Проверка на проходимость

Posted: 2011-06-22 01:26:44
by Mirage
Мат функции. Там внизу есть ссылки еще.

Re: Проверка на проходимость

Posted: 2011-06-22 01:41:09
by ZeroDX
там нету

Re: Проверка на проходимость

Posted: 2011-06-22 07:39:42
by Grin
Все тригонометрические функции представляются в ряды тейлора, собственно твой перевод как раз яркий пример.

В сфере еще проще.
Берется дистанция по законам геометрии уо:) то есть это наибольшая из координат вектора взятая по модулю - следствие из линейной комбинации:)

С каждым шагом заново вычисляется направление, и делается 1 шаг в этом направлении. вот и все:)

Никакие градусы читать не надо, весь алгоритм целочисленный.

Re: Проверка на проходимость

Posted: 2011-06-27 16:53:23
by Tiger1989
http://www.onlinedisk.ru/file/688008/
Это я проверял на 51 сфере может вам поможет

Re: Проверка на проходимость

Posted: 2011-07-04 10:42:41
by Tiger1989
ап

Re: Проверка на проходимость

Posted: 2011-07-05 03:06:31
by ZeroDX
А вроде в инже были встроены синус и косинус? Кстати, по каким критериям выбирает направление?

Re: Проверка на проходимость

Posted: 2011-07-05 13:45:20
by Tiger1989
Траекторию имеешь виду? Ну ближайший от Чара, если я верно понял

Re: Проверка на проходимость

Posted: 2011-07-05 14:04:59
by Mirage
ZeroDX wrote:А вроде в инже были встроены синус и косинус? Кстати, по каким критериям выбирает направление?


Code: Select all

sub main()
var i = cos(3.14)
uo.msg(i)
end sub

Направление - вектор от тебя до цели. 2 группы XYZ координат.
Шагнуть то в нужную сторону не сложно. Сложнее определить возможность шагнуть.

Re: Проверка на проходимость

Posted: 2011-07-06 22:39:58
by Tiger1989
Ну можно написать процедуру которая проверит проходим ли тайл или я не так понял?

Re: Проверка на проходимость

Posted: 2011-07-07 01:16:31
by ZeroDX
я хотел узнать какое из направлений выбрать? есть ситуации, когда из точки а в точку б есть 2 маршрута, одинаковые по длине

Re: Проверка на проходимость

Posted: 2011-07-07 02:01:15
by ZeroDX
Например вот
Image
Как полетит стрела?

Re: Проверка на проходимость

Posted: 2011-07-07 07:53:11
by Mirage
По параболе!
:roll:

Как у поиске. Нашел - замерил - если условия выполняются - пульнул. Остальные за бортом.

Re: Проверка на проходимость

Posted: 2011-07-07 08:21:25
by ZeroDX
Тяжко будет реализовать