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

Question

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)

Answer 1

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.

Answer 2

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)

Answer 3

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.

Answer 4

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.