@cwyss

@Web-eWorks I also added Lua API documentation for GetProjectedBodiesGrouped() :-)

Thank you, much appreciated! If I could bother you a little more, could you separate that out into its own (appropriately named) commit? It'd make review slightly easier, and keeps our commit history sane 😄

Apologies if this PR is too big, i.e., concerns too many features. But since all of this affects the selection/display of in-space bodies and happens in the same piece of code, I decided to put this in only one PR. Hopefully this also helps when reviewing... :-)

Hmm... +145/-105? That's very small in my book! The only thing I'd suggest is that you try to squash your commits a little: the restore feature commits are good, but the little cleanups like remove duplicate entry from ... and adjust selection area of ... could all be merged into a single commit.

I'm very busy with non-Pioneer work right now and I can't review the code at this time, but if @impaktor or @vakhoir want to take a look and sign off, I'd be happy to get this merged.

@Web-eWorks Rebased things a little:

If I could bother you a little more, could you separate that out into its own (appropriately named) commit? It'd make review slightly easier, and keeps our commit history sane

Added a separate commit for this

The only thing I'd suggest is that you try to squash your commits a little: the restore feature commits are good, but the little cleanups like remove duplicate entry from ... and adjust selection area of ... could all be merged into a single commit.

Items 1 and 2 squashed into c1c98b7, items 6 and 7 squashed into 322b0c3. In fact I realised yesterday that it probably wouldn't make much sense to have e.g. 6 without 7 anyway, at least IMO: if the nav target is part of a group but not its main body, the nav target box may be "far" away from the (main) body indicator and its label, i.e. the body indicator is completely outside of the box.

Well, I have nothing to complain about. PR is well described, and commits seem reasonable, and seems like good stuff, so thanks for good job, @cwyss!

I haven't reviewed the actual code, as I mostly have my head filled with gray lint, rather than brains. Sorry. (I've been meaning to learn that UI code stuff at some point, sorry)

Maybe @mike-f1 could take a look, if not too busy

Oh, if someone ask with a little of care, sure I try to find time ;) ... I also hope @cwyss let me merge this stuff also on top of my work, can I?

Below some question.

1. Speed: have you profiled all this (good) stuff? ...I don't fear will get too slow but:
   a) It seems in commit d5b14a4 you don't reserve ahead of time for each group (line 1514 in PiLuaGui.cpp old version): basically I reserved for the worst => all remaining bodies in the same group (...which could have been done better with a dedicated for on top, btw :P )
   b) IIRC, preparing and passing to Lua tables is expensive (expecially "hash" tables...)
   So I'm just curious about how much it slows things (if it slows things)...and having some number will help to understand if some more care is needed, at least in order to put a TODO for future reasoning
2. In the second commit I (re-)see a lot of variables (as you too notice): I think is strange to not find any relations: at least you could calculate click_radius = some_factor * iconsize:length() at its definition, but also label_offset should be related to iconsize (...I guess half with some margin?) and small_iconsize (...which also could(?) be defined on top right after the other variables)
3. In d5b14a4 the "media" function is wrong (line 1550 in LuaPiGui.cpp): when you add the coords of a second body, it is correct to sum these 2, but in case you get a third body then their coords are calculated using a wrong weight for the latter (...it is doubled :P ), and things go worse for each body added... I used to recalculate coords summing all bodies again and again and then dividing by the right number after for readability sake, but IIRC there's a method to speed up things...
4. ...which can be to not calculate the media anymore (as in commit 322b0c3) though I don't understand the reason it is working... May I ask how it is expected to works?

5. pioneer/src/LuaTable.h

   Line 71 in 436db08

   * > t.LoadVector(v.begin(), v.end());

   which is an "experiment/advice": I dunno if it slows thing as I didn't check how it works (...copy, move, append right after reserved space may all happens...)

...There were also a problem of a lot of hyperspace clouds being displayed in the same group but not clickable or which seems to exist, is this solved? ...did you see it?

Thanks @mike-f1 for taking a look. And please feel free to use this stuff yourself, that's fine with me.

Concerning your remarks:

1. No, have not done any profiling yet. In fact, I did not manage to get the build-in profiler going so far. The only infos on profiling I found are from Single frame profiling instrumentation. #2541 and Single frame profiler #2569, which are perhaps outdated. Any hints about how to profile are welcome! (I'm compiling on Linux with cmake)
   Concerning std::vector.reserve() and Lua tables, some theoretical considerations make me think that my code does not perform worse than yours, but I'll wait for the profiling results here.
2. Good point, I will definitely do this!
3. I think the code is correct. Note that GroupInfo holds two members related to the centre of the group: m_worldCoordSum is always the sum of the 3d positions of all bodies of the group, with no weights. m_centreCoords is the 2d screen position of the geometric centre of the group, which is calculated from m_worldCoordSum by dividing by the number of bodies and then transforming to 2d screen space coords. This way, when adding a new body to the group, all we have to do is add its 3d world coords to m_worldCoordSum and then update m_centreCoords.
4. I don't understand what you mean here, sorry.
5. not sure what you mean here either, but I will look at LuaTable.h
6. I also did notice the strange long list of hyperspace clouds in one group. In fact, the label on the indicator says "Hyperspace exit cloud (2)", i.e., there should be (and probably there are) two clouds in the internal list, yet the popup displays a lot more. I guess the problem lies elsewhere here, but have not really investigated.

@cwyss to build with the profiler enabled, simply run ./bootstrap -DPROFILER_ENABLED=1 -DCMAKE_BUILD_TYPE=RelWithDebInfo and compile as normal. The latter flag is not strictly needed, but building with a BUILD_TYPE of Debug will disable optimizations; it's better to profile a Release build against a Release build than it is a Debug build against a Debug build.

Then, simply run Pioneer as normal, and you'll find a timestamped HTML file and a folder named after your save file in your ~/.pioneer/profiler directory - one is a startup profile, and the other contains profiles from the running game.

Check Pi.cpp for more info - the profiling apparatus lives in that file (along with half of the game's architecture, sadly...)

Thanks @mike-f1 for taking a look. And please feel free to use this stuff yourself, that's fine with me.

You're welcome, and thanks you too for permission :)

Here the open points

1. I left a comment on code
2. Closing :)
3. see below
4. see below
5. Oh, it was a nitpick: you use a for to load results in Lua (line 1593 in LuaPiGui.cpp), that is an alternative

3-4:
mmmh... Well, apart from above comments I have hard times to figure how the previous algorithm, which is a simple "Hierarchical agglomerative clustering" with a bottom-up approach ever seen (as stated only in (squashed) commit message here ) is translated into this new version... And the first difference I sees is the "media": without it works quite differently.
Here (fifth example, the last ones) you can see an animation of how it should works: it should become clear the role of the media (even if you should imagine to have more than a couple of points which can be grouped on a single step)

Not a problem if you feel that a less complex algorithm may suffice, I'm only pointing out that it's a different approach.

There's some other points open in case you would use the same algorithm, but I left on code a lot of comments which should help,

EDIT: Edited to highlight better the differences between the implementations because I noted the example I given works only on couples of points (as your algorithm does :P )

@Web-eWorks Thanks, got the profiler running. Though apparently line 176 in CMakeLists.txt is faulty: The upstream line reads

add_compile_definitions(PIONEER_PROFILER=1)

which is not a cmake command. I changed it to

add_definitions(-DPIONEER_PROFILER=1)

which does the trick. Does this sound reasonable? If yes, then I can put this in another PR.

@mike-f1

• I made click_radius relative to iconsize, as suggested. In fact it's now relative to the cluster size collapse, since these two have to play well together. This way one can also choose the icon and cluster sizes independently, though for now they are equal. I left label_offset as it was, since it should only be related to the size of the target rectangle, but that one is local in a different file.
• I now use LuaTable::LoadVector() (your point 5.):
  

  pioneer/src/LuaPiGui.cpp

  Line 1592 in 37ceda8

  bodies_table.LoadVector(group.m_bodies.begin(), group.m_bodies.end());

• (points 3. and 4.) You are right, my algorithm is different than yours. Mine is not a proper hierarchical clustering algorithm, it's simply the old algorithm used in game.lua before d90e14e. And this simpler algorithm is sufficient I think, since from my in-game experience it produces good results.
• I did some profiling now, and the numbers seem to indicate that my code is slightly faster than yours, probably due to the simpler algorithm:

The numbers are mcycles for l_pigui_get_projected_bodies_grouped() from the pioneer profiler output, single frame, averaged over 5 sample frames; the number in parentheses is the standard deviation I computed. The columns represent different player positions in the solar system, with different viewing directions, thus giving different numbers of on-screen bodies with different numbers of bodies inside clusters.

accidentally closed this :)

@cwyss , it's enough for me!

I would add just a couple of considerations (which may or may not lead to a TODO):

1. There's a reason you don't want to reserve (...even a simple: reserve(5)) on GroupInfo::m_bodies?
2. There's a way to work directly on Lua table instead of copying at the end? It is worth to at least work directly on a counterpart of GroupInfo avoiding that copy?

...These are two question I simply would pose: not that I want to see code or something, but just to share some thought...

I'll run some tests and go over the code later this week; if everything checks out like I think it will, this should be good to merge!

@mike-f1

1. Concerning std::vector::reserve(): I consulted Stroustrup's "The C++ Prgramming Language" (4th edition) and he says that the implicit automatic growth strategy of std::vector is in almost all cases sufficient and that calling reserve() explicitly did not measurably affect performance. A common growth strategy according to Stroustrup is to go initially (i.e. when adding the first element) from zero to 8 allocated elements and then double the allocated size each time more space is needed. As we typically have many groups containing only few bodies (<= 8) and only few groups with many bodies (> 8), I think automatic growth saves memory (though this might not really be a concern for us) and also does not yield a significant performance penalty (though I have not checked this with the profiler). Therefore I did not use reserve() in GroupInfo.
   The other two calls of reserve() for filtered and groups I kept however, since here we know that both vectors will often be big, i.e. > 8, and we also have a reasonable estimate for their final size.

2. I think having the Lua stuff all at the end, separated from the "real" algorithm, is good and shouldn't give a performance penalty. Moreover we have to sort each group's bodies, and this is perhaps better done in C++ than with Lua tables. I may be biased here though, since I know C++ quite well but only very little about Lua 😄

Though apparently line 176 in CMakeLists.txt is faulty: The upstream line reads

add_compile_definitions(PIONEER_PROFILER=1)

which is not a cmake command. I changed it to

add_definitions(-DPIONEER_PROFILER=1)

which does the trick. I can put this in another PR.

Please do, @cwyss.

Concerning std::vector::reserve(): I consulted Stroustrup's "The C++ Prgramming Language" (4th edition) and he says that the implicit automatic ...

Well, it seems that, at least for gcc 8.3, they didn't read that book:
https://ideone.com/uZ9OCj

OK, let's settle this.

What Stroustrup meant is that typical vector implementations use power of 2 memory allocations for object storage. This means that to insert N elements in an empty vector, you'll have log2(N) reallocations, which is really low compared to high values of N. This could be even further amortised by signaling the memory allocator that the memory allocation might need to grow further in the future, which might lead said allocator to put the allocation at the start of an unfragmented chunk of memory. I don't know if it's actually being done, though.
However, even just the logarithmic allocation means that simply pushing your elements is quite fast, as the cost of an insertion is O(1) (the worst case being O(n) but with a 2/n probability).

All this means that the mental overhead of figuring out the size of the final container and calling reserve() on it might not be worth it, hence Stroustrup advice. I don't particularly agree with him, though.

Note that the GCC implementation is as typical as they come, with the 0, 1, 2, 4, 8, 16 pattern showing as predicted.

Now that we explained Stroustrup's advice, is it applicable here ?

Well... We're dealing with really small sizes here, so this is where you'll have the most reallocations occurring. Assuming there's an actual performance problem I'd go with reserve. I don't know if this part of the code is hot, though.

According to the profiling results, this code takes about 0.5% to 1% of the total time spend in MainLoop() (which corresponds to one frame?) So I assume there is not really a performance problem here. And as stated above, the simpler algorithm used in this PR already gives a (slight) performance improvement.

Np on my side, let Big Boys show their skills & reasoning :D

Turns out I didn't get a chance to go over this when I thought I would, but it's done now! Everything looks good, thank you very much @cwyss for your contribution!