Алгоритм Бразенхэма: FreeBasic To C++

Темы, связанные с проектированием и программированием roguelike-игр

Модераторы: Sanja, Максим Кич

Ответить
IPavel
Сообщения: 55
Зарегистрирован: 13 май 2013, 15:02

Алгоритм Бразенхэма: FreeBasic To C++

Сообщение IPavel » 20 май 2013, 07:23

Всем привет!
Решил узнать по больше об рогаликах, заодно и по практиковаться в программировании...
Пишу вобщем простейший рогалик по мативам:
http://rlgclub.ru/wiki/%D0%94%D0%B0%D0% ... 1%80%D0%BA
Ну если быть точным изучаю приёмы и переписываю код с FreeBasic на C++.
И застрял на месте проверки видимости
тайла для персонажа...
Вроде код на бейсики не сложный
и переложить его на С++ получилось быстро, но
мучает какое-то сомнение по поводу правильности...
Т.к. не совсем было понятно в некоторых моментах для чего делается то или другое...
Вобщем те кто на "ТЫ" с математикой и С++
Негляните получившиеся, правильно ли всё?
Код на FreeBasic:
Скрытый текст: ПОКАЗАТЬ
'Алгоритм Брезенхе́ма для линий

Код: Выделить всё

Function levelobj._LineOfSight(x1 As Integer, y1 As Integer, x2 As Integer, y2 As Integer) As Integer 
  Dim As Integer i, deltax, deltay, numtiles 
  Dim As Integer d, dinc1, dinc2 
  Dim As Integer x, xinc1, xinc2 
  Dim As Integer y, yinc1, yinc2 
  Dim isseen As Integer = TRUE 

  deltax = Abs(x2 - x1) 
  deltay = Abs(y2 - y1) 

  If deltax >= deltay Then 
    numtiles = deltax + 1 
    d = (2 * deltay) - deltax 
    dinc1 = deltay Shl 1 
    dinc2 = (deltay - deltax) Shl 1 
    xinc1 = 1 
    xinc2 = 1 
    yinc1 = 0 
    yinc2 = 1 
  Else 
    numtiles = deltay + 1 
    d = (2 * deltax) - deltay 
    dinc1 = deltax Shl 1 
    dinc2 = (deltax - deltay) Shl 1 
    xinc1 = 0 
    xinc2 = 1 
    yinc1 = 1 
    yinc2 = 1 
  End If 

  If x1 > x2 Then 
    xinc1 = - xinc1 
    xinc2 = - xinc2 
  End If 

  If y1 > y2 Then 
    yinc1 = - yinc1 
    yinc2 = - yinc2 
  End If 

  x = x1 
  y = y1 

  For i = 2 To numtiles 
    If _BlockingTile(x, y) Then 
      isseen = FALSE 
      Exit For 
    End If 
    If d < 0 Then 
      d = d + dinc1 
      x = x + xinc1 
      y = y + yinc1 
    Else 
      d = d + dinc2 
      x = x + xinc2 
      y = y + yinc2 
    End If 
  Next 

  Return isseen 
End Function
Код на C++:
Скрытый текст: ПОКАЗАТЬ
// алгоритм Бразенхэма.

Код: Выделить всё

bool LevelObj::LineOfSight(int x1, int y1, int x2, int y2)
{
	int i = 0, deltaX = 0, deltaY = 0, numTiles = 0;
	int d = 0, dInc1 = 0, dInc2 = 0;
	int x = 0, xInc1 = 0, xInc2 = 0;
	int y = 0, yInc1 = 0, yInc2 = 0;
	bool isSeen = true;

	deltaX = abs(x2 - x1);
	deltaY = abs(y2 - y1);

	if (deltaX >= deltaY)
	{
		numTiles = deltaX + 1;
		d = (2 * deltaY) - deltaX;
		dInc1 = deltaY << 1;
		dInc2 = (deltaY - deltaX) << 1;
		xInc1 = 1;
		xInc2 = 1;
		yInc1 = 0;
		yInc2 = 1;
	}
	else
	{
		numTiles = deltaY + 1;
		d = (2 * deltaX) - deltaY;
		dInc1 = deltaX << 1;
		dInc2 = (deltaX - deltaY) << 1;
		xInc1 = 0;
		xInc2 = 1;
		yInc1 = 1;
		yInc2 = 1;
	}

	if (x1 > x2)
	{
		xInc1 = - xInc1;
		xInc2 = - xInc2;
	}

	if (y1 > y2)
	{
		yInc1 = - yInc1;
		yInc2 = - yInc2;
	}

	x = x1;
	y = y1;

	for (i = 2; i <= numTiles; i++)
	{
		if (BlockingTile(x, y))
		{
			isSeen = false;
			break;
		}

		if (d < 0)
		{
			d = d + dInc1;
			x = x + xInc1;
			y = y + yInc1;
		}
		else
		{
			d = d + dInc2;
			x = x + xInc2;
			y = y + yInc2;
		}
	}

	return isSeen;
}
P.S. Если будет также не сложно прокомменте код построчно...
Для глубокого понимания...
Как я писал выше не все моменты были понятны...

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Re: Алгоритм Бразенхэма: FreeBasic To C++

Сообщение Максим Кич » 20 май 2013, 08:57

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

Во-вторых, сам алгоритм Брезенхема построчно прокомментирован и подробно описан хотя бы в соответствующей статье Википедии. Тем более, что как простейший и самый известный алгоритм растровой графики, он в деталях разобран практически в каждом учебнике, посвящённом компьютерной графике. Думаю, если разобраться как он сам работает, будет несложно понять, в чём проблема с его конкретным приложением.

Удачи в этом нелёгком деле!
Dump the screen? [y/n]

Аватара пользователя
Uvadzucumi
Сообщения: 365
Зарегистрирован: 29 ноя 2011, 07:13
Откуда: Дубай, ОАЭ (Минск, Беларусь)
Контактная информация:

Re: Алгоритм Бразенхэма: FreeBasic To C++

Сообщение Uvadzucumi » 20 май 2013, 11:06

@IPavel
судя по коду, на первый взгляд все верно. но в той книжке алгоритм странный. т.е. он помечает только пустые ячейки карты. те же, которые заняты стенами - всегда невидимые. поэтому необходимо всегда постобработку делать. без нее - будет казаться что неверно работает алгоритм.
Меня окружали милые, добрые люди... медленно сжимая кольцо

IPavel
Сообщения: 55
Зарегистрирован: 13 май 2013, 15:02

Re: Алгоритм Бразенхэма: FreeBasic To C++

Сообщение IPavel » 20 май 2013, 14:03

Максим Кич писал(а):Во-первых, я очень рекомендую пользоваться отступами и тегом Code — это значительно увеличит шансы на то, что кто-нибудь хотя бы попытается прочитать код. Примера ради, я исправил начальный пост, в дальнейшем лучше выкладывать код именно так.

Во-вторых, сам алгоритм Брезенхема построчно прокомментирован и подробно описан хотя бы в соответствующей статье Википедии. Тем более, что как простейший и самый известный алгоритм растровой графики, он в деталях разобран практически в каждом учебнике, посвящённом компьютерной графике. Думаю, если разобраться как он сам работает, будет несложно понять, в чём проблема с его конкретным приложением.

Удачи в этом нелёгком деле!

СПасибо... :)
На счёт тега "Код", не подумал...
А на счёт отступов...
Знаю что надо...
Но просто я когда переписывал код на с++ не думал его куда выкладывать...
Т.е. писал для себя...
Ну а для меня отступы не актуальны...

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

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Re: Алгоритм Бразенхэма: FreeBasic To C++

Сообщение Максим Кич » 20 май 2013, 15:26

Отступы для всех актуальны, просто это не сразу приходит.

А в плане кода, по мне лучше действительно взять код из Вики и не мучиться. Проверку на прозрачность надо вставить туда, где в примере вызов SetPixel, причём первый вызов за пределами цикла можно опустить, поскольку в этой точке по определению будет находиться один из двух персонажей.
Dump the screen? [y/n]

IPavel
Сообщения: 55
Зарегистрирован: 13 май 2013, 15:02

Re: Алгоритм Бразенхэма: FreeBasic To C++

Сообщение IPavel » 20 май 2013, 16:14

Максим Кич писал(а):Отступы для всех актуальны, просто это не сразу приходит.

А в плане кода, по мне лучше действительно взять код из Вики и не мучиться. Проверку на прозрачность надо вставить туда, где в примере вызов SetPixel, причём первый вызов за пределами цикла можно опустить, поскольку в этой точке по определению будет находиться один из двух персонажей.
Ну я имел в том плане не актуальны, что мне их не видно...
И для меня отступы не несут из за этого смысловой нагрузки...
Не буду я же считать сколько пробелов перед каждой строкой...
Я тогда просто с ума сойду... :)
А вобще согласен это хороший тон программирования.
И весьма повышает читабельность.

А по поводу алгоритма...

Мне больше вот отсюда код нравится...
http://compgraphics.info/2D/Brezenham.php
На мой взгляд понятно и сердито :)
вот адаптировал его немножко...
Скрытый текст: ПОКАЗАТЬ
 

Код: Выделить всё

bool line( int x1, int y1, int x2, int y2)
{
      bool isSeen = true;
      int dx = (x2 - x1 >= 0 ? 1 : -1);
      int dy = (y2 - y1 >= 0 ? 1 : -1);
 
      int lengthX = abs(x2 - x1);
      int lengthY = abs(y2 - y1);
 
      int length = max(lengthX, lengthY);
 
//      if (length == 0)
//      {
//            SetPixel(hdc, x1, y1, 0);
//      }
 
      if (lengthY <= lengthX)
      {
            // Начальные значения
            int x = x1;
            int y = y1;
            int d = -lengthX;
 
            // Основной цикл
            length++;
            for (int i = 2; i <= length; i ++)
            {
                  if (BlockingTile(x, y))
                    {
                    isSeen = false;
                   break;
                   }

                  x += dx;
                  d += 2 * lengthY;
                  if (d > 0) {
                        d -= 2 * lengthX;
                        y += dy;
                  }
            }
      }
      else
      {
            // Начальные значения
            int x = x1;
            int y = y1;
            int d = - lengthY;
 
            // Основной цикл
            length++;
            for (int i = 2; i<= length; i++)
            {
                  if (BlockingTile(x, y))
                  {
                  isSeen = false;
                   break;
                  }

                  y += dy;
                  d += 2 * lengthX;
                  if (d > 0) {
                        d -= 2 * lengthY;
                        x += dx;
                  }
            }
      }
      return isSeen;
}
Хотя там автор почему-то упоминает момент когда разница между расстояниями равна нулю,
т.е. (x2 - x1) = (y2 - y1),
то мол это отдельный случай и говорит что надо выйти тогда из цикла...
Этот момент закомментен здесь...
Вот только из-за этого и не включаю его в свой исходник...
Последний раз редактировалось IPavel 20 май 2013, 16:42, всего редактировалось 1 раз.

Аватара пользователя
Феникc
Сообщения: 679
Зарегистрирован: 27 ноя 2010, 15:01
Откуда: Челябинск

Re: Алгоритм Бразенхэма: FreeBasic To C++

Сообщение Феникc » 20 май 2013, 16:28

Хотя там автор почему-то упоминает момент когда разница между расстояниями равна нулю,
т.е. (x2 - x1) = (y2 - y1),
то мол это отдельный случай и говорит что надо выйти тогда из цикла...
Этот момент закомментен здесь...
Вот только из-за этого и не включаю его в свой исходник...
В данном случае это значит просто что мы пытаемся провести линию из данной точки в неё же, что смысла не имеет.
И да, как ты узнаешь результат этой функции? Если бы isSeen была глобальной, ещё понятно. А так, void функция и даже ни единого намёка на глобальную переменную, через которую это можно реализовать. Разве что BlockingTile там какую-то особую магию делает.
Всё вышесказанное - ИМХО, если не указано обратное.

IPavel
Сообщения: 55
Зарегистрирован: 13 май 2013, 15:02

Re: Алгоритм Бразенхэма: FreeBasic To C++

Сообщение IPavel » 20 май 2013, 16:39

Феникc писал(а):
Хотя там автор почему-то упоминает момент когда разница между расстояниями равна нулю,
т.е. (x2 - x1) = (y2 - y1),
то мол это отдельный случай и говорит что надо выйти тогда из цикла...
Этот момент закомментен здесь...
Вот только из-за этого и не включаю его в свой исходник...
В данном случае это значит просто что мы пытаемся провести линию из данной точки в неё же, что смысла не имеет.
И да, как ты узнаешь результат этой функции? Если бы isSeen была глобальной, ещё понятно. А так, void функция и даже ни единого намёка на глобальную переменную, через которую это можно реализовать. Разве что BlockingTile там какую-то особую магию делает.
Понял...
Про точку... надо подумать...
А то как-то сразу это в голову не пришло...
А на счёт функции...
Это конечно...
Просто на скорую руку подправил...
Возвращает конечно она bool.
Сейчас поправлю...
Спасибо :)

Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 32 гостя