Statistical mechanical perspective of entropy in this computer simulation

I am not sure that the video referred to in your question is a good basis for discussion here, since the microscopic rules are not given, and may not fall into the category of mainstream physics. If energy is being taken out of the system, and if there is an attractive interaction between the particles, it is not surprising to see them form a condensed phase, perhaps a solid. This does not contradict the basic idea of entropy. This is what happens in better-defined systems in physics, when the temperature is lowered and a substance crystallizes. (The change in the energy of the system is reflected in the increase in the entropy of the surroundings). But I'm not really sure what that video is showing, from the physics viewpoint.

However, the two links you mentioned in your comments are based in mainstream physics and it is possible that a bit more explanation here will help you. The "Entropy confusion - sixty symbols" video is trying to clear up a popular misconception that entropy is always associated with an obvious, visible, disorder in the system. It refers to the well-known example of hard spheres. In this model there are no attractions. The thermodynamics is based entirely on entropy. Nonetheless, if you reduce the volume of the system, at a certain point it forms a regular crystal. The fact is that the entropy of the crystalline solid is larger than the entropy of a random arrangement of hard spheres would be at the same density. (This was established maybe 60 years ago). Nonetheless, if you looked at a video of the process, you might argue that the solid is more ordered, just as you are trying to argue on the basis of the video that you are citing. The simplest explanation is that each hard sphere particle has more local space to explore around its crystal lattice position, than it would in a random arrangement, where the spheres get more jammed by their neighbours. The extra entropy (larger number of microstates) associated with this local freedom more than compensates for the loss in entropy associated with adopting a regular crystalline arrangement. Casually looking at the pictures, you might only see the regularity of the crystal, and miss the implications of the extra free volume.

Over the last decade or more Sharon Glotzer's group (the second link you mention in your comments) has done some fine work on computer simulation of hard particle systems, but where the particles are not spheres (instead, typically, they are polyhedra of various shapes). Again, entropy is the sole driving force. Many, more complicated, solid phases can be formed than in the case of spheres. Again, there is no paradox. The articles that she has written, and interviews she has given, to popularize these phenomena are attempts to explain the nature of entropy as a feature of physical systems, and no doubt beyond physics too. Science writers love to write about entropy in connection with apparently paradoxical things. The thing that confuses some people is that entropy is not always associated with a superficial picture of "order", as might be seen in an image or a video.

I fully agree with LonelyProf's answer about the very widespread misconception connecting increase of entropy to the increase of spacial disorder. As Glotzer's work and a lot of previous work in numerical statistical mechanics has shown, the connection is not always as simple as in the case of the perfect gas. Interaction matters! and it may change dramatically the fraction of ordered configuration over their total number. That's the origin of entropy induced order.

However, there is an additional problem when one is dealing with gravitational systems. Even worse, there is more than one problem.

First of all it should be clear that, even modifying the short range divergence of the newtonian attractive potential, the long range $1/r$ tail is a big problem. Actually it makes impossible to deal with gravitational systems as normal thermodynamic systems, since the resulting energy is not extensive: instead of increasing as N, it increases faster than N. This fact implies that the usual thermodynamic limit does not provide a finite value for the free energy per particle. Moreover, all nice results valid for classical stable and tempered interactions (tempering has to do with the asymptotic decay of interactions) do not hold automatically. As a result there is no guarantee that different ensembles could provide the same thermodynamic information.

A second source of difficulties, related to the previous, but not coinciding, is that the virial theorem implies a peculiar behavior of a gravitational system. The virial theorem of $1/r$ interaction says that $$ <K>= -\frac{1}{2}<V>, $$ where $K$ and $V$ represent the total kinetic and the total potential energy of the system. The consequence is that the total energy of the isolated gravitational system is $E=<K>+<V>=\frac{1}{2}<V>=-<K>$. So, if the total energy of the gravitational system decreases, for example because some energy is emitted in the form of radiation, the average distances decrease ($V$ is getting lower), but, quite counterintuitively the kinetic energy increases. If we consider the average kinetic energy as proportional to the temperature, we see that gravitational systems are systems with a negative heat capacity. Which is a well known problem for gravitational system thermodynamics since the sixties and extensively discussed by Lynden-Bell and Thirring at that time. Once more an effect of the difficulties connected to the treatment of gravitational systems as thermodynamic systems.

Thermodynamics of gravitational systems is not impossible and in recent years there has been a lot of work in this direction. However the conclusion is that it is quite a different thermodynamics with respect to the "ordinary" laboratory thermodynamic systems and a direct application of well known results to such systems requires some care. A gravitational system can hardly reach thermal equilibrium with a conventional thermodynamic system.

Suppose you have two particles separated a distance from each other. Gravity will bring them together, right? Well ... not really. They will accelerate towards each other, but if they have any initial velocity orthogonal to their initial displacement, they will miss each other, and their momentum will carry them past each other, and they will then travel away from each other. Thus, they will enter an orbit around each other. And if they do hit each other, then in a perfectly elastic collision they will bounce of each other and fly away, and will effectively be in an orbit with extreme eccentricity.

Adding more particles makes this more complicated, but ultimately it comes down to the same thing: gravity does not, in fact, cause particles to coalesce. If particles come together, then taking only gravity into account those particles will arrive with enough energy to fly apart to their original distances. For a stable sphere to form, you need other phenomena, such as radiation bleeding off energy, or for there to be some internal structure of the particles into which energy is being transferred. If energy is being transferred into internal structure, then those structures are gaining entropy.