Dev Blog : September 9th 2015

    Bench

    Creative Director
    Joined
    Jun 24, 2013
    Messages
    1,046
    Reaction score
    1,745
    • Schine
    • Wired for Logic
    • Legacy Citizen 6

    A month later, time to finally have a new dev blog. This time brought to you by our main man, schema ...


    A number of players have expressed interest in hearing a bit more in-depth on things like how we optimized our turrets in the recent update. Well in order to best cover how we improved the performance of some aspects of StarMade I’ll be writing a series of Dev Blogs explaining some of the difficulties of building a game like ours, and how we overcame those difficulties.

    Physics for any game are probably one of the most important aspects. There is a lot of code and effort put in game in that alone. There are a lot of brilliant libraries to use already, but depending on the game you will also have to manually customize to get the best results.

    There are several points to consider for physics:
    • How big is the world?
    • How many collidable objects does it contain?
    • How many objects are moving?
    • How detailed are the objects?
    • Do the objects’ shapes change?
    Each of these aspects brings forth another degree of complexity to physics. In StarMade you can pretty much answer these questions with “huge”, “a lot”, and “yes, yes, yes”.

    If StarMade were to try to run in a single huuuuge sector, you would probably be lucky to get a frame per day on a bigger server.

    To combat this humongous task, one of the prime mantras of programming is used: “Divide and conquer”. This means, a big problems can to be “cut up” into smaller problems which then can be handled more easily. Also we have to identify what we don’t need at all times (like a sector where nobody is at the end of the universe).

    Relatively early in StarMade’s live, the sector system was introduced. I’m now glad that I did it that early, because the more that complexity is added to the game itself, the harder it would get to do it afterwards. The sector system helps divide up everything, from physics to network load.

    As a few of you have noticed with MC and other games, a game’s world can only be so big when using a single “sector”.

    Most games usually use floating point numbers to define “where stuff is”, and that includes basically every polygon in the game. There are 4byte floating point numbers which are normally used, but because you can only fit so much into 4 byte (32 bits), due to the nature of floating point numbers, the precision (amount of decimal digits) decreases, the higher the number itself gets. This means, that numbers in the one million area have much less decimals than numbers between 0 and 1.

    For games in a bigger world this means the world is going to get buggy at a certain range, as all positions of the polygons and whatnot get very imprecise, as well as all math operations done on these.

    The easy way out for this is to just switch to double precision values (8 bytes), usually called ‘double’, which doubles the range in which values are precise another 32 times (which is incredibly huge).

    However, this method has a very deciding downside to it: Every single number will take double the space in the computer’s RAM, the graphics card’s RAM and on disk. Not only that, but also all that data has to travel from the different parts of a computer’s hardware, and there is only so much that can travel at the same time. This alone would be already be a major downside, but one thing that doesn’t grow as fast as other things in the computer world is a user’s network bandwidth. Using double means you have to send double the amount of position data for every object in the game’s world, and position data is the biggest thing that is sent and received constantly.

    StarMade’s sector system gets rid of that problem completely. Not only that, but by constantly monitoring which objects are in which sectors, we know exactly what areas we want to update, and where currently no active or moving object is. This means a lot of so called overhead can be eliminated, because we don’t have to look at every object to check if it’s active or not.

    One of the biggest physics advantage of having sectors are two things: Objects that are not anywhere close in terms of vicinity don’t have to ever be tested for collision or even distance to each other, and the limited sector range speeds up the so called “broad phase” of physics.

    Physics engines usually comes in 2 phases. The broad phase, in which an area is scanned for all the objects that can possibly collide. To do this, axis aligned bounding boxes are created, that means, a box around an object that is always aligned to the coordinate axes of the geometrical system. There are several methods to check which bounding box overlaps with which, the slowest being brute-forcing: meaning, testing every object with every object which gives us a whopping complexity of n^2 tests that have to be done each time. A n^2 is usually unacceptable if you want to have anything that remotely scales.

    The method used in StarMade is the physics engine’s axis scan. Imagine it like a 2D plane that moves from the back of the sector to the front. The complexity of that is n*log(n) in the worst case, which is a LOT better.

    After the broad phase is done, we know which objects possibly collide with others. So now a more detailed test for each pair can begin: the narrow phase.

    I will cover that in the next part of this blog.

    Thanks for reading,
    schema
     

    Ithirahad

    Arana'Aethi
    Joined
    Nov 14, 2013
    Messages
    4,152
    Reaction score
    1,330
    • Purchased!
    • Top Forum Contributor
    • Legacy Citizen 8
    ...Tl;dr: Giant universes of player-created shapes bouncing around and colliding with each other is nigh-impossible to compute nicely (without tricks, anyway), so we split the physics up into tiny universes called sectors and so everything works? :P
     
    • Like
    Reactions: Blodge

    Groovrider

    Moderator
    Joined
    Dec 17, 2014
    Messages
    534
    Reaction score
    195
    • Purchased!
    • Legacy Citizen 4
    I think I see where this is going. Turrets and other rail entities occupied the narrow phase scan something awful.
     
    Joined
    Dec 2, 2013
    Messages
    232
    Reaction score
    98
    • Legacy Citizen 2
    • Purchased!
    • Competition Winner - Small Fleets
    It's great to hear about some of the inner workings of the game.

    I understand now why sector and system transitions use to be so wonky, flinging you all over the place.
     
    Joined
    Mar 1, 2015
    Messages
    291
    Reaction score
    176
    • Wired for Logic
    • Community Content - Bronze 2
    • Purchased!
    Your description of the axis scan immediately reminded me of the baryon sweep from Star Trek TNG.
    So basically, you are using a collision plane to render the 3d hitboxes onto a 2d plane, effectively slicing the sector up hitboxes included, so that a slice of space with only one entity doesn't get collision checks? If so, it may be possible to create extra lag by lining your ships up, forcing them all to have to be tested together. Please correct me if I am wrong.
     

    Tunk

    Who's idea was this?
    Joined
    Sep 8, 2013
    Messages
    363
    Reaction score
    153
    • Purchased!
    • Community Content - Bronze 1
    • Legacy Citizen 4
    Honestly the dev blog is kinda light on detail, I was expecting a more technical explanation rather than layman overview.
    The Axis scan is a pretty neat idea, though wouldn't bounding spheres run through a cached pruned list be faster?
     

    Olxinos

    French fry. Caution: very salty!
    Joined
    May 7, 2015
    Messages
    151
    Reaction score
    88
    It's trivial to find the smallest aligned bounding box containing an entity, it's more complicated to compute the smallest bounding sphere. Besides, it wouldn't provide that much of an improvement in my opinion (the sphere isn't necessarily smaller than the aligned bounding box, actually, with rather long shaped ships it's likely to be the opposite in most cases).

    Edit: Ah, also, I was a bit surprised with this:
    The method used in StarMade is the physics engine’s axis scan. Imagine it like a 2D plane that moves from the back of the sector to the front. The complexity of that is n*log(n) in the worst case, which is a LOT better.
    If I understood well, the algorithm is supposed to return a set of pairs of entities which possibly collide. In this case, this is approximated by checking the collisions between the aligned bounding boxes.
    If this is right, I can't think of an algorithm performing in O(nlog(n)) in worst cases since in the case where all entities collide with each other, the simple task of building the list of all possible pairs already has squared complexity.
    In particular, the algorithm which is briefly mentioned has O(n^2) (worst case) complexity unless you're using some tricky data structure I don't know of taking into account some properties of the system to store these pairs (you won't escape the squared complexity once you iterate through these pairs though).
    It's true, however, that this algorithm will perform better than simple bruteforce, actually its worst case complexity is probably O(nlog(n)+NbCol) where NbCol is the number of collision pairs.
     
    Last edited:
    Joined
    Feb 8, 2015
    Messages
    226
    Reaction score
    36
    • Purchased!
    • Community Content - Bronze 1
    Interesting.... So is the reason planets are so laggy because their bounding boxes overlap? Also, I'm writing a game myself so im well aware of the difficulty of a single world's physics lag. You accomplished it marvelously, Bravo
     

    Bench

    Creative Director
    Joined
    Jun 24, 2013
    Messages
    1,046
    Reaction score
    1,745
    • Schine
    • Wired for Logic
    • Legacy Citizen 6
    Honestly the dev blog is kinda light on detail, I was expecting a more technical explanation rather than layman overview.
    There's another couple dev blogs coming after this that cover the narrow phase and then a look specifically at turrets, what the issue was and how we eventually overcame it. Have to set the foundation first.
     
    Joined
    Sep 10, 2015
    Messages
    131
    Reaction score
    28
    There's another couple dev blogs coming after this that cover the narrow phase and then a look specifically at turrets, what the issue was and how we eventually overcame it. Have to set the foundation first.
    Game building is such an interesting and complex task. One of the few things that taxes nearly every part of the brain.
     

    schema

    Cat God
    Joined
    Feb 17, 2012
    Messages
    1,552
    Reaction score
    2,604
    • Schine
    Well, to a way it is like
    Trekkerjoe says.

    However, the scan doesn't move inch by inch, it moves coordinate by coordinate.

    What is done is to first sort the bounding box minimum and maximum coordinates (x,y,z).

    By doing that we have a very big advantage: every minimum coordinate that started beyond a maximum coordinate can't possibly overlap with that box. Boxes only overlap if they have common one dimensional intersections in all three axes.

    So for example if one bounding box has an x range from 0 to 10, another bounding box can be excluded from the test if it's minimum starts at 11.

    This algorithm is not my idea and fairly common for physics libraries. I just used my own implementation of it to adapt to the special case of having blocks

    The reason why not more detail is given is that I'm walking a very thin line of getting caught in a mass of details that would be nearly impossibly to fit into blog posts.
     
    Joined
    Jul 21, 2013
    Messages
    2,932
    Reaction score
    460
    • Hardware Store
    The reason why not more detail is given is that I'm walking a very thin line of getting caught in a mass of details that would be nearly impossibly to fit into blog posts.
    To avoid that, why not post some pseudocode instead. Those interested in these details SHOULD be able to deduce them from there. (Even though I hate writing pseudocode myself)
     

    Olxinos

    French fry. Caution: very salty!
    Joined
    May 7, 2015
    Messages
    151
    Reaction score
    88
    To avoid that, why not post some pseudocode instead. Those interested in these details SHOULD be able to deduce them from there. (Even though I hate writing pseudocode myself)
    Live example (ideone link) in C++11 for one dimension (worst case complexity: O(nlog(n) + [number of collisions]) where n = [number of entities])
    For three dimensions, a trivial way is to run it 3 times along each axis and only keep the collisions which appear in all lists (worst case complexity: O(nlog(n)) where n = max([number of entities], [number of collisions]), if all the entities collide [number of collisions] = O([number of entities]^2) )
     
    Joined
    Jul 21, 2013
    Messages
    2,932
    Reaction score
    460
    • Hardware Store
    Live example (ideone link) in C++11 for one dimension (worst case complexity: O(nlog(n) + [number of collisions]) where n = [number of entities])
    For three dimensions, a trivial way is to run it 3 times along each axis and only keep the collisions which appear in all lists (worst case complexity: O(nlog(n)) where n = max([number of entities], [number of collisions]), if all the entities collide [number of collisions] = O([number of entities]^2) )
    1: I fail to see the relation to my post.
    2: language mismatch, C++11 is neither pseudocode nor java. :P
     

    Olxinos

    French fry. Caution: very salty!
    Joined
    May 7, 2015
    Messages
    151
    Reaction score
    88
    1: I fail to see the relation to my post.
    2: language mismatch, C++11 is neither pseudocode nor java. :p
    1: You talked about the possibility of giving pseudocode, meaning you may be interested in the algorithm. I quoted you if that was the case.

    2: I usually prefer actual code to pseudocode as pseudocode by definition isn't supposed to compile and may omit some (not that irrelevant) details. C++11 may not be java (the language in which the game is coded) but it's one of the most used/known languages and the one I know (besides it should be understandable by anyone who knows a programmation language).
     
    Last edited:

    Matt_Bradock

    The Shrink
    Joined
    Aug 4, 2013
    Messages
    798
    Reaction score
    464
    • Purchased!
    • Thinking Positive
    • Legacy Citizen 5
    I absolutely love the dev blog, so keep it coming, Bench and schema !
    Also, we came here for the details. Although I understand a lot less about actual algorhytms and code (only 2 semesters in software engineering) than most people posting here, I'm still intrigued, so don't hold back!