How to determine range of possible movement in turn-based, distance-based strategy game?

I'm creating a 2-dimensional, turn-based strategy game using c++ and SFML-2.0. Movement is distance-based rather than grid-based, with several different triangle-shaped pieces that, on a given turn, each may either rotate in place or move forward.

Movement will work in such a way that the player selects a location for the piece to move to, which generates a potential path for the piece to take. Once the player confirms his or her decision, the piece will move along that path to the desired location. Paths are limited by two factors: distance, how far a piece is able to go, taking into accounts any turns (so if there is a curve, it will be the length along the curve, and not directly from point to point); and steering angle, how far the piece can rotate at any (and up to every) point while moving (for example, from -30 to 30 degrees).

My question is, how should I go about determining the range of potential locations that the player can select to have the piece move to?

I'm not entirely sure what equations and/or algorithm to use here. My original plan was extremely over-complicated, to the point where it was near impossible to implement, let alone explain, and I am at this point totally lost with the project stalled.

How can I determine the range a unit can move, taking into account its turning radius?

For example, in the below image. The red, blue and green lines would all be the same length. The purple circle denotes the movement range the unit can move. (The shape is probably inaccurate and the lines probably aren't actually the same length, but you get the idea)

• It's still only going to be able to move the same (total) distance. So the question is really about figuring out "how far does it turn?"/"how much does it need to turn?"/"where does it need to turn?". You probably need to start from determining the regular path, then step a start-of-turn back for angles above a certain amount; note that final distance will be longer in a straight-line path (turning latest) than with the curves. – Clockwork-Muse Jul 16 '13 at 20:35
• Yes, the distance traveled is the main limiting factor. My biggest hurdle here is that I need to take into account that the piece can turn, and continue to turn, at any point it can reach, as long as it still has distance left available. – sfphilli Jul 16 '13 at 20:40
• What do you mean, the range a unit can move? You mean the points it can move to? How familiar are you with linear algebra (vectors)? – BlueRaja - Danny Pflughoeft Jul 16 '13 at 21:01
• What real-life scenario are you trying to model? Your problem is too vague on requirements, resulting in too many solution approaches being proposed. There are a well-known approaches to (virtually) every specific problem in this area, but everyone is guessing which of these many problems you are actually tackling. – Pieter Geerkens Jul 16 '13 at 22:20
• @PieterGeerkens I suppose because OP isn't requesting code, they're requesting an algorithm. And have provided enough detail about the scenario that an algorithm could reasonably be conceived. This is common and acceptable. – MichaelHouse Jul 17 '13 at 0:30

Generate a flow or distance field, using Dijsktra's.

Essentially, fill in a grid using the Dijkstra algorithm with no destination (probably a different name for that; don't know it). Just take each open node, compute reachable neighbors, push them on the open list, set on the closed list, update parent node's "next" path as appropriate, etc. When determining the cost to reach a new node, consider the turning limitations.

The result will now be that you have a network of all your nodes on how to get back to the start. Nodes which cannot be reached will not have been touched by the first step. Nodes that can be reached will have a "next node along best possible path to parent" element computed so you can both highlight all nodes and then also use this information to show or execute the movement path as the user hovers or clicks on highlighted areas.

• Not quite how I would explain the concept, or how I would implement it, but certainly the right approach. – Pieter Geerkens Jul 16 '13 at 21:28
• My understanding of the algorithm, as-is, is that node-traversal need to be path-independent. So, in order to accomplish this, you'd need to add another degree of freedom (another axis on which to create your nodes) dedicated to facing. In other words, you'd have a node for each combination of different X, Y, potentially Z, and Facing. Otherwise, finding the shortest path to enter a node doesn't distinguish between the different facings when leaving it. Is that correct? If that is the case, is this method possibly too intensive? – TASagent Jul 16 '13 at 21:34
• @TASagent: good point, I didn't think that one through entirely. The algorithm then is maybe a little off but the approach should work. – Sean Middleditch Jul 16 '13 at 21:36
• @PieterGeerkens: I agree it's a bad explanation. You should make your own answer that explains it all better. – Sean Middleditch Jul 16 '13 at 21:37
• This seems like it's pretty close to what I need, but I have to admit I've never heard of that algorithm, and so don't know how to generalize it to what I need. Do you happen to have a link to any good info or tutorials on it? – sfphilli Jul 16 '13 at 21:39

A brute force solution would be:

1. Create a circle of vertices around the unit, with the unit at the center. The radius of the circle is the maximum movement distance. The density of the vertices can change depending how detailed you want the final result to be.
2. For each vertex position, simulate the movement of the unit steering towards that position. This is done in a tight loop without rendering.
3. When the maximum distance is reached in the steering simulation, move the vertex to the point of the simulated unit. This point is the closest the unit could get to that vertex before the current turn was over. This has the effect of shrinking the circle to the size of actual movement.
4. Use those vertices, along with a vertex centered on the unit to create a rendered circle to draw the possible movement distances.

So, starting with the blue circle, you'd process your paths, ending up with the purple circle. Then you can use those points with a center point on the unit to make the red triangles required to display the shape. (Just making that image makes me realize that that shape is not correct, but it'll be interesting to see what's actually correct)

I'm going to expand on Sean's solution in a separate answer, as it represents a different approach from what I was initially proposing.

This solution probably represents the most accessible method. It requires partitioning your environment into nodes. Yes, this is re-introducing a grid-based approach, but it can be made relatively fine, or used for broad pathfinding with finer positioning handled within the node. The more coarse the node structure, the faster the pathfinding.

The big issue here is that you are actually dealing with ship facing, so many traditional pathfinding solutions can't be used without modification. These usually are path-agnostic, in that they don't care how you got to the node you're in. That works fine when acceleration, deceleration, and turning are instant and free. Unfortunately for you turning is not free. However, since there is really one extra piece of information that gets dropped in this simplification, we can encode it as another variable. In physics, this would be known as phase-space.

Assuming 2-dimensions for now, you can extrapolate for 3:

Ordinarily, you would need one node for each allowable, discrete coordinate position. For example:

(0,0) - (1,0) - (2,0)
| \  /  |  \  / |
(0,1) - (1,1) - (2,1)


Etc. You'd construct a nodegraph of adjacent points and connect them by spacial adjacency. Then you'd use Dijkstra's algorithm, killing nodes which exceed the movement value allowed for the turn, until there are no unexplored, living nodes remaining connected to explored nodes. Each node keeps track of the smallest distance required to reach it.

To expand this method to be usable with Rotation, imagine this same nodegraph in 3 dimensions. The Z-direction corresponds to rotation/facing, and is cyclical, meaning if you keep traveling in the +Z direction you get back to where you started. Now, nodes corresponding to adjacent positions are only connected across the facing that corresponds to that direction. You iterate over the nodes connected to already explored nodes as usual. I would recommend restricting to N, NE, E, SE, S, SW, W, NW in this scheme.

This solution can tell you all the accessible regions of space, as well as the best path to get there, how much rotation you have when you arrive there, and all of the orientations you could have when you arrive there.

Then, when actually executing the pathing, you're free to interpolate/cubic spline your way into making it look more authentic.

• This is excellent. I'll need to do a little research on the algorithm and experiment with it in my game over, but this really strikes me as the perfect fit, especially since I can generalize it to some other important parts of the game. – sfphilli Jul 16 '13 at 23:03

It sounds like you may need to first decide on how exactly you would like the turning on-the-go to work. Options like:

• If they move within the cone, first rotate, then start moving. This is the easier solution to implement and path for. It is also less interesting so I wouldn't want to use it.

• Continuous turning while moving, up to a total of 45 degrees. This one is a lot trickier, and hopefully the one you're after. Numerically integrating over the path using a fixed timestep is probably the easiest way to approach this one. Your cone will be bounded by the maximum (+X degrees every step) and minimum (-X degrees every step) turning.

How best to path through space with the second of these requirements depends largely on the environment they'll be moving in. If there are a lot of obstacles you have to traverse around, then things can get really tricky and really expensive. However, if there's not, then you can front-load (and even taper-off) the rotation to end up in the desired location.

I have a feeling that I may have only partially covered the topics you had a question about, so feel free to add more in the comments and I can expand the discussion.

• I most definitely want to use the second option, of turning up to (for example) 45 degrees at any, and potentially every, point along a path. There will also be obstacles, each larger than the pieces (think giant rocks). The way I was originally thinking about this was to generate a cone of possible endpoints, and then for each of those endpoints generate a new cone, and so on for every possible location until it hits the maximum distance traveled. That said, I'm not entirely sure how to go about implementing this without crazy overcomplication. – sfphilli Jul 16 '13 at 21:11
• Hmmm, it seems that I was/am a little unclear about some of the details. Looking back over the question I see you specified 'turn-based' and that the units can 'rotate or move' on their turn. Does that mean, then, that the player plots out their actions many turns in advance, and you want to do the pathfinding while they move? Some further clarification on how movement is supposed to work would be helpful. – TASagent Jul 16 '13 at 21:23
• No, what I meant was that on a given turn the player can either rotate their piece in place, however far around as they like, or they can move in the direction they are already looking. If they move, they can go a particular distance along a path, and they can turn or steer up to a particular angle (so anywhere from -45 to 45 degrees for example) while moving. So imagine a chosen path would involve a curve in order to move to the left or right. The path would be determined by the player picking a point they want to move to, within the range of possible points I'm having trouble determining. – sfphilli Jul 16 '13 at 21:35
• Ok, so it actually sounds like, unfortunately, your desired characteristics are possibly too restrictive for the Dijkstra algorithm we're talking about above :-\. Possibly. I'll sketch some things out for this later when I get home. – TASagent Jul 16 '13 at 21:47
• You may want to edit some of this information you've gathered to clarify the problem into the original question, so people who come later can start with more information. – TASagent Jul 16 '13 at 21:48