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

UBP написал(а):

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

Lua:

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 написал(а):

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

Нажмите для раскрытия...

Tectrex написал(а):

Оп, исправил, запатчил все остаточные баги, добавил rrt, там пятое десятое, разделил на модули, короче юзайте

Нажмите для раскрытия...