Meeting 27/7/2017

2017 Luglio, 30 Domenica 12:34


The article contains a brief review on the previous 2 meetings. The 2 meetings focus their attention on the main part of the game: given a room where lava has been already placed, which prop should be added in the room? Which qualitas should be put onn each prop? How can we connect qualitas?

 

Given a room, how can we choose which prop should be added inside the room?

 

Imagine you have a room where lava has been already placed. For simplicity, image this room rectangular. You have the list of all the props available. You need to select a subset of them that will be placed inside the room. The solution we thought manage the "which subset of props we choose".  Thus, we don't focus on "where a particular prop is placed within the room". 

The basic idea is to have a graph (an example is shown below [WARNING: discard the "QUALITAS" word!!!!!!!])  where each node is a particular prop available in the game. So if we have 1000 props the graph will have 1000 nodes. The edges represents a causal relationship: given the edge X --> Y, it means that if we add the prop X in the room, it makes sense to add the prop Y as well.

From a node N usually comes out not 1, but several nodes. for example:

 

BOTTONE --> FONTANA

BOTTONE --> PORTA CHIUSA

BOTTONE --> SPINE

 

This means that if we add a "BOTTONE", we may add either FONTANA, PORTA CHIUSA or SPINE as well. Imagine someone told you have add a BOTTONE. How can you choose among those 3 nodes? The solution is each edge has a label and that label is a float representing a probability. The sum of the probabilities of the edges coming out from a nodes must be 1. When you add a BOTTONE, you simply choose the next prop to add based on the proabilitities of the successors of the node BOTTONE.

 

 

This graph (called prop graph) contains cycles: given given a "PORTA CHIUSA", there is an edge to "CHIAVE" and vice versa. This is not wrong: if you have a key, you might have to generate a gate and vice versa: the graph doesn't contain the relations of actual props, but it's just a guide!

When you need to create the props to add in the room, you start from a random node in the graph, then you build a path that goes from the node you selected until a particular length of the path is obtained: the path might pass through the same node multiple times (example: we might have multiple bosses within the same room). However, traversing a node implies you need to create a prop inside the room

When do you stop? Several exit conditions can be found:

* the already mentioned "when the path you have created has at least N size";

* when you have path connecting prop X to prop Y (not necessarly via the shortest path);

* when you have a path maximizing a certain criterion (for example difficulty). This is probably implemented with A* and an heuristic;

 

The prop graph may be connected to the fuzziness bar of the whole labirynth: by tweaking that bar you add a proportional fuzziness to the graph values (i.e. with gaussian noise). Note that the absence of an edge cabe be affected by the noise itself. For example, if we encode the graph with an adjancnce matrix, we can add the noise to the 0 within the matrix (remember, no edges between the nodes means there is no edge between the 2 nodes). If, after the perturbance, the value is not 0 anymore (say 0.004) the dependency between the 2 nodes has been altered.

 

Improving room dependencies

 

After running the algorithm on the prop graph, we obtained a path of props within the graph itself: for example, we obtained something like:

 

 

Each node is a different prop instance generated inside the room. The red line represents the path we have generated by looking at the prop graph. To improve the room complexity, we may create, inside the path, additional branches: otherwise each room has a set of object linked together probably in a straight forward manner. For example, we may:

 

  1.   create props that start from the red path and goes to nothing (if the user selects this elements, they reach a "deadend" inside the room);
  2.  create props that start from nothing and merge inside the path: these are different way to solve the room;
  3. create props that create a shorter (or longer) path within the red path: this are other ways the user can execute to solve the room.

All this may be future implementation.

 

Note that, in order for a room to be solvable, we need to create a single path that will surely make the room solvable: the red path is such a path.

 

Qualitas modelling

 

The previous algorithm allowed us to determine which props should we add inside the room. But we still need to understand what are their behaviours. In order to do that, we need to model the qualitas in some way. 

Each prop has a list of qualitas. Each qualitas has a way to understand what is the prop they use. Abstractally, a qualitas is a container:

  • with a set of inputs (edges going into the qualitas);
  • witha a set of outputs (edges going out the qualitas);
  • an activation function (a function doing some stuff);

 

When all the inputs of a qualitas are activated, the function is executed and all the output of the qualitas are activated as well.

 

 

In this simple model, however, if a qualitas does not have any inputs, its output are automatically set, without any user actions. Sometimes we want that, but sometimes we'd like to have use interaction. Hence, there are some qualitas whose inputs are set only when the user does some osrt of action. For example the qualitas "onclick" has only an input and whatever outputs it likes. This input is set only when the user perform a click on the prop connected to the qualitas.

By connecting qualitas one to another, a graph of qualitas may be generated:

 

 

you should think of the edges and qualitas as a an electric circuit: depending whether or not current flows on a particular cable, an element may be activated or not. The qualitas themselves does not have state (for example qualitas "onAttack" does not have the inner state "HP"): the state of the current prop is within the prop itself; this leads to 2 effects:

  1. we can build a hierarchy of props, depending on their attributes. For example we can have an interface "HPOwner" where all its derived class has the attribute "HP". It makes sense, because for example if we are trying to add the qualitas "open" is tmakes sense to add such qualitas only on something that can be actually opened (door can be opened, while enemies can't). Each state of a prop is well defined inside this hierarchy: there is no uncertainty about them.
  2. The qualitas acts as some sort of behavioural plugins: they don't add sfurther state in the prop, but they add new business logic to them.

If a qualitas needs to send some attributes to another, it can send a dictionary to the output qualitas. For example the qualitas "onClick" will probably send a dictionary with the key "player" containing the reference of the player that performed the click. the qualitas can operate via Listener design pattern.

 

Classes of qualitas

Depending on how we want to create room (difficulty-focus, platform-focus) we may add different props and qualitas. A solution might be that a prop (and qualitas) has a characteristic that tells you how can you use it. For example, the "enemy" prop has the attribute "difficulty-focus" telling you that if you want to generate a difficult room, inserting that prop may help you (this chracteristic is together the "biome" feature telling you what prop you can add insde the room given a certain biome).

 

Algorithms to generate

 

As for the algorithm generating the edges of the qualitas graph, we can model it as a local search. 

We still need to think about the algorithm that generates the qualitas each prop has and the algorithm that connects the qualitas altogether. It's highly probasble that these algorithms should work together.