21 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • Робітниця.
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 14 097
    • Репутація: 5660

Re: Як запрограмувати "шлях" ?

koala написав:

Дякую.
Тоді ще питання: наскільки важлива швидкість? Тобто "1 зсув за 200мс" - це нормально, чи треба якось витримувати час? Ну, по діагоналі повільніше (бо діагональ довша), чи заборонені стрибки, якщо не встигає за певний час і т.д.?

ну швидкість має там якось налаштовуватись, в принципі нічого страшного, якщо рух по діагоналі буде швидшим ніж не по діагоналі, стрибки мона робити, якщо що

22 Відповідь від quez

  • quez
  • quez
  • Replace Team
  • Поза форумом
  • Звідки: Новий Єрусалим
  • Дата реєстрації: 01.05.2014
  • Повідомлень: 3 103
    • Репутація: 1621

Re: Як запрограмувати "шлях" ?

FakiNyan написав:
quez написав:

Математика непотрібна програмісту.

▼Прихований текст

Будь-яку пряму можна описати таким рівнянням: для деяких a i b будь-який x дасть відповідний y. a і b можна знайти за допомогою двох відомих точок на прямій.

намалюйте мені картинку, щоб легче зрозумілося

Все, що нам відомо - це рівняння прямої, ax+b=y, і дві точки, (x1, y1) i (x2, y2). Склавши два рівняння, в які замість x i y підставимо відомі координати, можна знайти a i b. Тепер, знаючи рівняння, можна для будь-якого x знайти y. Після цього обхід буде тривіальною задачею - отримали список точок, знайшли всі між першою і другою, між другою і третьою, ... , між останньою і першою. По них і ходите.

23 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • На форумі
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Як запрограмувати "шлях" ?

Насправді без стрибків легше.
Ідея така: якщо рухаємося з A в B, то спочатку знаходимо максимум з горизонтальної та вертикальної відстані, а потім проставляємо точки руху в цілих по максимальній вісі і наближених по меншій, умовно так:

if( abs( x1 - x2 ) > abs( y1 - y2 ) )
{
  int step = ( x1 > x2 ) ? -1 : 1;
  for( int x = x1; step*x <= step*x2; x += step )
  {
    PutPoint( x, Math.Round( y2 + ( x - x2 ) * (y1 - y2 ) / ( x1 - x2 ) ) );
    Thread.Sleep(200);
  }
}

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

Подякували: Chemist-i, FakiNyan2

koala вебсайт

24 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • Робітниця.
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 14 097
    • Репутація: 5660

Re: Як запрограмувати "шлях" ?

 private static void Walk(List<double[]> points)
        {
            for (int i = 0; i < points.Count - 1; i++)
            {
                double[] start = points.ElementAt(i);
                double[] end = points.ElementAt(i + 1);
                double length = Math.Floor(Math.Sqrt(Math.Pow((start[0] - end[0]), 2) + Math.Pow((start[1] - end[1]), 2)));
                matrix[(int)start[0], (int)start[1]] = 1;
                Console.WriteLine(length);
                if (Math.Abs((start[0] - end[0])) > Math.Abs(start[1] - end[1]))
                {
                    int step = (start[0] > end[0]) ? -1 : 1;
                    for (int x = (int)start[0]; step * x <= step * end[0]; x += step)
                    {
                        matrix[x, (int)Math.Round(end[1] + (x - end[0]) * (start[1] - end[1]) / (start[0] - end[0]))]=1;
                        //Thread.Sleep(200);
                    }
                }
            }

        }

ну я просто переписав ваш код, але щось не працює, як треба
http://не-дійсний-домен/96eSb/ef55774c11.png

25 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • На форумі
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Як запрограмувати "шлях" ?

FakiNyan написав:

ну я просто переписав ваш код, але щось не працює, як треба

koala написав:

Розгалудження (чи шаблонізацію, чи як захочете) самі доробити зможете

koala вебсайт

26 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • Робітниця.
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 14 097
    • Репутація: 5660

Re: Як запрограмувати "шлях" ?

ой, то мені ще тре розібратись, шо ото ви понаписували, ну гаразд, давайте розберем по частинам вами написане.
Нехай рухаємося з  5;4 в 3;2.
Якщо (5-3) > (4-2), а це не так, то нічого. Угу. Цікавий алгоритм. Тепер треба зробити розгалудження. Цікаво, що це за розгалудження таке, адже для мене розгалудження це щось типу http://не-дійсний-домен/96fFH/dab43175c2.jpg

27 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • На форумі
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Як запрограмувати "шлях" ?

Розгалуження - це конструкція if-else. На випадок, коли там друга координата довша.

koala вебсайт

28 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • Робітниця.
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 14 097
    • Репутація: 5660

Re: Як запрограмувати "шлях" ?

koala написав:

Розгалуження - це конструкція if-else. На випадок, коли там друга координата довша.

а, тю

29 Відповідь від FakiNyan Востаннє редагувалося FakiNyan (29.05.2014 21:01:31)

  • FakiNyan
  • FakiNyan
  • Робітниця.
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 14 097
    • Репутація: 5660

Re: Як запрограмувати "шлях" ?

koala написав:

Розгалуження - це конструкція if-else. На випадок, коли там друга координата довша.

Насправді я тільки зараз почав трохи розуміти ваш алгоритм, але не весь. У вас якось дуже страшно обчислюється y. Я зрозумів все так.
Спочатку ми обчислюємо довжини між компонентами координат. Це потрібно для того, аби знати, в якій площині рухатись, в горизонтальній чи в вертикальній. Наприклад, (2;3) i (2;5), очевидно, що змінювати треба другу компоненту, адже |2-2|<|3-5| і це рух по вертикалі, якщо друга компонента відповідає за вертикаль. Далі ми маємо визначитись, в яку саме сторону будемо рухатись, адже вертикаль складається з руху вниз, та руху вгору. Для цього ми порівнюємо відповідну компоненту першої координати з компонентою (чомусь згадав про кампот) другої координати. Тобто 3<5, і далі дивимось, якщо 3 > ніж 5, і 3 відноситься до першої координати, а 5 до другої, то очевидно, що нам потрібно рухатись в сторону другої координати, а для цього треба додати до 3 одиницю. Якщо ж 3>5, то потрібно віднімати (-1). Далі ми додаємо відповідну цифру до відповідної компоненти і отримуємо нову координату, котра приймається за поточку. І все починається заново.
Приклад.
Нехай рухаємося з (2;2) в (3;6).
Перевіряємо, відстань між якими компонентами більша. |2-3|?|2-6|=1<4
Тобто це друга компонента, на цій картинці перша компонента - це рух по вертикалі, а друга - по горизонталі.

▼Прихований текст

http://не-дійсний-домен/96uTi/855e364c56.png

Далі ми маємо зрозуміти, в яку сторону рухатись. Порівнюємо 2 та 6.
2<6 одже нам треба дійти до 6, для цього треба додавати 1.
Додаємо 1 до другої компоненти поточної координати.
Нова координата (2;3).
Перевіряємо відстань. |2-3|?|3-6|=1<3
Одже рухаємось знову по горизонталі (не дивіться на картинку).
Визначаємось з стороною.
3>6 - додаємо.
Нова координата (2;4)
Визначаємо площину. |2-3|?|4-6|=1<2
Знову горизонталь. Визначаємо сторону.
4<6 тому додаємо.
Нова координата (2;5)
Визначаємось з площиною. |2-3|?|5-6|=1==1
Ось тут треба ловити подібні випадки. Та змінювати обидві координати. Тому потрібно й шукати напрямок для зміни обох координат.
2<3 для першої координати, це означає, що треба додати 1.
5<6 для другої координати, це означає, що теж треба додати 1.
Нова координата (3;6).
Визначаємо площину. |3-3|?|6-6|=0==0
Це теж можна або відловлювати перевіряючи отак if(0+0==0) то кінець, але там ми підставляємо оті отримані різниці. Або можна на кожній ітерації шукати відстань між координатами, і якщо вона ==0, то кінець.
Як бачите, ми побудували шлях, але він дурний, як моя шльондровата сусідка-блондинка, котра дуже тупа та не гарна, але гадає, що гарна.
http://не-дійсний-домен/96vTt/c408e7e202.png
Нам потрібно було б зробити шлях "симетричним", але хід по діагоналі десь в середині не підійде, тому що у нас не парна кількість кроків тоді буде. Я гадаю, що шлях можна було б зробити ось таким.
http://не-дійсний-домен/96w28/f111c17908.png
Але як тоді нам визначатись, чи робити ось такий хід, чи робити хід по діагоналі?

30 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • На форумі
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Як запрограмувати "шлях" ?

Ні, не так. У нас є пряма з першої точки в останню; рівняння цієї прямої (x-x2)/(x1-x2) = (y-y2)/(y1-y2), доводиться це елементарно: рівняння прямої лінійне, і це рівняння лінійне, через дві точки можна провести тільки одну пряму - а обидві точки лежать на цій прямій. Звідси і "страшна формула". А тепер що робить мій код:
1. Визначаємо лінію руху ("площину", як ви сказали);
2. Визначаємо напрямок, ви правильно зрозуміли;
3. Ставимо точку в ( x, Math.Round( y2 + ( x - x2 ) * (y1 - y2 ) / ( x1 - x2 ) ) )
x тут просто поточна координата вздовж лінії руху, а y обчислюється як наближене значення на прямій, в результаті вийде щось схоже на ваш перший малюнок (там вийде (4, 2.5), і якщо округлення буде в більший бік, то пряма пройде саме так)
4. Рухаємося в потрібному напрямку, якщо ще не закінчили - переходимо на 3.

FakiNyan написав:

Приклад.
Нехай рухаємося з (2;2) в (3;6).
Перевіряємо, відстань між якими компонентами більша. |2-3|?|2-6|=1<4
Далі ми маємо зрозуміти, в яку сторону рухатись. Порівнюємо 2 та 6.
2<6 одже нам треба дійти до 6, для цього треба додавати 1.

Все так. А далі:
Знаходимо вторинну (першу) координату: x = Math.Round( x2 + ( y - y2 ) * (x1 - x2 ) / ( y1 - y2 ) ) = Math.Round( 3 + ( y - 6 ) * (2 - 3 ) / ( 2 - 6 ) ) = Math.Round( 3 + ( y - 6 ) / 4 ) = Math.Round( 3 + ( 2 - 6 ) / 4 ) = Math.Round( 2 ) = 2. Ставимо точку (2;2).
Додаємо 1 до головної (в цьому випадку - другої) координати. Знаходимо координату x = Math.Round( 3 + ( 3 - 6 ) / 4 ) = Math.Round( 2,25 ) = 2. Ставимо точку (2;3).
Додаємо 1 до головної координати. Знаходимо координату x = Math.Round( 3 + ( 4 - 6 ) / 4 ) = Math.Round( 2,5 ) = 2. Ставимо точку (2;4).
Додаємо 1 до головної координати. Знаходимо координату x = Math.Round( 3 + ( 5 - 6 ) / 4 ) = Math.Round( 2,75 ) = 3. Ставимо точку (3;5).
Додаємо 1 до головної координати. Знаходимо координату x = Math.Round( 3 + ( 6 - 6 ) / 4 ) = Math.Round( 3 ) = 3. Ставимо точку (3;6). Все, приїхали.
Якщо хочете, зберігайте останнє значення вторинної  координати і якщо воно змінилося, робіть дві позначки, щоб не робити діагонального ходу. Або робіть алгоритм Брезенхема чи модифікуйте його для своїх потреб...

Подякували: FakiNyan1

koala вебсайт

31 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • Робітниця.
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 14 097
    • Репутація: 5660

Re: Як запрограмувати "шлях" ?

Ви не повірите, я не розумію "рівняння прямої" як таке. (не знаю, що означає оте "як таке", але звучить солідно). Зараз піду дивитись відюшки старих дідів, котрі да дошці все детально пояснюють. Я на 80% впевненний, що з розумінням рівняння прямої моє життя стане кращим, та в світі ще одна людина вилікується від раку(мозку).

32 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • Робітниця.
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 14 097
    • Репутація: 5660

Re: Як запрограмувати "шлях" ?

от дописав вже, працює файно

 #region koala version
            for (int i = 0; i < points.Count - 1; i++)
            {
                double[] start = points.ElementAt(i);
                double[] end = points.ElementAt(i + 1);
                double length = Math.Floor(Math.Sqrt(Math.Pow((start[0] - end[0]), 2) + Math.Pow((start[1] - end[1]), 2)));
                matrix[(int)start[0], (int)start[1]] = 1;
                Console.WriteLine(length);
                int xx = (int)start[0], yy = (int)start[1];
                if (Math.Abs((start[0] - end[0])) > Math.Abs(start[1] - end[1]))
                {
                    int step = (start[0] > end[0]) ? -1 : 1;
                    for (int x = (int)start[0]; step * x <= step * end[0]; x += step)
                    {
                        yy = (int) Math.Round(end[1] + (x - end[0])*(start[1] - end[1])/(start[0] - end[0]));
                        matrix[x, yy] = 1;
                        //Thread.Sleep(200);
                    }
                }
                else
                    if (Math.Abs((start[1] - end[1])) > Math.Abs(start[0] - end[0]))
                    {
                        int step = (start[1] > end[1]) ? -1 : 1;
                        for (int y = (int)start[1]; step * y <= step * end[1]; y += step)
                        {
                            xx = (int) Math.Round(end[0] + (y - end[1])*(start[0] - end[0])/(start[1] - end[1]));
                            matrix[xx, y] = 1;
                            //Thread.Sleep(200);
                        }
                    }
                    else
                        if (Math.Abs((start[1] - end[1])) == Math.Abs(start[0] - end[0]))
                        {
                            int xStep = (start[0] > end[0]) ? -1 : 1;
                            int yStep = (start[1] > end[1]) ? -1 : 1;
                            yy += yStep;
                            xx+=xStep;
                            matrix[xx, yy] = 1;
                        }
            }
            #endregion
Подякували: 0xDADA11C7, koala, Chemist-i, leofun014

33 Відповідь від VitekSVM

  • VitekSVM
  • Користувач
  • Поза форумом
  • Дата реєстрації: 31.03.2014
  • Повідомлень: 23
    • Репутація: 14

Re: Як запрограмувати "шлях" ?

https://ru.wikipedia.org/wiki/Алгоритм_Брезенхэма

Подякували: leofun011