# How to generate a series of checkpoints randomly along a 2D line

I was wondering how I would go about generating a series of checkpoint gates along a 2D line in my game. A bit of background, my game is a 2D reinforcement learning car driving simulator, I have a self designed track and would like to programmatically spawn a series of checkpoint gates along the track as a reward feature for my neural network.

My track is a 2D PNG file, and I am using Unity Engine for my game. Any help on how to generate a series of checkpoints along this track would be of great help.

I would ideally like to specify the number of checkpoints that spawn as an attribute, and then they spawn on the track at evenly spaced intervals to cover the entire track start to finish. The intervals of spacing get smaller the more checkpoints I add, likewise the spacing gets further the fewer checkpoints I specify.

I need the checkpoint gates to spawn along the track, so that the vehicle can cross it and be rewarded.

Here is my current track:

• A straight away doesn't have as many meaningful decisions to make as a complex turn. An even distribution of check points might be a fine starting point but for learning I would consider adjusting the checkpoint distribution so that they (perhaps over time) reflect the complexity of track. As to the problem as stated, what problems have you encountered dividing the total track distance by the # of points & spacing them accordingly? Commented May 25 at 18:25
• Perhaps you can tell us why the track is coming in as PNG, and if that is an absolute hard requirement. Because to take it from PNG to something your code can sanely use, is about as difficult as writing code that just generates the track in a usable format in the first place. Neither is very hard, but both require some effort. I would still go with the latter. If you're forced to take it in as PNG, then I would still write a separate converter tool to provide it as a series of line segments and arcs to be stored as game data. Commented May 25 at 18:45
• But a quick and dirty approach would be to count the total amount of black pixel, divide it by the amount of checkpoints and each X pixel you have your checkpoint. If you however convert the png into a spline. you will have different options. Or if it is converted as a line renderer. Or something else. It would be easier for a fitting answer if you tell us how your cars are using the track, what the actual input for them is. Commented May 25 at 19:07
• @Engineer I am only using a PNG because I just drew the track. If there is an easier way of drawing the track without using a PNG than I am very much open to it, especially if it makes placing checkpoints easier. The only issue is I am not very knowledgeable on the better approaches to do this. If you would please provide some more information on an approach to this issue I would be very grateful. Commented May 25 at 20:05
• @Techwizard I've added a Step 4 in my answer, about track widths. It's worth reading that part, because it will become an issue later. For now, the basic approach I've outlined should get you started. Commented May 25 at 22:26

Let's start with the basics of how this problem is solved, and work it backward. At the end, I will discuss your choice of data format (PNG vs others).

Step 1: The 1-dimensional method for calculating distance along a track / course

The primary question you need answer to is, "At this point (any point on the track), how far along the track am I?". "How far" indicates distance. Distance is a scalar (1D) value, not a vector value. This is very important. When someone asks you, "How far is it from your house to the school?" they are not asking for directions. They are asking for distance -- either in a straight line, i.e. "as the crow flies", or by following the shortest path of streets. The answer will be a single quantity in meters or kilometers (or feet or miles). So for now let's not think of your track as a 2D, winding course, but just a straight, 1D line that loops back to its start.

First, let's assume the entire track's length is represented by a value of 1.0. This is calculated by dividing trackLength / trackLength. So if your track is 1200 metres long, then 1200 / 1200 = 1.0. This signifies the position at the very end (100%) of the track.

For any other point along the track, it is some distance (in the race direction) from the start line. For example, 60m from the start line would be 60 / 1200 = 0.05 or 5% of the track length. 900m in is 900/1200m = 0.75 = 75%. This fractional value is really just a percentage divided by 100.

From that we can see that the formula to get your fractional ("normalised") distance along the track is fracAlongTrack = distanceAlongTrack / trackLength.

To split the track into exactly (for example) N = 10 equidistant checkpoints, you apply this division, and invert the formula, instead multiplying by the track's length:

intervalFrac = 1.0 / 10 = 0.1; //in fractional / normalised terms

And then:

intervalDist = intervalFrac * trackLength = 0.1 * 1200 = 120; //meters

You can see that this is equivalent to 1200 / 10 = 120m. You can do it either way, as you like, in fractional form or in distance form.

Step 2: Checkpoint intervals: Fractions of fractions

You can also calculate (a) which checkpoint interval you are in (say between the 2nd and 3rd or between the 5th and 6th checkpoints) and how far into that interval between two checkpoints you are. So for example, we could ask, "how far, as a fraction, is 555 metres along the track?" where N=10 checkpoints and thus intervalFrac=10. Using our earlier formula:

fracAlongTrack = distanceAlongTrack / trackLength

0.4625 = 555 / 1200 or 46.25%

To find which set of checkpoints you are in can be done using modulus (remainder), using either of the following formulae (they are equivalent):

whichIntervalStart = floor(fracAlongTrack / intervalFrac);

whichIntervalStart = floor(distAlongTrack / intervalDist);

So as you can see if we use the 1st (fractional form) of this pair of formulae, doing the inner division first: 4.625 = 0.4625 / 0.1

and

4 = floor (4.625)

Note that whichIntervalStart will be the checkpoint immediately behind you [n], thus the next checkpoint is the following [n+1], if you stored an array of all checkpoints in order of distance from start to finish. Thus we are between checkpoints[4] and [5] (remember, the first checkpoint, or start line is checkpoints[0]). Since we know each checkpoint is 120m from the last, that means we're between 4*120=480 and 5*120=600 metres down the track (which is correct: 555 metres). Exactly how far between are we, though? We need to get a fraction (how far) of a fraction (checkpoint interval):

betweenCheckpointsFrac = (fracAlongTrack % intervalFrac) / intervalFrac

betweenCheckpointsDist = (distAlongTrack % intervalDist) / intervalDist

Again using the 1st (fractional form) of these two formulae: 0.625 = (0.4625 % 0.1) / 0.1

...Which is 62.5% between checkpoints [4] and [5] (the 5th and 6th checkpoints, if we call the start line checkpoints[0]). That would be betweenCheckpointsFrac * intervalDist = 0.625 * 120 = 75 metres from checkpoints[4], and 120-75 = 45 metres (backward) from checkpoints[5].

By reducing to 1D, we've made it so we can very easily check differences (distances) between various key points along the track - including where our AI agent's car currently is, if desired.

Step 3: From 2D vectors to 1D distances, and discerning exactly where checkpoints lie

Here is a basic outline... unfortunately, this early on, it is hard to proscribe exact approaches. You can always come back and ask more questions once you get to this part.

That PNG first needs to be converted to a series of straight 2D line segments (easy) and arcs (quite a bit harder to create and to use). These segments are placed into an array ordered from start to finish of your track. Each line segment needs to be able to tell you its (1D) length in real terms (meters, feet or what have you). For straight line segments, we just use Pythagoras to get the length. For curved... well, that entirely depends on how you represent the curved segments: some options are circular or elliptical arcs, bezier curve segments, cubic splines, etc. (Circle and ellipse arcs are easier to get linear distances from, than non-linear beziers and cubics, but are not as versatile in terms of shape.)

We then sum the lengths of every segment to get your total trackLength. And use the formulae given to see how far along the track the starts and ends of each of those segments are. Let's say you want to know exactly where your checkpoints are in relation to the starts / ends (intervals) of each line segment. Imagine you got 15 line segments,

[0.0, 0.06, 0.07, 0.08, 0.10, 0.14, 0.22, 0.26, 0.5, 0.63, 0.66, 0.70, 0.71, 0.80, 0.96]

and you have 10 checkpoints,

[0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9]

You could also nudge these forward by 0.05 so that you have a range from 0.05 to 0.95, thereby not conflicting with the start line. Then you have:

[0.05, 0.15, 0.25, 0.35, 0.45, 0.55, 0.65, 0.75, 0.85, 0.95]

And by merging these two arrays in ascending order,

[0.0, 0.05, 0.06, 0.07, 0.08, 0.10, 0.14, 0.15, 0.22, 0.25, 0.26, 0.35, 0.45, 0.5, 0.55, 0.63, 0.65, 0.66, 0.70, 0.71, 0.75, 0.80, 0.85, 0.95, 0.96]

You can now see an exhaustive list of the various points of importance in your track, and how far checkpoints are from neighbouring start and end points of track segments (in this contrived example all checkpoints end in the digit 5)... this is easily done by storing, for each array element, what it represents, e.g. "Checkpoint 3" or "Start of Segment 19". In reality you may have cases where your algorithm has the same value for the start of an interval and a checkpoint, so don't merge your arrays -- keep the checkpoints and trackSegments array separate or you may overwrite some data.

Step 4: Accounting for track width

This will be a problem for later, but I mention it here so you don't forget.

As we know, the shortest path around a track is always on the inside (lane). For example, the inner diameter of a doughnut is less than the outer diameter, meaning if I travel in that inner ring, I complete a single circuit faster than if I was on the outside, travelling at the same speed.

The 1D solution in and of itself only assumes a single track width that we can travel along - a single, infinitely thin line. Thus, everyone travelling at the same speed will finish at the same time.

Now, imagine the track was actually 10m wide (as the player sees it). If the centre of someone's car is 3 meters from the outermost edge of the 10m wide track (7m from the inner edge), how much faster would they have to go, to keep neck-and-neck with someone whose car-centre is at the innermost edge?

Conversely, we need to be clear about how to convert a 2D position (that includes how far "out" along the track width we are) to an accurate fracAlongTrack value -- since that is key to our calculations.

This can be resolved by calculating lengths and required velocities to complete the race on by travelling along the inner vs. the outer track 1D lines, and linearly interpolating between them. I will not go into further detail here, feel free to ask a question about this at another time. There are undoubtedly multiple ways to solve this.

An important note for first-timers

On the topic of non-linear curves and curve-length approximation: My strong suggestion to anyone new to this kind of thing is: rather approximate any curved segments of your track as a series of small / short straight line segments. This way, there is no calculus nor deeper understanding of non-linear Beziers and cubic splines required. What I mean by non-linear here is that for these types of curves, what you might think is, say, 60% or 0.6 fractionally along the curved segment -- visually speaking -- is not the same as what the underlying math will tell you it considers to be 0.6, because the formula used to plot is a non-linear one (such as distanceAlongCurve = t * t). That can quickly get tricky if your maths is not up to scratch, and can blindside you even if it is. Alternatively, use a curve library for Unity that can approximate linear distances along a curved segment - et voila!

From my own experience... I would still start with the simpler approach when implementing this from scratch: since you are pulling in this track from PNG anyway, I suggest you convert all those pixels into a series of straight (linearly defined) line segments. Again, how you do that can be the topic of a separate question; this answer is already long enough in just addressing the basic topic of how to set up checkpoints on a track. Then, later on, if you want to include non-linear curved segments, you can replace that code accordingly, once you have a functioning basis to work from.

Alternative to PNG

Yes, you could use something like Adobe Illustrator to produce an SVG, and then import those splines / segments as game data. How you go about parsing that data is up to you; IIRC there are parsers out there that will do it for you. This would be an improvement over trying to reduce your existing pixels-based image to a series of line segments. However, it would not solve the problem of non-linear distances along arcs... for that, again, you would be better off using a combination of Illustrator + a curves library for Unity that can provide linear distance approximations along curves.

Recommended approach to make this easy

1. Don't worry about graphics for now. Just use Debug.Log(), a pen, some graph paper and your brain to model the basic problem I've outlined in Steps 1 & 2, above.

2. Create an array of some straight line segments in code, as 2D vectors. Make sure the start and end points have the same (x, y)`! This is your track. Draw it on graph paper so you have a reference to look at, helping you to judge if your code is calculating distances correctly .

3. Use segmentation and distance arithmetic given in parts 1 and 2 of this answer, to create toy code that allows you to play around and accurately calculate distances between key track points -- even a car, which can be represented as another 1D value that increases its value from one tick to the next until it reaches the finish line, and wraps its value back to 0 again.

4. Move to 2D rendering -- requires 2D graphics / scene graph etc.

5. Solve the track-width velocity problem.