tag:blogger.com,1999:blog-36248726606990033922020-02-29T11:00:33.012+01:00MMO Software Architecture<center>A blog about some of the interesting problems, approaches and solutions within MMO game platform development.</center>Anonymoushttp://www.blogger.com/profile/02677945756979786674noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3624872660699003392.post-26582018670896242842012-06-01T17:16:00.003+02:002012-06-13T23:15:42.169+02:00Effective Execution StatisticsAs designer of a highly scalable system I'm always trying to get good execution statistics data. Even from the frequent short test runs I'm doing during daily development. For instance, how long time have the simulation threads spent executing each simulation tick? How much time is spent persisting/loading data? What is the client IO volume?<br /><br />I'm not talking about actual code profiling. What I'm after is rather a summary of how the essential processes and tasks have performed after each run. Was something unexpectedly slow or fast? Did some data set grow or shrink?<br /><br />The behavior and performance can change when something apparently unrelated is changed. Indirect caching and memory consumption changes are two potential culprits. But it's also easy to make mistakes with more direct dependencies, for instance being sloppy when adding some attribute to some game entity type which happens to cause twice the data amount to be sent to clients! An appropriate execution statistics summary after each run enables a simple sanity check to catch such things.<br /><br />Execution stats are not about fixed time/data limits - in this system there are no "hard" such requirements. If a simulation tick takes 3 ms that's good - but if it takes 50 ms for 1000 simultaneous players that can be ok too. Often I'm not looking at the measurement values by themselves as much as how much they change depending on code I modify. How long does it take on average? Is that average less or greater after I attempted to cache something? (This is very hard to see from series of individual time samples/time stamps.)<br /><br />And it's important to not only examine an average value, nor the maximum (or minimum) value. For any given metric, I find that all these values are important:<br /><ul><li>count (number of executions/packets/whatnot)</li><li>average / median</li><li>standard deviation</li><li>minimum and maximum.</li></ul><br />The count of course tells how many times something has occurred. This info must be there to put the other measurements in context. If a DB load has happened only once but took 900 ms, it's probably slow because nothing had been cached and the JVM hadn't optimized the code yet.<br /><br />The average and median indicate the general performance to expect over time. For different metrics the average or the median can be a more relevant measure. It's best to produce both! Combined with standard deviation these values provide a good indication of the "typical span" of a metric, for example that it usually takes 10-40 ms to execute.<br /><br />The extreme cases must be examined as well however. If a simulation tick has a good average performance but occasionally takes 1000 ms (when, say 10 or 100 is expected) this has a serious effect on game play and must be investigated.<br /><br /><h3> Collecting and Printing Statistics</h3>For a long time I was manually adding statistics measurements to the code in the way lots of people do - calling System.currentTimeMillis() or nanoTime() at some execution points and logging the time spent. But this was cumbersome, unclean, ad-hoc and the results (lots of logged values) were difficult to interpret.<br /><br />I finally ended up writing a relatively simple but effective and efficient statistics collector and printer. My objective was to emulate the logger in simplicity: Put the measurements to the collector in a single line just as you would put a string to the logger:<br /><code></code><br /><code>public class IOPacker {</code><br /><code> public static final Logger LOG = Logger.getLogger(IOPacker.class);</code><br /><code> public static final StatCompiler STAT = StatCompiler.getStatCompiler(IOPacker.class);</code><br /><code> ...</code><br /><code> public void pack() {</code><br /><div><code> long startTime = System.nanoTime();</code></div><code> ...</code><br /><code> STAT.putSample("Pack time [ms]", (System.nanoTime()-startTime)/1e6);</code><br /><code> }</code><br /><code>}</code><br /><br />To output the compiled statistics, I execute this line before the program exits:<br /><code> StatCompiler.logAllStats(LOG, Level.INFO);</code><br /><div></div><div><br /></div><div><h3> Efficient Representation</h3></div><div>Just like for a logger, the implementation needs to be as fast as possible. This is not terribly hard. But then there is the concern for memory: in a long application run, the amount of held data shouldn't grow indefinitely, even though we want the information to encompass the full run!</div><div><br /></div><div>The solution lies in managing the precision with which all the collected data samples are represented. The implementation is really a bucket map where each bucket represents a certain value interval. Within each decimal order of magnitude (e.g. between 1.0 and 9.9, between 10 and 99 and so on) up to 90 intervals (buckets) are stored. A bucket is simply a counter that records the number of samples that has hit its interval.<br /><br />This means that the memory size grows with the order of magnitude between the smallest and the largest data point, <i>but not with the number of data points</i>. As long as there is a lower boundary on the smallest data point precision we care about, and since we only create buckets when a sample actually hits them, there rarely needs to be more than a few dozen buckets. We will still safely reflect any unusually small or large values (far outside the "dense bucket range" in the middle), and we still get good results with sufficient precision:</div><div><br /></div><div><code></code></div><div><code>Pack time [ms]: sum: 3 326; avg: 11,9 (sd +- 48,6); count: 279; min<med<max: 5,5 < 8,2 < 823,2</code></div><div><br /><h3> Implementation</h3>The code is in a public Gist, feel free to use it! (without any warranty of course ;-) )<br /><br /><a href="https://gist.github.com/2854260" target="_blank">https://gist.github.com/2854260</a><br /><br /></div>Anonymoushttp://www.blogger.com/profile/02677945756979786674noreply@blogger.com0tag:blogger.com,1999:blog-3624872660699003392.post-61933833777239657122012-05-16T10:52:00.000+02:002012-05-16T10:52:15.482+02:00Computing Space Travel - ImplementationThis is the Java code implementing the space travel solution I described in the previous post.<br /><br />(The vector and point classes it uses are very similar to Java 3D's vecmath and it would be straight-forward to modify this code to use vecmath instead.)<br /><br /><br /><script src="https://gist.github.com/2708736.js"> </script>Anonymoushttp://www.blogger.com/profile/02677945756979786674noreply@blogger.com0tag:blogger.com,1999:blog-3624872660699003392.post-82119192940273821312012-05-09T11:45:00.001+02:002012-05-09T17:13:41.052+02:00Computing Space Travel<div>How can a 3D-autopilot be implemented in a space opera game? How do you compute the optimal trajectory from A to B in a solar system using classical mechanics?<br /><br />This has been one of the tougher problems I've encountered in the MMO game project I'm working on. No other space game I've played has had a solution for this. The problem is usually avoided by either inventing other physics or hiding or skipping the actual travel. But I aim higher than that. I want it to <i>feel</i> like piloting a ship in space.<br /><br />Since it's a space opera game, the simulation primarily involves classical mechanics, i.e. Newtonian physics. (Einsteinian relativity I consider non-practical from an implementation point-of-view. I don't say this <i>only</i> because it's harder physics... and the light-speed limit would definitely limit game design!) In the game, celestial orbits, space ship movement, thrust engine power, fuel consumption etc are all derived with Newtonian physics.</div><div><br /></div><div>A lot of such behavior can be computed using high school level physics. But planning an optimal (or at least fairly efficient) space trajectory path to reach a given destination proved to be a considerably more difficult problem. It took much longer to solve it than I had expected. In this post I thought I'd describe what I came up with. It is an interesting problem and the solution can perhaps be useful to others.</div><div><br /></div><h3> Defining the Problem</h3><div><br />The objective is to plan the space trajectory needed to rendezvous with a given destination within the solar system. It is needed to implement the game's autopilot which is used by both computer-controlled ships and players. The trajectory must be computed in advance since simply going in the direction of the destination would result in arriving with a speed very different from that of the destination object. We need to know beforehand when to 'gas' and when to 'break', and in what precise directions to do this.<br /><br />The planned trajectory should be fairly efficient (primarily regarding travel time, but also regarding fuel consumption) and preferably not cheat by using different physics than the player experiences with the manual controls. It must also be fairly fast to compute - it's an MMO game and there can be many thousands of travelling ships.</div><div><br /></div><div>The formal problem is: The travelling spaceship, at current position P in space and with current velocity V, is to travel and rendezvous with a destination object (a planet, another ship etc) which is at current position Q and with current velocity W. Since it's a rendezvous (e.g. docking or landing) the travelling spaceship must have the same velocity W as the destination upon arrival.<br /><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-TXBHsy-5lgo/T6lDWAuN8dI/AAAAAAAAACo/uzGmcg-tQMs/s1600/trajectory_start.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="246" src="http://3.bp.blogspot.com/-TXBHsy-5lgo/T6lDWAuN8dI/AAAAAAAAACo/uzGmcg-tQMs/s400/trajectory_start.png" width="400" /></a></div><br />The above diagram is in absolute frame coordinates (sometimes called the inertial frame). However since we're adhering to Newtonian physics we can simplify the problem by defining it relative to the travelling ship's starting position and velocity instead. The next diagram shows the same case but in relative frame coordinates.<br /><br /><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-PBANxgHIh1o/T6ltyKQPT1I/AAAAAAAAAC8/60qydd5y7aM/s1600/trajectory_delta.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="162" src="http://2.bp.blogspot.com/-PBANxgHIh1o/T6ltyKQPT1I/AAAAAAAAAC8/60qydd5y7aM/s320/trajectory_delta.png" width="320" /></a></div><br /> P<sub>0 </sub>= <b>0</b> Q<sub>0 </sub>= Q - P ΔV = W - V<br /><br />A game space ship travels using its thrust engine, which accelerates the vessel in whatever direction it is pointing. The planned trajectory should be expressed as a sequence of thrust applications, each describing a trajectory <i>leg</i>:<br /><br /><ol><li>From time 0 to t1 apply thrust X</li><li>From time t1 to t2 apply thrust Y</li><li>...</li></ol><br />The technical problem is: Find the trajectory legs (each expressed as a thrust vector and a length of time) that as soon as possible will move the ship to the same position and velocity as the destination, so that:<br /><br />P(t) = Q(t); velocity = ΔV; t as small as possible<br /><br /><br /><a name='more'></a><h3> Solution Approach</h3><br />This is not trivial. What is described here is actually my third approach. The first one was plain incorrect, and the second one was sub-optimal and missed the destination in certain cases. This one however I believe is fully correct and actually produces the optimal trajectory in all cases (in terms of shortest travel time). (If a physicist reads this I'd be happy for any comments!)<br /><br /><h4> Two Solution Parts</h4>Two things must happen in the trajectory: Our ship needs to change its speed to match that of the destination, and it must travel the distance to reach the destination.<br /><br />The naive approach would be to do one after the other. Simply first move to where the destination is and then adjust the speed! (Of course it takes time to adjust the speed and the destination will move in the mean time, but we can change the destination position to adjust for that.) Or first change the speed to match the destination, and then travel to it by applying an acceleration followed by an equal amount of deceleration?<br /><br />There are three problems with this one-after-the-other approach. First, it results in a sub-optimal trajectory meaning it will take longer time and consume more fuel than necessary. Second, it will look weird to the player. And third and most importantly, it works poorly for destinations that change their velocity over time, as almost all destinations do. (Planets are in orbit, other spaceships are travelling somewhere - or even actively evading you if you're chasing them...)<br /><br />To elaborate a little on this last point, it's true the problem definition above makes no mention of changes to the destination's velocity over time. It's been simplified to disregard the destination's own acceleration. In theory the change in velocity direction over time is possible to compute for orbiting celestial bodies, although difficult within the context of this problem. But other spaceships are impossible to predict because someone else is controlling them! <i>Therefore the trajectory must be recomputed regularly during the journey - and we might as well disregard the complication of the destination's continuously changing acceleration in this solution.</i><br /><br />The naive approach is inadequate and the two solution parts must therefore be 'integrated' within each trajectory leg.<br /><br /><h4> Impulse and Moment</h4>To begin with, let's describe the solution in terms of impulse and moment. Δp is the change in an object's <i>moment </i>achieved by applying a certain <i>impulse</i> I. Impulse is defined as applying a certain force F over a length of time Δt, and is also equal to the change in velocity ΔV multiplied by the object's mass m.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-blEn7gwxWr4/T6ooWyJTsMI/AAAAAAAAADI/ZJW8i3hTles/s1600/ImpulseEqn_I.gif" imageanchor="1"><img alt="I = F t = m V = p" border="0" src="http://4.bp.blogspot.com/-blEn7gwxWr4/T6ooWyJTsMI/AAAAAAAAADI/ZJW8i3hTles/s1600/ImpulseEqn_I.gif" title="" /></a></div><div><br /></div>(Note the use of vector notation. Since we're navigating 3D space we need 3D vectors to describe position, velocity, force, impulse etc.)</div><div><br /></div><div>t<sub>tot</sub> expresses the total time the trajectory will take to traverse. We shall try to find this value.</div><div><br /></div><div>We know that, over the course of the total trajectory, an impulse I<sub>V</sub> must have been applied to the ship that changes its velocity with ΔV. And since we know ΔV and the ship's mass m we can directly compute it via I<sub>V</sub> = m ΔV.</div><div><br /></div><div>We also know that, some impulses in addition to I<sub>V</sub> must have been applied that causes it to traverse the remaining distance to the destination so they rendezvous at the same point P(t<sub>tot</sub>) = Q(t<sub>tot</sub>). Furthermore, since I<sub>V</sub> brings the ship to the correct arrival velocity, the sum of these impulses must be zero (otherwise the arrival velocity will be wrong). We therefore define these impulses as I<sub>D</sub> and I<sub>D</sub>', where the direction of I<sub>D</sub> is such that it accelerates the ship towards the rendezvous point, and I<sub>D</sub>' = -I<sub>D</sub> so that the net velocity change from these two impulses is zero.<br /><br /></div><div><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-SwJE4fpcdKo/T6pOIAa9FVI/AAAAAAAAADw/udB2KwDB4zY/s1600/impulse_diagram.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="162" src="http://3.bp.blogspot.com/-SwJE4fpcdKo/T6pOIAa9FVI/AAAAAAAAADw/udB2KwDB4zY/s320/impulse_diagram.png" width="320" /></a></div><br />The above diagram illustrates the impulses that must have been applied to the ship over the course of the trajectory.<br /><br />In order to apply these impulses the trajectory needs to have two legs:<br /><br /><ul><li>the first trajectory leg applies I<sub>D</sub> and part of I<sub>V</sub>;</li><li>the second trajectory leg applies I<sub>D</sub>' and the remaining part of I<sub>V</sub>.</li></ul><br /><br /><h4> Finding I<sub>D</sub></h4>We know I<sub>V</sub>, and I<sub>D</sub>' is the inverse of I<sub>D</sub>. So the impulse we still need to find is I<sub>D</sub>.<br /><br />The purpose of I<sub>D</sub> and I<sub>D</sub>' is to traverse the distance to the rendezvous point. How do we define this distance? Note that the purpose of I<sub>D</sub> and I<sub>D</sub>' is to traverse the distance that results after the destination's velocity ΔV and our own I<sub>V</sub> have been taken into account.<br /><br />First, define the distance at time 0:<br /><br /><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-ttPIqoRB9cA/T6pdo0wqGVI/AAAAAAAAAEQ/AujZCPJbNDk/s1600/DistanceEqn_D0.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-ttPIqoRB9cA/T6pdo0wqGVI/AAAAAAAAAEQ/AujZCPJbNDk/s1600/DistanceEqn_D0.gif" /></a></div><br />Then we add the destination's movement (t ΔV) and subtract our own movement caused by I<sub>V:</sub><br /><sub><br /></sub><br /><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-Ew7ih12vwPA/T6pdsbe7cwI/AAAAAAAAAEY/-xuQLctAaCE/s1600/DistanceEqn_Dt.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-Ew7ih12vwPA/T6pdsbe7cwI/AAAAAAAAAEY/-xuQLctAaCE/s1600/DistanceEqn_Dt.gif" /></a></div><sub><br /></sub><br />By our definition of I<sub>D</sub>, its direction is equal to the direction of D(t<sub>tot</sub>). Its magnitude also depends on t<sub>tot</sub>. To nail down I<sub>D</sub> we must thus find t<sub>tot</sub>.<br /><br /><h3> Algebraic Solution</h3>There is an algebraic solution at this point. Assuming constant thrust F, the total time is bound by the following equation:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-Sz_PA-k4Knk/T6pjReYgyhI/AAAAAAAAAEk/uDm4N9WbJC4/s1600/i_tot_Eqn.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-Sz_PA-k4Knk/T6pjReYgyhI/AAAAAAAAAEk/uDm4N9WbJC4/s1600/i_tot_Eqn.gif" /></a></div><br /><div class="separator" style="clear: both; text-align: center;"></div>Unfortunately this results in a <a href="http://en.wikipedia.org/wiki/Quartic_function" target="_blank">quartic function</a> (polynomial of degree 4) which is a pain to solve (and afaik requires an iterative numerical approach in the end anyway, e.g. the <a href="http://en.wikipedia.org/wiki/Newton%27s_method" target="_blank">Newton-Raphson method</a>). So I've abandoned this approach.<br /><br /><div class="separator" style="clear: both; text-align: center;"></div><h3> Practical Solution</h3>Since short travel time is the top priority, we shall assume constant thrust at the maximum power level set by the player (or the computer-controlled pilot). At any moment the ship can exert this thrust in an arbitrary direction in 3D space.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-CsCAuaJ7CW8/T6pEmXTGqhI/AAAAAAAAADk/u1J0xj0zjlk/s1600/force_circle.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="200" src="http://1.bp.blogspot.com/-CsCAuaJ7CW8/T6pEmXTGqhI/AAAAAAAAADk/u1J0xj0zjlk/s200/force_circle.png" width="197" /></a></div><br />The radius represents the maximum thrust force. This scalar quantity will be referred to as F. <br /><br />Remember that we're looking for two trajectory legs, each described by a thrust vector and the length of time it is to be applied. F<sub>1</sub> represents the first thrust vector and F<sub>2</sub> represents the second. As the diagram shows, they are resultant vectors of F<sub>V</sub>, F<sub>D</sub> and F<sub>D</sub>'. Their relationship with the impulse quantities is:<br /><br />I<sub>V</sub> = t<sub>tot</sub> F<sub>V</sub><br />I<sub>D</sub> = t<sub>1</sub> F<sub>D</sub><br />I<sub>D</sub>' = t<sub>2</sub> F<sub>D</sub>'<br />t<sub>tot </sub>= t<sub>1</sub> + t<sub>2</sub><br /><br />Since we know I<sub>V</sub>, we also know the direction of F<sub>V</sub>. However we don't know its magnitude, other than that it is in the interval (0, F).<br /><br />If we <i>did</i> know its magnitude, the rest would be relatively straight-forward to calculate. Applying the equations described above, knowing F<sub>V </sub>would yield:<br />t<sub>tot</sub><br />D(t<sub>tot</sub>) <br />R<sub>D </sub>(unit vector with same direction as D(t<sub>tot</sub>) and F<sub>D</sub>)<br /><br />Now we look closer at the force diagram:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-jkTtwGZNP_w/T6pumT8RqtI/AAAAAAAAAE4/JR8Dh1VzVAQ/s1600/force_angles.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="310" src="http://3.bp.blogspot.com/-jkTtwGZNP_w/T6pumT8RqtI/AAAAAAAAAE4/JR8Dh1VzVAQ/s320/force_angles.png" width="320" /></a></div><br />Using the dot product between F<sub>V </sub>and R<sub>D</sub> we can write:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-FF7DHE3NTFI/T6p3BiKbAGI/AAAAAAAAAFE/niK7Gj3YCWY/s1600/alpha_Eqn.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-FF7DHE3NTFI/T6p3BiKbAGI/AAAAAAAAAFE/niK7Gj3YCWY/s1600/alpha_Eqn.gif" /></a></div><br />Using the law of sines we can write:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-K8r2jFjhCqI/T6p6M-gSnuI/AAAAAAAAAFQ/fn4kLE-2mXs/s1600/F_D_len_Eqn.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="38" src="http://4.bp.blogspot.com/-K8r2jFjhCqI/T6p6M-gSnuI/AAAAAAAAAFQ/fn4kLE-2mXs/s320/F_D_len_Eqn.gif" width="320" /></a></div><br />Now we have F<sub>D</sub>, which also gives us t<sub>1</sub>:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-ZgHhijPLbS4/T6p-lQfYJzI/AAAAAAAAAFc/cHi6TKWxD10/s1600/t1_Eqn.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-ZgHhijPLbS4/T6p-lQfYJzI/AAAAAAAAAFc/cHi6TKWxD10/s1600/t1_Eqn.gif" /></a></div><br />Having t<sub>1</sub> we can continue to calculate t<sub>2</sub>, F<sub>D</sub>'... and F<sub>1</sub> and F<sub>2</sub>.<br /><br /><b><span style="color: blue;">The solution thus consists of the two trajectory legs { F<sub>1</sub>; t<sub>1 </sub>} and { F<sub>2</sub>; t<sub>2 </sub>}!</span></b><br /><br />As stated earlier we merely assumed the knowledge of F<sub>V</sub>'s magnitude. In the next post I'll describe implementing this solution using the <a href="http://en.wikipedia.org/wiki/Bisection_method" target="_blank">bisection method</a> to iteratively find the greatest possible value for F<sub>V</sub> (the greatest value of F<sub>V</sub> yields the optimal trajectory). It turns out that the average number of iterations required is less than 10 which is fine performance-wise, and the resulting movement is, well, smooth!</div>Anonymoushttp://www.blogger.com/profile/02677945756979786674noreply@blogger.com0