Перемещение юнита точно по пути в координатах x, y

Question

Я играю в стратегическую игру, в которой отряды движутся по карте. Каждый ход определенное количество движения выделяется отряду, и если у отряда есть пункт назначения, очки применяются каждый ход, пока пункт назначения не будет достигнут. Фактическое расстояние используется, поэтому, если отряд перемещается на одну позицию в направлении x или y, он использует одну точку, но перемещение по диагонали занимает ~ 1.4 пункта. Отряд сохраняет фактическое положение как плавающее, которое затем округляется, чтобы можно было нарисовать положение на карте.

Путь описывается касанием отряда и перетаскиванием в конечное положение, а затем поднятием ручки или пальца. (Сейчас я делаю это на iPhone, но Android / Qt / Windows Mobile будет работать так же). Когда указатель перемещается, точки x записываются так, что отряд получает список промежуточных пунктов назначения на пути к конечному пункту назначения. Я обнаружил, что пункты назначения не расположены равномерно, но могут быть дальше друг от друга в зависимости от скорости движения указателя. Следование по пути важно, потому что в этой игре важны препятствия или местность. Я не пытаюсь переделать Flight Control, но это похожая механика.

Вот что я делал, но это кажется слишком сложным (псевдокод):

getDestination() {
- self.nextDestination = remove_from_array(destinations)
- self.gradient = delta y to destination / delta x to destination
- self.angle = atan(self.gradient)
- self.cosAngle = cos(self.angle)
- self.sinAngle = sin(self.angle)
}

move() {
- get movement allocation for this turn
- if self.nextDestination not valid
- - getNextDestination()
- while(nextDestination valid) && (movement allocation remains) {
- - find xStep and yStep using movement allocation and sinAngle/cosAngle calculated for current self.nextDestination
- - if current position + xStep crosses the destination
- - - find x movement remaining after self.nextDestination reached
- - - calculate remaining direct path movement allocation (xStep remaining / cosAngle)
- - - make self.position equal to self.nextDestination
- - else 
- - - apply xStep and yStep to current position
- }
- round squad's float coordinates to integer screen coordinates
- draw squad image on map
}

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

Предложения для лучшего способа сделать это?

• обновление - iPhone не имеет проблем с триггером и отслеживанием десятков позиций и треков, реализованных, как описано выше, и он все равно тянет поплавки. Метод Брезенхэма более эффективен, триггер более точен. Если бы я использовал целое число Брезенхэма, я бы хотел умножить на десять или около того, чтобы сохранить немного большую точность позиционирования, чтобы улучшить обнаружение столкновений / рельефа.

Answer 1

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

Вот псевдокод из Википедии

function line(x0, x1, y0, y1)
 int deltax := x1 - x0
 int deltay := y1 - y0
 real error := 0
 real deltaerr := deltay / deltax    // Assume deltax != 0 (line is not vertical),
       // note that this division needs to be done in a way that preserves the fractional part
 int y := y0
 for x from x0 to x1
     plot(x,y)
     error := error + deltaerr
     if abs(error) ≥ 0.5 then
         y := y + 1
         error := error - 1.0

Answer 2

Использование угла кажется контрпродуктивным, было бы проще сохранить вычисления в системе координат X-Y.