PQS Altiudes and Terrain Height

[Whitecat106]

Hello everyone,

I have written and released a boat navigation plugin here, I am focusing on a new method of navigation using courses (lists of coordinates that a vessel follows across the surface). The issue I am having is that my current system avoids a ship being moved onto land based on the biome (currently only water is a valid biome).

However for making the ship navigate through the various rivers on Kerbin the shore biome must be used, but the big issue is that the shore biome is not unique to coastal waters and thus covers coastal land too, this could mean a vessel could be beached on land during an update. The only way I can think of preventing this would be to make a protovessel 'image' ahead of the actual vessel and from this detect collisions with land (however this would certainly slow the system down).

I am hoping that someone may be able to assist me with a different solution?

I am thinking along the lines of differences in the PQS height of the body and the actual surface height; but I do not know enough to understand whether this could be used, to determine if the latitude and longitude of a certain point lies at sea level (0 meters) (implying that the point is valid and the vessel can travel here) or beneath the actual surface (implying that the point is invalid)?

Any ideas / code would be greatly appreciated!

Thanks,

Whitecat106

Edited September 9, 2015 by Whitecat106

[EladDv]

maybe try and scan ahead a bit with raycasts and stay in the middle of a river by trying to get those distances equal? if you can get a point at each bank say 50 meters ahead from your current location you could calculate the middle point of the river with simple trigonometry and then calculate what bearing your ship needs to be to get there. and if you'd like to you could enter a small deviation (with set min and max from center) to make it less robotic or just make the distances longer(but that might be an issue with sharp turns)

[stupid_chris]

getting the terrain height on latitude/longitude data is very, very slow. Your solution would probably be into raycasts, yeah.

[Whitecat106]

Thanks! I had noticed a reduced speed during jumps when checking by the terrain height (that didnt work anyway) so anything that can make everything smooth is a bonus. All I need is to be able to determine if a point lies at around 0m, the bearing and everything is pre-calculated and running in the background (on rails) with 30 second updates so not much detail is necessary its just verification so the player does not switch back to the vessel halfway through and find it sat 15 meters under the river bank and exploding..

I have no idea what a Raycast even is so I will do some research and see what I can come up with!

[EladDv]

raycast is basically you pointing at some direction and the game telling you what's there. it could be limited by distance (good for sea travel) and can return null if it hit nothing

[Whitecat106]

raycast is basically you pointing at some direction and the game telling you what's there. it could be limited by distance (good for sea travel) and can return null if it hit nothing

Thanks, it sounds like the exact solution!

I assume this process would work for background vessels (non active)? Since the boundaries of Kerbin's surface still exist regardless of the GameScene?

The only possible issue would be say collisions with unloaded vessels upon loading of the flight scene since the vessels have no physical presence for the raycast to detect if they are beyond 2.5km or in the background but this is pretty unlikely (and unlucky) anyway!

[EladDv]

Thanks, it sounds like the exact solution!

I assume this process would work for background vessels (non active)? Since the boundaries of Kerbin's surface still exist regardless of the GameScene?

The only possible issue would be say collisions with unloaded vessels upon loading of the flight scene since the vessels have no physical presence for the raycast to detect if they are beyond 2.5km or in the background but this is pretty unlikely (and unlucky) anyway!

i dont know if it works for unloaded entities but worst case and it dosnt you just do it once when loaded and set the course and keep a bunch of points to move between.

(Psudo code)

raycast casts[]=cast(Ship.position,direction,distance),cast(Ship.position,direction2,distance);
MiddlePoint=GetCenter(casts);
while(cast(middlePoint,MiddlePointToEndPointDirection,MTEDistance)!=null)
{
     Navigator.add(middlePoint);
     raycast casts[]=cast(middlePoint.position,direction,distance),cast(middlePoint.position,direction2,distance);
     MiddlePoint=GetCenter(casts);
 }
Navigator.add(endPoint);

- - - Updated - - -

actually you might want to use do{}....While() for eliminating the initial configuration.

[nightingale]

Have a look at the BiomeTracker class in Contract Configurator. It's used in the science subsystem to come up with a rough estimate of what proportion of a given biome is water by sampling points. It samples a 2048 x 4096 array of points, and completes in the background within a minute or two on my machine (to give you an idea of the slowness of this method). In my case I just store the aggregated value (biome + the ratio of it that is water).

double lonRads = Math.PI * longitude / 180.0;
double latRads = Math.PI * latitude / 180.0;
double cosLon = Math.Cos(lonRads);
double sinLon = Math.Sin(lonRads);
double cosLat = Math.Cos(latRads);
double sinLat = Math.Sin(latRads);
Vector3d radialVector = new Vector3d(cosLat * cosLon, sinLat, cosLat * sinLon);
double height = body.pqsController.GetSurfaceHeight(radialVector) - body.pqsController.radius;

There's also a CelestialBody.GetSurfaceNVector(lat, lon) method that is a bit easier coding-wise - can't remember why I didn't use it in the BiomeTracker code, this might've been slightly less expensive. Or it was because I had the numbers in (u, v) coordinates, so it was easier to just do it manually.

I'm thinking that if you use this in combination with an A* pathfinding algorithm (only checking for whether a point is water when you examine it) you'll get reasonable enough performance (although I'm 100% sure you'll have to do it as a coroutine). You'll probably also need some added smarts to increase the search resolution when you hit a "wall" - otherwise you'll by trying out too many points and performance will suffer, or you won't be at a detailed enough resolution to find the rivers/inlets.

EDIT: Oh and when I say it takes a couple minutes, that is in a coroutine that is limited to 0.01 seconds per invocation - that way it falls beneath the player's notice in terms of the performance hit.

Edited September 9, 2015 by nightingale

[Whitecat106]

Have a look at the BiomeTracker class in Contract Configurator. It's used in the science subsystem to come up with a rough estimate of what proportion of a given biome is water by sampling points. It samples a 2048 x 4096 array of points, and completes in the background within a minute or two on my machine (to give you an idea of the slowness of this method). In my case I just store the aggregated value (biome + the ratio of it that is water).

double lonRads = Math.PI * longitude / 180.0;
double latRads = Math.PI * latitude / 180.0;
double cosLon = Math.Cos(lonRads);
double sinLon = Math.Sin(lonRads);
double cosLat = Math.Cos(latRads);
double sinLat = Math.Sin(latRads);
Vector3d radialVector = new Vector3d(cosLat * cosLon, sinLat, cosLat * sinLon);
double height = body.pqsController.GetSurfaceHeight(radialVector) - body.pqsController.radius;

There's also a CelestialBody.GetSurfaceNVector(lat, lon) method that is a bit easier coding-wise - can't remember why I didn't use it in the BiomeTracker code, this might've been slightly less expensive. Or it was because I had the numbers in (u, v) coordinates, so it was easier to just do it manually.

I'm thinking that if you use this in combination with an A* pathfinding algorithm (only checking for whether a point is water when you examine it) you'll get reasonable enough performance (although I'm 100% sure you'll have to do it as a coroutine). You'll probably also need some added smarts to increase the search resolution when you hit a "wall" - otherwise you'll by trying out too many points and performance will suffer, or you won't be at a detailed enough resolution to find the rivers/inlets.

EDIT: Oh and when I say it takes a couple minutes, that is in a coroutine that is limited to 0.01 seconds per invocation - that way it falls beneath the player's notice in terms of the performance hit.

Thanks nightingale!

This was exactly what I was looking for and proves easier than Raycasts..

My code calculates a new latitude and longitude every 30 seconds and then verifies with the code you have provided above so thank you very much! I will make use of your algorithm idea in a following update when everything gets path finding and the 30 second check can move to a much faster background check!

The raycasts (which although work for background vessels, they aren't able to work when a vessel's new coordinates are actually underneath the surface of Kerbin (such as under a mountain) the raycasts cannot seem to detect the surface from within so the vessels spawn underground), plus the fact that at least 8 raycasts would need to be made to make sure no part of the vessel (since its orientation/heading can change - especially tricky if the root part of the vessel is at one end rather than central) impacts land.

Thanks everyone for your advice! I will look back to this thread for a future update to include some pathfinding rather than just avoidance!

[stupid_chris]

.... This is what I was warning against. Using the PQS to get height by latitude/longitude is extreeeemely slow. You will create a ridiculous amount of overhead if you use this often.

The PQS system is an incredibly complex mess, and it's ridiculously slow. Each access to pqsController.GetSurfaceHeight consumes a lot of resources, and really, if you're gonna be doing this as often as I think you will, that's not gonna work out. 20 Raycasts is going to be loads faster than just one access to this method.

[Whitecat106]

.... This is what I was warning against. Using the PQS to get height by latitude/longitude is extreeeemely slow. You will create a ridiculous amount of overhead if you use this often.

The PQS system is an incredibly complex mess, and it's ridiculously slow. Each access to pqsController.GetSurfaceHeight consumes a lot of resources, and really, if you're gonna be doing this as often as I think you will, that's not gonna work out. 20 Raycasts is going to be loads faster than just one access to this method.

At the moment the system only does this once every 30 seconds and in this time the game jitters a tad as a vessel is despawned copied and respawned at the coordinates so for the time being its a quick solution that doesn't change much. But as I said the issue with Raycasts seems to be height related again, and I think will still require the body pqs, the way I see it (correct me if I'm wrong):

- The latitude and longitude are calculated and then passed to a check subroutine (this system) to make sure the new coordinates are on water at an altitude of close to 0.

- Since the altitude of these points based on the terrain is unknown without using the Pqs the raycast origin altitude is unknown

- From what I can see the raycast origin altitude is not the Pqs altitude from sea level? I'm not sure what I mean here but the issue is basically this:

The raycasts are sent out from the origin point to a distance of 100m (pretty safe for a boat), but since the origin altitude is unknown the raycasts are sent from the sea level which is below the terrain level which is within the object/pqs thing of Kerbins surface, from what I can see this means that raycasts do not detect the boundary from within so all of the 'pings' return false allowing the vessel to spawn here underground. I tried sending out raycasts in all six directions but none returned true when below the surface. I will definitely need to play around with this for path finding in the future.

[stupid_chris]

Maybe once every 30s, but how many times when that is done? If you're doing this just a few time at each of those 30s intervals, you'll have noticable jitter, and that's going to get real annoying during extended periods of play.

For raycasts, what you want to be doing is Physics.Raycast(origin, direction, out hitInfo, maxDistance, layerMask). Is there any part that *has* to be on any ship? If so you can easily set an origin point that is directly below that part, exactly on the ocean level, and from there on you can just raycast in the direction you want. If the method returns true, you know there is land in that given direction. Then what you can do is send some raycasts every few seconds to see if anything is around. Something like this:

        public float angle = 0;

        //Run this every few seconds
        public void CheckForLand()
        {
            Ray ray = new Ray();
            Vector3 pos = this.part.transform.position; //replace for any "origin" you want
            float ASL = FlightGlobals.getAltitudeAtPos(pos);
            Vector3 origin = pos - (FlightGlobals.getUpAxis(pos).normalized * ASL); //This is on the sea level
            //The next few lines make sure the direction is horizontal in case speed is slightly upwards (or downwards)
            Vector3 v = origin + this.part.vessel.srf_velocity.normalized;
            ASL = FlightGlobals.getAltitudeAtPos(v);
            direction = Quaternion.AngleAxis(angle, origin) * direction; //Rotates the vector a certain angle
            angle += 20; //Or whatever angle offset you want on each pass
            angle %= 360; //Caps the angle at 360
            RaycastHit hit = new RaycastHit();
            //Raycasting
            if (Physics.Raycast(origin, direction, out hit, 100, 1 << 15))
            {
                //Do stuff here, the distance of land is stored in hit.distance
            }

            //Same but in opposite direction
            if (Physics.Raycast(origin, -direction, out hit, 100, 1 << 15))
            {
                //Do stuff here, the distance of land is stored in hit.distance
            }
        }

This is a rough sketch, but something like that would work. My vector math may be a bit off but I think it makes sense. This does two casts per frame, and if run every few seconds, you could check all around the boat every now and then. Just to give you an idea, every solar panel does a raycast per second. So this isn't gonna be heavy. The PQS though would.

[nightingale]

<snip>

This is a rough sketch, but something like that would work. My vector math may be a bit off but I think it makes sense. This does two casts per frame, and if run every few seconds, you could check all around the boat every now and then. Just to give you an idea, every solar panel does a raycast per second. So this isn't gonna be heavy. The PQS though would.

Looks like we're solving different problems, and to be honest I'm not sure which one is the one that WhiteCat is looking to have solved.

I assumed he is looking for navigation on a global scale (ie. get from point A to point B halfway across the globe). I also assumed that it needed to work when not focused on the vessel in question. Under those restrictions, I don't imagine the raycasting would work (I have no idea how/when the colliders for the celestial body are loaded, but assume they're only loaded for a fairly localized area around the active vessel.

And totally agree with you - the calls into PQS are a massive performance hit - but I don't see any better options if the restrictions above are correct.

So WhiteCat - if indeed you need localized navigation, then the solution stupid_chris provided is far better than mine.

[stupid_chris]

If the PQS is used on on-rail vessels, this will have a massive performance hit if only a few vessels are doing this in the background, and I strongly reccomend to not do this.

[nightingale]

If the PQS is used on on-rail vessels, this will have a massive performance hit if only a few vessels are doing this in the background, and I strongly reccomend to not do this.

Right - which is why I recommended it in a coroutine with a per-invocation time limit as in my example.

[Whitecat106]

Maybe once every 30s, but how many times when that is done? If you're doing this just a few time at each of those 30s intervals, you'll have noticable jitter, and that's going to get real annoying during extended periods of play.

For raycasts, what you want to be doing is Physics.Raycast(origin, direction, out hitInfo, maxDistance, layerMask). Is there any part that *has* to be on any ship? If so you can easily set an origin point that is directly below that part, exactly on the ocean level, and from there on you can just raycast in the direction you want. If the method returns true, you know there is land in that given direction. Then what you can do is send some raycasts every few seconds to see if anything is around. Something like this:

        public float angle = 0;

        //Run this every few seconds
        public void CheckForLand()
        {
            Ray ray = new Ray();
            Vector3 pos = this.part.transform.position; //replace for any "origin" you want
            float ASL = FlightGlobals.getAltitudeAtPos(pos);
            Vector3 origin = pos - (FlightGlobals.getUpAxis(pos).normalized * ASL); //This is on the sea level
            //The next few lines make sure the direction is horizontal in case speed is slightly upwards (or downwards)
            Vector3 v = origin + this.part.vessel.srf_velocity.normalized;
            ASL = FlightGlobals.getAltitudeAtPos(v);
            direction = Quaternion.AngleAxis(angle, origin) * direction; //Rotates the vector a certain angle
            angle += 20; //Or whatever angle offset you want on each pass
            angle %= 360; //Caps the angle at 360
            RaycastHit hit = new RaycastHit();
            //Raycasting
            if (Physics.Raycast(origin, direction, out hit, 100, 1 << 15))
            {
                //Do stuff here, the distance of land is stored in hit.distance
            }

            //Same but in opposite direction
            if (Physics.Raycast(origin, -direction, out hit, 100, 1 << 15))
            {
                //Do stuff here, the distance of land is stored in hit.distance
            }
        }

This is a rough sketch, but something like that would work. My vector math may be a bit off but I think it makes sense. This does two casts per frame, and if run every few seconds, you could check all around the boat every now and then. Just to give you an idea, every solar panel does a raycast per second. So this isn't gonna be heavy. The PQS though would.

Ahh I understand this much better now, my only question now is: Is there a way of getting the vector position of a latitude and longitude without a call to the PQS system and causing the performance hit? Since the vessel does not actually exist at the coordinates of the raycast yet.

Looks like we're solving different problems, and to be honest I'm not sure which one is the one that WhiteCat is looking to have solved.

I assumed he is looking for navigation on a global scale (ie. get from point A to point B halfway across the globe). I also assumed that it needed to work when not focused on the vessel in question. Under those restrictions, I don't imagine the raycasting would work (I have no idea how/when the colliders for the celestial body are loaded, but assume they're only loaded for a fairly localized area around the active vessel.

And totally agree with you - the calls into PQS are a massive performance hit - but I don't see any better options if the restrictions above are correct.

So WhiteCat - if indeed you need localized navigation, then the solution stupid_chris provided is far better than mine.

I understand what you mean, yes the navigation is globally and solely in the background right now, my code is abit of a mess at the moment but since this is a background process and that there is a noticeable jitter every 30 seconds due to the vessel.die and spawn system used to teleport the vessel to a new position while on rails, I think that unless a player would be moving an armada of boats the jitter would be okay (especially since high time warp practically limits this to only one jitter interrupting timewarp as the vessel arrives at the destination). When it comes to active pathfinding raycasts would be the way to go. Ill see what people say and how performance is when I release the update with the PQS system and switch to raycast if need be!

[Fengist]

Another solution may be sphereCast. It's like raycast but sends out a sphere of a size you can determine instead of a beam. Using it, you won't have to count on terrain being directly in front of you and being infinitesimally small. You can cast a 20 meter sphere and determine if the river is wide enough to navigate.

You may also want to look at rigidbody.sweeptest and physics.capsulecast. I've never played with them but look like they may do what you're wanting.

Edited September 10, 2015 by Fengist

[EladDv]

Another solution may be sphereCast. It's like raycast but sends out a sphere of a size you can determine instead of a beam. Using it, you won't have to count on terrain being directly in front of you and being infinitesimally small. You can cast a 20 meter sphere and determine if the river is wide enough to navigate.

You may also want to look at rigidbody.sweeptest and physics.capsulecast. I've never played with them but look like they may do what you're wanting.

the problem is that he's trying to get a path in the river and for that if you just periodically raycast the banks it's much more efficiant then the sphere cast due to the size

[nightingale]

Ahh I understand this much better now, my only question now is: Is there a way of getting the vector position of a latitude and longitude without a call to the PQS system and causing the performance hit? Since the vessel does not actually exist at the coordinates of the raycast yet.

CelestialBody.GetWorldSurfacePosition() just does some fairly simple trigonometry, it doesn't use the PQS system at all (but you need to provide an altitude). If the collider is loaded at the given latitude/longitude, then you could use it to raycast straight down from a specific altitude that is above the max terrain height and get the terrain height at the given position that way. However - this is what I was warning you about - I doubt that colliders are loaded for very far from the active vessel. Tens of kilometers is probably fine, but I suspect if you try to do this hundreds of km away it'll just return no hit (or maybe a default hit at sea level? haven't really looked into planetary colliders much).

[...] there is a noticeable jitter every 30 seconds due to the vessel.die and spawn system used to teleport the vessel to a new position while on rails [...]

Yikes. There has got to be a better way to move a vessel that's on rails. Looking at the persistence file, the stuff that I see that would need to be changed on a teleport are lat, lon, alt, nrm (normal vector for vessel's "up"), rot (quaternion for the vessel's rotation) and ORBIT. All of these are calculated in my code for SpawnVessel. Some are done directly in the config node before writing it though - those one you'll have to figure out how to get them to change in the protovessel if they are needed for what you are doing.

[Whitecat106]

CelestialBody.GetWorldSurfacePosition

() just does some fairly simple trigonometry, it doesn't use the PQS system at all (but you need to provide an altitude). If the collider is loaded at the given latitude/longitude, then you could use it to raycast straight down from a specific altitude that is above the max terrain height and get the terrain height at the given position that way. However - this is what I was warning you about - I doubt that colliders are loaded for very far from the active vessel. Tens of kilometers is probably fine, but I suspect if you try to do this hundreds of km away it'll just return no hit (or maybe a default hit at sea level? haven't really looked into planetary colliders much).

Yikes. There has got to be a better way to move a vessel that's on rails. Looking at the persistence file, the stuff that I see that would need to be changed on a teleport are lat, lon, alt, nrm (normal vector for vessel's "up"), rot (quaternion for the vessel's rotation) and ORBIT. All of these are calculated in my code for SpawnVessel. Some are done directly in the config node before writing it though - those one you'll have to figure out how to get them to change in the protovessel if they are needed for what you are doing.

I will experiment with the GetWorldSurfacePosition(), I think I have sometimes been confusing this for a PQS call, but yeah I understand what you mean I have no idea how colliders work beyond a flight scene, for instance the tracking station - would any colliders exist at all in this scene since no vessel really 'exists'?

My spawn vessel code is actually derived from your contract configurator code, it is the only method for spawning vessels I have found that works in the background and is pretty smooth (Previously with my Orbital Decay mod I used derivations from HyperEdit since this could manipulate vessel orbits in the background but sadly its landing function does not function for non active vessels). My code basically creates a copy of the craft information at the moment of update (at the vessel not protovessel level - so not very optimized), then deletes the original craft using vessel.die() (probably the big cause of the jitter) and spawns the copy in a very similar way to the SpawnVessel code. So I believe it is the removal of the original that actually causes the jitter. That being said the jitter is no more noticeable than the small pauses that occur sometimes when an asteroid enters a different SOI.

I have the exact same issue with Orbital Decay, to a greater degree, KSP just does not like changing vessel positions in the background. It would be a lot simpler to have a method of accessing the code used for the calculation of the vessel positions which moves the vessels themselves, from this, rather than having to force orbits/positions to change, a variable could just be altered in the 'natural' (probably somewhat hardcoded) way that KSP/Unity makes vessels orbit regardless of activity or background. If you get what I mean? I'm sure somewhere deep dark in KSP's code there is a subroutine of 'UpdateOrbit(vessel)' set to 'protected' rather than 'static' that could make things like this less forced. The issue has been around ever since the first teleport/hyperspace/orbital decay/solar sail mods and ideas came around (with most solar sail mods now using derivatives of Hyperedits orbital code too).

As Fengist said I will look at rigidbody.sweeptest and physics.capsulecast too, for now the issue is sort of fixed atleast until my 1.3.0 release with pathfinding.