2Д осуществления raycasting


Я реализовал алгоритм 2Д raycast в СФМЛ для обнаружения стен в 2D игры:

raycast

Как это работает

  1. Игрок может двигаться в любом направлении w s a d ключи. Курсор устанавливается плеер вектор направления, который рассчитывается от atan2() функция.

  2. Программа расчета следующей вертикальной и горизонтальной боковой расстояния, используя позицию игрока и касательных. Затем он сравнивает их квадратов (теорема Пифагора). Затем он выбирает низкой и перемещения луча по координатам. raycast

  3. Здесь начинается цикл raycast, программа проверяет, что луч направлен к стене. Когда луч указывает в право и вниз проблем нет, но когда он указывает вверх или влево нужно отремонтировать стены, проверяя, проверяя одну стену ранее.

  4. Если нет стены, то повторите шаг 2 и 3.

Код:

#include <SFML\Graphics.hpp>
#include <iostream>
#include <cassert>

using namespace sf;

const int MAP_W = 10;
const int MAP_H = 10;

const auto PI = acos(-1.0);

enum TileType
{
    EMPTY,
    BLOCKADE
};

//map data, 1 represents wall, 0 - no wall
int map[MAP_W][MAP_H] = 
{
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    { 1, 0, 0, 0, 1, 1, 0, 0, 0, 1 },
    { 1, 0, 0, 0, 1, 0, 0, 1, 0, 1 },
    { 1, 0, 0, 0, 1, 1, 1, 1, 0, 1 },
    { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
    { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 },
    { 1, 0, 0, 0, 0, 0, 1, 0, 0, 1 },
    { 1, 0, 1, 0, 0, 1, 0, 1, 0, 1 },
    { 1, 0, 1, 0, 0, 1, 0, 0, 0, 1 },
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
};

sf::Vector2i playerMapPos = { 5, 5 };
sf::Vector2f playerWorldPos;

sf::Vector2f tileSize;

//check window events
void checkEvents(RenderWindow & gameWindow)
{
    Event event;
    while (gameWindow.pollEvent(event))
    {
        if (event.type == Event::Closed)
            gameWindow.close();
    }
}

//update player movement
void updateSteering()
{
    float speed = 5.0f;

    if (Keyboard::isKeyPressed(Keyboard::Key::W))
    {
        playerWorldPos -= sf::Vector2f{ 0.0f, 1.0f } *speed;
    }

    if (Keyboard::isKeyPressed(Keyboard::Key::S))
    {
        playerWorldPos += sf::Vector2f{ 0.0f, 1.0f } *speed;
    }

    if (Keyboard::isKeyPressed(Keyboard::Key::A))
    {
        playerWorldPos -= sf::Vector2f{ 1.0f, 0.0f } *speed;
    }

    if (Keyboard::isKeyPressed(Keyboard::Key::D))
    {
        playerWorldPos += sf::Vector2f{ 1.0f, 0.0f } *speed;
    }

    playerMapPos = { (int)(playerWorldPos.x / tileSize.x), (int)(playerWorldPos.y / tileSize.y) };
}

//get raycast closest hit point
sf::Vector2f getDistToClosestHitPoint(float angle, sf::Vector2i rayMapPos, sf::Vector2f rayWorldPos)
{
    sf::Vector2f rayDir = { cos(angle), sin(angle) };

    float dyh = 0; //dist y to next horizontal tile
    float dxh = 0; //dist x to next horizontal tile

    if (rayWorldPos.y == rayMapPos.y * tileSize.y)
    {
        dyh = tileSize.y;
    }
    else
    {
        if (rayDir.y < 0) dyh = rayWorldPos.y - (rayMapPos.y * tileSize.y);
        else           dyh = (rayMapPos.y + 1) * tileSize.y - rayWorldPos.y;
    }

    dxh = dyh / tan(angle);
    if (rayDir.y < 0) //invert distances values when pointing upwards
    {
        dxh = -dxh;
        dyh = -dyh;
    }

    float dyv = 0; //dist y to next vertical tile
    float dxv = 0; //dist x to next vertical tile

    if (rayWorldPos.x == rayMapPos.x * tileSize.x)
    {
        dxv = tileSize.x;
    }
    else
    {
        if (rayDir.x < 0) dxv = rayWorldPos.x - (rayMapPos.x * tileSize.x);
        else           dxv = (rayMapPos.x + 1) * tileSize.x - rayWorldPos.x;
    }

    dyv = dxv * tan(angle);
    if (rayDir.x < 0) //invert distances values when pointing upwards
    {
        dxv = -dxv;
        dyv = -dyv;
    }

    //calc squares and compare them
    float sqrLenHor = dxh * dxh + dyh * dyh;
    float sqrLenVer = dxv * dxv + dyv * dyv;

    //select distances which squares are lower
    float dx = sqrLenHor < sqrLenVer ? dxh : dxv;
    float dy = sqrLenHor < sqrLenVer ? dyh : dyv;

    return { dx, dy };
}

void drawMap(RenderWindow & gameWindow)
{
    for (int y = 0; y < MAP_H; y++)
    {
        for (int x = 0; x < MAP_W; x++)
        {
            RectangleShape tile(tileSize);
            tile.setPosition(x * tileSize.x, y * tileSize.y);
            tile.setOutlineThickness(1.0f);
            tile.setOutlineColor(sf::Color::Black);

            //we need to check by [y][x] to draw correctly because of array structure
            if (map[y][x] == TileType::BLOCKADE)
            {
                //if map[y][x] is blockade, make it black
                tile.setFillColor(sf::Color::Black);
                tile.setOutlineColor(sf::Color::White);
            }

            gameWindow.draw(tile);
        }
    }
}

void visualizePlayerRaycast(RenderWindow & gameWindow)
{
    //draw line going from player position to next hit positions
    VertexArray hitLines(LinesStrip);
    hitLines.append({ playerWorldPos, Color::Red });

    //get mouse pos
    auto mousePos = Mouse::getPosition(gameWindow);

    //get player rotation angle and direction vector
    float angle = atan2(mousePos.y - playerWorldPos.y, mousePos.x - playerWorldPos.x);
    sf::Vector2f dir = { cos(angle), sin(angle) };

    //get distance to first hit point
    sf::Vector2f dist = getDistToClosestHitPoint(angle, playerMapPos, playerWorldPos);

    //first ray hit position coordinates
    sf::Vector2f rayWorldPos = { playerWorldPos.x + dist.x, playerWorldPos.y + dist.y };
    sf::Vector2i rayPosMap = { int(rayWorldPos.x / tileSize.x), int(rayWorldPos.y / tileSize.y) }; //just divide world coordinates by tile size

    bool hit = false;

    //raycast loop
    while (!hit)
    {
        //drawing ray hit lines
        hitLines.append({ { rayWorldPos.x, rayWorldPos.y }, sf::Color::Red });

        //drawing hit point circles
        CircleShape hitPoint(5);
        hitPoint.setOrigin({ 5, 5 });
        hitPoint.setPosition({ rayWorldPos.x, rayWorldPos.y });
        hitPoint.setFillColor(sf::Color::Red);
        gameWindow.draw(hitPoint);

        //out of array range exceptions handling
        if (rayPosMap.x < 0 || rayPosMap.x >= MAP_W || rayPosMap.y < 0 || rayPosMap.y >= MAP_H) break;

        //checking that actually hit side is wall side
        int hitTileX = rayPosMap.x;
        int hitTileY = rayPosMap.y;

        //fix checking walls when hit them on their right or bottom side, check walls earlier them
        if (rayWorldPos.x == rayPosMap.x * tileSize.x && dir.x < 0) //hit wall left side
        {
            hitTileX--;
        }

        if (rayWorldPos.y == rayPosMap.y * tileSize.y && dir.y < 0) //hit wall up side
        {
            hitTileY--;
        }

        if (map[hitTileY][hitTileX] == BLOCKADE)
        {
            hit = true; //end raycasting loop
        }
        else
        {
            //move ray to next closest horizontal or vertical side
            sf::Vector2f dist = getDistToClosestHitPoint(angle, { rayPosMap.x, rayPosMap.y }, { rayWorldPos.x, rayWorldPos.y });

            //draw triangle for better visualization of distance
            sf::VertexArray triangleVisual(LinesStrip);
            triangleVisual.append({ { rayWorldPos.x, rayWorldPos.y }, Color::Magenta });
            triangleVisual.append({ { rayWorldPos.x + dist.x, rayWorldPos.y }, Color::Magenta });
            triangleVisual.append({ { rayWorldPos.x + dist.x, rayWorldPos.y + dist.y }, Color::Magenta });
            gameWindow.draw(triangleVisual);

            //apply new move 
            rayWorldPos.x += dist.x;
            rayWorldPos.y += dist.y;

            //update map positions
            rayPosMap.x = rayWorldPos.x / tileSize.x;
            rayPosMap.y = rayWorldPos.y / tileSize.y;
        }
    }


    gameWindow.draw(hitLines);
}

void render(RenderWindow & gameWindow)
{
    gameWindow.clear(Color::White);
    drawMap(gameWindow);

    //draw player
    CircleShape player(25);
    player.setOrigin({ 25, 25 });
    player.setPosition(playerWorldPos);
    player.setFillColor(sf::Color::Black);
    gameWindow.draw(player);

    visualizePlayerRaycast(gameWindow);
    gameWindow.display();
}

int main()
{
    RenderWindow gameWindow(VideoMode(1000, 800), "Raycast Test");
    gameWindow.setFramerateLimit(60);

    //initialization
    tileSize = { (float)gameWindow.getView().getSize().x / MAP_W, (float)gameWindow.getView().getSize().y / MAP_H };
    playerWorldPos = { playerMapPos.x * tileSize.x, playerMapPos.y * tileSize.y, };

    while (gameWindow.isOpen())
    {
        checkEvents(gameWindow);
        updateSteering();
        render(gameWindow);
    }
}

Я хочу знать, как я могу оптимизировать его. Это реализуется правильно?



1977
5
задан 28 марта 2018 в 11:03 Источник Поделиться
Комментарии
2 ответа

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

Хотя вы будете иметь, чтобы адаптировать ее для своих целей, есть способ для препроцесса линия подходит, что вы можете прочитать в статье "быстрый правило на основе параметра бесплатный дискретного преобразования Хафа" по Genswein & Янг (1999):

https://www.researchgate.net/publication/220359297_A_Fast_Rule-Based_Parameter_Free_Discrete_Hough_Transform

Коротко говоря, ваш код будет вычислять все возможные линии визирования до лабиринтах или игра появится на экране впервые. Вы могли бы почти наверняка упростит линия-сторона, упомянутых в вышеуказанной газете технику, но общая техника стоит знать как средство для препроцесса вписывается в 2D цифрового изображения.


  1. Для каждого пиксела, присвоить двоичное представление всех цифровых линий, которые проходят через этот пиксель в некоторых собой сетку пикселей. (Вы можете использовать ваше полное сетки 10х10; ломая сетку в подсеток представляет некоторую сложность.)

  2. В вашем случае, представляют собой скорее не линии, а просто от края до края представление с использованием нумерации схеме, описанной в статье, отслеживать одновременно от края до края отрезка линии, а также допустимые конечные точки в вашей белый/черный (открытые/закрытые, доступные/заблокирован) сетки.

  3. Для каждого пикселя, поддерживают контейнер (например, карта, хэш, список, массив) разрешенных ходов.

  4. На ввод с клавиатуры, проверьте правильность разрешено двигаться.

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

Техника выше позволит за динамику перемещения и для проверки прямой видимости из любой точки.

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


  1. Начнем с методов, описанных выше для сетки 10х10, потом введут какую-то логику для предварительного расчета крайних случаях.

  2. Создайте тонкие линии визирования сетки. Ваш персонаж может двигаться в сетку 10х10, но свет визирования сетки может быть что-то вроде 100х100. Дискретное преобразование Хафа метод описал выше работает (произвольно) большие сетки, но это требует действия, чтобы сломать основной сетке на более мелкие сетки, а затем объединить результаты.

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


  • Полигон/пересечение линии. Ваши Черные блоки представляют собой один или более связанных контуров. Есть методы для проверки линии видимости отдельных пикселей сродни расчете полигон/линия пересечения.

  • В OpenGL. Создает 2D OpenGL для отображения 3D сцены с использованием или орто или перспективных проекций. Персонаж в игре бы видеть мир в качестве перспективной проекции. Учитывая 2D изображение в 3D-мире, вы можете использовать восьмеричного дерева набора или красно-черное дерево или какой-либо другой метод, чтобы быстро вычислить перекрестках. (Это нужно иметь в виду, если вы делаете движение от 2D к 3D игр.)

  • Радиальная "отливка закрутки": для каждой дискретной точке (x,y), которое персонаж может занимать, бросания лучей каждые N градусов. Вычислить точку, в которой каждый луч пересекает стену (см. полигон/выше пересечение линией). За что (Х,Y) точки, поддерживать карту, разрешенных направления движения. Сопоставьте эти направленные движения (например, 45 градусов вправо и вниз) в комбинации с клавиатуры. Если вы только Позвольте вверх, вниз, влево, вправо, чтобы создать восемь направлений, у вас не так много бросает, чтобы вычислить.

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

Подведем итоги:


  • Предварительное вычисление допустимых ходов или искать маршрут для каждого пикселя (Х,Y). Являются ли эти рассчитываются при генерации сцены, или расчетную, а затем сериализации/десериализации в/из диска зависит от вашего приложения.

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

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

Удачи!

1
ответ дан 3 апреля 2018 в 11:04 Источник Поделиться

1) Raycasting должен быть ультра быстрая

Чтобы сохранить трассировки лучей быстрее в более крупных карт или даже в 3D-карты, рекомендуется использовать бит-сдвиг вместо умножения/деления или даже некоторые сборки модулей.

Тригонометрические функции в ваши процедуры также время дорого, рассмотрите возможность использования тригонометрических таблиц для синуса, Косинуса и тангенса. Например float sin[]= {0.0,0.26,0.5,0.707 ...} corresponding to 0,15,30,45....,360 degrees упрощение углом кратным 15 градусов.

2) кадр анимации должен быть неизменным

Скорость анимации будет меняться от системы к системе. Рассмотреть измерение промежуток между рендеры подряд и держать добавочный размер шага же. Это также гарантирует, что ваша скорость анимации будет оставаться таким же, во всех устройствах.

3) используют двойную буферизацию для мерцания анимации

Использование перерисовка фона и переднего плана в каждый проход. Хотя графика СФМЛ основан на OpenGL, это может привести к не столь плавная анимация. Вы можете использовать двойную буферизацию, чтобы нарисовать следующий кадр вперед в памяти для плавной отрисовки.

1
ответ дан 28 марта 2018 в 05:03 Источник Поделиться