Plane pathfinding

[Scratch]

I was wondering how exactly does it work, what part of the plane path finding is it that takes so much CPU usage. Puzzles me because it seems a simple thing to do.

Now pathfinding works by giving a unit a destination coord, and all the plane does is ramp speed up/down according to distance away, or change its angle based on what vector it wants to go in until its pointing right at it. So why does it need to take so much CPU(unless it is engaging enemy units).

Units on the ground take less CPU effort, and they have to deal with ground obstacles. But planes have no obstacles. So why is this?

[lurker]

planes. don't. path.

[ILMTitan]

Pathfinding on the ground is relatively simple, because all of the obstacles are placed in a 2D matrix, for which lookup is very fast. Flying units, however, have to maneuver in a 3 dimensional space, for which there is no simple matrix. That means it has too look up individual units and check their position. I am not fully familiar with that section of the code, so I can only tell you I believe there is other optimizations going on, but I believe that is the crux of the problem.

[Tobi]

And as lurker said, it really isn't pathfinding, at best it's collision avoidance

(but I'm not into the details of that code so much that I know exactly what it does)

[Argh]

Some optimization could be made, by allowing game designers to control a variable that is currently derived from the plane's model format, namely the variable "radius", shown here, in context, from here:

Code: Select all

		if (collide && (aircraftState == AIRCRAFT_FLYING || aircraftState == AIRCRAFT_CRASHING)) {
			vector<CUnit*> nearUnits = qf->GetUnitsExact(pos, owner->radius + 6);
			vector<CUnit*>::iterator ui;

The other thing that should probably get done at some point is to change the code to actually check for collisions with the ground. It looks really silly when planes ram the ground, simply because they cannot detect it, then take no damage...

[manored]

Planes cant see the ground? that explains a lot :)

[Argh]

One easy fix, for the planes-can't-see-the-ground issue, would be to just get the ground heights at maybe 5 positions ahead of the plane, proportional to its speed, every SlowUpdate or so, to check for both really extreme changes in height ("hey, there's a mountain coming up") or for really variable height ("hey, let's fly above this crap, and not move up and down like crazy"). That would solve two major problems, which is that planes don't see the ground ahead of them, and yet they try to remain at a relative height Y from the ground, in their steering code, which results in really stupid behaviors when they travel over ground that isn't fairly flat...

Another good fix, which would probably improve performance a lot, is instead of having every plane everywhere check for potential collisions with other planes every frame... have each check on a random frame, from 1 --> SlowUpdate, and use a much larger radius for the check. Then they'd get a much more advanced warning, steer around each other much more reliably, and probably eat a lot fewer resources, because the load, per-frame, would be a lot lower, and it would be distributed among multiple frames...

[Scratch]

I'm of the opinion that we should almost completely get rid of collision avoidance for planes as it serves no useful function other than not rendering two or more planes in the same space, which doesn't bother me much, that is to say, for the benefit of collision detection for planes vs. the amount of gameplay lag it creates, we could just go ahead and get rid of it.

[Argh]

Actually, any game / mod that doesn't want planes to check for collisions can already do so.

Having tested that... well, it just looks really awful, frankly. Even in OTA view. Let alone any other POV.

I wouldn't want it to be mandatory.

[Scratch]

Another good fix, which would probably improve performance a lot, is instead of having every plane everywhere check for potential collisions with other planes every frame... have each check on a random frame, from 1 --> SlowUpdate, and use a much larger radius for the check. Then they'd get a much more advanced warning, steer around each other much more reliably, and probably eat a lot fewer resources, because the load, per-frame, would be a lot lower, and it would be distributed among multiple frames...

I don't understand completely, your telling me spring checks for spherical proximity every frame for every plane in comparison for every other plane?

So the solution you have is to only do collision checks for planes if they are within visual range of the plane then? This would make more sense.

One other more intelligent solution might be (although more cpu intensive) to check projected vectors of other planes in flight for intersection with itself on its own projected course, then do a radius clearance check, and if it passes to continue flying in that direction, or go up or below those projected collision paths by amount of the radius clearance * 2 or something.

I'm not sure how much sense that made but it would be interesting, because you could get genuine midair collisions if things get to heated up and then blow planes up kamikaze style. Of course, you would have to follow some coding rules with this one to make it feasible -

- only make checks if they come within a certain radius such as the turning rate of the plane multiplied by its size radius
- Make all trigonometric calculations ahead of time, no floating point calculations
- It may even be more efficient to use bounding box method to check for proximity, and also, why is spherical so important, neither checks truly take into account the polygons on the plane.

That would be going off on a tangent so just throwing it out there for the fun of it. I was playing Emain Macha the other day, and there are many people who don't play it just because their CPU won't handle the load of a fighter patrol.

[Argh]

I don't understand completely, your telling me spring checks for spherical proximity every frame for every plane in comparison for every other plane?

No, it just does a spherical check for 6X the size of the plane's hitsphere radius. Which is not a very effective way of going about this, tbh, as that doesn't take into account velocity- fast-moving planes don't get any time to predict collisions, slow-moving ones check far too often.

So the solution you have is to only do collision checks for planes if they are within visual range of the plane then? This would make more sense.

That's not what I was saying, exactly, but it's something like the general idea. Basically, what I'm saying is, "check a much larger radius, but check it a lot less often". IOW, get planes turning away from collisions well before it's an emergency, and allow game designers to alter a simple variable to manually set the value of (radius) if they choose to do so, to maximize efficiency.

One other more intelligent solution might be (although more cpu intensive) to check projected vectors of other planes in flight for intersection with itself on its own projected course, then do a radius clearance check, and if it passes to continue flying in that direction, or go up or below those projected collision paths by amount of the radius clearance * 2 or something.

Well, a raytrace check for collision is another approach, but it'd have to be run a lot more often than what I was proposing, to be effective, and then we'd be right back to CPU load issues.

I'm not sure how much sense that made but it would be interesting, because you could get genuine midair collisions if things get to heated up and then blow planes up kamikaze style.

We used to have that. In fact, by changing a few variables, you can make that happen again, that code wasn't removed, IIRC. Nobody liked it, frankly, so the defaults were set so that it doesn't happen. They just bounce off of each other, no real harm done. It's one of those things that sounded really cool until it was tried.

- only make checks if they come within a certain radius such as the turning rate of the plane multiplied by its size radius
- Make all trigonometric calculations ahead of time, no floating point calculations
- It may even be more efficient to use bounding box method to check for proximity, and also, why is spherical so important, neither checks truly take into account the polygons on the plane.

All of the above involve handling a lot more math than is prudent.

The spherical check is used because it's cheap, computationally- it's cheaper than a bounding box. Which is why everything in Spring uses spheres to determine collisions.

Anyhow, if you just want to see the stuff that's happening in the source, just go here, it's not terrifically complicated stuff, I was pretty surprised, tbh.

The stuff that's making it so CPU-intensive is all of the steering-code decisions that result, every frame, from the relatively simple checks of height and collisions (think, folks- it's making subtle decisions, every frame, to alter height, based on heightmap pixel values that may be only slightly different from each other, without taking into account the heightmap ahead of its current point at its current velocity next frame- very, very wasteful, and no wonder the results are poor...). Making it happen only once every SlowUpdate (about 0.5 seconds) and distributing the load over the previous 15 frames would help a lot.

[Tobi]

No, it just does a spherical check for 6X the size of the plane's hitsphere radius. Which is not a very effective way of going about this, tbh, as that doesn't take into account velocity- fast-moving planes don't get any time to predict collisions, slow-moving ones check far too often.

Not 6X, radius + 6.

I wonder where that magic number comes from tho, I guess indeed it should ideally be a function of speed.

[Argh]

Oops, my bad. That's even worse than 6X radius though...

I personally think that there should be 3 changes:

1. Make that radius +value be dependent on velocity and radius, with some game-designer value thrown in as a multiplier. A big, fast-moving plane with a slow turnrate needs a larger avoidance check than a small, very swiftly-turning plane.

2. Check the height of the map several times, based on velocity (need more checks, for faster-moving stuff) and current vector. If the average value is higher, then fly upwards starting this frame, delta determined by the amount of change. Ditto downwards. If any check is really above / below the mean (say, 50% or more- a very thin but high mountain, etc.) then use that value instead of the average.

3. Check less often. Use a randomizer, per plane, and do all of these complex checks once a SlowUpdate, but on frames between SlowUpdates, so that instead of causing a big CPU spike then, you get evenly-distributed results most of the time, but can afford the CPU time involved.

I dunno how to do no. 3, but I could write the logic for 1 and 2 easily enough.

[jK]

My suggestion:

Instead of using a specific radius to detect all possible collisions per plane.
Lay an array above the map with a very low resolution (perhaps 4x4 for 16x16 maps) and now add each plane in all fields which could be reached by the plane (depending on its speed & pos), and update this array perhaps each 4-8th gameframe.

Now you wouldn't need to check two planes in opposite corners anymore.

[BlackLiger]

If we started checking just the area round the plane, but for ALL objects, we could put in a primitive missile avoidance system also, which would be interesting to see.

[SwiftSpear]

It's a pathfinding problem. The pathfinder is aware of the positions of all objects already, it just doesn't use that information at all when calculating paths. Simply put, aircraft just shouldn't be assigned paths that are currently occupied, or in use, by other aircraft. It's possible to make the pathfinder intellegent enough to do so, especially with units as simple in their pathing as aircraft are. Fixing this on any level higher than the pather is asking to rape CPU usage.

[KDR_11k]

My suggestion:

Instead of using a specific radius to detect all possible collisions per plane.
Lay an array above the map with a very low resolution (perhaps 4x4 for 16x16 maps) and now add each plane in all fields which could be reached by the plane (depending on its speed & pos), and update this array perhaps each 4-8th gameframe.

Now you wouldn't need to check two planes in opposite corners anymore.

Wait, planes don't use quads?

[Argh]

Planes only check that radius, and their height each frame, so far as I can tell. The only exception is when they're looking for a landing spot, then they check whether the ground is blocking or not.

[Tobi]

My suggestion:

Instead of using a specific radius to detect all possible collisions per plane.
Lay an array above the map with a very low resolution (perhaps 4x4 for 16x16 maps) and now add each plane in all fields which could be reached by the plane (depending on its speed & pos), and update this array perhaps each 4-8th gameframe.

Now you wouldn't need to check two planes in opposite corners anymore.

Wait, planes don't use quads?

They do use quads.

Note in the code Argh quoted:

Code: Select all

      if (collide && (aircraftState == AIRCRAFT_FLYING || aircraftState == AIRCRAFT_CRASHING)) {
         vector<CUnit*> nearUnits = qf->GetUnitsExact(pos, owner->radius + 6);
         vector<CUnit*>::iterator ui;

qf means quadField.

I'm pretty sure it uses CQuadField about everywhere, but of course that doesn't really help much if you're looping through all units in a large radius.

[Forboding Angel]

Personally I have never noticed any problems or awful looks from nocollide, in fact, I love no collide.

Maybe it's because my planes fly so high. Hell the Dive bombers have cruise alt of 1000.

On an unrelated subject, has anyone else noticed that stealth=1; doesn't seem to be working right? I actually had to start giving things a jamming radius (albeit a small radius) just because of that...