|
|
looks aplicable, a thing I note about this setup is that no dead-ends exist, or even can exist afaik. edit: Yes, I see how that can occur, and how it is unlikely. That removes my only concern about the layout, I am all for it. |
|
|
Judging by the graph on its Wiki-page, it should be possible (but unlikely) for dead-ends to exist. By removing the node just right of the most bottom-left node, it should become a dead-end. Unless I misunderstood the implementation of the graph. All in all though, I'm definitely in favor of this map-type. |
|
|
gabrieltest_1.png (19,165 bytes) |
|
|
gabrieltest_2.png (20,002 bytes) |
|
|
Indeed, it is possible to have dead ends in a Gabriel Graph, though normally only on the periphery of the clusters. I wrote up a short MATLAB script to generate some random graphs and I've posted a couple examples with 80 nodes. You can see that straight random generation creates highly-connected maps without intersections, though without game experience I can't say what the in-game implications are. |
|
|
I was revving up on yet another why-we-can't-do-graph-untangling post when I realized that you were just proposing another map style, which is definitely fair game :) This one looks cool (as does clusters), I'd certainly like to give it a shot. Anyway: - New map styles only get added in new expansions, so it will be a while. - Can someone point me to a description of how to build these maps? - Would there be any copyright issues if we called this the "Gabriel" map type in-game? Would there be any copyright issues with using the method in general? Thanks! |
|
|
I think http://en.wikipedia.org/wiki/Gabriel_graph should answer all those questions, Keith. From what I gathered, it should be free game to call it a Gabriel map, but I can't say for sure. |
|
|
In my opinion, the more map types the better, everyone can pick a layout that suits them, though this does seem more like a replacement of the Simple/Realistic layout to make it more visually pleasing (which I understand is the point) rather than a new one in itself. |
|
|
Well, the Gabriel graph differs from Simple, Realistic, and Lattice in that the connections it makes are regular throughout the map, limiting the number of bottlenecks and giving a highly-connected system. And unlike Grid and Crosshatch, you have randomness to provide more variety in generation. I think that these two effects distinguish the Gabriel graph enough, and I'd love to see it in a future expansion along with Cluster. (I'd also like to see a cleanup of the Tree, Spokes, Snake, and Vines generation algorithms so that they don't look as deceptively complex as they currently do, but that's a whole 'nother issue.) To answer Keith's questions, I don't think there'll be a problem with using the Gabriel graph name. I wanted to submit this suggestion with a different name, leaving Gabriel graph in the description (much like how the Maze styles cite their generation algorithms), but couldn't think of a catchy, descriptive title. As for generation, even the slowest reasonable algorithms should work well, since there are at most 120 nodes to compute. If you have N nodes, generate a NxN squared distance matrix, where each cell has the squared distance between the row and column nodes. To check if edge A-B is in the Gabriel graph, sum rows A and B. If all the sums are greater than the value of cell A-B (except for the columns that correspond to A or B, which will equal that value), then edge A-B is in the Gabriel graph; otherwise not. It may not be the fastest algorithm, but it should be good enough. |
|
|
Bump for this, which never made it past "new", ahead of the upcoming expansion. As Zephilinox said above, the more map types, the better. |
- Anonymous
