Traffic Jams and Collisions

[Lumen]

Getting back into Starmade I'm sure many people have a problem with how the A.I. operate, more notably, the desire to ram into and lock onto other entities and stay there. I'm no expert in coding and handling process management, but these kinds of lock ups are going to cause several problems.

1. Processor will be wasted on stuck entities attempting to move in a direction.
2. NPC trading will grind to a hault
3. Drones will get stuck, asteroids won't be mined, pirates won't be engaged.
4. NPC faction actions will halt
5. It looks dumb

Fix actions

Out of combat Phase Shifting
For now simply eliminate clipping unless in combat. This will allow free traversing until a better AI is developed. The goal is to ease traffic and enable a living universe. Phase shifting feels better story wise seeing ships pass through stations, planets etc rather than attempting to reproduce with whatever object that's in its way.

Ship Shields side effect, Repulse
Adding a bubbling feature to shields may simply keep entities at a distance. I'm guessing scripting will be needed to override coordinates if this shield bump occurs. If bump -> external inertial dampeners until speed = 0, reamine until x.

Traffic routes
At the moment I believe the AI simply heads towards the 3d point without a care in the world. Establishing highways of some sort may help for auto piloting and NPC pilots when crews become a thing. If we were to divide traffic into 4 quadrants with two variables, up/down, left/right, AI traffic could set a point and depending on if the change is positive or negative, will slightly adjust the quadrant traffic route.

Say with X,Y coordinates, Jake is heading from 0, 0 to 2, 2. Both are positive so Jake stays to the right (Lean to the X axis) of the original flight path. When returning, lean right again (Leaning to the Y Axis) because the net path change would be -2, -2.


Just an observation and attempt at a simple solution. Nitpick or anything all you like. If you don't care don't respond.

 

[Nebulon-B_Frigate_FTW]

Limited shield repulsion would be great, as long as it weakened shields so ramming still did something to shielded targets.
Traffic routes are likely far off when NPCs get a rework.

 

[Szlfsz]

Yeah, AI pathfinding was, is, and will be troublesome, for several reasons..
- it is very CPU intense
- in a crowded situation, where every entity is moving, recalculations would be endless
- generaly it is a form of art in code writing, rarely done right, mostly becouse it is frkin' hard to do even in 2D, and this is Starmade with 360 degree of freedoom

But go ahead, help the devs with suggestions! Like implement flocking for fleets, or figure out what an AI sholud do to ram something intentionally, so to know how to avoid it

 

[Szlfsz]

For docking on stations, and special maneuvers occuring regularly, I suggest pre definied paths what an AI can follow...

For exaple a spiraling pathway toward the docking port, and an aproaching AI ship can join the pre-definied path at any point where it would cross the path first.. or the nearest point of the path to its aproach vector ...depending on what direction it is coming from...

...almost like pickup rails... more like resizable to the scale of the object the AI is targeting, but not necessary that blocky but curvy and invisible to the player.. even players could use it to autodock

 

[MacThule]

Very good idea!

Ship Shields side effect, Repulse
Adding a bubbling feature to shields may simply keep entities at a distance. I'm guessing scripting will be needed to override coordinates if this shield bump occurs. If bump -> external inertial dampeners until speed = 0, reamine until x.

I'm not too keen on this particular approach - it has side effects. There is already a collision prevention mechanic that kicks in when you rush towards an enemy ship at speed and it's a real pain. I used to be able to dive-bomb targets with torpedos on a Missile-pulse bombs, executing a very tight, high-speed turn up once I got close enough to the target's hull to clear it by 10 or 20 meters, but since the anti-collision optimization that tactic is gone. Once you get moderately close to your target at speed and if your trajectory intersects their hull you start being randomly warped around to force-prevent a collision.

Traffic routes
At the moment I believe the AI simply heads towards the 3d point without a care in the world. Establishing highways of some sort may help for auto piloting and NPC pilots when crews become a thing. If we were to divide traffic into 4 quadrants with two variables, up/down, left/right, AI traffic could set a point and depending on if the change is positive or negative, will slightly adjust the quadrant traffic route.

This is brilliant and should be easy to implement in a limited fashion. If NPC fleets used a small, random offset value it would reduce collisions a lot. Eloquent.

 

[Nosajimiki]

Big issue with repulsion based AI pathfinding to prevent collision is that it is a multi-body problem, similar to the 3-body problem in astrophysics but if gravity were a negative force. Basically, it's easy to figure out how two bodies interact with each-other in real space because they are just exerting their forces on each other each cycle. Once you introduce many bodies, then A repels from B & C, B repels from A & C, and C repels from A & B physics gets weird and you have the following issues to content with.

1 - You can only ever approximate the effect of more than 2 bodies exerting on each other. This creates a lot of risk of strange behaviors under lag when such approximations will become wildly less accurate.
2 - Counter forces canceling each other can cause ships to want to vibrate like heated molecules in a solid state. Basically, if all the guys on the outside of a group of bodies want to converge on the same enemy, then they will want to drift into the pack of ships until they create equilibrium with the forces pushing outward, the guys on the inside will all exert their own pushes outward as well. In theory this would make everything fly in formation, but in reality they will be constantly shoving each other causing a bunch of lag. It gets even more complicated if ships want to converge on different targets and need to try to push their way through each other's anti-gravity bubbles.

Pre-defined lanes will not help if you have things that intersect them like someone's home base being off-center in a system. It also does not address how ships will maneuver in a battle. A variation to this approach is dynamically computed flight paths. Here, ships take turns carving out areas of space saying "this is where I plan to be for the next few seconds". So ship A reserves the straightest possible flight path to his target by extruding his hitbox through space over distance. Then the next ship does the same, but without overlapping with the other guy's reserved flight path, and you repeat this process for everyone. The issues here though are as follows:
1 - Players do not participate in these flight paths; so, AI would have a hard time working alongside players for this.
2 - Minor things that alter flight paths, like turret debris drifting into your way or recoil, could cause a cascade of problems.
3 - Defining how big flight paths need to be may be difficult based on server settings and individual ships since some have way more loose controls than others.
4 - AI will need additional case handling for when a viable path does not exist.
5 - Lots of potential front-load processing may cause lag spikes.

These are both pretty imperfect and resource heavy systems and does not even begin to address how ships will perform tactically. With enough optimization, either system may work, but as you can see with the secondary issues that there would need to be a lot of finesse in how to handle these things; so, it's not really a particularly easy thing to solve compared to AI in other games where more factors are a given or processing resources are less scarce