Генерирование движения по кривой Безье

Я делаю небольшую игру, которая включает в себя пути для врага ИИ. Я хочу использовать путь, созданный с использованием кривых Cubic Bezier, но ему нужна формула, которая заставит врагов перемещаться по любой кривой с постоянной скоростью. Все, что я знаю, это постоянное движение по прямым дорожкам и генерация кривых Безье, но я не знаю, как хорошо работать вместе.Генерирование движения по кривой Безье

источник

2015-07-10 FRA32

Проблемы здесь состоит в том, что вы выбрали нелинейной кривой, на которой вы хотите линейной скорости.

Существует несколько вариантов, таких как аппроксимация кривой как линейной геометрии (например, сегментов линии или круговых дуг), а затем перемещение по ним на линейной скорости вместо фактической кривой. Сведение кривого идти по что относительно прямолинейно:

lines = [] 
x=curve.getX(0), y=curve.getY(0), nx, ny 
step=..., interval=1/step, t=step 
while(t<=1) { 
    nx = curve.getX(t) 
    ny = curve.getY(t) 
    lines.push(new line(x,y,nx,ny) 
    x = nx 
    y = ny 
    t += interval 
}

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

В качестве альтернативы вы можете создать таблицу поиска как часть процедуры рисования и записать расстояние вдоль кривой в этой точке, чтобы затем вы могли пересечь кривую с линейной скоростью путем двоичного поиска оставшейся части кривая для «следующего места», в которой вы должны быть. Больше первоначальной работы, чем вариант 1, но, безусловно, быстрее, как только начинается движение.

function arcLength(t) { 
    // true fact: computing the arc length of a bezier curve is not 
    // a thing you want to end up implementing yourself. It's not hard, 
    // but getting to a point where you undestand *why* it's not hard is 
    // is certainly time consuming, and depending on how much your brain 
    // is unwilling to just take maths at face value, definitely hard. 
    // Use someone else's implementation, like this one: 
    // https://github.com/Pomax/bezierjs/blob/gh-pages/lib/bezier.js#L87 
} 

Curve.draw = function() { 
    if (!this.curveLUT) { 
    // form a LUT however you like. The following demonstration 
    // code uses something similar to the above flattening: 
    for(i=0;i<LUT.length;i++) { 
     t = i/(LUT.length-1) 
     x = curve.getX(t) 
     y = curve.getY(t) 
     LUT.push({x:x, y:y, dist: arclength(t)}) 
    }  
    } 
    this.curveLUT.foreach(point -> point.draw()) 
}

И тогда, когда нам нужно идти по кривой в какой-то определенной скорости:

speed = ... 
currentPos = SomeLUTindex 
if (currentPos < LUT.length) { 
    currentDist = LUT[currentPos].dist 
    nextDist = currentDist + speed 
    nextPos = binarySearch(LUT.slice(currentPos), "dist", nextDist) 
}

с:

binarySearch(List, property, target) { 
    midIdx = (int) List.length/2 
    mid = List[midIdx] 
    curr = mid[property] 
    if(curr === target) return midIdx 
    if(curr > target) return binarySearch(List.slice(0,midIdx), property, target) 
    if(curr < target) return midIdx + binarySearch(List.slice(midIdx), property, target) 
}

Это выглядит, как она может рекурсию много, но бинарные поиски разрешения в ceil(log₂(n)), в худшем случае, так что даже в поисковой таблице с 10000 точками это займет следующее место максимум в 14 шагов. Оптимизация этой функции разворачивает ее прямолинейно, а не нарезая список, но проверяя определенные интервалы на нем - оба кода немного больше, но относительно легко реализовать с небольшой помощью от google и wikipedia.

источник

2015-07-11 22:56:01

Генерирование движения по кривой Безье

ответ

Смежные вопросы