GraphViz replacement

Programmers discuss here anything related to FreeOrion programming. Primarily for the developers to discuss.

Moderators: Committer, Committer

Message
Author
Lathanda
Space Floater
Posts: 24
Joined: Mon Feb 08, 2010 9:35 pm
Location: Germany, Pfarrkirchen

GraphViz replacement

#1 Post by Lathanda » Wed May 26, 2010 9:03 pm

I'm atm writing a replacement for GraphViz.
Here is a little preview what it will look like.
Far
Image
Near
Image
code is stable only needs optical fine tuning
Last edited by Lathanda on Fri May 28, 2010 8:05 am, edited 2 times in total.

User avatar
pd
Graphics Lead Emeritus
Posts: 1924
Joined: Mon Mar 08, 2004 6:17 pm
Location: 52°16'N 10°31'E

Re: GraphViz replacement

#2 Post by pd » Wed May 26, 2010 10:30 pm

What benefit does it have compared to the other? Would it mean one less dependency?

Lathanda
Space Floater
Posts: 24
Joined: Mon Feb 08, 2010 9:35 pm
Location: Germany, Pfarrkirchen

Re: GraphViz replacement

#3 Post by Lathanda » Thu May 27, 2010 6:00 am

pd wrote:What benefit does it have compared to the other? Would it mean one less dependency?
Sorry good question.
1) one less dependency
2) potenially better layout as the class knows that it layouts techs, for example it checks the tech category
3) better performance as the used layout algorithm can be simpler as it knows what it layouts out

dwlg122
Space Krill
Posts: 9
Joined: Sun May 23, 2010 7:52 am

Re: GraphViz replacement

#4 Post by dwlg122 » Thu May 27, 2010 7:38 am

I had some trouble compiling freeorion with the newest graphviz stable and unstable.
I needed to change some includes and then uses the libagraph patch (graphviz current do not longer provides libagraph)
So It would be great to have a replacement

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 12484
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: GraphViz replacement

#5 Post by Geoff the Medio » Thu May 27, 2010 9:00 am

dwlg122 wrote:I had some trouble compiling freeorion with the newest graphviz stable and unstable.
I needed to change some includes and then uses the libagraph patch (graphviz current do not longer provides libagraph)
So It would be great to have a replacement
There are also copyright issues that prevent us from updating to a newer version of graphviz, which might have resolved some of these version incompatibility issues. Replacing graphviz with custom code avoids that problem as well.

Lathanda
Space Floater
Posts: 24
Joined: Mon Feb 08, 2010 9:35 pm
Location: Germany, Pfarrkirchen

Re: GraphViz replacement

#6 Post by Lathanda » Thu May 27, 2010 8:32 pm

You can download my binary in order to test the new tech graph.

Please note that the first levels have really many dependencies, making it impossible to avoid the line mess.

If you have suggestions for improvments i'm happy to hear them

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 12484
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: GraphViz replacement

#7 Post by Geoff the Medio » Thu May 27, 2010 9:04 pm

What SVN revision of FreeOrion did you modify to produce this binary? Some of the data file formats have changed recently, so someone trying your binaries will need to be using data files from a very close or identical version to what you modified. (In case anyone's wondering, no the SVN revision in the title of the FreeOrion window in the posted screenshot probably doesn't correctly indicate the SVN revision that was modified.)

Lathanda
Space Floater
Posts: 24
Joined: Mon Feb 08, 2010 9:35 pm
Location: Germany, Pfarrkirchen

Re: GraphViz replacement

#8 Post by Lathanda » Thu May 27, 2010 10:06 pm

Geoff the Medio wrote:What SVN revision of FreeOrion did you modify to produce this binary? Some of the data file formats have changed recently, so someone trying your binaries will need to be using data files from a very close or identical version to what you modified. (In case anyone's wondering, no the SVN revision in the title of the FreeOrion window in the posted screenshot probably doesn't correctly indicate the SVN revision that was modified.)
Good question it's 4 days old. If i read the svn correct 3600

Lathanda
Space Floater
Posts: 24
Joined: Mon Feb 08, 2010 9:35 pm
Location: Germany, Pfarrkirchen

Re: GraphViz replacement

#9 Post by Lathanda » Thu May 27, 2010 10:58 pm

I updated from the svn and did a new build.
svn is freeorion 3608 default 3600
Shown version 3601
The binary should now work with the actual svn data

Lathanda
Space Floater
Posts: 24
Joined: Mon Feb 08, 2010 9:35 pm
Location: Germany, Pfarrkirchen

Re: GraphViz replacement

#10 Post by Lathanda » Tue Jun 01, 2010 9:04 am

I tried several ways to improve the look, but the general problem is the placing of the first column of techs.
Just ordering them by category is good, but a real analysis would take a lot of time and not really change anything. Imho Graphviz didn't look better and they probably did more calculations than i did.

I see a simple solution if we add a number in the Tech file and in the Tech class that implies the wanted row and implicit the ordering.
That way the techs of the first column can be placed i a logical way.
No algorithm can ever reach the ordering a designer wants.

For the Zooming speed. I wrote a version that does the zoom really fast (full fps), I replaced the manual zoom with glScale calls.
InWindow does an affine transformation in order to work
TreeDragged scales the Mausmove data.

There are two Problems, as GG is based on int values I get a little rounding error for each mouse move, with a high fps mouse the mouse pointer and tree gets async as the numerical error sum up.

I somehow broke the scrolling, if I zoom out completely, I get some sort of signal feedback that breack the scrollbar completly.

I read the doxygen of GG but the description there don't have enough detail information to solve that.
Perhaps someone can take a look who knows GG, I did more guessing than knowing.

Stable slow version only layout http://www.lathanda.de/fo/change.zip
unstable scrolling but fast zoom version http://www.lathanda.de/fo/change_f.zip



btw. I can't get the Debugger of VS C++ working, it doesn't show me local variables, anyone an idee what it could be, debugging with std::cout is annoying.

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 12484
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: GraphViz replacement

#11 Post by Geoff the Medio » Fri Jun 04, 2010 9:52 am

There's a quirk to C++ templates you should be aware of:

Code: Select all

std::list<std::pair<double,double>>
This is likely to cause erorrs on many compilers, because the closing >> is parsed as a stream operator >> and not as two template-parameter closing braces as intended. To avoid this, always put a space between template parameter braces:

Code: Select all

std::list<std::pair<double,double> >
...

Your problems with the debugger are probably related to using templates and the STL, which the debugger doesn't seem to handle very well. Sometimes adding a debug output line will cause the compiler to treat something differently, allowing the run-time debugger to be used on variables it otherwise couldn't. It's not very reliable, unfortunately. I'm hoping MSVS 2010 will be an improvement, but I haven't looked into it yet.

...

I don't have any objections to adding a "treeteir" parameter to techs. It would be best if the parameter could be made optional, though, with the value being determined automatically when it's not specified. Would that be too complicated?

Your TechPanel class seems to be taking a pointer to its parent in its constructor, and then using that to do its rendering and InWindow calculations. This parent dependence suggests that it might be better to remove the TechPanel class, and do everything within the LayoutPanel. This would presumably allow the rendering of all the panels to be optimized in various ways, at least including eliminating some redundant matrix push and popping...

Weird stuff is definitely happening with the scrolling.

The new style of dependency lines is harder to interpret than the old ones. The main problem, I think, is that the lines all originate from the same horizontal position and fan out at very extreme angles, leading to a jumble of cris-crossing lines. The old layout had the lines originating and arriving at all different places around the tech panel.

There are also a few unnecessary complications of the conneciton lines, such as in the attached, that should probably be worked out.

It would also be good to try to group together techs from the same category at the same vertical range of positions, as much as is reasonable, for all tiers of techs, not just the tier one techs. It's nice that each category's tier 1 techs are currently together, but there's a lot more to a category than just tier 1...
Attachments
Lathanda_Tech_Layout_Draft.png
tech dependency arc odditiy
Lathanda_Tech_Layout_Draft.png (70.91 KiB) Viewed 2039 times

Lathanda
Space Floater
Posts: 24
Joined: Mon Feb 08, 2010 9:35 pm
Location: Germany, Pfarrkirchen

Re: GraphViz replacement

#12 Post by Lathanda » Wed Jun 09, 2010 6:48 pm

Geoff the Medio wrote:There's a quirk to C++ templates you should be aware of:
Your TechPanel class seems to be taking a pointer to its parent in its constructor, and then using that to do its rendering and InWindow calculations. This parent dependence suggests that it might be better to remove the TechPanel class, and do everything within the LayoutPanel. This would presumably allow the rendering of all the panels to be optimized in various ways, at least including eliminating some redundant matrix push and popping...

Weird stuff is definitely happening with the scrolling.

The new style of dependency lines is harder to interpret than the old ones. The main problem, I think, is that the lines all originate from the same horizontal position and fan out at very extreme angles, leading to a jumble of cris-crossing lines. The old layout had the lines originating and arriving at all different places around the tech panel.

There are also a few unnecessary complications of the conneciton lines, such as in the attached, that should probably be worked out.

It would also be good to try to group together techs from the same category at the same vertical range of positions, as much as is reasonable, for all tiers of techs, not just the tier one techs. It's nice that each category's tier 1 techs are currently together, but there's a lot more to a category than just tier 1...
The speed can definitly be improved if techpanel is part of the layout class as, the ask every item if it's hit by a click is O(n) and there are O(log(n)) Algorithms to determine the clicked item, with table Layout O(1).
But i don't really beleave the difference matters with 90 items.

Spliting the origin to several points instead of one line is no real problem, but i don't really see the improvement.

The extrem angles are a result of the category sorting. The angle get better if the nodes are ordered by theirs structual order. In priciple category should reflect the structure but it simply doesn't.
Some techs have neither parents nor children in their own category.
I can experiment a bit, by adding the order hint i mentioned. Perhaps some additional info can improve the lines without switching to much more complicated algorithm.

But it will take some time, as my holidays are over. I'll probably will need another 2 weeks.

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 12484
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: GraphViz replacement

#13 Post by Geoff the Medio » Thu Jun 10, 2010 4:42 am

Another C++ pointer: For initializer lists, you don't need to be so verbose. For example, from GraphLayout::Node::Node:

Code: Select all

    m_y(0),
    m_parents(),
should be the same as or faster than:

Code: Select all

    m_y(GG::Y(0)),
    m_parents(std::list<GraphLayout::Node*>()),
Lathanda wrote:The speed can definitly be improved if techpanel is part of the layout class as, the ask every item if it's hit by a click is O(n) and there are O(log(n)) Algorithms to determine the clicked item, with table Layout O(1).
But i don't really beleave the difference matters with 90 items.
The motivation for the changes wasn't just about speed improvement. I don't like the TechPanels needing to keep pointers to their parent Layout surface. They should ideally not need to know anything about where they're located, or in particular, require a particular class to contain them. If you want to use GL scaling stuff to do zooming, rather than resizing the TechPanels and having them render themselves differently depending on their size, and also deal with the logic to handle whether the mouse is within a (GL scaled) tech panel, then it would possibly be easier and cleaner to do all that rendering and/or logic within the LayoutPanel...

That said, if you get it to work, it's probably OK as is.
Spliting the origin to several points instead of one line is no real problem, but i don't really see the improvement.

The extrem angles are a result of the category sorting.
The problem now is partly that the extreme angle lines also originate at the same horizontal position, so blend in with the other lines starting poitns. If they originated at various horizontal positions, like in the attached, then there'd be a bit more variety and spacing.
The angle get better if the nodes are ordered by theirs structual order. In priciple category should reflect the structure but it simply doesn't. Some techs have neither parents nor children in their own category.
This is true, but this is the nature of the tech tree, and we shouldn't need to adjust the tree's structure (within reason) just to make the UI code logic easier.

It might also help if you made some more effort to keep categories of techs together when possible. In the (other) attached, the ships category first tier techs are much too high on the screen compared to the second tier ships techs, for no apparent reason, leading to unnecessary very long and highly-angled dependency lines.
Attachments
Ships_Category_Extreme_Angles.png
Extreme angle of ships category dependency arcs with modified tech tree layout
Ships_Category_Extreme_Angles.png (105.3 KiB) Viewed 2005 times
v0.3.14_tech_tree.png
v0.3.14 tech tree excerpt
v0.3.14_tech_tree.png (51.3 KiB) Viewed 2005 times

Lathanda
Space Floater
Posts: 24
Joined: Mon Feb 08, 2010 9:35 pm
Location: Germany, Pfarrkirchen

Re: GraphViz replacement

#14 Post by Lathanda » Thu Jun 10, 2010 4:52 am

The reason for the placing is that the first tier doesn't yet know where the second tier will be placed.
So it's in row.
In order to use follow up tiers, we need a multiscan algorithm and some sort of metric that decides between bad layout and good layout.
I didn't mean to change the techs in order to improve layout, i meant to overrule category if the placing is bad.

The graphviz version, neither uses category nor tier.

As "good" layouting is near AI, I'll try some tricks but atm real life is winning.

Lathanda
Space Floater
Posts: 24
Joined: Mon Feb 08, 2010 9:35 pm
Location: Germany, Pfarrkirchen

Re: GraphViz replacement

#15 Post by Lathanda » Thu Jan 06, 2011 12:17 am

I did a new version,
the zooming is now done using opengl.

The wish to make Techpanel independent from from it's layout failed for the reason that GG Render all loop is a global procedure instead of a virtual method, not allowing to add zooming code there.
Atm techpanel has to do it's own zooming, and therefore has a reference to LayoutPanel.

The layoutcode needs some tweaking, but I think is going into the right direction.

http://www.lathanda.de/fo/UI.zip

Post Reply