IEEE Transactions on Games is looking for a few more Associate Editors

[Julian Togelius]

Hi all,

ToG is seeing an increase in submissions, and is therefore looking for
a few new Associate Editors. AEs are generally senior researchers
within the games field that want to contribute to the field by helping
to run our flagship publication venue. If you are interested in
serving as Associate Editor (warning: there's a bunch of work and not
much reward), please fill out this form:

https://forms.gle/MAqLyedUSj67fuy29

It is expected that going forward, the database populated by this form
will be used when selecting new AEs to invite.

Julian

--
Julian Togelius
Associate Professor, New York University
Department of Computer Science and Engineering
Editor-in-Chief, IEEE Transactions on Games
jul...@togelius.com | http://julian.togelius.com

[Ian Badcoe]

Hi all,

I've got four days allocated by my Sumo Digital for "learning" and I've chosen to do some research around my long-term interest in PGC...

Obviously that's not a huge total amount of time, so I need to focus quite sharply.

I have always thought that graph rewrites were an underexplored area.  I have in the past, for example, in this group discussed transforms a village represented by a connected subgraph being transformed into a "walled village" by inserting wall and/or gate nodes on all the edges connecting it to the main graph.

Similarly a mountain pass might be injected by identifying two subgraphs for adjoining mountains and inserting nodes on all edges that bridge between them.

An additional refinement might be to add edges between inserted nodes, say to represent the track running up the pass. 

I always assumed that that sort of topological rewrite would be something well understood in graph theory, but when I asked/searched in the past I did not have much luck...

Since time is limited, I thought I would focus on only the graph generation and not the following layout into space/geometry, although I think simple topological constraints on the rewrites can be used to ensure that if we start with a graph that can be laid out (say in 2D) then the rewritten graph will also have that property.  If this works then some simple layout tool + manual annotation might serve to illustrate the general idea. 

My first day on this is tomorrow, I should have asked last week, I know, but busy busy busy...

Any and all suggestions gladly received.  I do not have an academic institution's access to non-free resources (although I do have a friend who might look up a reasonable number of things for me...) but any information on:

- existing work in the area (or adjoining)

- relevant terminology (which may account for not finding things in the past, jargon's a killer...)

- useful articles (ideally freely accessible)

- anything else you might think relevant

I will share results, if significant, back here...

For anyone wondering who I am, I was active on here a few decades back, but I have been busy.  I currently work for Sumo Digital and the last release I was involved in was: Sackboy: A Big Adventure

Sackboy: A Big Adventure Sackboy: A Big Adventure is a platform game. Unlike previous LittleBigPlanet entries with 2.5D platforming, it f...

Regards,

Ian

[Joris Dormans]

Hi Ian,

In my experience moving between models that do and do not represent a topology and those that do not is one of the tougher nuts to crack.

But also one that is very important as ultimately you need a topology to represent a level while things like narrative, pacing, and mission structure are frequently better expressed with graphs that are not necessarily topological.

In the past I have used the following approaches to deal with this issue:

- Voronoi diagrams have a nice topological structure and can be treated as graphs to a certain extend. They are an interesting middle ground. What I frequently do is use a Voronoi diagram as a basic seed for a graph. The nodes in that graph that correspond to the cells in the Voronoi cannot change, but additional nodes and edges can be used to extend that original graphs to represent things in the cells or characteristics of the cells.

- Something similar can be done with tile maps, where each tile can be represent as a node in a graph connected to its neighbors.

- Sometimes a graph representing a mission can be transformed into a set of instructions that can be used to build topological space that can accommodate that mission.

- In the past I have also used auto layout techniques for graphs and use them to create tilemaps, but that never seemed to work well for me.

- I have also tried to generate a Voronoi diagram and search for a subgraph within that matches the structure of a mission graph I generated, but I never got that to perform very well.

In Unexplored 1 and 2 (which I know you are familiar with) I move back and forth between such structures during the generation process all the time. Currently my level generation first builds a simple tilemap to represent a basic spatial sketch, it extrapolates a graph from that outline so each individual node in that graph can be linked to specific locations. A mission is generated by extending that graph. And the extension is used to trigger transformations in the orginal tilemap. For world generation I do something very similar but I start from a Voronoi diagram, and build the mission graph extension on top of that. In the latter case the graph representing that mission is far less elaborate anyway.

I hope that helps!

Best,

Joris 

--

---
You received this message because you are subscribed to the Google Groups "Procedural Content Generation" group.
To unsubscribe from this group and stop receiving emails from it, send an email to proceduralcont...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/proceduralcontent/63565822.6358792.1625753214536%40mail.yahoo.com.

[Ian Badcoe]

Thanks Joris this is very good input, although given my 4 days I think I may avoid much of the complexity simply by "not getting that far" but it is all worth bearing in mind...

Voronoi is a good thought, or I even wondered about something simpler than that with just rectangular areas that are annotated about neighbour information (maybe this is like your high-level tile map?)  One might tag the edge between adjoining areas with things like "passable", "transparent" or "one way" (although I seem to recall the presence of the latter makes things complex very quickly, e.g. whether one-way edges make an invalid map is essentially a distributed, rather than a local property, but I think if one-ways are always of only local significance, then they can be embedded in a fully traversable "master graph" without breaking it...

The map<->mission linkage is another very good point.  Again I have always been surprised how rapidly a meaningful map reaches a point there it can only continue to be understood if it is implying some aspects of "mission".  Even the one-way edges I mentioned above imply simple aspects of story: "but the player could not return that way and so he had to..."

Maybe a good bit of background on this would be to play some Unexplored 1 and 2 :-)  On the other hand I might do that in my own time, since the work time available is quite limited...

--

All this contrasts with the other approach which has always appealed to me, which is the natural evolution or "Dwarf Fortress" approach.  e.g. you build a landscape with no towns or anything, and then you turn agents lose and tell them, "build with the objective of growing your population" or something similar.  Then, because the AI works within reasonably realistic constraints, you get constructions that make sense within those constraints (the town is where the river can be bridged, the villages serve clusters of farms etc...)  Then a final layer of agents is told "here is a world that makes sense, look where plot can be injected"...  If towns already have things like ruling families, banks, thieves guilds, merchants, then adding plots may require only small refinements (make a bank clerk corrupt, give the crime lord an attractive child, take out a major bridge in a landslide...)

Thanks again!

Ian

To view this discussion on the web visit https://groups.google.com/d/msgid/proceduralcontent/CAK8bmyJkDhDpD1ZH-86sECfBpa5abc7_it1RgKNA_6P8r_f2FQ%40mail.gmail.com.

[Joris Dormans]

Hi Ian,

I also likes how this contrasts with the Dwarf Fortress approach. I haven't explored the agent based techniques at all, but maybe I should one of these days.

Incidentally, my high-level tile maps look like this:

And they have very similar properties as you describe. (x = room, e = entrance, u=undefined, B=blocked, the white tiles indicate corridors, the black arrows are gates (to be opened from one side), the green ones are valves (traversable in one direction).

So they are very much what you describe.

Best,

Joris

To view this discussion on the web visit https://groups.google.com/d/msgid/proceduralcontent/1991764557.6302913.1625760639721%40mail.yahoo.com.

[Ian Badcoe]

Thanks again!  I'll study that in detail tomorrow...

Have you written any documents on the Unexplored 2 approach, I have read ones on Unexplored 1 (and will refresh my on those memory tomorrow too...)

The talk of going forward and back between the topology and the layout has reminded me of an approach I had some success with some years back...

I rewrote the graph and laid it out at the same time, e.g.:

0 - start with trivial laid out graph such as Entrance -- X -- Exit
1 - apply one rewrite, inserting new nodes (I had no deletions) at too close but non-topology-crossing positions

2 - relax the graph

2a - edges have a target length and spring force to that length, nodes have a minimum separation (sum of radii) and a force if they go inside that

2b - edges that get too extended auto-split by inserting extra nodes, e.g. X ---- Y becomes X -- c -- Y which allows curved corridors to form

3 - while not complex enough, goto 1

This worked something like this:

Graph based game level generation early demo #2

Graph based game level generation early demo #2

(Oh, yeah, the corridors have width too, and that repels nodes if they overlap...)

Or (for Joris) with cycles:

Procedural level generation prototype

Procedural level generation prototype

 (although one of the doors inserted there is futile, because this did not have the topological awareness I was describing in my first post, with that it would pull out a sub-graph to hide behind doors and also ensure the key was "closer" (more accessible) to the entrance than at least one door...)  Or it might just inject all doors before cycles...

You could regard this as a cycling between topology (in the rewrite) and geometry (in the relaxation) it is just that the representation covers both in different modes. 

Regards,

Ian

To view this discussion on the web visit https://groups.google.com/d/msgid/proceduralcontent/CAK8bmyKWaDWOdt93HmORReGzF1SenFrpMCfKUPKtk5muBvmBpA%40mail.gmail.com.

[Jim Whitehead]

Hi Ian,

Hope you have fun with your PCG deep dive over the next few days!

When I think of effective use of graph rewrite grammars, Joris Dorman's paper, "Generating Missions and Spaces for Adaptable Play Experiences" comes to mind. 

https://pure.hva.nl/ws/files/149264/453867_Dormans_Bakkes_-_Generating_Missions_and_Spaces_for_Adaptable_Play_Experiences.pdf

The techniques described in this paper are the nucleus of the pcg which appears in Unexplored (https://www.ludomotion.com/).

- Jim

[Alia McCutcheon]

Hi Ian,

This is a great start! I had a lot of success with a very similar approach for Don't Starve and then extended it for Oxygen Not Included by making the whole process hierarchical. See Voronoi Tree Maps for inspiration.

Cheers,

A.

To view this discussion on the web visit https://groups.google.com/d/msgid/proceduralcontent/472208094.5725305.1625777662833%40mail.yahoo.com.

[Joris Dormans]

The things I wrote about Unexplored 2 are all on Gamasutra: https://www.gamasutra.com/blogs/JorisDormans/604407/

Although I don't think they are not really on target in this case.

Best,

Joris

To view this discussion on the web visit https://groups.google.com/d/msgid/proceduralcontent/472208094.5725305.1625777662833%40mail.yahoo.com.

[Ian Badcoe]

Thanks all!

Joris - OK, since time is limited, I'll not look at your Unexplored 2 write-up at this time, thanks!

Jim - thanks!  I do not think I have read that exact paper of Joris's, so I will now...

Alia - I love your Voronoi diagram there!  I have not played your games ( the more I work on games, the less I play them, it seems :-( ), BUT my son has.  So I'll ask him later.  I recall he was very taken with Don't Starve at the time...

- I hadn't encountered Voronoi Tree Maps before, but I've just looked them up and they seem a wonderfully simple but expressive idea, thanks indeed for this pointer!

Regards,

Ian

p.s. this work is not all happening in the next few days, but rather spread throughout the rest of the year, so there is time for any follow-up thoughts we might have :-)

To view this discussion on the web visit https://groups.google.com/d/msgid/proceduralcontent/CAK8bmy%2BZnjkwgzZvnzd8_MNSfLhGti3z%3DJG%2BOznOHzDy%2B6LFSQ%40mail.gmail.com.

[Ian Badcoe]

Hi again all,

I've just got to my second day on this, so I just thought I'd give a quick update...

(I have been working in my own time too :-))

I ported my existing Java project to Unity and have it working as far as this:




(that's a very basic set of templates expanding from S -> e -> E)

This is an "expand the graph and relax after each expand" approach...

...then the final (white) geometry is created by unioning the working (red) geometry together and adding "details" like the small white circles in the large rooms (pillars).

My next steps are:

1) Layered Unions - if a room contains more than one sort of border (like "wall", "edge of pit", "edge of water", "edge of grass") then I have an idea I can construct those on different layers, with some additional rules for how layers interact.  e.g. Grass cuts a hole in floor -- because the stone stops at the edge of the grass and there may be a step -- and water cuts a hole in grass AND floor -- because neither can extend over the water.  If there was a bridge it might cut the water and (effectively) put floor back, but more likely a just pass through both (because logically at a different height)

2) Hierarchic templates - At the moment the nodes you see in the graph above are all the information, however I have long thought that what I ought to do is record the tree of template expansions so that an earlier template can continue to have an effect on later ones.  e.g:



Suppose the circled area had been created by an early template that made a room cluster, and the detail of exactly what rooms we added decided later (let's assume we didn't fill all four in the same...)  Then template-choice and rendering decisions (I use "rendering" for the whole of the process after "layout" which creates actual geometry, it's a multi-phase process in any developed system) can be constrained by the presence of the early template having added meta-data that says (i) this is a cluster, (ii) its settings are as follows...

For example, I am imagining that the other rooms on this level might be platforms hanging in the void, but these four rooms might be embedded inside in a solid pillar of rock (Union layers would let the paths and rooms cut the rock).

Additionally templates in the hierarchy might add layout constraints, like these four rooms might be constrained with an extra spring force to keep them together, and might repel other rooms, so that they don't force themselves into the rock...

3) Then render into 3D (2.5D at the moment, probably as paths cannot cross, nor rooms be placed above each other)

4) But an extension to cover multiple "storeys" isn't so hard after that, just track what is on what storey (somethings (stairs) being on >1) and do not calculate layout constrains across them...

Regards,

Ian

p.s. if anyone is looking for a platform in which to do research, Unity is a really friendly system for rapid prototyping.  Very easy to get started and pretty powerful (UE is more the AAA industry choice but, to paraphrase one of our tech directors, it is a 747 cockpit and none of the controls are labelled...)

To view this discussion on the web visit https://groups.google.com/d/msgid/proceduralcontent/1849526427.6726817.1625822224903%40mail.yahoo.com.

[Ian Badcoe]

This is crude as yet, but I just wanted to demonstrate multiple layers of unions...

Each layer is colour coded:

- white --> the edge of a drop

- grey --> wall

- blue --> pool

- brown --> internal decor

- red --> edge of lava

So you can see:

- the river of lava runs out of a room and down the corridor

-- the joints in the river I did not do yet, I need to extend the framework to understand "N things with different widths continue across this join"

-- it stops where it stops because the template that put the small circular side-room on explicitly override it, I probably need to adjust that template not to change the properties of the main corridor, but longer term I probably need to theme via topologically-connected areas rather than template-by-template

- round rooms with a pool and four pillars are output by a particular template

- there are places where the walled corridor gives way to bridges (rooms without walls are also easy, I just commented them all out while I tested something else...)

Hierarchic templates are also in place as a framework, but they aren't really doing anything as yet...

Note quite sure of next steps as yet, I do find with that this one cannot create the large-scale "framework" systems in a vacuum, one needs specific detailed usages to really define how the big stuff ends up fitted together...

I might push it into 3D geometry generation, which may shake some more stuff loose...

Cheers!

Ian

To view this discussion on the web visit https://groups.google.com/d/msgid/proceduralcontent/533015314.134142.1628845681326%40mail.yahoo.com.

[Ian Badcoe]

Just a quick update:

This is still a demo of the simpler part of the approach, e.g. that meaningful geometry can be generated fast enough.

This takes ~20 seconds for "20 nodes" in size, 30 nodes takes ~50s, because the relaxation takes non-linearly longer... but if the level was cut up into slightly separated sections that non-linearity would be reduced.

Ian

To view this discussion on the web visit https://groups.google.com/d/msgid/proceduralcontent/438474974.1494961.1629729733795%40mail.yahoo.com.

[Ian Badcoe]

Hi all,

Possibly a final update on this one...

So I shelved my graph-based experiment...  I think it could be taken further but it is not "blossoming" the way I hoped.  I hoping it would trigger further ideas and I might guide development by what made those ideas easy to implement.  Instead it was progressing only very slowly past a basic level and it began to feel like a bit of a drag.

I think I get a couple of positive results from it:

1) that incrementally building a graph and relaxing its representation (2D, but that's not required) as you go can work.  Obviously the relaxation gets more expensive as the graph grows and an approach that was able to move whole blocks around without needing to optimize their inside might be more efficient...

OR... my current approach can add new content anywhere, but if the approach was able to grow into empty space, say by growing North, then the previously completed Southern parts could be treated as fixed context not requiring further oprimisation.

2) that creating 2D maps via union + subtract geometry representations can generate quite rich geometry.  (I don't know of a general term for this, it is like CSG but in 2D, "Constructive Flat Geometry" (CFG)?)  The limitations here, however, were:

- depending on what geometry you feed into it, you may get numerical precision problems.  I wasn't _plagued_ with those, but there were various tolerances built into the CFG algorithms (like "all verts within 0.1mm of each other are the same vert) and those made me nervous every time I looked at them.  On the whole they behaved, but I did wonder if they were a problem that would strike later...  I did at several points rework bits to make them more stable in the face of such things (like making them not care if a vert they were trying to introduce had to merge into an existing one) but I'd say that was only 99% there...

- depending on the exact nature of the inputs, you might need care in composing them because there is nothing topological about the CFG logic.  Thus if something cuts right through something that should be impenetrable, that will make hole you don't want...

Negative results:

3) as discussed before I started, graph layout of geometry (as opposed to graph generation of plot/logical structure) isn't the most natural fit...

4) it is very hard to construct PCG in the absence of an actual game to inform the process.  e.g. I put red/blue bits in my prototype thinking "that might be fire/water" but without an actual need/reason for fire/water in the levels, it is impossible to evaluate whether that is really working...  similarly I didn't get as far as doors and keys, in part, again, because without a narrative reason for them it is really hard to imagine what the right rules for positioning them would be.  I thought that the emerging levels would inspire me as to what the game should be (and thus get two way feedback) but so far it all remains very sterile and abstract :-(

Thus I am tentatively looking into a different approach...

Which I will describe in a separate message.

Regards,

Ian

To view this discussion on the web visit https://groups.google.com/d/msgid/proceduralcontent/1454551611.2779472.1630593231660%40mail.yahoo.com.