Offline BeepBeep 3 Benchmark1

From CRV
Jump to: navigation, search

Pingus Synthetic execution traces of the video game Pingus, used for runtime verification. All details regarding these traces can be found in the paper Automated Bug Finding in Video Games: A Case Study for Runtime Monitoring. We highly recommend you scan that paper first.

List of categories

Benchmark Data

Pingus is a clone of Psygnosis’ Lemmings game series made by Ingo Ruhnke. It regularly counts among the highest quality open source games available and was once ranked in the Top 10 Linux games by CNN. The game is divided into more than 70 levels, each of which being populated with various kinds of obstacles, walls, and gaps. Between 10 and 100 autonomous, penguin-like characters (the Pingus) progressively enter the level from a trapdoor and start walking across the area. A Pingu keeps walking in the same direction until it either reaches a wall (in which case it turns around) or falls into a gap (and dies, if it falls from too high).

The goal of the game is to have a minimum percentage of the incoming Pingus safely reach the exit door. To this end, the player can give special abilities to certain Pingus, allowing them to modify the landscape in order to create a walkable path to the goal. For example, some Pingus can become Bashers and dig into the ground; others can become Builders and construct a staircase to reach over a gap. Other abilities modify the behaviour of other Pingus: hence the Blocker stands in the way and makes any Pingu that reaches it turn around as if it encountered a wall.

The Trace Part

The dataset is made of about 20 traces consisting of a simulated execution of the game; each of these traces contains from 10 to 90 Pingus walking in the game field at the same time. You can download the trace files from DataHub (click on the button "Go to resource"). For convenience, the traces are also available directly on the server, in the (read-only) folder /home/beepbeep3/traces/pingus.

Event structure

All traces are in XML format. Each event of the trace has the following structure:

<message>
 <characters>
  <character>
   <timestamp>123456</timestamp>
   <id>0</id>
   <status>WALKER</status>
   <position>
    <x>62</x>
    <y>0</y>
   </position>
   <velocity>
    <x>1</x>
    <y>0</y>
   </velocity>
  </character>
  ...
 </characters>
</message>

The event is contained in a message element, which contains a single characters element. Within this element, there are multiple character elements, corresponding to the properties of a single Pingu on the game field. Each Pingu has a unique ID, a position (x-y) and a velocity vector (x-y). In addition, each Pingu has a status, which can be "walker" (normal state), "hidden" (not yet injected into the playing field) or any of these special abilities: "blocker", "basher", "blower", "builder", "faller".

IDs are unique within each individual message element, but obviously, they repeat from one event to the next. Some Pingus, however, may disappear at some point in the trace if they die, so the number of character elements is not fixed for the entire trace. Within each message, IDs do not appear in any particular order: this depends on the iterator on game elements provided by the game itself. We cannot assume either that IDs start at 0 or that they form a continuous sequence.

In this simulation, the game loop runs at about 100 Hz; hence message elements correspond to snapshots of the game's state roughly 0.01 seconds apart. The traces in the dataset correspond to approximately two minutes of playing in the same, simple level.

The traces were programmatically generated by the Pingu Generator.

Naming convention

Trace files are labelled using the following convention: description-x.xml where x is the number of Pingus in the level, and description tells which of the properties described below this trace violates. A trace where no property is violated has all-ok for its description.

The Property Part

The paper on Pingus (see link at top of the page) describes many properties one can verify on the execution of the game. For the purpose of this benchmark, we picked three of them.

Property 1: Spontaneous Pingu creation

Informal Description

From one event to the next, Pingus can only disappear from the game field; no Pingu can be created mid-game.

Demonstration Traces

Here are two counter-examples of this property (for the sake of clarity, we only list IDs occurring in each event):

  {0,1,2}, {0,1,2,4}
  {0,1,2}, {0,1,3}

Here are two examples of this property (for the sake of clarity, we only list IDs occurring in each event):

  {0,1,2}, {0,1,2}, {0,1,2}
  {0,1,2}, {0,2}, {0,2}, {0}

In the dataset, the traces labelled pingu-creation violate this property.

Formal Specification

This property can be checked in multiple ways. For example, in past-time first-order LTL, one can say that for every ID found in an event, in the previous event, there must be a tag with the same ID:

G (∀ x ∊ /characters/character/id : Y (∃ y ∊ /characters/character/id : x = y))

Another possibility is first to aggregate all IDs from each event into a set, and then check that the sequence of such sets is monotonically decreasing, etc.

A FO-LTL Specification

See above.


Clarification Requests