Нерестовые юниты в мире, производимом шума Перлина?

Есть некоторые проблемы, с которыми я столкнулся в моей игре на основе шума Perlin. Посмотрите на скриншот ниже.

Белые области, которые вы видите, - это стены, а черные области - для прогулок. Треугольник посередине - это игрок.

Я реализовал физику в этой игре, нарисовав ее на текстуре (белые или черные пиксели), а затем получив ее из процессора.

Однако сейчас я стою с другой проблемой под рукой. Я хочу, чтобы юниты (или крипы, как бы вы их ни называли) постоянно появлялись на краю экрана. Дело в том, что в финальной игре будет «туман войны», который не позволяет игроку видеть это далеко в любом случае.

Я подумал, что смогу просто отсканировать пиксели по краям экрана и посмотреть, является ли их физическая текстура черной, и затем случайным образом появиться там. Однако, если вы еще раз посмотрите на скриншот, есть (в верхнем левом углу) пример, где я не хотел бы, чтобы крипы появлялись (так как они не смогли бы добраться до игрока оттуда) ,

Можно ли каким-то образом заставить GPU определять эти точки появления для меня, или каким-то другим способом? Я думал о создании векторов между предложенной точкой на краю экрана и игроком, а затем следовал за ней каждые 10 вокселей и смотрел, сталкивается ли стена, прежде чем создать там юнит.

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

Есть предложения по этому вопросу?

Примечание 1 Для порожденных юнитов я не хочу использовать какую-либо форму поиска пути, чтобы избежать столкновений со стенами, поскольку эти юниты бегут к игроку. Следовательно, юниты должны появляться на краю экрана, в месте, где проход по прямой линии к игроку не сталкивался бы ни с какими стенами.

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

Это принцип, которому вы должны следовать для прохождения границы:

http://en.wikipedia.org/wiki/File:Marchsquares.png (я не могу пока публиковать фотографии)

Описание Википедии (хотя оно намного сложнее, поскольку используется с другими приложениями):

http://en.wikipedia.org/wiki/Marching_squares

Сделать заливку от позиции игрока; каждая область, которая «затоплена», является действительной игровой площадкой, а все остальные являются стенами.

РЕДАКТИРОВАТЬ: Что касается дополнительного требования «достижимо по прямой», имейте в виду, что в дискретном пространстве , вы должны определить это немного дальше. Например, все пути выше могут быть действительной «прямой линией» в такой среде, и я видел, как все они использовались в игре в тот или иной момент:

В частности, большинство из них не являются коммутативными - это означает, что просто потому, что вы можете достичь B из A по «прямой линии», не означает, что вы также можете достичь A из B; и противоположное не обязательно верно.

Кроме того, возникает вопрос о том, как вы справляетесь с диагональным движением, если блокируется одна или обе «боковые» точки.

Как насчет того, чтобы просто позволить появиться нерестам? Я не вижу особой проблемы в этом.

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

void straightlineFill(Point startPoint, Texture target)
{
    queue<Point> pointQueue;
    for (int dx = -1;dx <=1;dx ++)
            for(int dy = -1;dy <=1;dy++)
                if(dx != 0 && dy != 0)
                    pointQueue.push(point(startPoint.x + dx, startPoint.y + dy));
    while (!pointQueue.empty())
    {
        point front = pointQueue.front();
        pointQueue.pop();
        if (target.pixelAt(front) == COLOR_SPAWNABLE||
            target.pixelAt(front) == COLOR_WALL||
            target.pixelAt(front) == COLOR_NOT_SPAWNABLE)
                continue;
        taraget.setPixelAt(front, colorFilled); 
        for (int dx = -1;dx <=1;dx ++)
            for(int dy = -1;dy <=1;dy++)
                if(dx != 0 && dy != 0)
                    pointQueue.push(point(front.x + dx, front.y + dy));
        // up until now was the normal floodfill code
        // and here is the part that will do the real straight line checking

        // lineDX & lineDY will keep how much the line we are checking is skewed
        int lineDX = front.x - startPoint.x;
        int lineDY = front.y - startPoint.y;

        // step will show us how much we have to travel to reach each point of line
        point step;
        if (abs(lineDX) < abs(lineDY))
        {
            if (lineDX < 0)
                step = point(-1,0);
            if (lineDX == 0)
                if (lineDY < 0)
                    step = point(0,-1);
                else
                    step = point(0,1);
            if (lineDX > 0)
                step = point(1,0);
        }

        if (abs(lineDX) < abs(lineDY))
        {
            if (lineDY < 0)
                step = point(0,-1);
            if (lineDY == 0)
                if (lineDX < 0)
                    step = point(-1,0);
                else
                    step = point(1,0);
            if (lineDY > 0)
                step = point(0,1);
        }

        // moved will keep how much we have traveled so far, it's just some value that will speed up calculations and doesn't have any mathematical value
        point moved = 0;

        // spawnable will keep if the current pixel is a valid spawnpaint

        bool spawnable = true;

        // now we will travel on the straight line from player position to the edges of the map and check if whole line is valid spawn points or not.

        while (target.isInside(front))
        {
            front = front + step;
            moved = moved + point(step.x * lineDX, step.y * lineDY);
            if (step.x != 0 && moved.x < moved.y)
            {
                moved.x = moved.x - lineDY * sign(lineDY);
                front.y = front.y + sign(lineDY);
            }
            if (step.y != 0 && moved.y < moved.x)
            {
                moved.y = moved.y - lineDX * sign(lineDX);
                front.x = front.x + sign(lineDX);
            }

            if (target.getPixelAt(front) == COLOR_WALL)
                spawnable = false;

            if (spawnable)
            {
                target.setPixelAt(front,COLOR_SPAWNABLE);
                for (int dx = -1;dx <=1;dx ++)
                    for(int dy = -1;dy <=1;dy++)
                        if(dx != 0 && dy != 0)
                            pointQueue.push(point(front.x + dx, front.y + dy));             
            }
            else
            {
                target.setPixelAt(front,COLOR_NOT_SPAWNABLE);
            }
        }
    }
}

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

Это статические данные, поэтому вы можете их предварительно просчитать.

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

1. Горизонтальный: где оранжевый на синий меняется.
2. Вертикальный: где красный меняется от зеленого и оранжевого.

Вот то, что я на самом деле использовал в своей собственной игре (2-й мир, создаваемый симплексным шумом, почти в точности как у вас) - Rays. Начните с игрока, определите ориентацию (случайную, если хотите) и двигайтесь вдоль этой линии, пока не столкнетесь с чем-либо (край экрана ИЛИ астероид). Если вы нажмете край экрана (а не астероид / белый шарик), то вы поймете, что существует прямая, открытая линия от края экрана до игрока. Затем возьмите монстра в точке, в которую вы попали. Если вы попали в астероид, повторите тест.

Другое решение (не на GPU), которое вы можете использовать, - это поиск пути. Прежде чем рисовать карту, найдите путь от каждой потенциальной точки появления на каждом краю карты и посмотрите, есть ли путь к центру. * Поиск пути вполне приемлем по соотношению цена / производительность, но вы можете сделать это до начала игры, если это проблема.

Любая точка появления, у которой нет пути, может быть помещена в список исключений; или наоборот (любая точка с путем может быть включена в список включения).