Moving a unit precisely along a path in x,y coordinates

Question

I am playing around with a strategy game where squads move around a map. Each turn a certain amount of movement is allocated to a squad and if the squad has a destination the points are applied each turn until the destination is reached. Actual distance is used so if a squad moves one position in the x or y direction it uses one point, but moving diagonally takes ~1.4 points. The squad maintains actual position as float which is then rounded to allow drawing the position on the map.

The path is described by touching the squad and dragging to the end position then lifting the pen or finger. (I'm doing this on an iPhone now but Android/Qt/Windows Mobile would work the same) As the pointer moves x, y points are recorded so that the squad gains a list of intermediate destinations on the way to the final destination. I'm finding that the destinations are not evenly spaced but can be further apart depending on the speed of the pointer movement. Following the path is important because obstacles or terrain matter in this game. I'm not trying to remake Flight Control but that's a similar mechanic.

Here's what I've been doing, but it just seems too complicated (pseudocode):

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
}

That's simplified of course, stuff like sign needs to be tweaked to ensure movement is in the right direction. If trig is the best way to do it then lookup tables can be used or maybe it doesn't matter on modern devices like it used to.

Suggestions for a better way to do it?

• an update - iPhone has zero issues with trig and tracking tens of positions and tracks implemented as described above and it draws in floats anyway. The Bresenham method is more efficient, trig is more precise. If I was to use integer Bresenham I would want to multiply by ten or so to maintain a little more positional accuracy to benefit collisions/terrain detection.

Answer 1

I think that Bresenham's line algorithm is what you need. The Wikipedia article is a good place to start and you should be able to find more some sample code somewhere.

Here's the pseudo code from Wikipedia

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

Using an angle seems counter productive, it would be simpler to keep the calculation in the X-Y coordinate system.