Meeting 31/08/2017

2017 Settembre, 4 Lunedì 13:41

In the following article, I will revivew the themes discussed in the previous meeting. The focus of such meeting was that to design the algorithm laying out the logic and the qualitas connections of the props added in a room


In order to completely understand the ideas inside this meeting, you need to have a grasp on heuristics and, in general, A*

I want to remind you that all of these are just ideas, not design.


First of all, it's official: we are behind the schedule of this project. Because of this, I thought it was mandatory to further restrict the alpha version of the game: the first version should consist of only 1 room automatically populated.

Remember the last stuffs we have asserted in the meeting: we have an algorithm that computes the list of props to add in the room. Furthermore, such list is ordered and the order is a "existence dependency" from the object at position i-th to the one at (i+1)-th: in other words, we add the object B because we have added the object A.

But how those object are related? And what are the qualitas of such objects? This meeting tried to solve these issues.

First of all, each prop has a different number of qualitas. The prop themselves are inside an interface hierarchy: for example the prop "Boss" implements "HPAble" (with HP) while "Boss" prop doesn't implement the interface "Openable". This interface graph can be exploit to prune (remember what pruning is, right?) which qualitas can be assigned to a particular prop: for example the qualitas "doOpen" can't be assign to something that is not "Openable" (for example it can't be assign to a "Boss" or "Enemy"). Pruining tell us what can we safely excluded, but tell us nothing about what can be added.

Now, Suppose you have 4 prop in the room: a fountain, a flamethrower, a boss and a treasure. You need add a qualitas, for example "OnKill". You scroll all the prop and remove the ones that doesn't implement the interface "HPable" (OnKill qualitas requires you to have a HPable). Let assume that we decided that flamethrowers don't have HP. So you have restrict the choice to who will receive this qualitas, aka either the fountain, the boss or the chest with the trasure.



In order to establish which prop should have the qualitas, we add for each prop class as many double fields as there are interfaces implemented: so if Boss implements "HPAble" and "Moveable", we will add the field "hasMeaningToHPAble" and "hasMeaningToMoveable": each of them is a propbability between 0.0 and 1.0. We choose which prop will receive the qualitas based on a weighted random choice between the props left from the previous operation: so if the fountain has hasMeaningToHPAble=0.01, the boss hasMeaningToHPAble=0.98 and the chest hasMeaningToHPAble= 0.5, we choose a random weight based on such values. For example, we choose the boss.

This is a simple algorithm to choose a qualitas to assign to a prop. The probabilities are hard coded.

Now you can model the qualitas of the props and the business logic link among them as a graph with as many layers as there are props. We need to find an algorithm that (at fuzziness = 0) will create "serious maze", aka mazes where the player can detect what the logic is inside the room. We need to create an algorithm that creates serious algorithm, aka seriious connection of qualitas and assign qualitas to prop correctly.

How can we do it? An idea would be to see this problem as a search in the state space: each state of the problem would be a qualitas graph, with variable nodes and variable edges. Each successor might have:

  • a new node representing a qualitas;
  • a qualitas removed from the graph;
  • a new connection between 2 qualitas;

The issue now is to find a valid heuristic, aka something that tells A* (we will use as search algorithm A* itself) if the qualitas graph is meaningful or not. Now,

A qualitas graph is meaningful for a player if all the edges between the qualitas are meaningful for the player. Regarding that, we can model the function that, given an edge of the qualitas graph, determines the meaningfulness of the connection as:


\sigma : P x P x Q x Q --> R

In other words, such functions pick:

  1. a prop p1 (inside the set P);
  2. a qualitas q1 assigned to p1 (inside the set Q);
  3. a prop p2 (inside the set P);
  4. a qualitas q2 assigned to p2 (inside the set Q);


The function will evaluate this tuple and assign it a meaningful value in R (for example 0.5). Note that we might hardcode this function but for 4 props and 5 qualitas (hence a very small problem), we should hardcode 4*4*5*5 = 400 values. It's clearly too much.

So we need to think about a solution (if the local search solution is to be chosen) to compress this matrix. Note that after that, we need to get the meaning value of the whole graph, for example, given the semantic meaning of all 15 edges in the qualitas graph, what should be the semantic meaning of the graph? How can we aggregate the values? Possible solutions are:

  1. sum;
  2. product;
  3. max;
  4. average;


Finally note that "creating serious mazes" is not a synonym of "creating maze that lead to a reward to the player".

As per usual, if you have suggestions of complaints, please email me.