Исходник Софт Прорыв из всех прорывов, навигационная сетка

[Tectrex]

Этот код — навигационная система для игры, которая строит сетку из точек, по которым можно перемещаться.

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

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

Алгоритм работает так: сначала он инициализирует сетку, вычисляет размеры и центрирует её. потом, когда ты двигаешься, он обновляет узлы вокруг тебя. если узел устарел или его нет, он создаёт новый и обновляет его связи с соседями. для каждого узла он проверяет высоту с помощью функции, которая смотрит, есть ли прямая видимость между двумя точками. если высота найдена, он добавляет её в узел. потом он проверяет, можно ли пройти к соседям (прямая видимость и разница высот не слишком большая). если можно, он добавляет связь между узлами. ЩЫЫЩПЗЫЩПЗЫПЩЩХЫП ля прикол как же тупо юзать процесс лайн оф сайт, но работает же!

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

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

В общем КОД ГОВНО вот эти все nav.mesh[idx][NODE_NEIGHBORS][idx_nei] это что за пиздец? почему нельзя было сделать нормальные структуры данных? сука работает - не трогай, вызовы на каждом кадре? это rocket science, блять. Если что-то не работает, то это не баг, это фича. но в этом коде фич больше, чем в раннем доступе киберпанка сука на релизе.

Код открыт балуйтесь 🥸
Юзать: /path x y z координаты без запятых вводить

ворк только онфут

Rei котеночек спасибо тебе за способ каста сетки

 

[Vespan]

Оно в реальном времени без лагов будет работать, если внезапно появилось припятсвие - обойдет? Или сетка создается только раз при /path
Можно еще сделать прыжок как и банихоп так и перепрыгивать припятсвия если это поможет быстрее добратся к точке назначения

Можно было как модуль сделать

 

[Tectrex]

Оно в реальном времени без лагов будет работать, если внезапно появилось припятсвие - обойдет? Или сетка создается только раз при /path

Можно было как модуль сделать

Сетка обновляется в реальном времени, но с задержкой из-за map_update_rate. Если препятствие появится, система его обойдет, но только после обновления сетки. Лаги неизбежны

 

[Azller Lollison]

разъебалово, рял мощно

 

[Acerdragons]

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

Пара вопросов:
- Т.к при увеличении сетки из Терминатора (тоже пытался) фпс становится все меньше, поэтому хотел попробовать "Запечь" все эти грани, просчитать их один раз и сохранить в файл. Получится ли реализовать такой функционал здесь? ИМХО, позволит анализировать кастомные карты и не упираться в постоянный прострел лучами и получить лаги;
- Еще насколько помню Rei выставит угол наклона для сетки 45 градусов, но методом тыка понял, что можно поставить 60, и в некоторых местах бот стал проходить лучше;
- Хотел затестить скрипт, но при вводе /path и координат ничего не выдает, не в консоли, нигде. Координаты вводил те, которые в зоне видимости сетки;

 

[Tectrex]

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

Пара вопросов:
- Т.к при увеличении сетки из Терминатора (тоже пытался) фпс становится все меньше, поэтому хотел попробовать "Запечь" все эти грани, просчитать их один раз и сохранить в файл. Получится ли реализовать такой функционал здесь? ИМХО, позволит анализировать кастомные карты и не упираться в постоянный прострел лучами и получить лаги;
- Еще насколько помню Rei выставит угол наклона для сетки 45 градусов, но методом тыка понял, что можно поставить 60, и в некоторых местах бот стал проходить лучше;
- Хотел затестить скрипт, но при вводе /path и координат ничего не выдает, не в консоли, нигде. Координаты вводил те, которые в зоне видимости сетки;

Запечь грани, это очень интересно, но подойдет только для тех мест, где не может появится лишнее препятствие. На условной улице, ты запечешь грани, но тут появится огромный объект, который не был просчитан, вот. Насчет работоспособности, алгоритм иногда не можешь просчитать путь, даже когда все находится внутри сетки, честно не знаю почему так, долго копался, и забил, залил в исходник, буду рад если кто-то это будет разбирать и фиксить мои ошибки. Чтобы потом люди делали умных ботов которые могут подстраиваться под любые изменения в карте без внешних вмешательств кодера.

 

[UBP]

эвристика не учитывает рельеф местности, а так-же ты используешь astar который для больших расстояний не оптимизирован и потребляет очень много памяти, из-чего если ввести координаты которые очень далеко от тебя словишь краш.
Вместо него мог использовать RRT (Rapidly-exploring Random Tree Star)
Почему не в виде модуля?
Пример rrt из fivetuning

local public = {}

function public.getDistance(x1,y1,z1,x2,y2,z2)
    return math.sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2) + (z1 - z2)*(z1 - z2))
end

function public.isValidPosition(position)
    local x, y, z = position[1], position[2], position[3]
    local groundZ = getGroundZFor3dCoord(x, y, z)
    return math.abs(z - groundZ) <= 5
end

function public.adaptiveStepSize(current, goal)
    local distance = public.GetDistance(current[1], current[2], current[3], goal[1], goal[2], goal[3])
    return math.min(5, math.max(1, distance / 10))
end

function public.smoothPath(path)
    local smoothedPath = {}
    for i = 2, #path - 2 do
        local p0, p1, p2, p3 = path[i-1], path[i], path[i+1], path[i+2]
        for t = 0, 1, 0.1 do
            local t2 = t * t
            local t3 = t2 * t
            local x = 0.5 * ((2 * p1[1]) + (-p0[1] + p2[1]) * t + (2*p0[1] - 5*p1[1] + 4*p2[1] - p3[1]) * t2 + (-p0[1] + 3*p1[1] - 3*p2[1] + p3[1]) * t3)
            local y = 0.5 * ((2 * p1[2]) + (-p0[2] + p2[2]) * t + (2*p0[2] - 5*p1[2] + 4*p2[2] - p3[2]) * t2 + (-p0[2] + 3*p1[2] - 3*p2[2] + p3[2]) * t3)
            local z = 0.5 * ((2 * p1[3]) + (-p0[3] + p2[3]) * t + (2*p0[3] - 5*p1[3] + 4*p2[3] - p3[3]) * t2 + (-p0[3] + 3*p1[3] - 3*p2[3] + p3[3]) * t3)
            table.insert(smoothedPath, {x, y, z})
        end
    end
    return smoothedPath
en


function public.rrtStarSearch(startX, startY, startZ, endX, endY, endZ, maxIterations)
    local tree = {{startX, startY, startZ}}
    local parent = {}
    local cost = {[1] = 0}

    local function getSquaredDistance(x1, y1, z1, x2, y2, z2)
        return (x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2
    end

    local function GetDistance(x1, y1, z1, x2, y2, z2)
        return math.sqrt(getSquaredDistance(x1, y1, z1, x2, y2, z2))
    end

    local function nearestNeighbors(point, radius)
        local neighbors = {}
        local squaredRadius = radius * radius
        for i, treePoint in ipairs(tree) do
            if getSquaredDistance(point[1], point[2], point[3], treePoint[1], treePoint[2], treePoint[3]) <= squaredRadius then
                table.insert(neighbors, i)
            end
        end
        return neighbors
    end

    local function adaptiveStepSize(current, goal)
        local distance = public.GetDistance(current[1], current[2], current[3], goal[1], goal[2], goal[3])
        return math.min(5, math.max(1, distance / 10))
    end

    local goalVector = {endX - startX, endY - startY, endZ - startZ}
    local goalDistance = math.sqrt(goalVector[1]^2 + goalVector[2]^2 + goalVector[3]^2)
    goalVector[1], goalVector[2], goalVector[3] = goalVector[1]/goalDistance, goalVector[2]/goalDistance, goalVector[3]/goalDistance

    local function adaptiveBias(iteration)
        return math.max(0.1, 1 - iteration / maxIterations)
    end

    for i = 1, maxIterations do
        local randomPoint
        local bias = adaptiveBias(i)
        if math.random() < bias then
            randomPoint = {
                startX + goalVector[1] * goalDistance * math.random(),
                startY + goalVector[2] * goalDistance * math.random(),
                startZ + goalVector[3] * goalDistance * math.random()
            }
        else
            randomPoint = {
                startX + (endX - startX) * math.random(),
                startY + (endY - startY) * math.random(),
                startZ + (endZ - startZ) * math.random()
            }
        end

        -- ближайшая точка в дереве
        local nearestIndex, minSquaredDist = 1, math.huge
        for j, point in ipairs(tree) do
            local squaredDist = getSquaredDistance(point[1], point[2], point[3], randomPoint[1], randomPoint[2], randomPoint[3])
            if squaredDist < minSquaredDist then
                minSquaredDist, nearestIndex = squaredDist, j
            end
        end

        -- создаем новую точку в направлении случайной точки
        local nearestPoint = tree[nearestIndex]
        local stepSize = public.adaptiveStepSize(nearestPoint, randomPoint)
        local dx, dy, dz = randomPoint[1] - nearestPoint[1], randomPoint[2] - nearestPoint[2], randomPoint[3] - nearestPoint[3]
        local length = math.sqrt(dx*dx + dy*dy + dz*dz)
        local newPoint = {
            nearestPoint[1] + dx / length * stepSize,
            nearestPoint[2] + dy / length * stepSize,
            nearestPoint[3] + dz / length * stepSize
        }

        -- Проверяем, можно ли добавить новую точку
        if public.isValidPosition(newPoint) and isLineOfSightClear(nearestPoint[1], nearestPoint[2], nearestPoint[3], newPoint[1], newPoint[2], newPoint[3], true, false, false, true, false, false, false) then
            local newIndex = #tree + 1
            tree[newIndex] = newPoint

            -- Находим лучшего родителя
            local minCost = cost[nearestIndex] + public.GetDistance(nearestPoint[1], nearestPoint[2], nearestPoint[3], newPoint[1], newPoint[2], newPoint[3])
            parent[newIndex] = nearestIndex
            cost[newIndex] = minCost

            -- Улучшение: Динамический радиус поиска соседей
            local searchRadius = math.min(20, 20 * (1 - i / maxIterations) + 5)
            local neighbors = public.nearestNeighbors(newPoint, searchRadius)

            for _, neighborIndex in ipairs(neighbors) do
                local neighborPoint = tree[neighborIndex]
                if isLineOfSightClear(neighborPoint[1], neighborPoint[2], neighborPoint[3], newPoint[1], newPoint[2], newPoint[3], true, false, false, true, false, false, false) then
                    local tentativeCost = cost[neighborIndex] + public.GetDistance(neighborPoint[1], neighborPoint[2], neighborPoint[3], newPoint[1], newPoint[2], newPoint[3])
                    if tentativeCost < minCost then
                        parent[newIndex], minCost = neighborIndex, tentativeCost
                    end
                end
            end
            cost[newIndex] = minCost

            -- Перепроверяем соседей
            for _, neighborIndex in ipairs(neighbors) do
                local neighborPoint = tree[neighborIndex]
                if isLineOfSightClear(newPoint[1], newPoint[2], newPoint[3], neighborPoint[1], neighborPoint[2], neighborPoint[3], true, false, false, true, false, false, false) then
                    local tentativeCost = minCost + public.GetDistance(newPoint[1], newPoint[2], newPoint[3], neighborPoint[1], neighborPoint[2], neighborPoint[3])
                    if tentativeCost < cost[neighborIndex] then
                        parent[neighborIndex], cost[neighborIndex] = newIndex, tentativeCost
                    end
                end
            end

            -- Оптимизация: Проверяем достижение цели с использованием квадрата расстояния
            if getSquaredDistance(newPoint[1], newPoint[2], newPoint[3], endX, endY, endZ) < 25 then
                -- Восстанавливаем путь
                local path, current = {newPoint}, newIndex
                while parent[current] do
                    current = parent[current]
                    table.insert(path, 1, tree[current])
                end
                return public.smoothPath(path)
            end
        end
    end

    return nil  -- Путь не найден
end
return public

 

[Musaigen]

эвристика не учитывает рельеф местности, а так-же ты используешь astar который для больших расстояний не оптимизирован и потребляет очень много памяти, из-чего если ввести координаты которые очень далеко от тебя словишь краш.
Вместо него мог использовать RRT (Rapidly-exploring Random Tree Star)
Почему не в виде модуля?
Пример rrt из fivetuning

local public = {}

function public.getDistance(x1,y1,z1,x2,y2,z2)
    return math.sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2) + (z1 - z2)*(z1 - z2))
end

function public.isValidPosition(position)
    local x, y, z = position[1], position[2], position[3]
    local groundZ = getGroundZFor3dCoord(x, y, z)
    return math.abs(z - groundZ) <= 5
end

function public.adaptiveStepSize(current, goal)
    local distance = public.GetDistance(current[1], current[2], current[3], goal[1], goal[2], goal[3])
    return math.min(5, math.max(1, distance / 10))
end

function public.smoothPath(path)
    local smoothedPath = {}
    for i = 2, #path - 2 do
        local p0, p1, p2, p3 = path[i-1], path[i], path[i+1], path[i+2]
        for t = 0, 1, 0.1 do
            local t2 = t * t
            local t3 = t2 * t
            local x = 0.5 * ((2 * p1[1]) + (-p0[1] + p2[1]) * t + (2*p0[1] - 5*p1[1] + 4*p2[1] - p3[1]) * t2 + (-p0[1] + 3*p1[1] - 3*p2[1] + p3[1]) * t3)
            local y = 0.5 * ((2 * p1[2]) + (-p0[2] + p2[2]) * t + (2*p0[2] - 5*p1[2] + 4*p2[2] - p3[2]) * t2 + (-p0[2] + 3*p1[2] - 3*p2[2] + p3[2]) * t3)
            local z = 0.5 * ((2 * p1[3]) + (-p0[3] + p2[3]) * t + (2*p0[3] - 5*p1[3] + 4*p2[3] - p3[3]) * t2 + (-p0[3] + 3*p1[3] - 3*p2[3] + p3[3]) * t3)
            table.insert(smoothedPath, {x, y, z})
        end
    end
    return smoothedPath
en


function public.rrtStarSearch(startX, startY, startZ, endX, endY, endZ, maxIterations)
    local tree = {{startX, startY, startZ}}
    local parent = {}
    local cost = {[1] = 0}

    local function getSquaredDistance(x1, y1, z1, x2, y2, z2)
        return (x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2
    end

    local function GetDistance(x1, y1, z1, x2, y2, z2)
        return math.sqrt(getSquaredDistance(x1, y1, z1, x2, y2, z2))
    end

    local function nearestNeighbors(point, radius)
        local neighbors = {}
        local squaredRadius = radius * radius
        for i, treePoint in ipairs(tree) do
            if getSquaredDistance(point[1], point[2], point[3], treePoint[1], treePoint[2], treePoint[3]) <= squaredRadius then
                table.insert(neighbors, i)
            end
        end
        return neighbors
    end

    local function adaptiveStepSize(current, goal)
        local distance = public.GetDistance(current[1], current[2], current[3], goal[1], goal[2], goal[3])
        return math.min(5, math.max(1, distance / 10))
    end

    local goalVector = {endX - startX, endY - startY, endZ - startZ}
    local goalDistance = math.sqrt(goalVector[1]^2 + goalVector[2]^2 + goalVector[3]^2)
    goalVector[1], goalVector[2], goalVector[3] = goalVector[1]/goalDistance, goalVector[2]/goalDistance, goalVector[3]/goalDistance

    local function adaptiveBias(iteration)
        return math.max(0.1, 1 - iteration / maxIterations)
    end

    for i = 1, maxIterations do
        local randomPoint
        local bias = adaptiveBias(i)
        if math.random() < bias then
            randomPoint = {
                startX + goalVector[1] * goalDistance * math.random(),
                startY + goalVector[2] * goalDistance * math.random(),
                startZ + goalVector[3] * goalDistance * math.random()
            }
        else
            randomPoint = {
                startX + (endX - startX) * math.random(),
                startY + (endY - startY) * math.random(),
                startZ + (endZ - startZ) * math.random()
            }
        end

        -- ближайшая точка в дереве
        local nearestIndex, minSquaredDist = 1, math.huge
        for j, point in ipairs(tree) do
            local squaredDist = getSquaredDistance(point[1], point[2], point[3], randomPoint[1], randomPoint[2], randomPoint[3])
            if squaredDist < minSquaredDist then
                minSquaredDist, nearestIndex = squaredDist, j
            end
        end

        -- создаем новую точку в направлении случайной точки
        local nearestPoint = tree[nearestIndex]
        local stepSize = public.adaptiveStepSize(nearestPoint, randomPoint)
        local dx, dy, dz = randomPoint[1] - nearestPoint[1], randomPoint[2] - nearestPoint[2], randomPoint[3] - nearestPoint[3]
        local length = math.sqrt(dx*dx + dy*dy + dz*dz)
        local newPoint = {
            nearestPoint[1] + dx / length * stepSize,
            nearestPoint[2] + dy / length * stepSize,
            nearestPoint[3] + dz / length * stepSize
        }

        -- Проверяем, можно ли добавить новую точку
        if public.isValidPosition(newPoint) and isLineOfSightClear(nearestPoint[1], nearestPoint[2], nearestPoint[3], newPoint[1], newPoint[2], newPoint[3], true, false, false, true, false, false, false) then
            local newIndex = #tree + 1
            tree[newIndex] = newPoint

            -- Находим лучшего родителя
            local minCost = cost[nearestIndex] + public.GetDistance(nearestPoint[1], nearestPoint[2], nearestPoint[3], newPoint[1], newPoint[2], newPoint[3])
            parent[newIndex] = nearestIndex
            cost[newIndex] = minCost

            -- Улучшение: Динамический радиус поиска соседей
            local searchRadius = math.min(20, 20 * (1 - i / maxIterations) + 5)
            local neighbors = public.nearestNeighbors(newPoint, searchRadius)

            for _, neighborIndex in ipairs(neighbors) do
                local neighborPoint = tree[neighborIndex]
                if isLineOfSightClear(neighborPoint[1], neighborPoint[2], neighborPoint[3], newPoint[1], newPoint[2], newPoint[3], true, false, false, true, false, false, false) then
                    local tentativeCost = cost[neighborIndex] + public.GetDistance(neighborPoint[1], neighborPoint[2], neighborPoint[3], newPoint[1], newPoint[2], newPoint[3])
                    if tentativeCost < minCost then
                        parent[newIndex], minCost = neighborIndex, tentativeCost
                    end
                end
            end
            cost[newIndex] = minCost

            -- Перепроверяем соседей
            for _, neighborIndex in ipairs(neighbors) do
                local neighborPoint = tree[neighborIndex]
                if isLineOfSightClear(newPoint[1], newPoint[2], newPoint[3], neighborPoint[1], neighborPoint[2], neighborPoint[3], true, false, false, true, false, false, false) then
                    local tentativeCost = minCost + public.GetDistance(newPoint[1], newPoint[2], newPoint[3], neighborPoint[1], neighborPoint[2], neighborPoint[3])
                    if tentativeCost < cost[neighborIndex] then
                        parent[neighborIndex], cost[neighborIndex] = newIndex, tentativeCost
                    end
                end
            end

            -- Оптимизация: Проверяем достижение цели с использованием квадрата расстояния
            if getSquaredDistance(newPoint[1], newPoint[2], newPoint[3], endX, endY, endZ) < 25 then
                -- Восстанавливаем путь
                local path, current = {newPoint}, newIndex
                while parent[current] do
                    current = parent[current]
                    table.insert(path, 1, tree[current])
                end
                return public.smoothPath(path)
            end
        end
    end

    return nil  -- Путь не найден
end
return public

А этот код хотя бы тестировался? Даже на расстояние в 5 или 50 метров по оси Y он ничего не выплевывает, и это я ещё не говорил за базовые ошибки из разряда "Функция public.GetDistance не найдена", но при этом есть public.getDistance, и копия этой же функции, но локальная в 44 строке. Также, никто не заставляет всовывать в А* координаты на огромном расстоянии от старта, ведь их можно разделять на куски и искать следующий путь только при приближении игрока.

 

[UBP]

А этот код хотя бы тестировался? Даже на расстояние в 5 или 50 метров по оси Y он ничего не выплевывает, и это я ещё не говорил за базовые ошибки из разряда "Функция public.GetDistance не найдена", но при этом есть public.getDistance, и копия этой же функции, но локальная в 44 строке.

криво вырезал

 

[Acerdragons]

Возможно, это не самое красивое решение, и довольно простое. Но была идея получить все объекты в радиусе с помощью выгрузки через FSO_Map_Stealer, а затем интерпретировать эти данные с помощью инфы о размерах (я так понимаю они будут представлены в виде коробок, box-ов)

Если кому поможет, вот список, наверное не полный (прикрепил файл)

Очень хочется увидеть реализацию оптимизированного pathfinder в SAMP), но нет компетенции, готов помогать чем смогу