Поле зрения

Материал из Клуб любителей рогаликов
Перейти к: навигация, поиск

Данная статья была написана для RLNews Darren'а Hebden'а

Написана Rйgis Dubois 19/07/99.
email: heroicjourneys@altern.org
homepage: www.altern.org/heroicjourneys
Все исходники на Си. Используйте их при желании!

Окей, это другая статья, связанная с знаменитой проблемой "линии зрения" ("line of sight"). Зачем нужна такая статья? Затем, что даже со всей предоставляемой по интернету помощью я был не в состоянии найти легкое и эффективное решение для этой задачи. Итак, здесь я объясню свой метод. Это ОЧЕНЬ простой метод, договорились? Это означает, что он возможно медленный, что результат не очень точный но он легко должен осуществим и понятен. Так что хватит разговоров и давайте начнём!

<< Ах... да, и последнее. Простите мой слабый английский, но я француз и как и многие из вас знают, парни, французы не слишком известны своими достижениями в английском :) >>

Примечание: во всех примерах мы будем использовать следующие структуры:

struct coord
{
  int x,y;
};

struct map
{
  int data[line][col];
  short visible[line][col]; 0 - невидимый, 1 - видимый
};

Хорошо, мы хотим, выделить вокруг персонажа область, представляющую что он может видеть. Это означает, что наш персонаж сможет видеть каждое из пустых пространств или монстров на его линии зрения, но не сможет видеть что находится за стенами или закрытыми дверями. Как это сделать? Хорошо, мы просто бросим от персонажа несколько лучей по кругу, чтобы они покрыли всё, что может видеть игрок. Эй! Я слышу, что вы сейчас закричите! Вы думаете "Круг? Так, мы собираемся использовать cos и sin, а?". Хорошо, вы правы, они нам нужны, но мы не позволим CPU вычислять их во время работы, мы используем заранее сгенерированный массив, что мы потеряем в памяти, мы приобретём в скорости:

const double Pi = 3.1415926535; //нужно объяснять, что это такое?
//  массивы заполненные с градацией по 5 градусов. 5*72=360
double Cosinus[71];
double Sinus[71];

Почему разбиение 5 градусов? Хорошо, а почему бы и нет? Я нашёл его эффективным или вроде того, но вы можете разбить его так, чтобы это заполняло ваш радиус зрения.

Теперь, давайте создадим массив:

void GenerateTables()
{
  int i;

  for (i=0;i<72;i++)
  {
 Cosinus[i]=cos(i*5*Pi/180);
  }
  for (i=0;i<72;i++)
  {
 Sinus[i]=sin(i*5*Pi/180);
  }
}

Думаю, мне не нужно объяснять данную функцию..

Прекрасно, теперь нам нужна функция для правильного округления double. Например, если у нас 2,3 мы хотим, чтобы функция возвращала нам 2, а если у нас 2,6 мы хотим, чтобы функция возвращала нам 3. Я проверил все стандартные библиотеки в Cи, но не смог найти ни одной. Если вы знаете хоть одну, пожалуйста, сообщите мне по email'у!

//Округление числа до ближайшего целого.
int round(double x)
{
  double b;

   if (modf(x,&b)>0.5)
    return((int)b+1);
  else
    return((int)b);
}

Следующий шаг должен получить координаты луча, который мы будем откладывать. Мы отложим его от игрока, под определенным углом. Итак, у нас есть начало линии, которую мы откладываем (x,y игрока) но мы хотим получить координаты конца линии. Вот функция, которая нам их выдаст:

struct coord CastRay(int x,int y,int r, int angle)
{
struct coord c;
c.x=round(x+r*Cosinus[(int)angle/5]);
c.y=round(y-r*Sinus[(int)angle/5]);
return (c);
}

Эй парни, вы понимаете это? Это же простая геометрия! Небольшая проекция. Пожалуйста обратите внимание, что здесь r радиан или длина луча, который мы откладываем. Это означает дипазон зрения.

Хорошо, мы имеем координаты луча, который мы хотим отложить, так что нам нужно отложить его. Для этого мы используем хорошо известный линейный алгоритм Bresenham'а. Вот программа линии зрения, я поясню её позже:

int Sgn(int x)
{
  if (x==0) return(0);
  if (x>0) return(1);
  if (x<0) return(-1);
}

// Процедура Line of Sight.
struct Map Los(struct Map m,int x1,int y1,int x2,int y2)
{
  int i,j,dx,dy,sdx,sdy,dxabs,dyabs,x,y,px,py;

  dx=x2-x1;
  dy=y2-y1;
  dxabs=abs(dx);
  dyabs=abs(dy);
  sdx=Sgn(dx);
  sdy=Sgn(dy);
  x=dyabs/2;
  y=dxabs/2;
  px=x1;
  py=y1;
  if (dxabs>=dyabs)
  {
    for (i=0;i<dxabs;i++)
    {
      y+=dyabs;
      if (y>=dxabs)
      {
        y-=dxabs;
        py+=sdy;
      }
       px+=sdx;
      if (m.visible[py][px]==0) //тайл видим?
      {//no?
       m.visible[py][px]=1;  //нет
       PutTile(px,py,m.data[py][px]); //рисуем тайл на экране
      }
      //если здесь не пусто или не открытая дверь, остановка...
      if (m.data[py][px]!=Empty && m.data[py][px]!=OpenDoor) 
      return(m);
    }
  }   
  else 
  {
    for (i=0;i<dyabs;i++)
    {
       x+=dxabs;
       if (x>dyabs)
       {
         x-=dyabs;
         px+=sdx;
       }
       py+=sdy;
       if (m.visible[py][px]==0)
       {
         m.visible[py][px]=1;
         PutTile(px,py,m.data[py][px]);
       }
       if (m.data[py][px]!=Empty && m.data[py][px]!=OpenDoor)
         return(m);
    }
  }
  return(m);
}

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

Хорошо это была трудная часть, теперь давайте завершим написанием функции LookAround(), которая отложит 72 луча от игрока чтобы они образовали круг и следовательно, поле зрения:

void LookAround()
{
  struct coord c;
  int i;

  for (i=0;i<72;i++)
  {
     //мы получаем координаты линии зрения
     c=CastRay(p.px,p.py,p.sight,i*5); 
     map=Los(map,player.px,player.py,c.x,c.y); 
  };
}

И вот, всё готово! Я знаю, что вы можете счесть этот метод не самым быстрым, но это несомненно работает поскольку я использую это в моем собственном roguelike проекте. Я надеюсь, что объяснения были не слишком темны... Если так, пишите мне на e-mail.

http://www.altern.org/heroicjourneys

Удачи! Regis.



Автор: Regis Dubois.
Источник: Field Of Vision.
Перевел: Дмитрий О. Бужинский [Bu], 23.05.2005.