What's the best way to implement one-dimensional collision detection?

Question

I'm writing a piece of simulation software, and need an efficient way to test for collisions along a line.

The simulation is of a train crossing several switches on a track. When a wheel comes within N inches of the switch, the switch turns on, then turns off when the wheel leaves. Since all wheels are the same size, and all switches are the same size, I can represent them as a single coordinate X along the track. Switch distances and wheel distances don't change in relation to each other, once set.

This is a fairly trivial problem when done through brute force by placing the X coordinates in lists, and traversing them, but I need a way to do so efficiently, because it needs to be extremely accurate, even when the train is moving at high speeds. There's a ton of tutorials on 2D collision detection, but I'm not sure the best way to go about this unique 1D scenario.

---

Apparently there's some confusion about what my data looks like.

I'm simulating a single site, not an entire region. The trains can be of any length, with different types of cars, but there is only ever one train. My train data is in the form {48,96,508,556,626,674,...}, indicating the distances from the front of the train (0) to the center of the axle.

(Train data will more likely come to me in the form of an ordered list of Car objects, each of which has a length and a list of integers representing axle distances from the front of that car, but it all gets aggregated into a single list, since all axles are the same to me.)

My switches are all within several hundred feet, and will often be entirely covered by the train, The switches can be at any interval from hundreds of feet to several inches apart, and is in the same form as the train: {0,8,512,520,...}, indicating the distances from the beginning of the site to the center of the switch.

Finally, I know the distance at which the wheel activates the switch, in inches.

For example, using the above sample data, and a an activation distance of 8 inches, the first switch at X=0 would activate when the train hits X=40, meaning the train is 40 inches into the site. When the train hits X=48, the switch at X=8 is also activated. At X=56, the first switch goes off, and at X=64, the second switch also goes off. Different axles are turning different switches on and off as it crosses the site.

The train is usually running at speeds under 10 mph, but can go much higher. (Right now our simulation is capped at 30 mph, but higher would be great.)

Answer 1

Store the switch list as a doubly-linked list as indicated by Ben.

Keep a pointer in the wheel object (or structure, assuming there is one) to the next switch and the previous switch relative to your current position. Intialize these as the wheel is placed on the track.

As you move over each switch, swap out the "next" and "previous" switches in your wheel object for the new "next" and "previous" that can be quickly obtained by examining the doubly-linked list.

This avoids all searches, except possibly initial placement of the wheel.

Additionally, the "switch" structure could be used to hold a proximity pointer back to all of the wheels that list it as "previous" or "next". (There's a mutex here, so be careful of who updates this.) This can provide a quick update of who's approaching any given switch and their distance from it.

Answer 2

Pre-process your switch locations and sensitivity range into a list of track segments. Each segment has a length, and between each segment a set of switch 'on' or 'off' events.

switch_on ( 0 ), ( length: 8 ), switch_on ( 1 ), // x = zero here 
segment ( length: 8 ), switch_off ( 0 ),
segment ( length: 8 ), switch_off ( 1 ),
segment ( length: 488 ), switch_on ( 2 ),
segment ( length: 8 ), switch_on ( 3 ),
segment ( length: 8 ), switch_off ( 2 ),
segment ( length: 8 ), switch_off ( 3 ),
...

For each axle, have its current location also represented along with the track segment it is on.

If you're doing an event based simulation, the next event should be scheduled for the min value of the distance from an axle to the end of its current track segment. This is independent of the train speed, and accurate (you won't miss switches if the train goes faster). Store the events in a heap if necessary (it's often not worth it for less than 30 or so, profile the event scheduling if necessary).

Processing an event will be O(no-of-axles). Most steps will involve one or two switch state changes and a position update. At each event, one axle will cause one switch to go on or off (switches which would be simultaneous according to the data cause two events, zero time apart), and all axle times to the end of their segments need to be compared. You can either assume that all axles travel at the same speed or not; it doesn't matter as far as processing the events, it only makes the calculation of the time to reach the next switch specific to the axle in question.

If you're on a fixed time step simulation, then process all events which would have occurred up to the time at the end of the step, then one event to move the axles to the point they reach at the end of the step.

Answer 3

Assuming that Axle-to-Axle distances are always larger the activation distance, and that routes don't change frequently after the train enters, you should be able to speed things up with pre-calculation. Basically, for each switch, calculate a list of train travel distances at which it will toggle, then walk through the lists as the train advances.

Pseudocode:

axles  = {48,96,508,556,626,674,...}
switches ={0,8,512,520,...}
activate = 8
float toggledist[num_switches]
boolean switchState[num_switches]={false,false,false,...}
int idx[num_switches]

for (i in switches)
  n = 0
  for (a in axles)
    toggledist[n++] = switches[i]+axles[a]-activate
    toggledist[n++] = switches[i]+axles[a]+activate

travel= 0.0f;

each (cycle)
  travel += TrainVelocity*time;
  for (i in switches)
    while (trigger>=toggledist[idx[i]])
      switchState[i]=!switchState[i];
      //additional processing for switch change here, if needed
      idx[i]++;