Switcher behavior isn't atomic

chrispbs commented 7 years ago

BkCommonLib version: 1.12.2-v1

TrainCarts version: 1.12.1-v3-SNAPSHOT (#103)

Spigot version: 1.12.1

Problem or bug:

Switcher routing operations aren't atomic. (I can't decide if this is a bug, or a misunderstanding about the way switchers work and therefore a feature request - you be the judge!)

I have a pair of double junctions forming a branch line that leads to a station. The green line shows the paths northbound trains can take, and the blue line shows the paths southbound trains can take (please forgive the amateurish Paint job):

Track layout

Northbound trains that serve the station are tagged stationN; southbound trains that serve the station are tagged stationS. I've implemented this using switchers and waiters as follows (red = waiter, yellow = switcher, orange = waiter above a switcher):

Northern junction:

Southern junction:

This setup works most of the time, but falls apart when two trains approach a switcher at the same time: here's an example of it happening with a northbound train on the branch line and a southbound train on the main line. From what I understand, here's what happens:

The northbound train arrives at the 5-block waiter on the branch line, looks 5 rails ahead and sees them all clear. The train proceeds.
The southbound train arrives at the 5-block waiter on the main line, looks 5 rails ahead and sees them all clear (because the northbound train hasn't reached the switcher yet). The train proceeds.
The northbound train arrives at the switcher. The logic causes the rail to switch to west-east position.
The southbound train arrives at the switcher. The logic causes the rail to switch to north-south position.
The northbound train, which is still passing over the switcher, splits; the back half of the train gets taken southbound down the main line.

The problem gets compounded further down the line: trains end up colliding and switching onto opposing rails, leading to a (literal) trainwreck requiring manual cleanup.

Expected behaviour:

This could (I think) be solved in one of two ways:

Making switcher operations atomic: a train can't pass over a switcher if another train is already being routed by it. Ideally, trains would be placed in a queue in the order in which they arrived at the switcher, would be stopped on the rail before the switcher awaiting their turn to proceed, and would then automatically proceed when allowed. (Maybe it'd be too much to retrofit this into a switcher, and a new sign type would be needed.)
Having a way of defining a mutual exclusion zone for an arbitrary area of track: only one train can enter the mutual exclusion zone at a time, the others being queued in the same way as described above. Perhaps there could also be a way of defining priorities for trains approaching from certain directions, so (for instance) main line traffic always gets right of way over branch line traffic. I tried doing this with detectors, but there's just not enough track space to fit in all the signs, and it wouldn't solve the queueing problem so there's the possibility that the same problem might still occur.

The second option seems like the most practical from the point of view of me, a user - I could define the following three mutual exclusion zones which (I think) would solve my problem:

Proposed mutual exclusion zones

Perhaps you, the developers, feel differently... :)

Steps to reproduce:

Hopefully the screenshots above are sufficient for understanding how the problem can be reproduced; it's always reproducible, given enough time for two trains to arrive at a switcher simultaneously. If not, let me know and I'll give you access to a private server that demonstrates the problem.

bergerkiller commented 7 years ago

I never expected to see broken mutexes in train form! I understand the issue and I'd say it should be labeled a bug. This is the main reason waiter signs exist in the first place.

chrispbs commented 7 years ago

Interestingly, the new waitDistance property in commit cf756a8 (#167) can be used to wallpaper over this bug, because any wait distance applied to two trains is sufficient to ensure that one always waits for the other to clear the switcher rail before proceeding. However, if trains are frequent enough, this can quickly lead to a deadlock scenario, in which trains passing down the mainline are both blocking trains leaving the branch line and being blocked by trains entering the branch line:

Deadlock

I haven't thought about this for long enough to figure out whether being able to prioritize trains from certain directions over others on the switcher rail would fix the problem.

bergerkiller commented 7 years ago

Well it took some time but I've gotten a first version of this ready. Went with the obvious and called it a mutex. You can define cuboid regions and ensure mutual exclusion: only one train can be in that zone at one time, new trains trying to enter will be blocked. It still has a few minor flaws to it (the obvious one being deadlocks with more than one mutex-), but for a first version it will do nicely.

https://puu.sh/xXWcL/8389881154.mp4

https://ci.mg-dev.eu/job/TrainCarts/143/

Deadlocks are tricky, and to fix that sort of stuff I will need to roll out a more advanced system. Covering multiple intersects with a single mutex solves all deadlock issues (just like actual mutexes do). If I replace the scene in the video with 4 mutex signs underneath the crossings, deadlocks happen quite quickly.

chrispbs commented 7 years ago

This sounds perfect, thanks - I'll download build #143 and see if I can create those mutex zones I drew. Am I correct in thinking that I no longer need any of the waiters if this works?

bergerkiller commented 7 years ago

Yeah, you don't need any waiter signs then

chrispbs commented 7 years ago

I'm getting frequent IndexOutOfBoundsExceptions with TrainCarts build #144 and BKCommonLib build #251.

This is at the southern junction I originally described, but with the waiters removed. There aren't any mutexes, just the switchers. All trains have their waitDistance property set to 2.

If I destroy the rails immediately north and south of the north-west switcher at the southern junction, and spawn a northbound train to go via the branch line, the north-west switcher works fine (although of course the train can't go in any other direction):

Working

But if I recreate either of the removed rails, northbound trains that go via the branch line stop on top of the north-west switcher:

Not working

I get the following exception sometimes, but not always (I haven't figured out the pattern yet):

[18:29:23 ERROR]: [Train_Carts] Failed to perform physics on train 'train1' at null:
[18:29:23 ERROR]: [BKCommonLib] java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
[18:29:23 ERROR]: [BKCommonLib]   at java.util.ArrayList.rangeCheck(ArrayList.java:653)
[18:29:23 ERROR]: [BKCommonLib]   at java.util.ArrayList.get(ArrayList.java:429)
[18:29:23 ERROR]: [BKCommonLib]   at com.bergerkiller.bukkit.tc.controller.MinecartGroup.head(MinecartGroup.java:115)
[18:29:23 ERROR]: [BKCommonLib]   at com.bergerkiller.bukkit.tc.controller.MinecartGroup.head(MinecartGroup.java:119)
[18:29:23 ERROR]: [BKCommonLib]   at com.bergerkiller.bukkit.tc.controller.MinecartGroup.getSpeedAhead(MinecartGroup.java:994)
[18:29:23 ERROR]: [BKCommonLib]   at com.bergerkiller.bukkit.tc.controller.MinecartGroup.doPhysics_step(MinecartGroup.java:1137)
[18:29:23 ERROR]: [BKCommonLib]   at com.bergerkiller.bukkit.tc.controller.MinecartGroup.doPhysics(MinecartGroup.java:955)
[18:29:23 ERROR]: [BKCommonLib]   at com.bergerkiller.bukkit.tc.controller.MinecartMember.onTick(MinecartMember.java:1424)
[18:29:23 ERROR]: [BKCommonLib]   at com.bergerkiller.bukkit.common.internal.hooks.EntityHook.onTick(EntityHook.java:114)
[18:29:23 ERROR]: [BKCommonLib]   at com.bergerkiller.mountiplex.reflection.util.fast.GeneratedInvoker$mplgen27186555.invokeVA(Unknown Source)
[18:29:23 ERROR]: [BKCommonLib]   at com.bergerkiller.mountiplex.reflection.ClassInterceptor$CallbackMethodInterceptor.intercept(ClassInterceptor.java:637)
[18:29:23 ERROR]: [BKCommonLib]   at net.minecraft.server.v1_12_R1.EntityMinecartRideable$$EnhancerByCGLIB$$79f995be.B_(<generated>)
[18:29:23 ERROR]: [BKCommonLib]   at net.minecraft.server.v1_12_R1.World.entityJoinedWorld(World.java:1518)
[18:29:23 ERROR]: [BKCommonLib]   at net.minecraft.server.v1_12_R1.World.h(World.java:1493)
[18:29:23 ERROR]: [BKCommonLib]   at net.minecraft.server.v1_12_R1.World.tickEntities(World.java:1346)
[18:29:23 ERROR]: [BKCommonLib]   at net.minecraft.server.v1_12_R1.WorldServer.tickEntities(WorldServer.java:646)
[18:29:23 ERROR]: [BKCommonLib]   at net.minecraft.server.v1_12_R1.MinecraftServer.D(MinecraftServer.java:750)
[18:29:23 ERROR]: [BKCommonLib]   at net.minecraft.server.v1_12_R1.DedicatedServer.D(DedicatedServer.java:371)
[18:29:23 ERROR]: [BKCommonLib]   at net.minecraft.server.v1_12_R1.MinecraftServer.C(MinecraftServer.java:651)
[18:29:23 ERROR]: [BKCommonLib]   at net.minecraft.server.v1_12_R1.MinecraftServer.run(MinecraftServer.java:555)
[18:29:23 ERROR]: [BKCommonLib]   at java.lang.Thread.run(Thread.java:748)

This happens even when there are no other trains present (i.e. after issuing a /train destroyall).

bergerkiller commented 7 years ago

This can only happen if the train turned into a size of 0 (so empty). It's odd, and can do no harm here because the train is gone anyway, so erroring on the update doesn't matter in this case. I fixed the error though.

https://ci.mg-dev.eu/job/TrainCarts/145/

I suspect its creating an empty train somewhere... maybe as part of the train splitting logic.

bergerhealer / TrainCarts