Intersecting Paths on a Hexagon Grid

In an earlier post, I discussed a co-ordinate system for a hexagon grid.

In this post, I will discuss a problem I worked on recently concerning such a system.

Essence of Glory is a game of formations and positioning. One way this manifests is in the system for close Assaults. These do not necessarily refer to hand to hand combat (although boarding parties are one possibility), but "close" engagements. Sort of how two airplanes coming within a mile of each other is a near miss.

The system we are using for Assault stipulates that an Assault occurs between two opposing wings of ships if they pass through each other during the Movement phase.

The question is, how do we determine when ships pass through each other?

There are two options, really. Either track ships as they move and report any collisions, or do some calculations based on their paths.

The first option isn't really useful, because we want Assaults to occur any time ships' paths cross.
We don't necessarily care if they are in the same space at the same time.

So we are better off looking at the movement paths as a whole. Remember the grid system?

A vector can describe either a position, or a change in position.
[2,0] may be the position to spaces to the right on the horizontal axis, or it may represent a movement of two units in that direction.

It would be possible to describe the movement of a unit with one vector, but it wouldn't be as useful. For example, a ship starting at [0,0] might move to [-2, 1], but did it pass through [-1, 0] or [-1,1]?
If we described that movement using only the vector [-2, 1], we would have no way of knowing.

Instead, we can store the movement of a ship with a series of unit vectors. Unit vectors are those with length one. Note that in hex co-ordinates, [-1, 1] is a unit vector, but [1,1] is not.

So, a ship starting at [0,0] and moving to [-2, 1] could have its movement described with the sequence of unit vectors {[-1,0], [-1, 1]} or with {[-1,1], [-1,0]}.

To find all the hexes through which a ship passed during the course of its movement, just add each of the unit vectors in its path to its starting position in turn.

Then, to find which ships will assault each other, find all hexes that all ships passed through during the movement phase, and then find those that are shared between opposing ships.