Arcen Games
Games => AI War Classic => AI War Classic  Mods & Modding => Topic started by: Pumpkin on November 08, 2015, 07:26:25 PM

Hey, folks. I recently found GraphViz (http://www.graphviz.org/), aka "graph visualizer", and I'm actually having fun experimenting and building some AI War's maps with it (and with some perl scripts behind).
I updated my old map styles suggestions with images (here (https://arcengames.com/mantisbt/view.php?id=17780), here (https://arcengames.com/mantisbt/view.php?id=16415) and here (https://arcengames.com/mantisbt/view.php?id=16142)) and dedicated a page of my site to it (here (http://gardn.fr/algo/graph/)).
I'm searching some cool ideas. And I bet you folks can help. Is there a map style you always wished for? Have you ideas of strange forms a galaxy may have (something like wheel)? Or maybe ideas of strategies that would be easier or challenged by some exotic map styles?
I'm quite found of this kind of map and I can't wait to play AI War on it:
(http://gardn.fr/algo/graph/rimworld_12_0.25.png)

New idea: gravity! The more the planets are near the middle of the galaxy, the more they're near each other, the more they're connected to each other, like if there is a big black hole in the middle. However, I'm not totally sure I'm willing to play in this kind of galaxy. Must be !!fun!!, though.
(http://gardn.fr/algo/graph/gravity.png)

Okay, a last one before I go to bed. (Man, I'm sooo tired... I shouldn't do this that late.)
The idea is to build a tree and connect all the leaves in a circle.
Y'know, I don't like "encapsulated" too much. However, I felt there was something to do with that "encapsulated" idea.
(http://gardn.fr/algo/graph/circletree.png)

I find the "gravity" map really interesting!

Cool stuff!

I want to share something. It's a rule to follow for easily designing a graph "in one piece". (I wasn't able to find the exact English term for that. The French term is "connexe".)
The rule is:
Each planet must have at least one link toward a following planet.
or
Each planet must have at least one link toward a previous planet.
So if this rule is respected, the graph will be "in one piece".
* * *
As I didn't find this rule, I'll try to prove it.
1) If all previous planets are "in one piece" (alternatively: if all following planets will be "in one piece"), then linking the current planet to any of them at least once will keep the graph "in one piece".
2) The first planet alone is a graph "in one piece" (alternatively: the last planet will be a graph "in one piece").
3) If the first (alternatively: last) state respect the property ("in one piece"), and each step applied to a state where the property is respected keep the property true, then the property will always be true even after an infinite number of steps.
* * *
And that, folks, was my first mathematical demonstration in English. Wohoo! Please be nice with the shaky formulation.
However, the "forward" version of the proof should be inconsistent, because it says "will be a graph in one piece". If someone can come up with a better proof for the forward version, it would be amazing. But maybe this kind of rule&proof have already been made by some true mathematician.
Also, always branching in the same direction (always forward or always backward) is an easy rule for not creating two edges between the two same planets.
The idea behind this rule is to loop through all the planets and give them link to previous or following planets, and varying some parameters depending on the planet's number. For instance, I made the "gravity" galaxy with this rule and a decreasing branching factor (the probability for a planet to have many links). This mean that low rank planets end with many links and stack in the middle, while high rank planets form few links and end in the outside of the galaxy. The last planets are dead ends because nobody links to them.
The "rimworld" galaxy was this rule plus a range: each planet can only be linked to planets that are at most N ranks higher. And if higher is more than the total size of the galaxy (80, for instance), I use a modulo to make it loop to the beginning, creating a grand circle.
I'll try to make a "natural" clustered galaxy with a modulo: each planet has more chance to link to planets in the same modulo than itself. Let's see how it works.

I wasn't able to find the exact English term for that. The French term is "connexe".
I believe this is called a "Connected Graph".

Well. The "natural" cluster algo turned out to be more complicated than I thought in the first place.
Meanwhile, I came up with and worked out the "cube" map style.
I had ideas of Arcen releasing some real 3D maps in the future AIW2, but, heh, be real. It would be too difficult for a too little improvement. (But just for a moment, imagine a map that you can grab and turn and watch around! Realistic as they currently are would be so interesting to consider as 3D maps! And imagine all the awesome possibilities for cool 3D map style! Sphere, torus, hollow complex structures, etc!)
Well, stop dreaming. However, simple fake3D maps can easily be achieved. Once again, the perl program that produced this is available on my website. Enjoy!
(http://gardn.fr/algo/graph/cube.png)

Just as a curiosity, are you able to do one where each possible pair of planets simply has the same % chance to be connected? It would probably need some untangling to be even remotely readable, but I'd like to see how it would look.

Just as a curiosity, are you able to do one where each possible pair of planets simply has the same % chance to be connected? It would probably need some untangling to be even remotely readable, but I'd like to see how it would look.
Well, it won't work. It's an interesting idea, but it won't work. At least the code is small and easy to write. The main problem is that there is no guarantee that the graph will be in one piece. Also, the result might be too much linked and unplayable (at least not fun ; go play on lattice for something both !!fun!! and playable). See the last chapter in my site's page (here (http://gardn.fr/algo/graph/)) for code and details.
Here are the results.
(http://gardn.fr/algo/graph/purerand_0_05.png) (http://gardn.fr/algo/graph/purerand_0_01.png)
Anyway, I'm always happy to hear comments and ideas.

One I wanted to do a long while ago. I finally managed to bring back my dusty trigonometry skill and displayed the Torus. For the mathhater folks out there, let just say that the graph is child play to define (just a tiny bit harder than the grid) but a trigonightmare to display in 2D.
I can't wait to play on this kind of map!!! :D
(http://gardn.fr/algo/graph/torus_12_6.png) (http://gardn.fr/algo/graph/torus_12_7.png)
Enjoy!

I'm still waking up at night with ideas for a graph. ><
(http://gardn.fr/algo/graph/looptree.png)
I like this one. For a part it has the look of a tree: narrow, long branches and leaves (deadends) sprouting out here and there, but it also has loops, which is great for a map to explore. It's also (likely) nonplanar (though I believe this one is planar...). Anyway, sounds nontrivial enough. The algo is ridiculously simple, though. (Same old link (http://gardn.fr/algo/graph/).)

I'm slowly gaining ground toward the second page for this thread... Some more ideas and it'll be 2 pages! Yay!
A twist on the Snake map style, with "legs". The intent is to create a linear path, like with the Snake, but with optional sideplanets to capture or ignore.
(http://gardn.fr/algo/graph/centipede.png) (http://gardn.fr/algo/graph/centripede.png) (http://gardn.fr/algo/graph/full_centipede.png)
From left to right:
 Between 0 and 2 "legs" per planet.
 Between 0 and 3 "legs" makes the "snake" shorter.
 Always 2 "legs".
I must improve the code to allow two parameters: maximum number of "legs" per planet and chances for each "leg" to not appear.

While I was thinking about "alternate" snakes...
(http://gardn.fr/algo/graph/ladder.png)
Nothing fancy. I don't know why neato makes little wrinkles here and there, though.

I want to share something. It's a rule to follow for easily designing a graph "in one piece". (I wasn't able to find the exact English term for that. The French term is "connexe".)
The rule is:
Each planet must have at least one link toward a following planet.
or
Each planet must have at least one link toward a previous planet.
So if this rule is respected, the graph will be "in one piece".
* * *
As I didn't find this rule, I'll try to prove it.
1) If all previous planets are "in one piece" (alternatively: if all following planets will be "in one piece"), then linking the current planet to any of them at least once will keep the graph "in one piece".
2) The first planet alone is a graph "in one piece" (alternatively: the last planet will be a graph "in one piece").
3) If the first (alternatively: last) state respect the property ("in one piece"), and each step applied to a state where the property is respected keep the property true, then the property will always be true even after an infinite number of steps.
* * *
And that, folks, was my first mathematical demonstration in English. Wohoo! Please be nice with the shaky formulation.
However, the "forward" version of the proof should be inconsistent, because it says "will be a graph in one piece". If someone can come up with a better proof for the forward version, it would be amazing. But maybe this kind of rule&proof have already been made by some true mathematician.
Also, always branching in the same direction (always forward or always backward) is an easy rule for not creating two edges between the two same planets.
The idea behind this rule is to loop through all the planets and give them link to previous or following planets, and varying some parameters depending on the planet's number. For instance, I made the "gravity" galaxy with this rule and a decreasing branching factor (the probability for a planet to have many links). This mean that low rank planets end with many links and stack in the middle, while high rank planets form few links and end in the outside of the galaxy. The last planets are dead ends because nobody links to them.
The "rimworld" galaxy was this rule plus a range: each planet can only be linked to planets that are at most N ranks higher. And if higher is more than the total size of the galaxy (80, for instance), I use a modulo to make it loop to the beginning, creating a grand circle.
I'll try to make a "natural" clustered galaxy with a modulo: each planet has more chance to link to planets in the same modulo than itself. Let's see how it works.
Can you try to refine what you are trying to prove here, I got some lessons on graph theory, so I might possibly be of help, but could not get what you are trying to prove.
Btw, the word you were looking for is connectedness.

Btw, the word you were looking for is connectedness.
Thanks a lot!
I (...) could not get what you are trying to prove.
I was trying to prove that my way to build a fully connected graph ("in one piece") actually and always makes a fully connected graph.
That way was:
1) start with a graph of 1 vertex;
2) each time you add a new vertex, link it at least once with a previously existing vertex.
The proof this method always produce a fully connected graph is recursive:
1) If all previous planets are "in one piece" (alternatively: if all following planets will be "in one piece"), then linking the current planet to any of them at least once will keep the graph "in one piece".
2) The first planet alone is a graph "in one piece" (alternatively: the last planet will be a graph "in one piece").
3) If the first (alternatively: last) state respect the property ("in one piece"), and each step applied to a state where the property is respected keep the property true, then the property will always be true even after an infinite number of steps.
Did that answer your question? Or haven't I understood the question?

https://en.wikipedia.org/wiki/Connectivity_(graph_theory)#Connected_graph
This will definitely help you to come up with the definition which you will need for your argument.
The "rule" you defined there is not exactly a rule. I had some problems with your approach.
For example, In 3, you say "alternatively last" after an infinite number of steps, which is a bit problematic.
In 2, you say a single point is a connected graph, but for an algorithm, you dont need this. Just produce any two connected nodes, and build upon it.
First one just says this: "You can't make a connected graph not connected by adding new vertexes." This is trivially true already.
I dont know about GraphViz, so I dont know what exactly you need, but if I were to code these things, I would just produce a fully connected graph with every possible vertex included, and erase the vertices one by one.

Woah, okay, things just get out of my hands. Sorry about the confusion I created. I was far from expecting such a precise answer with my little messyfunny maththingy.
First and foremost, I'm totally fine: I'm not trying hard to achieve anything and I need nothing for my script code. I was just having fun trying to come up with a mathematical proof that this algorithm works (actually creates a connected graph).
For example, In 3, you say "alternatively last" after an infinite number of steps, which is a bit problematic.
Yeah, sure. Forget "infinite", just "any number of step", cause, sure, you need a "last" step of course.
First one just says this: "You can't make a connected graph not connected by adding new vertexes."
That's a very concise definition, indeed. GG to you.
This is trivially true already.
That, however, is personal. While I totally agree with it, I don't feel getting away with "bah, it's trivial" is a good attitude. Well, being AIW players, we can't be put off by the perspective of challenge, can we?
But, yeah. Your oneliner is good. I would just be a little more nitpicking (I think it's only fair :P) and add "... by adding one new vertex linked to at least one other (previously created so part of the connected graph) vertex". Then, by adding multiple vertices, one at a time, each respecting this condition, the graph will still be connected after an infinite any number of steps added vertices. (Because, clearly, I can add multiple vertices to a connected graph that would produce a nonconnected graph: by putting them aside, linked with no vertices.)
if I were to code these things, I would just produce a fully connected graph with every possible vertex included, and erase the vertices one by one.
Did you meant "with every possible edges included, and erase edges one by one"? Because there is no "every possible vertices" (at least it doesn't seem to be a finite number).
Even so, would you check if the graph is still connected after each edge removal, and step back if it's not any more? That sounds like a lot of computational overhead. And how would you stop? When reaching a target number of edges?
I don't understand that last sentence. Would you explain it further, please?

Did you meant "with every possible edges included, and erase edges one by one"? Because there is no "every possible vertices" (at least it doesn't seem to be a finite number).
Even so, would you check if the graph is still connected after each edge removal, and step back if it's not any more? That sounds like a lot of computational overhead. And how would you stop? When reaching a target number of edges?
I don't understand that last sentence. Would you explain it further, please?
Yes, a fully connected graph means that. For a constant number of nodes, number of possible vertices is finite, and it is combinatorial of n with 2. And yes, you need a control code for connectedness, and yes, you can define it after "k" erasings or something.
But after a second thought, I dont think my way is superior than your way. It really depends on what you are trying to achieve, and in maps for AIW, your way would be superior. Sorry about that.
Here is how to deal with connectedness. You should use some search algorithms to check that whether you can reach every possible point. To do this, you need to "color" them, like "visited but not all neighbours visited" "not visited" "visited, and all neighbours are visited". If for any step, you are in a position where every visited one has also their neighbours visited, but there are also some unvisited ones, then the graph is unconnected.
Other way to deal with the connectedness is to extract adjacency matrix. This matrix just consists of 0s and 1s, and shows that whether there is any direct link between the relevant column (ith point) and relevant row (jth point). First degree of this shows all connected points of course. If you take square of it, you will get positive values for all two points that could be reached by going two steps. If you take cube of this matrix, you will get positive values in the cells that represent points that could be reached via 3 steps. And so on. So, if you check adjacency matrix's power up to number of nodes, and find that there are some zeros in some specific cells in each of those powers, then this means, there are some points that cant be reached from one to other no matter how many steps you are using, and that means graph is unconnected.
I hope that helps.

At least one of us is wrong on the use of the word "vertex". I believe vertex = node, and not vertex = edge.
Anyway, your way of checking the connectiveness of a graph with the successive powers of a matrix is very interesting.
However my goal was to create scripts that build connected graphs without the need of connectiveness checking. Hence the little proof. I believe even that smart matrix thing is a bit CPUexpensive. But maybe I'm wrong and with that it wouldn't be a problem checking connectiveness even once per removed edge.
Anyway, making scripts that always produce connected graph without the need of checking is a very interesting challenge.

At least one of us is wrong on the use of the word "vertex". I believe vertex = node, and not vertex = edge.
Anyway, your way of checking the connectiveness of a graph with the successive powers of a matrix is very interesting.
However my goal was to create scripts that build connected graphs without the need of connectiveness checking. Hence the little proof. I believe even that smart matrix thing is a bit CPUexpensive. But maybe I'm wrong and with that it wouldn't be a problem checking connectiveness even once per removed edge.
Anyway, making scripts that always produce connected graph without the need of checking is a very interesting challenge.
You are the one that uses it correctly, I just checked.
I see what you are trying to achieve, but if you dont go with some randomness, every algorithm which you try to write would produce look alike maps, that is why I tried to convince you that some connectedness checking is required.
Anyways, here is an algorithm that will give you the thing you want.
1) Draw two points, and connect them. Name the set of connected points as P.
2) Draw an additional point. Connect it to some random member of P. After connection, include this point in P.
3) Repeat step 2 as many times as you wanted.
4) If you want more ways to go from one point to the other, you can add just some random edges between the points.

You may also be interested in Minimal Spanning Trees (https://en.wikipedia.org/wiki/Minimum_spanning_tree).

You may also be interested in Minimal Spanning Trees (https://en.wikipedia.org/wiki/Minimum_spanning_tree).
Sure. However trees are only one kind of map (and not the most interesting, IMO). I'm personally more interested in exotic map design.
However, there are very cool things in the field of graph theory, even if they're not interesting for the very particular AIW's map generation.

Sure. However trees are only one kind of map (and not the most interesting, IMO). I'm personally more interested in exotic map design.
Ah, but you can start with a MST and then modify it, adding extra random links, etc.

Oh, I was just thinking about a little idea about AIW2, so I write it down here.
I think it would be nice to have "statistics" about the currently displayed galaxy in the lobby, like the exact number of planets, the total number of wormholes (number of edges x2) and the average number of wormholes per planet (nb_wormhole/nb_planets). I can't think of other interesting stats to display about graph; my math knowledge ends here. Someone?