New starname clustering method, some questions

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

Moderator: Committer

Message
Author
Chriss
Dyson Forest
Posts: 231
Joined: Sun May 11, 2008 10:50 am

New starname clustering method, some questions

#1 Post by Chriss »

I'd like to change the way starnames are clustered so that they are not clustered based on euclidean distance, but based on jumps. Basically, my idea is to have a center system (high number of starlanes) and then name the neighboring systems likewise, more or less regardless of distance. Not sure yet of the details, I'm still trying if I can make it work at all.

Currently, I have a list of systems (what get's passed to starnames's name_star_systems), and the starlanes (fo.sys_get_starlanes(system)). How do I get info on the starlanes, notably where they point to? In graph-speak, how do I find the neighbors of a system? How can I use the python object "system" at that stage? That's the only reference to a HasStarlaneToSystemID function I am aware of...

I use PyDev so far, with autocompleate in IDE for Python API in classpath to help me find things. Does that make sense? Since it does not seem to be complete as far as the c++ interface is concerned, are there better ways?
Attached patches are released under GPL 2.0 or later.

User avatar
Dilvish
AI Lead and Programmer Emeritus
Posts: 4768
Joined: Sat Sep 22, 2012 6:25 pm

Re: New starname clustering method, some questions

#2 Post by Dilvish »

if you search the AI code for 'neighbors' you should see examples on how to access and use the starlane info.
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

User avatar
Vezzra
Release Manager, Design
Posts: 6095
Joined: Wed Nov 16, 2011 12:56 pm
Location: Sol III

Re: New starname clustering method, some questions

#3 Post by Vezzra »

Chriss wrote:I have a list of systems (what get's passed to starnames's name_star_systems), and the starlanes (fo.sys_get_starlanes(system)). How do I get info on the starlanes, notably where they point to? In graph-speak, how do I find the neighbors of a system?
sys_get_starlanes(system) returns a list of ids of the systems system has starlanes to. So, you don't need to process the list you get from sys_get_starlanes any further, it is already the list of the directly adjacent neighbor systems.

Starlanes do not exists as separate universe objects, a starlane is nothing else than the id of the target system, stored in a list with the source system. Meaning, for a starlane to be bidirectional, the target system itself also has the id of the source system stored in its own list of starlanes (=starlane targets).
How can I use the python object "system" at that stage?
The object "system" is nothing else than the integer system id. You can use it wherever functions exposed to the server-side Python scripts expect/accept a system id as parameter (e.g. all the sys_* calls).

The server-side Python interface is still very incomplete. I didn't add much more than what was required to reproduce the functionality of the original C++ universe generation code. So, if there is something you're missing/like to have, tell me, and I'll try to add it to the interface.

User avatar
Dilvish
AI Lead and Programmer Emeritus
Posts: 4768
Joined: Sat Sep 22, 2012 6:25 pm

Re: New starname clustering method, some questions

#4 Post by Dilvish »

Vezzra wrote:
How can I use the python object "system" at that stage?
The object "system" is nothing else than the integer system id. You can use it wherever functions exposed to the server-side Python scripts expect/accept a system id as parameter (e.g. all the sys_* calls).
That seems to me like a rather confusing way to talk about it, because the server python interface does indeed include system objects that are more than just mere integers. I think we should stick with
Vezzra wrote:sys_get_starlanes(system) returns a list of ids of the systems system has starlanes to.
and note that you can get the corresponding system objects via calls to universe.getSystem(target_system_id). The attributes and methods of the boost-python system object are defined in python/PythonUniverseWrapper.cpp, and are summarized at AI_Python_API. I'll try to get around to editing that page to clarify which portions are truly specific to the python AI API; pretty much everything in it that is not specific to the AI will also apply to the python server API.
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

User avatar
Vezzra
Release Manager, Design
Posts: 6095
Joined: Wed Nov 16, 2011 12:56 pm
Location: Sol III

Re: New starname clustering method, some questions

#5 Post by Vezzra »

Dilvish wrote:That seems to me like a rather confusing way to talk about it, because the server python interface does indeed include system objects that are more than just mere integers.
I think you're confusing something with the AI Python interface, because the "freeorion" module that gets imported by the server-side Python scripts is wrapped up like this:

Code: Select all

BOOST_PYTHON_MODULE(freeorion) {
    FreeOrionPython::WrapGameStateEnums();
    FreeOrionPython::WrapGalaxySetupData();
    WrapServerAPI();
}
And WarpServerAPI() doesn't contain anything that exposes any of the universe object classes. I've specifically tried to avoid incorporating handling of objects, to keep the interface as simple script-like and procedural as possible. Assuming that this is easier for non-programmers to learn, understand and handle than handing them classes, objects, methods etc., the whole OOP stuff. As powerful as that is, if you aim for simplicity, better stick to a simple set of functions as interface.
I think we should stick with
Vezzra wrote:sys_get_starlanes(system) returns a list of ids of the systems system has starlanes to.
and note that you can get the corresponding system objects via calls to universe.getSystem(target_system_id).
Well, that's currently not possible, because not exposed to server-side Python. For that to work, we'd need to include the AI Python wrappers too:
The attributes and methods of the boost-python system object are defined in python/PythonUniverseWrapper.cpp, and are summarized at AI_Python_API. I'll try to get around to editing that page to clarify which portions are truly specific to the python AI API; pretty much everything in it that is not specific to the AI will also apply to the python server API.
The basic problem we're going to run into when we open that can of worms is that the AI Python interface is a client-side interface. It exposes classes/functions that are client specific, like the issueing of orders, that are not present on the server side (AFAIK).

So, if we want to integrate the two (ATM completely separate) interfaces, this will need a major refactoring/restructuring of both interfaces. We need to determine which components they have in common and can be shared, which are different and therefore must be defined/exposed separately on each side, and then create the respective client- and server-side and common modules.

In principle that's a good idea, it surely would reduce some good amount of duplicate code, but to me that looks like a major project. Do you really want to take that on? I won't object, it's just that both of us already have a lot on our plate... ;)

Chriss
Dyson Forest
Posts: 231
Joined: Sun May 11, 2008 10:50 am

Re: New starname clustering method, some questions

#6 Post by Chriss »

Vezzra wrote:sys_get_starlanes(system) returns a list of ids of the systems system has starlanes to. So, you don't need to process the list you get from sys_get_starlanes any further, it is already the list of the directly adjacent neighbor systems.
That's a nice solution... I'd even say nifty, because it is so simple. I think that should be all that I need for a first draft. Thanks.

About the whole server vs. client side issue... Maybe simply state the distinction at the appropriate places?
However... the docs I've been using all state Python AI Interface I think... Is there anything specific to the server side?
Attached patches are released under GPL 2.0 or later.

User avatar
Dilvish
AI Lead and Programmer Emeritus
Posts: 4768
Joined: Sat Sep 22, 2012 6:25 pm

Re: New starname clustering method, some questions

#7 Post by Dilvish »

Vezzra wrote:I think you're confusing something with the AI Python interface
My apologies, I did confuse something-- I had seen that PythonServer.cpp and PythonServerWrapper.cpp both had an include for PythonWrappers.h, which simply exposes WrapUniverseClasses(), WrapGalaxySetupData(), WrapGameStateEnums(), WrapEmpire() and WrapLogger(), and apparently I mistakenly assumed that all of those wrappers were then used instead of just some.
and note that you can get the corresponding system objects via calls to universe.getSystem(target_system_id).
Well, that's currently not possible, because not exposed to server-side Python. For that to work, we'd need to include the AI Python wrappers too:
I'm not sure what you mean here by the term 'AI Python wrapper', but I'm pretty sure I would have a different meaning for it (explained more below).
The attributes and methods of the boost-python system object are defined in python/PythonUniverseWrapper.cpp, and are summarized at AI_Python_API. I'll try to get around to editing that page to clarify which portions are truly specific to the python AI API; pretty much everything in it that is not specific to the AI will also apply to the python server API.
The basic problem we're going to run into when we open that can of worms is that the AI Python interface is a client-side interface. It exposes classes/functions that are client specific, like the issueing of orders, that are not present on the server side (AFAIK).
As I had tried to explain in the quote you cite, and as I indicated I would try to clarify on the Wiki, the wiki page currently titled AI_Python_API Has two major sets of components, those specific to the client-side AI interface (defined in the FreeOrion/AI directory), and those that are part of the generic FO python interface (defined in FreeOrion/python and exposed via PythonWrappers.h). I would not expect the server to incorporate any of the AI client wrapper from FreeOrion/AI. I don't think that any of the FreeOrion/python wrappers reference anything from the FreeOrion/AI interface, and if they did have any client specific code (nothing comes to mind but there might be a small bit) then perhaps it should be moved to make a more clear distinction between the AI Python Interface, the Server Python Interface, and the underlying generic FO Python Interface that gets incorporated (at least in part) by both AI and Server.
And WarpServerAPI() doesn't contain anything that exposes any of the universe object classes. I've specifically tried to avoid incorporating handling of objects, to keep the interface as simple script-like and procedural as possible. Assuming that this is easier for non-programmers to learn, understand and handle than handing them classes, objects, methods etc., the whole OOP stuff. As powerful as that is, if you aim for simplicity, better stick to a simple set of functions as interface.
Hmm, I think that making helper functions available so that some things can be done with this scripting in very simple ways is a fine idea, but I don't see how that means it needs to be restricted to only that. The whole point of this interface is to allow more complex scripting than FOCS will allow, and the whole point of the classes and whatnot is to help organize information and routines in ways that are easier to keep track of and use. If you entirely do away with the class exposures it seems to me that either you're going to wind up with much more complicated code or with significantly hobbled functionality.
So, if we want to integrate the two (ATM completely separate) interfaces, this will need a major refactoring/restructuring of both interfaces. We need to determine which components they have in common and can be shared, which are different and therefore must be defined/exposed separately on each side, and then create the respective client- and server-side and common modules.
Did my discussion of nomenclature and code organization help clear things up? It could be that you have currently added things directly into the server-specific interface that at least sort of duplicate things previously exposed in the other FreeOrion/python wrappers, but you might still want to keep those to enable the 'simple' scripting options you want to support. I have no idea what major refactoring/restructiring of the main FreeOrion/python wrappers or of the FreeOrion/AI interface you might be envisioning.
In principle that's a good idea, it surely would reduce some good amount of duplicate code, but to me that looks like a major project. Do you really want to take that on? I won't object, it's just that both of us already have a lot on our plate... ;)
Hocus, Pocus, Magic, Presto! The attached seems to do the basic job for me. There was one additional server compile reference necessary for PythonEmpireWrapper.cpp. The adjustment for the MSVC project looked straightforward so I made it; I left the xcode project alone.
Attachments

[The extension patch has been deactivated and can no longer be displayed.]

If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

User avatar
Vezzra
Release Manager, Design
Posts: 6095
Joined: Wed Nov 16, 2011 12:56 pm
Location: Sol III

Re: New starname clustering method, some questions

#8 Post by Vezzra »

Chriss wrote:Is there anything specific to the server side?
Yes, of course. Server-side Python scripts need to be able to manipulate the universe - creating systems, planets, ships, fleets; manipulating empires, species, specials etc. AI Python can't include any of this.

Chriss
Dyson Forest
Posts: 231
Joined: Sun May 11, 2008 10:50 am

Re: New starname clustering method, some questions

#9 Post by Chriss »

Sorry, I meant: is there documentation specific to the server side python interface? Apart from the code?
Attached patches are released under GPL 2.0 or later.

User avatar
Vezzra
Release Manager, Design
Posts: 6095
Joined: Wed Nov 16, 2011 12:56 pm
Location: Sol III

Re: New starname clustering method, some questions

#10 Post by Vezzra »

Chriss wrote:Sorry, I meant: is there documentation specific to the server side python interface? Apart from the code?
Oh sorry, should have read more carefully. No, there's no documentation to the server-side Python interface yet. It's of course on the todo list, because an interface without documentation can't really be effectively used, but I didn't get around to it yet.

The only "reference" currently existing are the universe generation scripts themselves. I've tried to put comments in there explaining what the code is supposed to do, maybe you can glance something from it. I can't tell much about the part doing the star system naming, this one has been written by Dilvish.

User avatar
Vezzra
Release Manager, Design
Posts: 6095
Joined: Wed Nov 16, 2011 12:56 pm
Location: Sol III

Re: New starname clustering method, some questions

#11 Post by Vezzra »

Dilvish wrote:My apologies, I did confuse something-- I had seen that PythonServer.cpp and PythonServerWrapper.cpp both had an include for PythonWrappers.h, which simply exposes WrapUniverseClasses(), WrapGalaxySetupData(), WrapGameStateEnums(), WrapEmpire() and WrapLogger(), and apparently I mistakenly assumed that all of those wrappers were then used instead of just some.
Well, looks like I've too been confused, in my case about the AI Python interface. :lol:
I'm not sure what you mean here by the term 'AI Python wrapper', but I'm pretty sure I would have a different meaning for it (explained more below).
Yeah, that cleared up a lot. Until now I thought that the entire Python interface (except the stuff I implemented when writing the Python interface for scripted universe generation) was designed solely with the AI in mind and therefore purely client-side. I had no idea that the thing already has been so cleanly separated into client specific and common stuff.

Which is freaking awesome, as it of course allows to incorporate the entire common part into the server-side interface far more easily. :D
I don't think that any of the FreeOrion/python wrappers reference anything from the FreeOrion/AI interface, and if they did have any client specific code (nothing comes to mind but there might be a small bit) then perhaps it should be moved to make a more clear distinction between the AI Python Interface, the Server Python Interface, and the underlying generic FO Python Interface that gets incorporated (at least in part) by both AI and Server.
That sounds like a decent plan. I just took a quick glance, and most of the stuff looks like it's not client specific. We might have to more thoroughly dig through the entire thing to see if there are things that need to be moved in or out of the common interface, but having the interface already set up with that separation certainly makes everything tremendously easier.

I think I did see some things in the Python AI specific interface, that could be moved to common, and there are things in common where I'm not sure how they work on the client or server side without having client-/server specific wrappers. So I might get back to you with maybe dumb questions during the next months ;)
Hmm, I think that making helper functions available so that some things can be done with this scripting in very simple ways is a fine idea, but I don't see how that means it needs to be restricted to only that. The whole point of this interface is to allow more complex scripting than FOCS will allow, and the whole point of the classes and whatnot is to help organize information and routines in ways that are easier to keep track of and use. If you entirely do away with the class exposures it seems to me that either you're going to wind up with much more complicated code or with significantly hobbled functionality.
Depends on how much you really can/need to employ the powers of OOP. As long as you're not deriving classes and overriding methods, I don't see any real gain working with classes and object references instead of ids and simple functions.

For example, from what I've seen, when querying a list of certain objects, lets say, all the empires, you need to pass a list of ids to Python. To get the actual objects, you need to call getter functions which you pass the ids. That's exactly what I want to prevent the content scripter to have to deal with. He shouldn't have to pay attention what type of object the empire reference he got is. He calls a function that provides him with a list of empires, and he can now work with the references in that list, without having to obtain the "real" references in a second step. Or keeping in mind which functions he needs to pass an id, and which take object references. I very much want to shield the content scripter from that. Judging by Mats comments, he has a hard time wrapping his brain around the universe generation code as it is, having to deal with details like integer ids versus objects is not going to help.

Using only ids and simple funtions also has the advantage of having a cleaner C++/Python interface. IMO passing around integers is less messy and tricky than passing around object/class instance references. As you've maybe seen when glancing at the current server-side interface, I tried to avoid passing around references to C++ class instances as much as I could. Even when passing lists or maps, I use the list and dict boost python containers, instead of creating a lot of custom classes with the indexing suite.

Now, having said all that, there might be good reasons to provide the full class interface to Python, as of course that allows you to do things that will not be possible otherwise. In that case, your idea of keeping the current set of functions of the server-side interface as helper functions for easier use is certainly a sound, viable option. However, it might be a better idea to implement these helper functions purely on the Python side, by that I mean wrappers for the API provided by the C++ side written in Python and encapsulated in a module that gets imported in the universe generation/turn events scripts.

The question is: Do we really need a full blown class interface on the Python side? What would get more complicated or impossible to do if we only worked with ids and a simple, procedural interface? You've done most of the AI scripting, I guess there's no one who is better fitted to answer that question. ;)
Did my discussion of nomenclature and code organization help clear things up?
Oh yes :D
It could be that you have currently added things directly into the server-specific interface that at least sort of duplicate things previously exposed in the other FreeOrion/python wrappers, but you might still want to keep those to enable the 'simple' scripting options you want to support.
See above, I think that's better done as a wrapper layer implemented in Python. I want to keep the interface as small as possible.
I have no idea what major refactoring/restructiring of the main FreeOrion/python wrappers or of the FreeOrion/AI interface you might be envisioning.
Well, what I envisioned is basically already done. I still wonder if a overhaul might be a good idea. There are a lot of things I don't know why they are done the way they're done. Maybe some things can be done simpler/cleaner? Some stuff looks quite complicated, I wonder if that is really necessary.

And, of course, inconsistent naming styles. That's definitely something that needs to be done, getting everything conform to PEP8 (as far as that's possible). It might be a good idea to temporarily provide all classes/functions/methods that don't conform to PEP8 with PEP8 compliant alternatives. This way newly written scripts can already use the PEP8 compliant class/function/whatever names, without breaking the existing scripts, which can be converted step by step, whenever one of us gets around to do a chunk.
Hocus, Pocus, Magic, Presto! The attached seems to do the basic job for me.
Dilvish the Warlock makes his entrance 8)

Yep, that worked straight out of the box, I just had to add PythonEmpireWrapper.cpp to the server build target in the Xcode project too. Have to test things a bit more thoroughly, but so far looks very promising.

User avatar
Dilvish
AI Lead and Programmer Emeritus
Posts: 4768
Joined: Sat Sep 22, 2012 6:25 pm

Re: New starname clustering method, some questions

#12 Post by Dilvish »

Vezzra wrote:Server-side Python scripts need to be able to manipulate the universe - creating systems, planets, ships, fleets; manipulating empires, species, specials etc. AI Python can't include any of this.
Well, "can't" might be a bit strong. Recall that the human client has to fall back on creating ships, assigning species to planets, etc, to accurately make certain predictions. That's all fine because it is simply manipulating its local universe copy, even when it uses the same code as the server does to manipulate the server's master copy of the universe. Right now the AI avoids doing such things by hardcoding some predictive calculations, which is obviously susceptible to divergence in the face of user mods (plus plain old AI programmer error :D ). So the actual number of functions that truly *need* to be restricted from the AI client is probably quite small, I think.
Vezzra wrote:I can't tell much about the part doing the star system naming, this one has been written by Dilvish.
Oh, right, the focus of the original post, hehe. Ok, Chriss, here's the basics for you. The thing you'll want to change is how the clustering is done. The main clustering routine is cluster_stars, and although it is slightly oriented towards the current euclidean distance clustering I don't think you'll actually have to change anything in it. It does pass around lists of system coords, and you wouldn't actually need the coords, you would just be working with the system indices, but for generality/consistency across different clustering methods I think you may as well keep passing the info in this format. Depending on how the clustering works out you might want to increase the number of convergence loops used in this routine, but that's optional and I think it would be the only change here.

One thing you will need to change is this line of assign_clusters so that it uses a least-jumps distance rather than a euclidean distance. For euclidean distance it was slightly computationally cheaper to work with distance squared, which is not the case for least-jumps, so you might want to rename that variable something more general. As for getting the least-jumps distance, there is a universe function that determines the whole n x n matrix for n systems, but I don't know if that's currently exposed. You could start start out by building it yourself from the neighbor information.

The other thing you would need to change is recalc_centers so that instead of doing a euclidean coordinate averaging within each cluster, it simply chooses a central one of the nodes within each cluster (the one with the min least-jumps dist to all the other nodes in that cluster).

I think that would do it.
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

Chriss
Dyson Forest
Posts: 231
Joined: Sun May 11, 2008 10:50 am

Re: New starname clustering method, some questions

#13 Post by Chriss »

The code is more or less readable as far as I've dug in. No issue as far as "what does this code do". The issue is typically with "what else is there" in terms of functionality. I found the function to get the neighbours by using "print dir(fo)" and looking at the log. It is just not as easy as an auto-complete IDE or dir() and type() in an interactive shell would be. Interactive shell, btw? Is that possible?

As far as the actual implementation goes, I haven't dug into all the clustering details yet. Yes, I thought that simply using another distance metric should do, but after the first glance I am not so sure any more. My first pass will probably be something like: mark all systems with more than n starlanes as centers, add all connected systems with 1 starlane to that center. Then see how that looks like and improve. That part should be a no brainer, but I am not sure yet what will work for all systems with more than 1 starlane.
Attached patches are released under GPL 2.0 or later.

User avatar
Vezzra
Release Manager, Design
Posts: 6095
Joined: Wed Nov 16, 2011 12:56 pm
Location: Sol III

Re: New starname clustering method, some questions

#14 Post by Vezzra »

Dilvish wrote:Well, "can't" might be a bit strong. Recall that the human client has to fall back on creating ships, assigning species to planets, etc, to accurately make certain predictions.
Well, yeah, you're right of course, but I guess there are still things that aren't present in the client interface (creating specials? moving around universe objects? creating star systems?).
So the actual number of functions that truly *need* to be restricted from the AI client is probably quite small, I think.
The smaller the better. More stuff that can go into the common interface. :D

User avatar
Vezzra
Release Manager, Design
Posts: 6095
Joined: Wed Nov 16, 2011 12:56 pm
Location: Sol III

Re: New starname clustering method, some questions

#15 Post by Vezzra »

Chriss wrote:Interactive shell, btw? Is that possible?
Maybe, but if, then I don't know how...

Post Reply