Sentient Sketchbook

Webservice Structure

The webservice can generate new map sketches, create variations of provided map sketches, or evaluate existing map sketches; all of these functionalities will be described later in this section. The webservices communicates with other applications (clients) using data structures in the JSON (JavaScript Object Notation) format, which is a lightweight data-interchange format easily understandable by both humans and machines. The core component of JSON data structures are values which can be a text string, a number, true or false, an object (an unordered set of name/value pairs) and an array (an ordered collections of value); it is thus valid to have an array of objects or an object with both objects and numbers in its set. Regardless of the method call, a client application must provide as input (via a POST request) a JSON object containing the specifications of the map sketch, the desired qualities and constraints on the generated or evaluated sketches, and (optionally) any parameters needed for the genetic algorithm; the webservice processes this input and returns a JSON data structure as a result, the format of which depends on the method call made. The input JSON object contains several values which customize the generation or evaluation properties of the method call, and will be described in the next sections.

Defining a map sketch

A map sketch consists of tiles of different tile types laid on a grid; the tile types of the map sketch are used to evaluate the map's fitness and to test whether its constraints are satisfied. The input JSON object contains a TileTypes value which is an array of tile type definitions, each definition being a JSON object with the following values:

name string which is used for identifying the tile type when defining constraints and fitness functions.
asciiChar string which is used to produce an ASCII version of the map sketch as output of the webservice.
passable boolean which specifies if the tile type allows or blocks movement, for the purposes of pathfinding.
defaultTile boolean which specifies if this is the default tile type or a special tile. If a tile type does not have this property, it is assumed to be a special tile.

Defining fitness functions and constraints

In order to evaluate map sketches (e.g. for optimizing them through evolution, or for testing if their playability constraints are met), multiple fitnesses (for feasible maps) and constraints (for infeasible maps) can be defined in the input JSON object in a Fitness array and a Constraints array respectively. All fitness and constraint definitions are JSON objects with the following values:

name string which is used when displaying the map sketch's fitness scores (only for evaluation method calls).
type string specifying which algorithms are used to evaluate the fitness score.
weight double specifying how much each fitness contributes to the total fitness score which guides evolution; negative weights are possible when a fitness should be minimized. This is an optional variable; if omitted, the weight is presumed to be 1.
referenceTiles string specifying which tile types are considered to evaluate the fitness score.
targetTiles string specifying which tile types are targeted to evaluate the fitness score. This is an optional variable used in certain types of fitness functions.
arguments string specifying any additional arguments for this type of fitness. This is an optional variable.

Among the values of a fitness or constraint definition, the type is most important as it specifies the algorithms used to calculate the fitness score but also how the other values (except name and weight) will be interpreted. Each of the referenceTiles, targetTiles and arguments values are a text string which may contain multiple parameters separated by commas (the text string is split within the webservice). The different types of fitness functions which can be included in the Fitness array are described below, according on their type values:

  • SafeAreaThresholdFitness evaluates the number of tiles which are safe to any referenceTiles. If the fitness has a targetTiles value, then only tiles of the types in targetTiles is considered; otherwise all passable tiles are considered. The arguments value defines the lowest safety score for a tile to be considered safe.
  • SafeAreaThresholdBalance uses the same structure as SafeAreaThresholdFitness and evaluates if each of the referenceTiles has a similar number of safe passable tiles (if targetTiles is omitted) or tile types which match the targetTiles value.
  • TileSafetyFitness evaluates the total safety score of all targetTiles with regards to all referenceTiles.
  • TileSafetyBalance evaluates if the cumulative safety score of all targetTiles for each of the referenceTiles is similar.
  • ExplorationFitness evaluates the exploration effort to discover all targetTiles from all referenceTiles. If the targetTiles value is omitted, the fitness evaluates the exploration effort from all referenceTiles to all other referenceTiles.
  • ExplorationBalance evaluates if the exploration effort is similar for each of the referenceTiles when discovering all of the targetTiles or when discovering all other referenceTiles (if targetTiles is omitted).

The different types of constraints which can be included in the Constraints array are described below, according on their type values:

  • ConnectivityConstraint measures how many of the targetTiles are not connected via a passable path to referenceTiles; if targetTiles is omitted, this constraint enumerates the disconnected paths between referenceTiles. Optionally, if the arguments has a "disconnected" value then the constraint is only satisfied if no passable paths exist between the specified tiles.
  • NumericalConstraint measures the number of excess or missing referenceTiles as specified in the arguments. The arguments value can specify a number (A) or two numbers (A,B) as the numerical bounds: the possible syntax for arguments is "equals,A", "notEquals,A", "maximum,A", "minimum,A", "inRange,A,B", "notInRange,A,B".
  • ConditionalConnectivityConstraint is similar to ConnectivityConstraint but enumerates disconnected paths as if certain tile types were impassable or passable (overriding specifications in TileTypes). Passability/impassability is specified in the arguments, where a tile type is preceded by "passable" or "impassable" (e.g. for a map sketch with "wall" and "treasure" tile types, this constraint could have an arguments value of "passablewall, impassabletreasure").
  • DistanceConstraint enumerates those shortest paths between referenceTiles and targetTiles which are with numerical bounds specified in the arguments as per NumericalConstraint. If targetTiles is omitted, paths between referenceTiles are considered.

Defining evolutionary parameters

The input JSON object can specify evolutionary parameters as a Parameters object. Some of those parameters are necessary for any evolutionary run which generates map sketches, while optional parameter values can override the default parameters used for evolution.

Necessary parameters, which must be defined for any method call for evolving map sketches are described below:

runsinteger which is the number of evolutionary runs and the number of map sketches returned from the call to the webservice.
mapSizeXinteger which is the width of the map sketch, in tiles.
mapSizeYinteger which is the height of the map sketch, in tiles.
populationinteger which is the number of individuals (both feasible and infeasible) in the genetic algorithm.
maxGenerationsinteger which is the number of generations of evolution, before the webservice returns the best result.

Optional parameters, which can override the default webservice values (and included in the description) are below:

fi2popboolean which signifies if the feasible-infeasible 2 population genetic algorithm should be used; if this value is false, then a single-population approach is used and the death penalty (i.e. a fitness of 0) is applied to infeasible individuals (default: true).
steadyPercentageinteger which is the number of best individuals copied to the next generation (default: 1).
crossoverPointsinteger which specifies the N in the N-point crossover carried out by the GA. The minimal value for this parameter is 1 (default: 2).
mutateOnlyProbabilityinteger is the chance (in 100) of asexual mutation. If this value is 100 or above, the GA evolves via asexual mutation alone (default: 0).
mutateAnyProbabilityinteger is the chance (in 100) of mutating an offspring made via crossover (default: 5).
mutateTileMinNumberinteger is the minimum number of tiles that change in each mutation cycle (default: 5% of the total map tiles).
mutateTileMaxNumberinteger is the maximum number of tiles that change in each mutation cycle (default: 20% of the total map tiles).
mutateShiftinteger is the chance (in 100) of any mutation swapping adjacent tiles (default: 5).
mutateToggleAinteger is the chance (in 100) of any mutation changing a tile of type A (A being the tile type's name) to the default tile type and vice versa (default: 0).

Evolving a map sketch

Map sketches can be evolved via the sketchgenerator method call; this call returns the fittest feasible individual of an evolutionary run, or the fittest individuals of multiple runs (one individual per run). The client provides a JSON object as input (via a POST request) which must contain values for TileTypes, Fitness, Constraints (even if it is empty) and Parameters with the essential parameters described above. Optionally, the input JSON object can also contain a ReferenceTileMaps value as an array of one or more sketches which seed evolution; the sketches are provided as ASCII text, with characters defined in the accompanying TileTypes; rows are divided by semi-colons. Note that the map size of ReferenceTileMaps overrides the mapSizeX and mapSizeY parameters (which can be omitted): evolved sketches will have the same map size as the ReferenceTileMaps. The output of the evolutionary process is a JSON array containing one or more sketches in ASCII text in the same format as ReferenceTileMaps. The number of sketches should be equal to the runs value of the Parameters object; however, some runs may not result in feasible individuals (e.g. in cases of highly constrained search spaces, few generations of evolution, or poorly designed constraints). In such cases, the number of sketches in the output may be fewer than the number of runs, or the array may even be empty.

Evaluating a map sketch

Evolution requires that every map sketch is tested for constraint satisfaction and also evaluated on the provided fitness scores; however, the results of evolution method calls do not contain such information for the sake of readability and bandwidth. However, generated or custom-made sketches can be evaluated via the same fitness functions and constraints used internally in the generator. Two method calls allow for such an evaluation: sketchevaluator and sketchdetailevaluator, the latter offering all the functionalities of the former but with additional feedback for visualizing properties of the map sketch. For both methods, the client provides a JSON object as input (via a POST request) with a ReferenceTileMaps array of map sketches to be evaluated (using the same format as the evolution method call), along with TileTypes, Fitness and Constraints. The output of sketchevaluator is a JSON array of the same size as the input ReferenceTileMaps. Each item of the array is a JSON object with the following values: a feasible boolean value which is true if the map sketch satisfies all constraints, a scores array containing the map's scores for all fitnesses in the Fitness collection, if the map is feasible, or the map's distance from feasibility for all constraints in the Constraints collection, if the map is infeasible. Within the scores collection, each score is preceded by the name of the fitness or constraint being evaluated. In addition to the feasible and scores arguments, the output contains a parsedInput argument; for sketchevaluator method calls, parsedInput only contains the asciiMap argument, which is the same ASCII format of the map sketch being evaluated (for easier reference or asynchronous requests). For sketchdetailevaluator method calls, the parsedInput argument of each map contains (beyond asciiMap) a layers object containing several maps used internally by the generator; these maps can be boolean (0 or 1) or floating point (with each number separated by commas) and map rows are divided by semi-colons. The names and types of maps depend on the constraints and fitnesses. For instance, if the input JSON has a SafeAreaThresholdFitness, maps named safetyMatrix (and an identifier of the reference tile's coordinates) will be added to layers: these floating point maps specify the safety score of all map tiles for one reference tile (contained in the map's name).