FreeOrion

Since we're not quite sure how starlanes would effect the game (we might be lowering the offroad-starlane ratio, there's been much discussion on this in the starlane thread)

It might be better to have the matrix express estimated travel time instead of number of hops.

_________________
Empire Team Lead

I couldn't agree with you more, unfortunetly... The way an adjacency matrix works is it takes the pathways from one node to another and calculates the number of possible hops of n between those two nodes. Adjacency matricies are used primarilly in network theory and most internet routers use them. They are good because it assumes that a hop of 2 is going to be shorter than a hop of 4. And its VERY easy math to figure out how far away (and thus what type of threat it is) a node is. I'm think that in our universe of having the starlanes connect only the 3-5 closest stars that if there is a shorter path the AI won't care at least not until v.7 or so.

A--------------------------------------------B = 1 hop

A--------C----------D----------------------B = 3 hops

In most cases A directly to B will be shorter than the other. However as the AI code matures i'm sure we can put some exceptions and other considerations to help "optimize" the AI.

_________________
Aquitaine is my Hero....

Good!

I will more or less mirror the C++ interface, with Python-constructs used where useful. For example, instead of getting the start-iterator for TechManager, you will use I would appreciate feedback, so just tell me how you want things to be.

Well, the thing is, if we allow offroad travel, which we probably will, then the graph is actually going to be fully connected, in other words, you can get anywhere from anywhere else in some finite amount of time.
(Unlike in a network where you can only go along the graph edges)

If you just do a breadth-first search of the starlane graph to calculate node distances, you're going to misjudge the threat levels of nodes where going offroad is faster than going via starlane.

Also, if we have anything like downgrading/upgrading of starlanes (like MOO3 was going to originally), then you've got to deal with weighted edges, in which case, a path of more hops might be shorter.

That's why you're probably going to want minimum travel time instead of just number of starlane hops. This can still be done in an adjacency matrix. It'd just be different data stored for each pair.

_________________
Empire Team Lead

I think the best way is allow the player to plot out their trajectory and have the game return an estimated time. They just drag a line between two points for their trajectory. Maybe a left click drag to get an estimate and release to confirm with shift button to set rally points and cancel by reversing the order.In terms of gameplay the minimunm path doesn't mean the best path as the player might run into another worlds colonize by another player. They may want to got offroad to avoid interception. I say just let the player decide. I don't think we want a remake of moo3

Is the galaxy generated on a grid? Because then it should be easy. When starlanes are generate, you have the coordinates so you can easily find the time estimate with or without tech bonus since you also have all the coordinates of non-starlanes and non-wormholes. Grids also make specicals like location of nebula, and other effect easy to take into account latter on. For the sake of user simplicity you may the points near a star to count as part of the star so the player won't have a hard time clicking onto a star. This grid method should make the galaxy independent of what ppl decide about starlanes, tech, special terrain effects...

Fleets should have also have the option of floating in space to serve like an sensor outpost.

As far as AI is concerned, I have suggested that fleets and planet have a number that measures strength/value. This value should help the AI and players. The AI can chart a course around a high strength fleet to attack a high value planet. The charting can be done like use starlane controlled by friendly force and go directly to intended target if system linking to targe has strength > your fleet strength else go through the system linking to target.

_________________

Since v0.1 has no starlanes, for now just rely on absolute distances between stars. In the future, we will have a graph that represents all the starlane paths, and a matrix with both the absolute and the stalane distances between systems. The graph will use A* /Dijkstra's algorithm to determine paths. All of this functionality can be exposed to Python, but don't bother implementing it in Python.

Just to let you know: I'm still alive. I'm learning for my final exams, therefore I don't have time to work on Python. Expect no progress until November