Author Topic: I'm having fun with GraphViz  (Read 5090 times)

Offline Pumpkin

  • Hero Member Mark III
  • *****
  • Posts: 1,200
  • Neinzul Gardener Enclave
I'm having fun with GraphViz
« on: November 08, 2015, 07:26:25 PM »
Hey, folks. I recently found GraphViz, 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, here and here) and dedicated a page of my site to it (here).
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:
Please excuse my english: I'm not a native speaker. Don't hesitate to correct me.

Offline Pumpkin

  • Hero Member Mark III
  • *****
  • Posts: 1,200
  • Neinzul Gardener Enclave
Re: I'm having fun with GraphViz
« Reply #1 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.

Please excuse my english: I'm not a native speaker. Don't hesitate to correct me.

Offline Pumpkin

  • Hero Member Mark III
  • *****
  • Posts: 1,200
  • Neinzul Gardener Enclave
Re: I'm having fun with GraphViz
« Reply #2 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.

Please excuse my english: I'm not a native speaker. Don't hesitate to correct me.

Offline chemical_art

  • Core Member Mark IV
  • *****
  • Posts: 3,952
  • Fabulous
Re: I'm having fun with GraphViz
« Reply #3 on: November 08, 2015, 10:21:59 PM »
I find the "gravity" map really interesting!
Life is short. Have fun.

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,107
Re: I'm having fun with GraphViz
« Reply #4 on: November 08, 2015, 11:04:43 PM »
Cool stuff!

Offline Pumpkin

  • Hero Member Mark III
  • *****
  • Posts: 1,200
  • Neinzul Gardener Enclave
Re: I'm having fun with GraphViz
« Reply #5 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.
Please excuse my english: I'm not a native speaker. Don't hesitate to correct me.

Offline Elestan

  • Full Member Mark II
  • ***
  • Posts: 157
Re: I'm having fun with GraphViz
« Reply #6 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".

Offline Pumpkin

  • Hero Member Mark III
  • *****
  • Posts: 1,200
  • Neinzul Gardener Enclave
Re: I'm having fun with GraphViz
« Reply #7 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!

Please excuse my english: I'm not a native speaker. Don't hesitate to correct me.

Offline ewokonfire

  • Newbie Mark III
  • *
  • Posts: 25
Re: I'm having fun with GraphViz
« Reply #8 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.

Offline Pumpkin

  • Hero Member Mark III
  • *****
  • Posts: 1,200
  • Neinzul Gardener Enclave
Re: I'm having fun with GraphViz
« Reply #9 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) for code and details.

Here are the results.


Anyway, I'm always happy to hear comments and ideas.
Please excuse my english: I'm not a native speaker. Don't hesitate to correct me.

Offline Pumpkin

  • Hero Member Mark III
  • *****
  • Posts: 1,200
  • Neinzul Gardener Enclave
Re: I'm having fun with GraphViz
« Reply #10 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



Enjoy!
Please excuse my english: I'm not a native speaker. Don't hesitate to correct me.

Offline Pumpkin

  • Hero Member Mark III
  • *****
  • Posts: 1,200
  • Neinzul Gardener Enclave
Re: I'm having fun with GraphViz
« Reply #11 on: April 24, 2016, 09:31:52 PM »
I'm still waking up at night with ideas for a graph. ><



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.)
Please excuse my english: I'm not a native speaker. Don't hesitate to correct me.

Offline Pumpkin

  • Hero Member Mark III
  • *****
  • Posts: 1,200
  • Neinzul Gardener Enclave
Re: I'm having fun with GraphViz
« Reply #12 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.



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.
Please excuse my english: I'm not a native speaker. Don't hesitate to correct me.

Offline Pumpkin

  • Hero Member Mark III
  • *****
  • Posts: 1,200
  • Neinzul Gardener Enclave
Re: I'm having fun with GraphViz
« Reply #13 on: May 04, 2016, 01:54:26 PM »
While I was thinking about "alternate" snakes...



Nothing fancy. I don't know why neato makes little wrinkles here and there, though.
Please excuse my english: I'm not a native speaker. Don't hesitate to correct me.

Offline tombik

  • Full Member Mark II
  • ***
  • Posts: 171
Re: I'm having fun with GraphViz
« Reply #14 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.