If the thickness of your line / the radius of the circle following it’s considerably narrower than your grid spacing, then it suffices to take the circle traversing your line and approximate it as a bounding sq..

This bounding sq. has a number one nook (furthest forward alongside its velocity vector) and a trailing nook (furthest behind).

We are able to use the unique algorithm on these two factors. Each time the main nook enters a brand new cell, our bounding sq. has begun to overlap a number of new cells (because it spans some space, and may cross into a number of cells directly). Each time the trailing nook enters a brand new cell, our bounding sq. has exited one a number of previously-occupied cells.

This is code that does that, in Unity-style C#:

public Vector2 gridSpacing = new Vector2(1, 1);

public struct CastEvent : System.IComparable<CastEvent> {
    public readonly float time;
    public readonly bool coming into;
    public readonly Vector2Int cell;
    public readonly Vector2 path;
    
    CastEvent(float time, bool coming into, Vector2Int cell, Vector2 path) {
        this.time = time;
        this.coming into = coming into;
        this.cell = cell;
        this.path = path;
    }

    public CastEvent Regulate(float delta, Vector2 path) {
        return new CastEvent(time + delta, coming into, cell, path);
    }

    public static CastEvent Enter(float time, Vector2Int cell, Vector2 path) {
        return new CastEvent(time, true, cell, path);
    }

    public static CastEvent Exit(float time, Vector2Int cell, Vector2Int path) {
        return new CastEvent(time, false, cell, path);
    }

    public int CompareTo(CastEvent different) {
        return time.CompareTo(different.time);
    }
}

IEnumerator<CastEvent> CircleCastApproximate(Vector2 startPosition, Vector2 velocity, float radius, float maxTime = float.PositiveInfinity)
{
    Vector2Int path = new Vector2Int(velocity.x >= 0f ? 1 : -1, velocity.y >= 0f ? 1 : -1);
    Vector2 leadPosition = (startPosition + radius * (Vector2)path)/gridSpacing;
    Vector2 tailPosition = (startPosition - radius * (Vector2)path)/gridSpacing;

    // The cells by which the top-left and bottom-right 
    // corners of the circle's bounding field fall.
    Vector2Int leadCell = Vector2Int.FloorToInt(leadPosition);
    Vector2Int tailCell = Vector2Int.FloorToInt(tailPosition);

    // Cell-aligned bounding field of the circle.
    Vector2Int minCorner = Vector2Int.Min(leadCell, tailCell);
    Vector2Int maxCorner = Vector2Int.Max(leadCell, tailCell);

    // Set lead and tail positions to values within the vary 0...1
    // to symbolize their fractional progress via their cell.
    leadPosition -= leadCell;
    tailPosition -= tailCell;

    // The time it takes to traverse one full grid cell, horizontally, and vertically.
    Vector2 timeDelta = (gridSpacing / velocity) * path;

    // Initialize the timestamps when every level enters a brand new column...
    Vector2 nextEntryTime;
    Vector2 nextExitTime;
    if (velocity.x > 0f) {
        nextEntryTime.x = (1f - leadPosition.x) * timeDelta.x;
        nextExitTime.x = (1f - tailPosition.x) * timeDelta.x;
    } else if (velocity.x < 0f) {
        nextEntryTime.x = leadPosition.x * timeDelta.x;
        nextExitTime.x = tailPosition.x * timeDelta.x;
    } else {
        nextEntryTime.x = nextExitTime.x = float.PositiveInfinity;
    }

    // ...or row.
    if (velocity.y > 0f) {
        nextEntryTime.y = (1f - leadPosition.y) * timeDelta.y;
        nextExitTime.y = (1f - tailPosition.y) * timeDelta.y;
    } else if (velocity.y < 0f) {
        nextEntryTime.y = leadPosition.y * timeDelta.y;
        nextExitTime.y = tailPosition.y * timeDelta.y;
    } else {
        nextEntryTime.y = nextExitTime.y = float.PositiveInfinity;
    }

    // Log an preliminary collision with the entire cells we're overlapping
    // in our beginning place. (Skip this to disregard preliminary overlaps)
    for (int x = minCorner.x; x <= maxCorner.x; x++) {
        for (int y = minCorner.y; y <= maxCorner.y; y++) {
            yield return CastEvent.Enter(0f, new Vector2Int(x, y), Vector2Int.zero);
        }
    }

    float accumulatedTime = 0f;
    whereas(true) {
        float nextEventTime = Mathf.Min(nextEntryTime.x, nextEntryTime.y, nextExitTime.x, nextExitTime.y);

        float totalTime = accumulatedTime + nextEventTime;

        if (totalTime > maxTime)
            yield break;

        if(nextEventTime == nextExitTime.x) {
            int top = (leadCell.y - tailCell.y) * path.y;
            for (int i = 0; i <= top; i++) {
                int y = tailCell.y + i * path.y;
                yield return CastEvent.Exit(totalTime, new Vector2Int(tailCell.x, y), new Vector2Int(path.x, 0));
            }
            tailCell.x += path.x;
            nextExitTime.x += timeDelta.x;
        }

        if (nextEventTime == nextExitTime.y) {
            int width = (leadCell.x - tailCell.x) * path.x;
            for (int i = 0; i <= width; i++) {
                int x = tailCell.x + i * path.x;
                yield return CastEvent.Exit(totalTime, new Vector2Int(x, tailCell.y), new Vector2Int(0, path.y));
            }
            tailCell.y += path.y;
            nextExitTime.y += timeDelta.y;
        }

        if (nextEventTime == nextEntryTime.x) {                
            leadCell.x += path.x;
            int top = (leadCell.y - tailCell.y) * path.y;
            for (int i = 0; i <= top; i++) {
                int y = tailCell.y + i * path.y;
                yield return CastEvent.Enter(totalTime, new Vector2Int(leadCell.x, y), new Vector2Int(path.x, 0));
            }
            nextEntryTime.x += timeDelta.x;
        }

        if (nextEventTime == nextEntryTime.y) {
            leadCell.y += path.y;
            int width = (leadCell.x - tailCell.x) * path.x;
            for (int i = 0; i <= width; i++) {
                int x = tailCell.x + i * path.x;
                yield return CastEvent.Enter(totalTime, new Vector2Int(x, leadCell.y), new Vector2Int(0, path.y));
            }
            nextEntryTime.y += timeDelta.y;
        }

        // Shift our time horizon so the newest occasion is zero.
        // This avoids lack of precision in our occasion ordering because the time turns into giant.
        accumulatedTime = totalTime;
        nextEntryTime -= nextEventTime * Vector2.one;
        nextExitTime -= nextEventTime * Vector2.one;
    }
}

I’ve proven the 2-dimensional case right here, but it surely must be clear find out how to prolong this to 3D if that is what you want.

Word that probably all 4 crossing occasions may very well be the following, if all of them happen on the identical time stamp. That is why they’re all if as an alternative of some being else if. So long as we deal with the exit occasions earlier than the enter occasions, we do not artificially enlarge our bounding field.

One warning when adapting this code: proofread very rigorously. One x that did not get modified to a y resulting from a copy-paste error can simply offer you improper outcomes or an infinite loop. (I discovered three such errors whereas I used to be drafting it) There could also be alternatives to refactor a few of the widespread operations into features/lambdas to scale back this copy-paste danger.

That is an approximation, but it surely’s a conservative approximation: utilizing this, you may by no means miss a collision it’s best to have detected. When travelling diagonally, we are able to get right into a scenario the place the bounding field of the circle clips a cell that the circle itself by no means touches, giving us a false constructive. On this occasion, you possibly can do some redundant collision checks inside that cell.

When the bounding field enters a row or column of a number of cells unexpectedly, the true circle will often enter a kind of cells barely earlier than the others. So that you’d wish to examine for a collision in all cells this algorithm stories as being entered on the identical time stamp, to make certain you discover the earliest of them.

For those who want tighter precision than simply the bounding field, you may buffer a spread of outputs from this algorithm and carry out a extra detailed circle forged or ray-versus-rounded-rectangle examine in opposition to every cell, and use that to reject false positives or re-order them. The algorithm above then serves as a type of broad part, serving to you zero-in on a small set of cells that want the dearer detailed examine.

This is an instance of how we are able to increase the bounding field algorithm to get a precise match:

// Compute how lengthy it takes for some extent particle to hit a circle on the origin.
float TimeToHitCircle(Vector2 startPosition, Vector2 velocity, float radius, out Vector2 path, bool coming into) {   

    // Primary quadratic system.
    float a = Vector2.Dot(velocity, velocity);
    float b = 2f * Vector2.Dot(startPosition, velocity);
    float c = Vector2.Dot(startPosition, startPosition) - radius * radius;

    float discriminant = b * b - 4f * a * c;

    if (discriminant < 0f) {
        path = Vector2.zero;
        return float.NaN;
    }

    float signal = coming into ? -1f : 1f;
    // TODO: There are methods to rearrange this for higher numerical stability.
    float t = (-b + signal * Mathf.Sqrt(discriminant)) / (2f * a);

    if (signal * t > 0f) {
        Debug.LogErrorFormat("begin {0}, vel {1}, rad {2}, coming into {3}", startPosition, velocity, radius, coming into);
    }

    path = signal * (startPosition + t * velocity).normalized;
    return t;
}

// Used to keep up our sorted buffer of occasions.
// TODO: A heap/precedence queue could deal with this extra effectively.
void InsertSorted(Listing<CastEvent> eventBuffer, CastEvent merchandise) {
    int index = eventBuffer.BinarySearch(merchandise);
    if (index < 0)
        index = ~index;
    eventBuffer.Insert(index, merchandise);
}

Vector2 OffsetFromCenterOfCell(Vector2Int cell, Vector2 place) {
    return place - gridSpacing * (cell + Vector2.one * 0.5f);
}

IEnumerator<CastEvent> CircleCastExact(Vector2 startPosition, Vector2 velocity, float radius, float maxTime = float.PositiveInfinity) {
    
    // Spin up our crude bounding field model to enumerate the cells we *may* contact.
    var broadPhase = CircleCastApproximate(startPosition, velocity, radius, maxTime);
    broadPhase.MoveNext();              

    // Compute how a lot earlier/later the circle may contact a nook, in comparison with the sq..
    // That is how a lot time we have to sit up for guarantee we appropriately order our intersections.
    float timeError = TimeToHitCircle(new Vector2(Mathf.Signal(velocity.x), Mathf.Signal(velocity.y)) * -radius, velocity, radius, out Vector2 unused, true);
    
    // First, filter the preliminary overlaps to solely those we truly contact.
    Vector2 halfGrid = gridSpacing * 0.5f;
    whereas (broadPhase.Present.time == 0) {
        var offset = OffsetFromCenterOfCell(broadPhase.Present.cell, startPosition);

        var onCell = new Vector2(
                Mathf.Clamp(offset.x, -halfGrid.x, halfGrid.x),
                Mathf.Clamp(offset.y, -halfGrid.y, halfGrid.y)
        );
        if ((offset - onCell).sqrMagnitude < radius * radius)
            yield return broadPhase.Present;
        broadPhase.MoveNext();
    }

    // We'll hold a sorted buffer of upcoming occasions.
    var eventBuffer = new Listing<CastEvent>();

    do {
        var present = broadPhase.Present;

        // So long as the following occasion from the broad part is way sufficient previous the beginning of our buffer,
        // then we all know no undiscovered occasion can intervene. So it is secure to emit our earliest buffered occasion.
        whereas (eventBuffer.Rely > 0 && eventBuffer[0].time + timeError <= present.time) {
            yield return eventBuffer[0];
            eventBuffer.RemoveAt(0);
        }
        
        // We have emptied out the occasions we all know are within the appropriate order.
        // Time to take this subsequent approximate occasion from the broad part and put it so as.

        // Shift our scenario so the cell we're coming into/exiting is centered on the origin.
        Vector2 offset = OffsetFromCenterOfCell(present.cell, startPosition);

        // Compute our place relative to the cell middle on the time our bounding field touches it.
        Vector2 positionAtTime = offset + present.time * velocity;

        // If we entered this cell horizontally, we care about our vertical alignment, and vice versa.
        Vector2 alongSide = new Vector2(present.path.y, present.path.x);

        // How far are we off the cell's middle line in the intervening time of bounding field contact with its edge?
        float deviation = Mathf.Abs(Vector2.Dot(positionAtTime, alongSide));
        float restrict = Mathf.Abs(Vector2.Dot(gridSpacing, alongSide)) / 2f;

        // If we're lower than half the grid spacing off-center, then we have hit the sting proper on time.
        if (deviation <= restrict) {
            InsertSorted(eventBuffer, present);
            proceed;
        }

        // In any other case, we're sweeping previous the nook, and we'd hit it at a distinct time, or miss.

        // Shift our place once more, so the nook is centered at (0, 0).
        positionAtTime -= new Vector2(Mathf.Signal(positionAtTime.x), Mathf.Signal(positionAtTime.y)) * halfGrid;

        // The time when a shifting circle hits a stationary level 
        // is similar because the time when a shifting level hits a stationary circle.
        float addedTime = TimeToHitCircle(positionAtTime, velocity, radius, out Vector2 path, present.coming into);

        // We truly miss this cell. Discard it with out including it to our buffer.
        if (float.IsNaN(addedTime)) {
            proceed;
        }

        // Regulate the timing of this occasion: later for coming into, earlier for exiting.
        present = present.Regulate(addedTime, path);
                   
        // We exit cells from "earlier than" the ray began. Ignore them.
        if(present.time > 0f)
            InsertSorted(eventBuffer, present);

    } whereas (broadPhase.MoveNext());

    // Our broadphase ray has terminated, now we simply must empty any occasions left in our queue.
    foreach(var merchandise in eventBuffer) {
        if (merchandise.time > maxTime)
            yield break;

        yield return merchandise;
    }
}

Word that you simply solely want so as to add the time error offset should you care concerning the “exit” occasions. For those who simply wish to appropriately order the cells the circle enters, then it is secure to do away with the exit occasions completely and deal with the time error as zero (entrance occasions from the broadphase can solely occur later than reported, by no means earlier)