Author Topic: Shrugger! Unity!  (Read 121025 times)

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: Shrugger! Unity!
« Reply #135 on: January 02, 2014, 04:46:13 pm »
Any idea where I could find one; ideally in digital form?  :D

Edit: Complete with the formulas and all, preferably.

Nope.  I don't even know what it was called.  Plus, the last time I saw it was....2000?

Teacher just passed it around and when I got it I took a good look at it and exclaimed, "You don't have to be a rocket scientist to understand this!  You would have to be to use it though..."

Offline keith.lamothe

  • Arcen Games Staff
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 19,505
Re: Shrugger! Unity!
« Reply #136 on: January 02, 2014, 04:47:29 pm »
Do you already have formulae for computing the point of turnover when making a least-time zero-zero intercept with a fixed point?  I'm figuring you'd need that anyway for general navigation.  It seems that the problem of "when to I switch from angular-accel to angular-decel" (basically, "angular turnover") would be solved the same way :)
Have ideas or bug reports for one of our games? Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Shrugging Khan

  • Hero Member Mark III
  • *****
  • Posts: 1,217
  • Neinzul Y PzKpfw Tiger!
Re: Shrugger! Unity!
« Reply #137 on: January 02, 2014, 06:32:35 pm »
So far, navigation worked on a basis of "take as much angular drag as you need" for rotation and "use this script I copied out of google" for thrust, and I'm trying to replace those placeholders with something more to the point. So I guess I should take a stern look at that intercept script and figure out what makes it tick, then try to rewrite it to work for rotation instead?  :o

Ah, turns out the intercept script I used back in summer wasn't at all meant for navigation, and I actually adjusted adapted a "fire gun and compensate for lead" script...which lead to the ships "navigating" by flying at each other at full thrust, passing each other, and decelerating after THAT point.

So no, it appears I have nothing sensible at all  :o
« Last Edit: January 02, 2014, 06:41:25 pm by Shrugging Khan »
The beatings shall continue
until morale improves!

Offline keith.lamothe

  • Arcen Games Staff
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 19,505
Re: Shrugger! Unity!
« Reply #138 on: January 02, 2014, 07:21:28 pm »
So far, navigation worked on a basis of "take as much angular drag as you need" for rotation and "use this script I copied out of google" for thrust, and I'm trying to replace those placeholders with something more to the point. So I guess I should take a stern look at that intercept script and figure out what makes it tick, then try to rewrite it to work for rotation instead?  :o

Ah, turns out the intercept script I used back in summer wasn't at all meant for navigation, and I actually adjusted adapted a "fire gun and compensate for lead" script...which lead to the ships "navigating" by flying at each other at full thrust, passing each other, and decelerating after THAT point.

So no, it appears I have nothing sensible at all  :o
Ah, yes, looks like they're just going for "least time" intercepts based on the target's current position, velocity, and acceleration.  That can indeed generate intercepts, and if you're going for ramming speed that's probably exactly what you want (though target evasion is naturally a problem; suggest to this captain that it is unwise to try to ram a target more maneuverable than one's own ship).

If you're trying to board the enemy, or if you're trying to engage fixed defenses without flying past them, you want a "zero-zero" intercept, or close to it.  Meaning coming to zero distance-to-taget and zero velocity.  You may actually want to maintain some velocity at intercept, and you may want to not actually collide with the target, so you're not actually aiming for 0 and 0, but close enough.

If you're not particular about how long it takes to achieve that zero-zero condition then you can have a three stage trip: accelerate, hold constant velocity, and then decelerate.  If you're trying to go for a "least-time" AND "zero-zero" intercept (I may be abusing the terms to combine them, but you get the idea: zero-zero in minimum time) then you'll actually want to do a full-bore accel up to the instant at which you must engage full decel to avoid overshooting the target.  It's tremendously wasteful of energy but that may not be an operative concern for the captain.  It also assumes no maximum velocity, whereas realistically you can't accelerate past c and practically you probably need to stop well short of that to avoid losing that hood ornament (and the forward half of your hull) to particle collisions.

Anyway, if your ship has max accel equal to max decel, I think the solution to finding "turnover" (the time, or point, at which you switch from accel to decel) is fairly simple: find how long it takes you to travel half the distance at max accel.  That way your velocity-over-time graph looks like an isoceles triangle, where the top point is turnover.

Recall that d = 1/2 * a * (t^2) where d is distance, a is accel, and t is time.  This assumes an initial velocity of zero; that can be factored in without too much pain if necessary.

So if you're 10 light-minutes (call it 180 million km) from a target planet, are at rest, and have a maximum accel of 500 gravities (call it 4.9 km/s^2), then you want to accelerate until you're 90 million kilometers away and then slam on the brakes all the way in.  To find that time:

(beware: I should not be trusted with math, and I may have pooched this badly)

90,000,000 km = 1/2 * 4.9km/s^2 * Ts^2

180,000,000 km = 4.9km/s^2 * Ts^2

36,734,694 = T^2

6061 = T

or a turnover time of about 1.7 hours.  You'd reach a maximum velocity of roughly 30 thousand kilometers per second (10 percent of c) and decelerate from there.



I think ;)

Have ideas or bug reports for one of our games? Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Shrugging Khan

  • Hero Member Mark III
  • *****
  • Posts: 1,217
  • Neinzul Y PzKpfw Tiger!
Re: Shrugger! Unity!
« Reply #139 on: January 03, 2014, 04:10:15 am »
Fortunately, we're dealing with much shorter distances here. Relativistic physics need not concern us overly much  :P

Well, planning the acceleration and deceleration on a 50-50 base is fine if the target doesn't do anything, but everyone's moving around! Bastards! So the ideal turnover point might actually shift around!
Could I still calculate that point by some handy formula, or does this transgress into mathematics too advanced for us to handle?  :o
The beatings shall continue
until morale improves!

Offline keith.lamothe

  • Arcen Games Staff
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 19,505
Re: Shrugger! Unity!
« Reply #140 on: January 03, 2014, 09:56:29 am »
Fortunately, we're dealing with much shorter distances here. Relativistic physics need not concern us overly much  :P
The example I gave was something like 20% longer than the distance from the earth to the sun.  Are you dealing with millions of km, thousands, or what? :)

Quote
Well, planning the acceleration and deceleration on a 50-50 base is fine if the target doesn't do anything, but everyone's moving around! Bastards! So the ideal turnover point might actually shift around!
Could I still calculate that point by some handy formula, or does this transgress into mathematics too advanced for us to handle?  :o
Well, again, are you trying to ram the target, or board it?

If ramming, then you don't really need a turnover point.  The idea is to hit turnover right in the enemy ship's engine room, with as much velocity as possible ;)  Bonus points for delivering a greeting card from Sir Isaac Newton.

But with a target whose position, velocity, or even acceleration are not constant, things do get more complicated, as it requires prediction of where the target will be at a given time, and ifguring out if you can be there at that time.

And if those changes to target position, velocity, or acceleration are not even known beforehand, then obviously you cannot generate a guaranteed solution at all.

At that point, what you can do is plot a sort of conical volume showing all possible points where the target could be after x seconds.  Then it's a matter of plotting your course and acceleration such that "your cone" envelops "their cone" (for the section up to time T, where T is the longest time it would take you to reach any point within that section), with an actual course heading that will generate a collision on the target's most likely actual course.  Then just recompute that course every time there's any alteration in the target's acceleration or heading, etc.  Of course, if you can't find a course an acceleration that give you that kind of envelopment, then the target ship is capable of evading you regardless of how you fly (whether or not they actually would evade you is up to them).

But this is probably only feasible with relatively low accelerations, and the ability to change headings relatively fast (not overcoming momentum in the old direction quickly, but generating momentum in the new direction quickly).  If you've got ships that can pull 100,000 gravities or whatever then those cones might look more like spheres and I'm not sure what impact that would have on the practical value of the technique.


On the other hand, if you're actually trying for something like a zero-zero intercept with the evading target then... um, shoot its engines out? :)  More seriously, you're going to want some way of predicting the target's location, velocity, and accel (as in the case of forming up with a friendly target) OR some way of disabling the target's ability to change its accel and heading OR some way to "grapple" the enemy ship (or tractor beam it, or whatever) once you're close enough.  Or I guess maybe you just have to get within weapons range and make it so there's no target to get close to anymore.

But the basic idea is similar to the ramming case, you basically check for that conical area overlap and do a full burn towards the target, but periodically check "if I engage full decel now, how far will I go before I reach zero velocity?" and when that number is >= "my remaining distance to target", engage full decel.  And then potentially keep re-checking to see if the target putting on more accel or whatever makes it so that you want to start accelerating again.


Anyway, I think the basic solution to "but what if the situation keeps changing?" is "then re-run the math every time the situation changes" :)  Or every time it's changed enough to be significant, etc.


In terms of concrete distances, velocities, accelerations, and objectives (least-time vs zero-zero, i.e. ramming vs boarding), can you give me an example of what you're trying to do?
Have ideas or bug reports for one of our games? Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Shrugging Khan

  • Hero Member Mark III
  • *****
  • Posts: 1,217
  • Neinzul Y PzKpfw Tiger!
Re: Shrugger! Unity!
« Reply #141 on: January 03, 2014, 03:57:29 pm »
An example...ultimately, I'm just trying to replace my ramshackle placeholder methods of making things move with something more navigationally sound. I didn't think it would be that hard to calculate things like these, so I just went and asked  :o
By now, I'm fairly sure I need to do more research and wrap my head around some basic physics formulae that  had forgotten since school.

For example, I'm trying to make ships, starting out at large distances (a few tens of thousands of kilometers), accelerate towards one another in order to engage in close-range combat (anything close enough for the crew to successfully hit the enemy). Now, some overshooting jousting is alright, and so is stopping short and going for a standoff, but right now they either overshoot by ridiculous degrees, sit still and fire artillery-style, or engage in ridiculous handshake-distance dogfights depending on how agile, accurate or fast I make them - a system in which decisions concerning acceleration and deceleration are made purely based on "who's more agile" and "who has longer range", but entirely without any considerations of one's ship's present velocity, its velocity relative to the enemy, or the thrust of either one.

Now, that applied to actual movement rather than rotation, but the problem is the same - I'd like to find a straightforward formula with which to let the AI make reasonable decisions as to whether they should accelerate or decelerate whatever manoeuvre they're currently carrying out.
The beatings shall continue
until morale improves!

Offline keith.lamothe

  • Arcen Games Staff
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 19,505
Re: Shrugger! Unity!
« Reply #142 on: January 03, 2014, 04:10:51 pm »
Now, that applied to actual movement rather than rotation, but the problem is the same - I'd like to find a straightforward formula with which to let the AI make reasonable decisions as to whether they should accelerate or decelerate whatever manoeuvre they're currently carrying out.
It's similar for angular velocity as for "normal" velocity, I think.

Basically, if you want to change to a different heading in the least possible time (such that you can stay there, rather than overshooting it), a simple brute force approach is:

1) Engage maximum angular acceleration towards that heading.
2) Periodically check "if I engaged maximum angular deceleration right now, what would my heading be when I'd fought my angular velocity down to 0?"
3) And if that result is at or past your target heading, engage maximum angular deceleration.


Anyway, I don't think you're dealing with something that calls for very advanced math.  For me I just visualize it as a graph of velocity over time:
a) The y-value of the curve at any given x is the velocity where time=x.
b) The slope of the curve at any given x is the acceleration where time=x.
c) The area under the curve to the left of any given x is the total distance travelled by time=x.


Also, one key thing in your case is to not let yourself get tangled up trying to solve multiple not-fundamentally-related problems simultaneously.  For example:
- figure out how you want to handle zero-zero intercepts
- and then figure out how you want to handle least-time intercepts
- and then figure out how you want to account for predictable changes in target accel/velocity/position
- and then figure out how you want to account for unpredictable changes in such things

Honestly, by the end you've moved from a purely mathematical problem to one bordering on the psychological; all the math can do then is tell you what you need to do to make sure the target can't get away (whatever it decides), or whether you can't guarantee that physically.
Have ideas or bug reports for one of our games? Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Shrugging Khan

  • Hero Member Mark III
  • *****
  • Posts: 1,217
  • Neinzul Y PzKpfw Tiger!
Re: Shrugger! Unity!
« Reply #143 on: January 03, 2014, 04:58:16 pm »
So THAT's how reasonable people do it!

Yeah, my failing is definitely at least partially due to lacking basics. Guess it's back off to Wikipedia and looking up Angular Acceleration formulae for me...I mean, I can hardly make my AI do the right thing when I can't even figure out the way to do it myself.

Thanks for all the help; I hope it isn't too frustrating to try and help and slow learner like me :)
The beatings shall continue
until morale improves!

Offline keith.lamothe

  • Arcen Games Staff
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 19,505
Re: Shrugger! Unity!
« Reply #144 on: January 03, 2014, 05:21:47 pm »
So THAT's how reasonable people do it!
Never assume I'm a reasonable person ;)

Quote
Yeah, my failing is definitely at least partially due to lacking basics. Guess it's back off to Wikipedia and looking up Angular Acceleration formulae for me...I mean, I can hardly make my AI do the right thing when I can't even figure out the way to do it myself.
It's not all that fancy, accelerating from rest gives a distance of 1/2*a*(t^2).  Or, in other words:
1) take the time
2) square it
3) multiply by accel
4) divide by 2
5) done :)

So if your thrusters let you change your angular velocity by 10-degrees-per-second every second, then you know that blasting those thrusters at full for 1 second will actually change your heading by (10*(1^2))/2 = 5 degrees, leaving you with an angular velocity of 10.  Doing it for 2 seconds changes your heading by (10*(2^2)/2 = 20 degrees, with a final angular velocity of 20.  3 seconds gives a total delta of 45 degrees, with a final angular velocity of 30.  And so on.

On the flip side, if you currently have an angular velocity of 30, you know it will take you 30 / 10 = 3 seconds to decelerate to an angular velocity of 0.  And since your acceleration and deceleration power is the same you already know that you'll come to a stop 45 degrees from where you are now (distance from decelerating-to-rest is the same as distance from accelerating-from-rest if decel = -accel).

So if your desired heading is more than 45 degrees further along than you are now, just keep those thrusters burning.

If your desired heading is less than (or equal to) 45 degrees further along than you are now, go to max decel (by firing the thrusters that will turn you in the other direction, probably).


Quote
Thanks for all the help; I hope it isn't too frustrating to try and help and slow learner like me :)
Not frustrating at all :)  I just hope I'm not oversimplifying things, as sometimes I take questionable short-cuts in math ;)


Edit:
Another way of thinking of the "how far will I go if I accelerate at X for Y seconds?" thing is:

a) First, imagine your velocity-over-time curve while travelling at a constant velocity (accel = 0) of 10 meters-per-second for 10 seconds.  It's a pretty boring "curve", and if you plot it and shade the area under it you just get a 10x10 square, right?  Well, the area of that square (100, naturally) is the distance you travelled.

b) Next, imagine the same curve but with a constant acceleration of -1 meter-per-second-squared.  So your velocity starts at 10 m/s and reaches at 0 m/s at the very end of the 10 second interval.  If you plot that "curve" you get a right triangle with a base of 10 and a height of 10.  Or an exact half of the square from example a.  Naturally, its area is half that of the square, meaning you will come to rest 50 meters from wherever you were at time=0.

c) Same deal if you started at 0 m/s and held a constant acceleration of 1 meter-per-second-squared for 10 seconds.
« Last Edit: January 03, 2014, 05:26:51 pm by keith.lamothe »
Have ideas or bug reports for one of our games? Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Shrugging Khan

  • Hero Member Mark III
  • *****
  • Posts: 1,217
  • Neinzul Y PzKpfw Tiger!
Re: Shrugger! Unity!
« Reply #145 on: January 04, 2014, 08:34:19 am »
Alright, so if I were to try and make them discern the right time to revert thrust, the formula would look something like...

if ( ( angularVelocity / ( acceleration / mass ) ^ 2 ) > ( 2 * distance / ( acceleration / mass ) )
    {
        flip();
    }

...I get the feeling that's not entirely right on my part  ???
The beatings shall continue
until morale improves!

Offline keith.lamothe

  • Arcen Games Staff
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 19,505
Re: Shrugger! Unity!
« Reply #146 on: January 04, 2014, 09:52:30 am »
Alright, so if I were to try and make them discern the right time to revert thrust, the formula would look something like...

if ( ( angularVelocity / ( acceleration / mass ) ^ 2 ) > ( 2 * distance / ( acceleration / mass ) )
    {
        flip();
    }

...I get the feeling that's not entirely right on my part  ???
The main thing that looks wrong is your factoring in of mass.  Did you mean thrust/mass instead of accel/mass?  Thrust/mass would be part of computing your accel (I think).  The difference in what I'm saying is that I'm assuming you already know your max acceleration and deceleration.  So I'd probably do something like

float myCurrentAngle = this.GetCurrentHeadingInDegrees(); // just assuming you've got this stored somewhere, or easily computed

Point targetPoint = enemy.Location; // assuming you want to directly face where it is now, though you may want to face where you think it will be at some point in the future instead

float desiredAngle = AngleBetweenPointsDegrees(my.Location,targetPoint); // computing this isn't too hard

float desiredDelta = desiredAngle - myCurrentAngle;
if(desiredDelta < 0) desiredDelta += 360f; // you'd actually want to compute if it'd be shorter to turn the other direction if you weren't already in a hard turn, but for simplicity

float myAngularVelocity = this.GetCurrentAngularVelocity(); // again, assuming you have this stored somewhere, or easily computed; assuming positive

float myAngularAcceleration = this.GetMaxAngularAcceleration(); // ditto; assuming positive

float timeRequiredToDecelerateToRest = (myAngularVelocity / myAngularAcceleration);

float deltaThatWouldResultFromImmediateDecelerationToRest = myAngularAcceleration * timeRequiredToDecelerateToRest * timeRequiredToDecelerateToRest;

if(deltaThatWouldResultFromImmediateDecelerationToRest >= desiredDelta) flip();


Naturally it could be compressed into far fewer lines, but I find "one step per line" to be helpful for self-documenting code; the comments wouldn't be needed at all for simply understanding what it does.


Of course, this is all on a 2D plane; if you're not clamping all units to the ecliptic or whatever that gets messier :)
Have ideas or bug reports for one of our games? Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: Shrugger! Unity!
« Reply #147 on: January 04, 2014, 10:27:10 am »
So THAT's how reasonable people do it!
Never assume I'm a reasonable person ;)

And never underestimate the unreasonable lengths that reasonable people will go to.
If you want a reasonable solution, ask an unreasonable person. ;)

(Just like if you want a job done efficiently, ask a lazy person)

Offline Shrugging Khan

  • Hero Member Mark III
  • *****
  • Posts: 1,217
  • Neinzul Y PzKpfw Tiger!
Re: Shrugger! Unity!
« Reply #148 on: January 04, 2014, 04:14:38 pm »
Of course, this is all on a 2D plane; if you're not clamping all units to the ecliptic or whatever that gets messier :)
Why would I do that? The point of 3D is having three dimensions!

So...yeah. I'm probably going to spend most of tomorrow experimenting; I doubt I'll be able to make do with placeholder systems when an actual solution seems so close at hand. Any last tips regarding the transformation of your code to something three-dimensional?  :)
The beatings shall continue
until morale improves!

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: Shrugger! Unity!
« Reply #149 on: January 04, 2014, 04:48:54 pm »
Of course, this is all on a 2D plane; if you're not clamping all units to the ecliptic or whatever that gets messier :)
Why would I do that? The point of 3D is having three dimensions!

How I Learned to Stop Worrying and Love Quaternions.

(No really: you're going to have to get comfortable with them if you want to do any kind of rotation in 3D space without going into gimbal lock).

 

SMF spam blocked by CleanTalk