Wormholes, stargates, and AI

YAY I got my 3dmap.

yeah... did you know, that there is an entirely other post dedicated to that?

Alright I give! Please someone delete this post! I didn't see the other post, and I will add to that, thanks!

To give the geeky answer - this is a classic NP problem theoretically, though there's a fairly discrete limit for the game (e.g. how many discovered wormhole pairs the empire in question knows about).

You can't just do n+1. You also have to check every combination of TWO wormholes (if you're going from A to B, a wormhole near A may get you halfway and another near the first exit may get you near . And actually, you have to check every order of two wormholes - because going through one 'pair' and then the other is very different than going through them in opposite order. So it's every *permutation* of two wormholes.

But you also have to check every permutation of THREE wormholes, for the same reasons, and so on, until you've checked every arrangement of using EVERY known wormhole. Yes, you can prune a lot of these early (as soon as they get longer than the shortest path you've found so far). You can do even better, by building up pathfinding trees, etc. - this is basically the same problem *the internet has* for routing - there are an almost unlimited ways for two computers to route traffic between each other - how does the internet manage it?

Trust me, it's a hard, but very interesting, problem, classic computer science. I can understand the GC team declining to reimplement even a stripped-down version of BGP or OSPF. I think the problem is actually simple enough that you can solve it for the scope of the game, but I can understand them having higher priorities. It's something you might consider hiring a CS student intern to solve for you as a project - it's a well-bounded problem since you have some control of the conditions (e.g. how many end points are being considered, how many discovered wormhole pairs can exist, the fact that the travel costs vary in a predictable fashion, etc.).

MOO/MOO2-style stargates are easier (assuming only one empire can use them at a time). The wrinkle is that the ship has to check every turn to make sure any stargates it was planning on including are still in 'friendly' hands and recompute the course if one is lost or a faster route is possible because of a new/captured one.

I couldn't do this on the last CS test I had, but here goes....

The Internet does a lot of things to manage traffic. It is a big mesh of routing points so there are tons of ways to get from one end of the Internet to the other end. Each routing point disqualifies redundant links by selecting one of the shortest and this prunes the mesh of the Internet into an open shortest path first tree. There are other routing methods but this one seems to be the heart of the Internet.

We need the cost of getting from any one wormhole to any other. Call these links. The number of links is determined by the recursive formula:
N=wormholes=2 -> L=number of links=0 (trivial, no links)
N=4 -> L=number of links=4
N>4 -> L = (n-2)+number of links from next smaller N

The number of links needed is
N L
2 0
4 4
6 12
8 24
10 40
12 60
...

So galciv 2 has to setup a matrix of link costs. And, it has to have one for each computer controlled civ, because some civs won't know some wormholes.
Then every time a unit wants to move it has to perform a check of all permutations of wormholes n(n-1)(n-2)...(2)
Each check is going to assign a link cost of 1 for going thru a wormhole and a cost from the matrix for flying to the next wormhole in the permutation.
There are ways I can think to limit this search.
First, find the cost of flying straight to the destination, and whenever a cost goes above that, don't finish computing it.
Second, some CIVs aren't intelligent, and they may get frustrated after calculating beyond 2 jumps, or they may implement a no wormhole policy.
Third, let us turn off wormholes in the options in case we are running slow computers.
Fourth, limit the number of wormholes to something reasonable, like 6, even at the large galaxies. Make sure those wormholes go long distances so they are useful. Honestly, the chances of finding 3 working wormhole lanes in our galaxy???
Fifth, only perform the check on ships that need to move far...that counts out sentry ships and exploration ships that need to comb the galaxy sector by sector.

6 wormholes = 720 checks per ship using wormholes.
Please if I've done something wrong go ahead and tell me.

[quott] Honestly, the chances of finding 3 working wormhole lanes in our galaxy???
Scientificly speaking, somewhere between 0 and 100%!!!
Honestly, we do not know enough to say anything about that at the moment, as we do not know under what conditions they exist if they do exist. But the question is beside the point, almost all space game I know of uses ftl-travel, witch is at the moment consideres scientfically impossible, so lets yust keep discussing wormholes from a game-fun perspective.

Wormholes is not the way.

What we need is TDMs (Time Distortion Modules) that cost lots to research and build and can only be used in certain ships.

This device would fold the space/time plane so a man-made wormhole could be created.

Due to the cost and limitations a network of stargates could be cheaper.

Isn't that how the stargates worked? Folding the space-time plane so a man-made wormhole could be created.

Alternatively the the stargates may have worked by "hacking" the laws of physics and effectively rewriting them for a limited period of time sort of like "the distance between the Arcean homeworld and the Altarian homeworld is 300 lightyears, no it's 300 kilometres beacause I'm rewriting the rules that govern the universe". The immense cost of energy could come down to the need to force the universe to play by the man-made rules (300 km between Arcea and Altaria) rather than the god-made rules (300 lightyears between Altaria and Arcea) and combat the basic drive of the universe to return to how it is coded to behave.

In otherwords the stargate and hyperdrive functions are actually entirely supernatural and work by twisting the basic natural laws of distance and time to allow the completely impossable to become "possible" and the energy cost is the cost of forcing the universe to comply and keeping logic, order and "sanity" firmly under control. They're not wormholes beacause wormholes a feuture of the natural order following certain inherant laws, instead they are paradoxes that are both a wormhole and not a wormhole, possible and not possible, real and not real.