Arcen Games

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

Title: I'm having fun with GraphViz
Post 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)
Title: Re: I'm having fun with GraphViz
Post by: Pumpkin on November 08, 2015, 07:56:08 PM
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)
Title: Re: I'm having fun with GraphViz
Post by: Pumpkin on November 08, 2015, 08:09:58 PM
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)
Title: Re: I'm having fun with GraphViz
Post by: chemical_art on November 08, 2015, 10:21:59 PM
I find the "gravity" map really interesting!
Title: Re: I'm having fun with GraphViz
Post by: Draco18s on November 08, 2015, 11:04:43 PM
Cool stuff!
Title: Re: I'm having fun with GraphViz
Post by: Pumpkin on November 10, 2015, 05:12:58 AM
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 "rim-world" 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.
Title: Re: I'm having fun with GraphViz
Post by: Elestan on November 11, 2015, 09:59:14 AM
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".
Title: Re: I'm having fun with GraphViz
Post by: Pumpkin on November 27, 2015, 10:12:28 AM
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 fake-3D 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)
Title: Re: I'm having fun with GraphViz
Post by: ewokonfire on January 23, 2016, 11:07:24 PM
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.
Title: Re: I'm having fun with GraphViz
Post by: Pumpkin on February 06, 2016, 03:40:03 PM
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.
Title: Re: I'm having fun with GraphViz
Post by: Pumpkin on February 15, 2016, 06:48:21 PM
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 math-hater folks out there, let just say that the graph is child play to define (just a tiny bit harder than the grid) but a trigo-nightmare 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!
Title: Re: I'm having fun with GraphViz
Post by: Pumpkin on April 24, 2016, 09:31:52 PM
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 (dead-ends) sprouting out here and there, but it also has loops, which is great for a map to explore. It's also (likely) non-planar (though I believe this one is planar...). Anyway, sounds non-trivial enough. The algo is ridiculously simple, though. (Same old link (http://gardn.fr/algo/graph/).)
Title: Re: I'm having fun with GraphViz
Post by: Pumpkin on May 04, 2016, 01:42:08 PM
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 side-planets 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.
Title: Re: I'm having fun with GraphViz
Post by: Pumpkin on May 04, 2016, 01:54:26 PM
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.
Title: Re: I'm having fun with GraphViz
Post by: tombik on May 04, 2016, 03:33:26 PM
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 "rim-world" 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.
Title: Re: I'm having fun with GraphViz
Post by: Pumpkin on May 05, 2016, 04:35:59 AM
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:
Quote
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?
Title: Re: I'm having fun with GraphViz
Post by: tombik on May 09, 2016, 09:58:59 AM
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.
Title: Re: I'm having fun with GraphViz
Post by: Pumpkin on May 10, 2016, 03:24:06 AM
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 messy-funny math-thingy.

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.
Quote
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 non-connected 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?
Title: Re: I'm having fun with GraphViz
Post by: tombik on May 10, 2016, 11:08:15 AM
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.
Title: Re: I'm having fun with GraphViz
Post by: Pumpkin on May 10, 2016, 01:57:06 PM
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 CPU-expensive. 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.
Title: Re: I'm having fun with GraphViz
Post by: tombik on May 10, 2016, 07:10:51 PM
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 CPU-expensive. 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.
Title: Re: I'm having fun with GraphViz
Post by: Draco18s on May 11, 2016, 12:06:13 PM
You may also be interested in Minimal Spanning Trees (https://en.wikipedia.org/wiki/Minimum_spanning_tree).
Title: Re: I'm having fun with GraphViz
Post by: Pumpkin on May 12, 2016, 05:31:22 AM
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.
Title: Re: I'm having fun with GraphViz
Post by: Draco18s on May 12, 2016, 12:38:19 PM
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.
Title: Re: I'm having fun with GraphViz
Post by: Pumpkin on May 31, 2016, 02:38:24 AM
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?