Aurora 4x

VB6 Aurora => Aurora Suggestions => Topic started by: sloanjh on April 06, 2009, 10:51:07 PM

Title: NPR AI and timestep size
Post by: sloanjh on April 06, 2009, 10:51:07 PM
Hi Steve,

  Let me say upfront that I realize that this suggestion entails a lot of coding on your part, and (possibly) a major paradigm shift with the way Aurora handles movement.  OTOH, I'm 20 Aurora years into my campaign that has 1 NPR, and I've hit two effects which are having a major impact on my gameplay - I'm worried about performance once there are several NPR empires and my empire is 3-4 times as big.  The good news is that a LOT of the hang-ups from the early days are smooth as silk now - micromanaging which side of a JP a jump ship was on for ferry purposes, the "go tearing off across the system due to a 'survey next 5 bodies'" bug, intelligent NPR, etc.  But you know users - we're never satisfied :-)[/list]

2a)  If I want to do a 5-day update, it takes ~4 times as long for the computer to think if I use a 6 hour interval than if I used a 1 day interval, and ~24 times for a 1 hour interval.  The reason this is a problem in 4.0b but wasn't in 2.x or 3.x is that I'm not controlling the NPRs any more.  In the old days, I knew roughly when and where an encounter was going to take place, and could cut the timestep based on that knowledge.  In 4.x, any system might have NPRs or Precursors in it, and so I have to guess when I need to cut the timestep.  If I guess wrong, then I either zip right by the contact without ever seeing it or, as was the case with my first Precursor encounter, they end up 6 hours travel time inside my sensor envelope.  Last night I went back to the Precursor system - what I ended up doing was saving my database more and more frequently as I got closer to them, so that I could replay it with a smaller timestep if I mis-guessed (which I ended up doing - I mis-guessed their missile range during a several-hour stern chase and was taking ~30 second timesteps)

2b)  While exploring asteriods or moons, I "have to" cut the timestep and update times.  Since (my recollection is) the ships only execute 1 order per timestep, and don't get another 5 bodies until the end of the update, I could have them spending 5 days for a survey or three that took 4 hours.

2c)  Due to the interrupt frequency in #1 above, I frequently find myself using 6 hour intervals in 4.0b in places where I would have used a shorter interval in 3.x or 2.x.  The reason for doing this is that way I know I can get 6 hours of Aurora clock to advance before being interrupted.

One thing I'm very curious about is if you're seeing similar issues in your campaign, and if not, what am I doing wrong :-) ) is a way to further make things more efficient.  It's rather silly for my freighters running back and forth between Earth and Pluto to be taking 20 minute timesteps just because some survey ship is working a crowded asteroid belt 3 jumps away.  The key observation is that it's impossible for movers in one system to affect movers in another system unless they either jump between them or send a message (generate an interrupt event).  So you could set up a priority queue in each system that had movers in it, and do coarse grain updates in systems that don't have much going on.  Basically, you could register each system's queue in a queue of queues, with the priority determined by the time of the next event in that system.  The flow of control would be that the top system in the queue would advance its internal clock to its first event, then calculate and reset its priority in the queue.  If an event that affected other systems (either a jump or an interrupt) occurred, then all systems would bring their internal clocks up to the time of the event.  This would let the mining ship run small, tight timesteps without affecting the freighters in Sol; every time the accumulated time added up to a timestep in Sol (e.g. about once a day, which might correspond to 100 timesteps in the mining system) the Sol system would advance its clock in a single (rather than 100) timestep(s).  If the mining ships found minerals on an asteroid (causing an interrupt), the Sol system (and any other systems) would advance its clock (again in a single timestep) up to the time of the event before displaying the interrupt to the player.

[/list]

Note that the only thing (I think) I'm advocating changing here is the mechanism for performing sub-steps within an e.g. 1-day update.  The interrupts, updates (top row on F3 screen) and economic update mechanisms would stay the same.  Another point: if you're worried about mis-estimating the time of a particular event (e.g. sensor contact) that's a long time off and important not to over-shoot, go ahead and cut the time-to-event by 10% for that particular event type.  That should hone in VERY rapidly on the actual time that the event should occur, e.g. an undershoot of a day should go down to an undershoot of ~1 second after only four iterations/timesteps.  As for sensor detection events, this method might be efficient enough that each mover can just brute-force them by calculating the closing velocity to every alien sensor platform in the system and predicting when it will move within range (then picking the shortest) - even with 10-20 fleets on a side you could easily win out over e.g. "calculate next 5 moves" in a system with 100s of asteroids, and you'd be doing a LOT fewer updates (I think).  (Missile salvos might cause a problem with idea, if there are too many of them, however - they might need special optimizations.)

Hope you like the suggestion....
John
Title: Re: NPR AI and timestep size
Post by: Hawkeye on April 07, 2009, 11:36:55 AM
Quote from: "sloanjh"
Hi Steve,
Minor Suggestions:  
Put in a pop-up progress meter (with an interrupt button) that shows what percent of the update has been processed (you might want to do this only for 1-hour or more updates).  The progress meter could simply update at the end of each interval - the idea is that if the NPR is doing something very fine-grain that takes a lot of time (like fighting a battle), the player would know that time had slowed down and could request that Aurora "come up for air" by hitting the interrupt button, which would tell it to interrupt at the end of the next interval.


John


After Ctrl/Alt/Del-ing a few times out of aurora because I thought my system was hanging, I now have the windows task manager with the "Systemleistung" tab open, while running aurora (the one that shows how much the processor is working) so I can see if the program is still running, or my system has shut down.

This aside, all very good suggestions. Interrupts because of NPRs are minor, so far for me, but those reestablished contacs are a pain in the but (I have colonies on Mars, Titan and Mercur and those civies drive me nuts)


Hawkeye, Germany
Title: Re: NPR AI and timestep size
Post by: SteveAlt on April 08, 2009, 08:39:47 AM
I haven't replied to this yet because I want the time to go through it properly. I will reply once I can tear myself away from Trade and concentrate :)

Steve
Title: Re: NPR AI and timestep size
Post by: sloanjh on April 08, 2009, 08:05:30 PM
Quote from: "SteveAlt"
I haven't replied to this yet because I want the time to go through it properly. I will reply once I can tear myself away from Trade and concentrate :-)

BTW, I realized I said "F12" when I meant "F3" above - I did an edit to fix it.

John
Title: Re: NPR AI and timestep size
Post by: SteveAlt on April 14, 2009, 02:25:17 PM
Quote from: "sloanjh"
Hi Steve,

  Let me say upfront that I realize that this suggestion entails a lot of coding on your part, and (possibly) a major paradigm shift with the way Aurora handles movement.  OTOH, I'm 20 Aurora years into my campaign that has 1 NPR, and I've hit two effects which are having a major impact on my gameplay - I'm worried about performance once there are several NPR empires and my empire is 3-4 times as big.  The good news is that a LOT of the hang-ups from the early days are smooth as silk now - micromanaging which side of a JP a jump ship was on for ferry purposes, the "go tearing off across the system due to a 'survey next 5 bodies'" bug, intelligent NPR, etc.  But you know users - we're never satisfied :-)[/list]
As this is a long mail I am going to answer in sections. I've read this far and realise you are quite correct that the clock shouldn't stop for NPR events. Any NPR events that should stop time should instead by picked up by the pre-increment checks. The check for an interrupt is made in the section that creates the event message. I have added an extra step so that an interrupt is only generated if the event is for a race that is not an NPR or a Precursor. I don't tend to use the timestep intervals which is probably why I haven't tackled this sooner.

In addition, I have split the existing single contact event into several new ones, including Unknown, Civilian, Hostile, Neutral, Friendly, Allied (these are part of new diplomacy rules in v4.1), Missile, Wreck, Mineral Packet, Jump Gate, Ground Forces and Shipyards. I can mark some of these as non-interrupt. At the moment I am going for Civilian, Friendly, Allied, Wreck, Mineral Packet and Jump Gate but I can change this depending on the general consensus. The type of contact will only be known if it is active or there is a transponder involved. Otherwise it will be unknown. I can't differentiate on course changes because Aurora keeps no record of past movements and there is no real concept of course. It is all done with movement between two points, one of which may be moving between increments.

I have also set the Civilian Activity event so it will not act as an interrupt

I'll get back to you on the progress meter. It is something I have thought about and I had one in SA. I am just concerned about the performance implications because of the number of steps in Aurora and the amount of time it would take to update a window in between each step.

Steve
Title: Re: NPR AI and timestep size
Post by: SteveAlt on April 14, 2009, 02:54:56 PM
Quote from: "sloanjh"
2a)  If I want to do a 5-day update, it takes ~4 times as long for the computer to think if I use a 6 hour interval than if I used a 1 day interval, and ~24 times for a 1 hour interval.  The reason this is a problem in 4.0b but wasn't in 2.x or 3.x is that I'm not controlling the NPRs any more.  In the old days, I knew roughly when and where an encounter was going to take place, and could cut the timestep based on that knowledge.  In 4.x, any system might have NPRs or Precursors in it, and so I have to guess when I need to cut the timestep.  If I guess wrong, then I either zip right by the contact without ever seeing it or, as was the case with my first Precursor encounter, they end up 6 hours travel time inside my sensor envelope.  Last night I went back to the Precursor system - what I ended up doing was saving my database more and more frequently as I got closer to them, so that I could replay it with a smaller timestep if I mis-guessed (which I ended up doing - I mis-guessed their missile range during a several-hour stern chase and was taking ~30 second timesteps)

2b)  While exploring asteriods or moons, I "have to" cut the timestep and update times.  Since (my recollection is) the ships only execute 1 order per timestep, and don't get another 5 bodies until the end of the update, I could have them spending 5 days for a survey or three that took 4 hours.

2c)  Due to the interrupt frequency in #1 above, I frequently find myself using 6 hour intervals in 4.0b in places where I would have used a shorter interval in 3.x or 2.x.  The reason for doing this is that way I know I can get 6 hours of Aurora clock to advance before being interrupted.

One thing I'm very curious about is if you're seeing similar issues in your campaign, and if not, what am I doing wrong :). Of course, with timesteps involved or just course changes because of asteroid surveys, freighters unloading, etc., it becomes even more difficult. So instead Aurora checks the direction of the target during the previous impulse to see if it is moving toward or away from the missile. This is not an exact course - the program just checks to see if it's current position is closer than its position at the start of the previous increment. If it is, the code assumes it is directly closing at max speed and if not, it is assumes it will be stationary. In this way, the program will err on the side of caution in determining how far to move the missiles. If the missiles will move into detection range of the target fleet based on the previous assumptions then the time increment is reduced to the point at which that happens. Other fleets are not taken into account. Mainly because the formula for determining when one object moving at speed X will move within a specified distance of another object that is on a tangential course at a different speed is bad enough. Imagine doing it for a dozen different objects on different courses at different speeds and calculating all of their various sensor ranges before every increment against that particular target.

After missiles are checked the program does a similar thing with fleets that are on a direct intercept course. For example, an NPR has detected one of your fleets and is heading straight for it. The same checks are performed as with missiles and with the same difficulties involved. Next, any ships that transit into a system with fleets of a different race will stop time at that point.

The above obviously doesn't cover every possibility but it is a reasonable compromise between performance and manageability. It can still be improved with more intelligence and I can add more checks at the expense of slowing down the performance of the game. The missile checks are performed for every increment above 40 seconds and the fleet/transit checks are performed for increments above 299 seconds. I could reduce those numbers as well.

Steve
Title: Re: NPR AI and timestep size
Post by: SteveAlt on April 14, 2009, 02:56:01 PM
I'll tackle part 3 later - the Pub is calling :)

Steve
Title: Re: NPR AI and timestep size
Post by: sloanjh on April 14, 2009, 08:30:24 PM
Quote from: "SteveAlt"
If you know the formula for when one object moving at speed X will move within a specified distance of another object that is on a tangential course at a different speed, it would be very useful to me :-) and b) to avoid transcription errors.

The trick is to look at the relative velocity, i.e. go to a frame where the target ("another object") is at rest.  Then go to a coordinate system where the separation D is in the "x" direction.  At that point, you've got a triangle whose base is length D, the side coming out of the target is length R ("specified distance") and has an angle phi from the base.  I'll use X as the length of the other side, which is the distance the object needs to travel in the special frame - you can solve for time by dividing X by the relative speed.  Let's call the angle between the relative velocity and the separation theta.  Phi and X are the two unknowns - everything else is known.  Note that you can get cos(theta) without using trigonometry functions by taking the dot product of unit vectors in the D and X directions; sin(theta) is simply the cross product.

Note that I'm using D, X, and R both as distances and as the names of the various sides.

We need two equations to solve for phi and X - to get them we make two right triangles by dropping a perpendicular from the apex of the triangle (where X and R meet) to D.  The height of this perpendicular is both X*sin(theta) and R*sin(phi).  For convenience, it's easier to square both sides of the equation:

X^2*sin^2(theta) = R^2*sin^2(phi).

The other equation says the sum of the two bits that D has been broken into must equal D:

D = X*cos(theta) + R*cos(phi) ,

The trick is to use sin^2 + cos^2 = 1 to get phi to drop out, so we re-write the second equation as

(D - X*cos(theta))^2 = R^2*cos^2(phi).

Adding the two equations together, rearranging terms, and using the cos^2+sin^2 trick for both theta and phi gives

D^2 - 2*X*D*cos(theta) + X^2 = R^2.

This is a quadratic equation for X; solutions are

X = D*cos(theta) +/- sqrt(D^2cos^2(theta) - (D^2-R^2))

You want the "-" branch, since that's where the course enters the circle of radius R around the target; the "+" branch is the exit distance, while D*cos(theta) is the point of closest approach (useful for detecting if you need to bother with that target).  Using the cos^2 + sin^2 trick again to simplify the determinant, we end up with:

X = D*cos(theta) - sqrt(R^2 - D^2*sin^2(theta)).

This makes sense - if theta is zero, then the course is directly for the object, and X = D-R.  If you're just going to have a grazing hit, then the determinant (or is it descriminant?) is zero, so R = D*sin(theta), which again is correct for this configuration (since X is tangent to the circle so R and X are at right angles).

OK, so the final answer isn't as yukky as I thought - I only had gotten it to the quadratic equation - I was going to let you do the rest :-)

PM me if you want a more detailed derivation for any of the steps.

Best,
John
Title: Re: NPR AI and timestep size
Post by: sloanjh on April 14, 2009, 09:37:28 PM
Quote from: "SteveAlt"
It's not something that has ever been a problem. However I use one day updates with no timestep so even in the 5 asteroids situation that usually isn't long enough to cause any delay. The only time I go for shorter updates is when surveying a 4-point system or if I can see contacts. I only use 5-day increments in the very early stages. Also, there are some checks in place for NPRs in v4.0 that weren't there in the past.
Aha!!  I tend not to want to go above 6 hour sub-intervals (and 1-day updates), although my workaround for that hang involves zipping through the first part of the econ cycle with 1-day sub-intervals.  
Quote
Other fleets are not taken into account. Mainly because the formula for determining when one object moving at speed X will move within a specified distance of another object that is on a tangential course at a different speed is bad enough. Imagine doing it for a dozen different objects on different courses at different speeds and calculating all of their various sensor ranges before every increment against that particular target.
This is the optimization I'm advocating.  In a particular increment, most movers will not change course or speed (or sensor state).  This means that you don't have to repeat the calculation unless something changes.  If you put a "time of intercept" column in for each mover (or just remembered it in memory) then you'd only have to adjust it for changes.  Since the number of things that changed should be small (remember I'm talking about sub-intervals here, so no human/NPR generated changes), then you can go through the list of movers that changed course and/or sensor state (another column for "status changed"?) and recalculate whether the change impacts any of the existing movers in that system - if the new time of intercept to the changed guy is later than the existing one for the mover, then the mover doesn't have a status change.  My suspicion is that this would require doing the calculation a LOT fewer times - enough so that you could afford to do the same thing with sensor envelopes that you're doing now for missiles.
Quote
After missiles are checked the program does a similar thing with fleets that are on a direct intercept course. For example, an NPR has detected one of your fleets and is heading straight for it. The same checks are performed as with missiles and with the same difficulties involved. Next, any ships that transit into a system with fleets of a different race will stop time at that point.
I suspect there's a bug in this for precursors and/or NPR - I definitely had precursors land a LONG way inside my sensor envelope when first detected.

Like I said, I realize this would be a fairly big rearrangment (although I think you're a lot closer to it than I originally thought) - I was just putting it out there as a suggestion.

John

PS - Sounds good on the interrupt and event handling stuff in your other post.  On the progress meter, if you only triggered a window update e.g. every 5% I suspect it wouldn't be horrible.  The one I don't have a good idea for is the econ updates - they're the ones that one often doesn't know if they've hung or just slowed down somewhere.
Title: Re: NPR AI and timestep size
Post by: SteveAlt on April 16, 2009, 08:11:14 AM
Quote from: "sloanjh"
Shift the updating strategy in Aurora from a fixed time-step driven paradigm to a variable "advance by time to next event" paradigm.  I realize that this is probably a huge rearrangement of the code, but I think it will scale much better with number of NPRs, ships, systems, etc.  Here are a few ideas on how it might work:

Every mover (a fleet or a missile salvo) looks at its order list and estimates "time at which current command will complete, or when a detection is possible".  This is inserted into a priority queue, with the earliest event having the highest priority.  When it's time to do a timestep, figure out how long to make it by peeking at the highest priority (earliest) mover, and choose the timestep to take the clock to his event time, or by some maximum timestep time (e.g. a day) that you throw in for stability purposes.  The big advantage here is that the computer is doing the micromanaging of the timestep interval size (the lower row on the F3 screen), rather than me; it can use its omniscience to know that nothing is going to happen for about 1 hour, 22 minutes, and 35 seconds, so it can just jump to that time.  Processing a timestep consists of doing all the stuff that's done now (like figuring out if CargoFlt003 is done loading those 10 automated mines); any mover whose estimated time to completion changes (e.g. because they've gone on to a new order) updates their priority in the queue.  Those whose estimated time hasn't changed don't need to do anything in the queue, since it's using absolute time, not time remaining.
Essentially what you are talking about there is running the movement phase without actually moving anything so I can work out when things will happen and then running it again but broken into timesteps that correspond to when things do happen. My first reaction is that this would take a lot of effort but is possible. However, it is going to take a LOT longer to run an increment than it does now. The "run movement without moving" won't take much less time than it does now and then there will be several new movement steps, each of which take as long to execute as a regular timestep and there could be a lot more of them. Also, none of the above will affect the ability to interrupt when a precursor is detected because detection would still only take place after each step and most detection will be of fleets in motion rather than at the end of a step, so I am not sure what we gain. I am not saying that the intelligence of movement can't be improved but I not sure if this is the way to do it.

Quote
The second idea here (once you've got the first one coded up :). I may not intially agree with everything but they always get me thinking.

Going back to the initial idea of working everything out first, I guess I would only really need to work out the first move of each fleet, not all the moves, and I wouldn't need to physically change any records except the movement records so that would be quicker. In fact, an alternative might simply be to run through all of the existing first moves for every fleet and then just advance time by the shortest amount then repeat the process, rather than trying to work out a queue system. It still comes back to the problem though that detection is the main issue and this doesn't solve that any better than the existing timestep system, unless I am missing something.

Steve
Title: Re: NPR AI and timestep size
Post by: SteveAlt on April 16, 2009, 08:20:24 AM
Quote
This is the optimization I'm advocating.  In a particular increment, most movers will not change course or speed (or sensor state).  This means that you don't have to repeat the calculation unless something changes.  If you put a "time of intercept" column in for each mover (or just remembered it in memory) then you'd only have to adjust it for changes.  Since the number of things that changed should be small (remember I'm talking about sub-intervals here, so no human/NPR generated changes), then you can go through the list of movers that changed course and/or sensor state (another column for "status changed"?) and recalculate whether the change impacts any of the existing movers in that system - if the new time of intercept to the changed guy is later than the existing one for the mover, then the mover doesn't have a status change.  My suspicion is that this would require doing the calculation a LOT fewer times - enough so that you could afford to do the same thing with sensor envelopes that you're doing now for missiles.

I suspect there's a bug in this for precursors and/or NPR - I definitely had precursors land a LONG way inside my sensor envelope when first detected.
It isn't really a bug; more of a feature :). The problem is that the check only takes place when one fleet is actually acting on a follow or move to order. If two fleets just happen to be near each other the code will not come into play. At the moment the sensor update cycle is fairly simple. For each system in which more than one Empire is present a list of sensors is created. Then each object in that system is checked against every sensor and as soon as a detection takes place of a given type (active, thermal, etc) then the code moves on to the next type of detection or the next object.

For 'live' detection to take place, every object is going to have to know at what range it can detect every other object for every type of sensor before any movement takes place. Then some type of calculation would have to be made to see when one of those sensors detected one of those objects. The obvious way will be to compare the path of each object and trying to figure out when it will enter one of the sensor ranges. But it will have to be done for every sensor and every object that could possibily interact and all of the sensors could be moving too. That is going to be very complex and time-consuming. It will take far long than a regular, much easier, sensor update

Steve
Title: Re: NPR AI and timestep size
Post by: SteveAlt on April 16, 2009, 08:30:44 AM
Quote from: "sloanjh"
Quote from: "SteveAlt"
If you know the formula for when one object moving at speed X will move within a specified distance of another object that is on a tangential course at a different speed, it would be very useful to me :-) and b) to avoid transcription errors.

The trick is to look at the relative velocity, i.e. go to a frame where the target ("another object") is at rest.  Then go to a coordinate system where the separation D is in the "x" direction.  At that point, you've got a triangle whose base is length D, the side coming out of the target is length R ("specified distance") and has an angle phi from the base.  I'll use X as the length of the other side, which is the distance the object needs to travel in the special frame - you can solve for time by dividing X by the relative speed.  Let's call the angle between the relative velocity and the separation theta.  Phi and X are the two unknowns - everything else is known.  Note that you can get cos(theta) without using trigonometry functions by taking the dot product of unit vectors in the D and X directions; sin(theta) is simply the cross product.

Note that I'm using D, X, and R both as distances and as the names of the various sides.

We need two equations to solve for phi and X - to get them we make two right triangles by dropping a perpendicular from the apex of the triangle (where X and R meet) to D.  The height of this perpendicular is both X*sin(theta) and R*sin(phi).  For convenience, it's easier to square both sides of the equation:

X^2*sin^2(theta) = R^2*sin^2(phi).

The other equation says the sum of the two bits that D has been broken into must equal D:

D = X*cos(theta) + R*cos(phi) ,

The trick is to use sin^2 + cos^2 = 1 to get phi to drop out, so we re-write the second equation as

(D - X*cos(theta))^2 = R^2*cos^2(phi).

Adding the two equations together, rearranging terms, and using the cos^2+sin^2 trick for both theta and phi gives

D^2 - 2*X*D*cos(theta) + X^2 = R^2.

This is a quadratic equation for X; solutions are

X = D*cos(theta) +/- sqrt(D^2cos^2(theta) - (D^2-R^2))

You want the "-" branch, since that's where the course enters the circle of radius R around the target; the "+" branch is the exit distance, while D*cos(theta) is the point of closest approach (useful for detecting if you need to bother with that target).  Using the cos^2 + sin^2 trick again to simplify the determinant, we end up with:

X = D*cos(theta) - sqrt(R^2 - D^2*sin^2(theta)).

This makes sense - if theta is zero, then the course is directly for the object, and X = D-R.  If you're just going to have a grazing hit, then the determinant (or is it descriminant?) is zero, so R = D*sin(theta), which again is correct for this configuration (since X is tangent to the circle so R and X are at right angles).

OK, so the final answer isn't as yukky as I thought - I only had gotten it to the quadratic equation - I was going to let you do the rest :)

Unfortunately a lot of the above is all Greek to me. I have set Aurora up in a way that means I really haven't had to bother much with trigonometry. Almost everything is done betwen two points using pythogoras and I only really need to bother with trig when calculating a point on a circle for planetary orbits, plus the occasional angle between two points. It doesn't help that the degree system for VB6 starts at 90 (but treats it as zero) and goes counterclockwise. It has just made my life so much easier because there are no courses or headings in Aurora, just calculations about how far along a line between two points a ship will move. If I am going to tackle this, I need to go back to school on the trigonometry side.

Even so, assuming I did manage to get my head around it, I am still going to have to calculate all of the sensor ranges for every object against every other object and then run the above calculation in a matrix for every combination of two objects. It just seems that will take an awful long time in performance terms

Steve
Title: Re: NPR AI and timestep size
Post by: Paul M on April 16, 2009, 09:10:47 AM
The problem also lies in the time stepping as basically you need to determine if a hostile task force will end up inside the detection range of an object at the end of the current move, if so then stop the time at the point just where it would.  This is seriously unfun to even consider how to do.  If the game ran in real time with compression (such as harpoon did) it would be easier as might be fixed time intervals but with user defined one then it just gets messier and even worse so when a fleet goes from outside detection range to inside combat range inside of one time step.

A possibility is to add a routine that calcualtes the ending seperation of two forces at the end of the requested time step if the current forces are undetected now.  If no detection then it keeps the time step if there would be detection then it defaults to the next lowest time step and checks again, if no detection then it uses that one, if not it tries with the next lower time step until it reaches a time step that doesn't result in detection.  It executes that time step and posts a message up about switching time due to pending contact in system x by task force y.

This allows the player to find the unit in question and manually set the time to allow for the encounter to play out, without hopefully adding in much computing overhead.  It is a serious issue; however, as I have goofed and hit the wrong time step sometime or otherwise didn't expect combat only to have aliens show up at extremely close range to my ships.  This is also important for a SM who has to advance the game until something happens...and a warning to the SM that hostile fleets occupy the same system would also be useful.

But the trouble is...this is likely computationally much more difficult then I suspect it is as you have to make a detection matix and then apply a test to see if the sum of the matrix is 0 or ?1.  Again all of this is easier for a game like harpoon which is real time.
Title: Re: NPR AI and timestep size
Post by: SteveAlt on April 16, 2009, 10:39:04 AM
Quote from: "Paul M"
The problem also lies in the time stepping as basically you need to determine if a hostile task force will end up inside the detection range of an object at the end of the current move, if so then stop the time at the point just where it would.  This is seriously unfun to even consider how to do.  If the game ran in real time with compression (such as harpoon did) it would be easier as might be fixed time intervals but with user defined one then it just gets messier and even worse so when a fleet goes from outside detection range to inside combat range inside of one time step.

A possibility is to add a routine that calcualtes the ending seperation of two forces at the end of the requested time step if the current forces are undetected now.  If no detection then it keeps the time step if there would be detection then it defaults to the next lowest time step and checks again, if no detection then it uses that one, if not it tries with the next lower time step until it reaches a time step that doesn't result in detection.  It executes that time step and posts a message up about switching time due to pending contact in system x by task force y.

This allows the player to find the unit in question and manually set the time to allow for the encounter to play out, without hopefully adding in much computing overhead.  It is a serious issue; however, as I have goofed and hit the wrong time step sometime or otherwise didn't expect combat only to have aliens show up at extremely close range to my ships.  This is also important for a SM who has to advance the game until something happens...and a warning to the SM that hostile fleets occupy the same system would also be useful.

But the trouble is...this is likely computationally much more difficult then I suspect it is as you have to make a detection matix and then apply a test to see if the sum of the matrix is 0 or ?1.  Again all of this is easier for a game like harpoon which is real time.
Harpoon is a great game and there is a lot of influence from that game on Aurora. The problem for me is that Aurora handles much larger timescales. For a pure-tactical battle you could run the game with perhaps 30 minutes increments and 5 second or 30 second sub-pulses and you would have something very close to Harpoon because the sensors are checked every increment. Perhaps the real way to tackle this is for me to concentrate on optimising the movement and sensor code so it executes more quickly and therefore allows a large number of small sub-pulses to be executed quickly.

EDIT - maybe I load everything into memory and run the sub-pulses then update the database at the end of the increment. Or on a smaller scale, at least retain the sensor information for each ship in memory because at the moment it is recreated during every sub-pulse. There must be a lot of mileage in this area.

Steve
Title: Re: NPR AI and timestep size
Post by: Father Tim on April 16, 2009, 03:33:44 PM
How about just adding an 'undo' button, so that when my nice, presumed-peaceful 5-day increment ends with an NPR fleet three-and-a-half days inside my planetary sensor envelop I can 'go back' those five days and choose a one day time advance instead.  Then when I do legitimately spot the NPR a few hours later (with my three-hour updates) my fleet can react appropriately.
Title: Re: NPR AI and timestep size
Post by: schroeam on April 16, 2009, 04:00:51 PM
Quote from: "Father Tim"
How about just adding an 'undo' button, so that when my nice, presumed-peaceful 5-day increment ends with an NPR fleet three-and-a-half days inside my planetary sensor envelop I can 'go back' those five days and choose a one day time advance instead.  Then when I do legitimately spot the NPR a few hours later (with my three-hour updates) my fleet can react appropriately.

That would be rather difficult with Access and would vastly increase the size of the database by using internal backup fields to store the previous turn's data.  I'm not sure how Steve is going to handle this, or if he even is (he may be satisfied with the performance right now, effort vs benefit and all), but it will probably have to be in the coding of how each increment is performed.

Adam.
Title: Re: NPR AI and timestep size
Post by: sloanjh on April 16, 2009, 09:10:36 PM
Quote from: "SteveAlt"
Hmm! I probably should have studied harder in maths :-)
Quote
Even so, assuming I did manage to get my head around it, I am still going to have to calculate all of the sensor ranges for every object against every other object and then run the above calculation in a matrix for every combination of two objects. It just seems that will take an awful long time in performance terms
I'll say more in another response, but I think the underlying optimization is that, even though you might do more calculation in the first time step, you can take much longer timesteps and you only have to re-calculate the intercept time for things that change state.  So subsequent updates only require the calculation for N_changed_state rows and columns of the matrix.  This takes it (calculating the intercept times for a timestep update after the first) from quadratic time to linear time in the number of objects in the system, assuming that only a few things change state at one time.

Best,
John
Title: Re: NPR AI and timestep size
Post by: sloanjh on April 16, 2009, 09:57:07 PM
Quote from: "SteveAlt"
Quote from: "sloanjh"
Shift the updating strategy in Aurora from a fixed time-step driven paradigm to a variable "advance by time to next event" paradigm.  I realize that this is probably a huge rearrangement of the code, but I think it will scale much better with number of NPRs, ships, systems, etc.  Here are a few ideas on how it might work:

Every mover (a fleet or a missile salvo) looks at its order list and estimates "time at which current command will complete, or when a detection is possible".  This is inserted into a priority queue, with the earliest event having the highest priority.  When it's time to do a timestep, figure out how long to make it by peeking at the highest priority (earliest) mover, and choose the timestep to take the clock to his event time, or by some maximum timestep time (e.g. a day) that you throw in for stability purposes.  The big advantage here is that the computer is doing the micromanaging of the timestep interval size (the lower row on the F3 screen), rather than me; it can use its omniscience to know that nothing is going to happen for about 1 hour, 22 minutes, and 35 seconds, so it can just jump to that time.  Processing a timestep consists of doing all the stuff that's done now (like figuring out if CargoFlt003 is done loading those 10 automated mines); any mover whose estimated time to completion changes (e.g. because they've gone on to a new order) updates their priority in the queue.  Those whose estimated time hasn't changed don't need to do anything in the queue, since it's using absolute time, not time remaining.
Essentially what you are talking about there is running the movement phase without actually moving anything so I can work out when things will happen and then running it again but broken into timesteps that correspond to when things do happen. My first reaction is that this would take a lot of effort but is possible. However, it is going to take a LOT longer to run an increment than it does now. The "run movement without moving" won't take much less time than it does now and then there will be several new movement steps, each of which take as long to execute as a regular timestep and there could be a lot more of them. Also, none of the above will affect the ability to interrupt when a precursor is detected because detection would still only take place after each step and most detection will be of fleets in motion rather than at the end of a step, so I am not sure what we gain. I am not saying that the intelligence of movement can't be improved but I not sure if this is the way to do it.
Response below, to the "only work out the first move of each fleet".
Quote
Quote
The second idea here (once you've got the first one coded up :). I may not intially agree with everything but they always get me thinking.

Going back to the initial idea of working everything out first, I guess I would only really need to work out the first move of each fleet, not all the moves, and I wouldn't need to physically change any records except the movement records so that would be quicker. In fact, an alternative might simply be to run through all of the existing first moves for every fleet and then just advance time by the shortest amount then repeat the process, rather than trying to work out a queue system. It still comes back to the problem though that detection is the main issue and this doesn't solve that any better than the existing timestep system, unless I am missing something.

Yes, this (only working out the first move) is exactly the idea.  You wouldn't even have to change the movement records - all you'd need to change is a (new) "time of next status change/event" field.  The shortest time in the DB for this new field would be exactly the "shortest" amount that you mention.

As for detection, I have two observations (based on reading some of the other posts):

1)  If everyone already has a "time of next event" field calculated, then you only need to recalculate it if either that time went by during the last timestep (by which I mean sub-pulse) or if the object's or a potential target's orders/speed/... changed (due to either the time going by or the player/AI changing orders) or if the object was hit by weapons.  I'm operating on the assumption that such a status change is very rare - maybe 10% for a "large" (e.g. 1-day) update and probably <10 objects for a "tiny" (e.g. 5 second, 30-second, etc. sub-pulse).  Let's assume that only 1 object changed state during the last timestep.  Then I have to do two calculations:

A) For every other object in the system, find the next time-of-intercept, and put the smallest of these in the object's "time of next event" field.

B) For every other object in the system, find the next time-of-intercept (hey!! I just realized that's the same quantity!!) - if it's earlier than the other object's time-of-next-event update the other object with the new time-of-next event.

So it's even cheaper than I thought - for everything that changed, loop over all the other objects and update the time-of-next-event field for both the thing that changed and the other object, as necessary.

Another thing I just realized - most systems (except maybe Sol in a multi-power game) won't have multiple races present simultaneously, so most of the time you won't have to do any detection.  And Sol shouldn't be that bad, since most of the traffic generating events will be civilian, and so will have transponders on which means they don't need to view detection as an event.

2)  Even if each timestep works out to be somewhat more expensive, the big advantage comes because (I suspect) you can get away with a LOT fewer timesteps - a player doesn't have to be afraid of doing 1-day or 5-day (or even 20 minute) increments.  This comes back to your idea of looking at first moves.  I'm beginning to think that the only thing you have to worry about is detection events.  So how about this: you only play this trick in systems with multiple races.  In other systems, things can just go as they do now.

More in othe replies....

John
Title: Re: NPR AI and timestep size
Post by: sloanjh on April 16, 2009, 10:07:04 PM
Quote from: "SteveAlt"
It isn't really a bug; more of a feature :-)  I'm 99% sure that the Precursors had detected me - they were on a reciprocal heading and actually already past me when they appeared, plus I'm pretty sure I was inside their planetary sensor's detection envelope.

2)  For a given pair of objects, you only need to use the sensor range that's biggest when calculating the intercept time - I don't think you need to redo the calcuation for each sensor type.

John
Title: Re: NPR AI and timestep size
Post by: sloanjh on April 16, 2009, 10:25:52 PM
Quote from: "SteveAlt"
Quote from: "Paul M"
The problem also lies in the time stepping as basically you need to determine if a hostile task force will end up inside the detection range of an object at the end of the current move, if so then stop the time at the point just where it would.  This is seriously unfun to even consider how to do.  If the game ran in real time with compression (such as harpoon did) it would be easier as might be fixed time intervals but with user defined one then it just gets messier and even worse so when a fleet goes from outside detection range to inside combat range inside of one time step.

A possibility is to add a routine that calcualtes the ending seperation of two forces at the end of the requested time step if the current forces are undetected now.  If no detection then it keeps the time step if there would be detection then it defaults to the next lowest time step and checks again, if no detection then it uses that one, if not it tries with the next lower time step until it reaches a time step that doesn't result in detection.  It executes that time step and posts a message up about switching time due to pending contact in system x by task force y.

This allows the player to find the unit in question and manually set the time to allow for the encounter to play out, without hopefully adding in much computing overhead.  It is a serious issue; however, as I have goofed and hit the wrong time step sometime or otherwise didn't expect combat only to have aliens show up at extremely close range to my ships.  This is also important for a SM who has to advance the game until something happens...and a warning to the SM that hostile fleets occupy the same system would also be useful.

But the trouble is...this is likely computationally much more difficult then I suspect it is as you have to make a detection matix and then apply a test to see if the sum of the matrix is 0 or ?1.  Again all of this is easier for a game like harpoon which is real time.
Harpoon is a great game and there is a lot of influence from that game on Aurora. The problem for me is that Aurora handles much larger timescales. For a pure-tactical battle you could run the game with perhaps 30 minutes increments and 5 second or 30 second sub-pulses and you would have something very close to Harpoon because the sensors are checked every increment. Perhaps the real way to tackle this is for me to concentrate on optimising the movement and sensor code so it executes more quickly and therefore allows a large number of small sub-pulses to be executed quickly.

EDIT - maybe I load everything into memory and run the sub-pulses then update the database at the end of the increment. Or on a smaller scale, at least retain the sensor information for each ship in memory because at the moment it is recreated during every sub-pulse. There must be a lot of mileage in this area.

Steve

More random comments :-)


John
Title: Re: NPR AI and timestep size
Post by: Paul M on April 17, 2009, 06:30:26 AM
Looking at this there is a simple fix, it is un-elegant in the extreme but it has the advantage of being workable.  If I understand Steve's response detection is only checked at the end of each time increment this results in the problem that you do a 5 day update and get told that your world/fleet was wiped out before you could even respond.  The solution that looks best to me at this point is to check if the ship ends its movement in a the detection radius of something if it does then don't play with the time but move the ship backwards along its bearing until it is (30 + 30(1-crewgrade*0.01)s)*velocity km inside the detection radius.

Where this gets complicated is if it ends up in multiple detection radius:
1. check against all detection radii
2. if inside longest ranged one calculate its position if backed up
3. check if backed up position is inside any other detection radius (excluding the 1 alread checked against)
4. if so back it up against that detection radius
5. check if backed up position is inside any other detection radius (excluding the 2 alread checked against)
6  if so back it up against that detection radius
7  check if the backed up position is inside any other detection radius (excluding the 3 alread checked against)
8  repeat until you check yields no other possible detections at this point this is the final position of the TG at the end of the movement increment.

The other possibility is calculate the intercept time of the fleets.  Check that against the time increment and reduce the time increment to a step where such an intercept (defined as one force entering the detection radius of another) no longer occurs.  Pup a "combat immenant" message in the events.

I am still not convinced this will work and it clearly can be exploited.  The issue here is the time increment when you don't expect combat can be large (5 days for example) so its hard to figure out how to deal with this and to not bollux up combat scale increments which the above would do in all likelyhood.  An engaged flag could be used to disable it so that once a unit was involved in combat these checks don't occur (active FC would do this).

Anyway this looks to me to be the best way to deal with it...it is in effect an automatic "undo until detection range."

What could bollux it up is that the civillians show as red on my screen all the time even though I have them set to neutral in the race.

Another idea would be to only use this on time increments greater than 3 hours (8 hours, 1 day, 5 days and 30 days) this would make it not an issue in a combat situation removing the need for a combat flag...even 8 hours is iffy.  But clearly 1 day, 5 days and 30 days are "peace time" advance rates and here is where the real effort needs to be put in.
Title: Re: NPR AI and timestep size
Post by: sloanjh on April 18, 2009, 05:47:15 PM
Hi Steve,

  Something just occurred to me.  You said that the sensor detection algorithm does essentially N^2 comparisons, where N is the number of ships in a system.  Does this mean that 30-40 civilian fleets running around in my home system is going to kill performance, since I've got another 20-30 ships (with sensors) in parking orbit?

Thanks,
John
Title: Re: NPR AI and timestep size
Post by: mikew on April 19, 2009, 10:21:06 AM
Here is something that *may* be a little more workable in determining intra-interval detection without any "higher math"  For each group of ships determine the range to each other "group" in the system and compare against longest range sensor(s).  For the next turn, determine the range again and compute a closing speed (range rate) by simply dividing the range difference by the time between checks.  If you presume that these will remain relatively constant, you can then determine with a fair amount of confidence whether the groups will enter detection range in the next interval.  This would only have to be done for fleets in systems with other potential targets.  If ships reach a turnpoint, transit a warp point, etc., you'd have to restart calculations of course, since that changes the range rate criteria.  At any such event, you can simply assign arbitrary range rates to other groups of ships equivalent to the maximum possible closing speed to determine whether a detection might be possible- once you run the first interval, you then have an actual rate for future calculations.

  When the numbers indicate a potential detection range arrival, calculate positions of the ships/populations/whatever involved, recalculate the range rate, and determine whether to continue and for how long, and begin again.  Eventually, your algorithm will bring you down to the shortest possible interval and your ships then enter detection range, at which point player interaction is called for as necessary.  This iterative process will likely result in somewhat longer processing times, as it will at some point or another shorten the interval to check for detections which don't actually occur, and will likely do so multiple times during approach to actual contact, but it WILL get you to the correct point of first detection.  With straight line movers, closing range rates will decrease as the range drops, so you will never have a ship manage to unexpectedly appear inside detection range.

  This will be complicated if fleets are spread out over a large areas, but if they vessels are clumped relatively close together, only the best sensors need to be checked on the basis that short range sensors won't make the initial detection in any case.  Based on what I've read so far, though, fleets won't be excessively large, and there won't be that many ships in any single system, so the overhead of calculating intevals shouldn't be that great.  The slowdown will occur when the system starts running the shorter intervals as ships approach detection range.  I don't know how long a typical update takes, so I can't estimate how much this will slow everything down- you might just be grabbing a soda from the fridge, or you might be cooking dinner- it depends on how long your normal intervals take to calculate.

  So, bottom line - you'll end up breaking your intervals down more often when multiple ships are in the same system.  You'll always do new calculations when ships transit to new systems (I imagine that happens now anyway), and if potential targets are in the system you'll need shorten intervals when ships approach waypoints to turn or change speed, and in addition when ships are calculated to potentially enter detection ranges based on previous closing speeds.  You will NOT have to retain any additional data on previous positions, nor use any new formula.  It should only result in significant slowdowns when vessels are actually in systems with possible targets, and then only when either approaching to contact or if vessels are maneuvering during the turn.

Mike
Title: Re: NPR AI and timestep size
Post by: ShadoCat on April 19, 2009, 01:47:04 PM
Mike's solution looks workable.  It'll give what you need without too many extra clock cycles.

The key is data pruning.  The more potential interactions you can toss out, the faster you will be.

If you combine with Paul's trig (which I understood after I dusted off the brain sells that shut down when I hit "transformations between non-linear vector spaces").  

You can use the trig figure out which interactions you need to consider.  In fact, you can even use it to determine which sub pulse you need to look at the interaction.  Thus, if the equations says that you won't enter into detection envelopes, then the interactions are never checked again until courses are changed, so only check again if courses change.  If they say that there will be an interaction in 4 pulses, only check again after 4 impulses.
Title: Re: NPR AI and timestep size
Post by: SteveAlt on April 27, 2009, 08:03:29 AM
Quote from: "sloanjh"
Hi Steve,

  Something just occurred to me.  You said that the sensor detection algorithm does essentially N^2 comparisons, where N is the number of ships in a system.  Does this mean that 30-40 civilian fleets running around in my home system is going to kill performance, since I've got another 20-30 ships (with sensors) in parking orbit?
It's not as bad as it might seem at first. Although theoretically each of the 30 ships will attempt to detect each of the other 30, as soon as a ship is detected the check for other sensors of the same type is ignored.

Steve
Title: Re: NPR AI and timestep size
Post by: SteveAlt on April 27, 2009, 08:38:55 AM
Rather than respond to each of the posts above, all of which contain a lot of very good suggestions that it will take me a while to assimilate properly, I thought I would provide on update on what I have been up to over the last week. I have decided that due partly to my fear of math :)

Steve
Title: Re: NPR AI and timestep size
Post by: ShadoCat on April 27, 2009, 05:07:35 PM
Steve, if you want any help with the math or the algorithms, just ask.

I don't know the new versions of VB or Access but I can pseudo code something up for you.
Title: Re: NPR AI and timestep size
Post by: SteveAlt on April 29, 2009, 09:17:59 AM
Quote from: "ShadoCat"
Steve, if you want any help with the math or the algorithms, just ask.

I don't know the new versions of VB or Access but I can pseudo code something up for you.
Thanks for the offer. John has already sent me some excellent code to tackle the prediction option but I am not going to work through it for the moment. I am saving it as a backup, or potential bonus, for the current recoding exercise. As with so many Aurora projects, this one is turning out to be huge. It is amazing how many parts of the program are being affected. Any part of the program that requires data access to fleets, ships, sensors, fleet orders, contacts and missiles during movement and detection or access to contacts at any time has to be rewritten to access the object model instead. I am currently working on converting missile movement to objects, which affects everything concerning point defence or point defence assignments, including fire control assignments and missile detection. If I had realised how large it was, I may not have started but there is no turning back now.

Steve
Title: Re: NPR AI and timestep size
Post by: ShadoCat on April 30, 2009, 01:48:01 AM
Quote from: "SteveAlt"
I am currently working on converting missile movement to objects, which affects everything concerning point defence or point defence assignments, including fire control assignments and missile detection. If I had realised how large it was, I may not have started but there is no turning back now.

Heh.

If guys thought out how much effort interesting ideas would take, people on this side of the Atlantic would still be speaking dozens of native languages....