Lecture 11 - PowerPoint PPT Presentation

Lecture 11 l.jpg
1 / 17

Lecture 11 Space Invaders Space invaders: a simple video game The display of the space invaders is depicted in the following figure. Space invaders (Conti.) The spaceship can be moved around the screen using the cursor keys .


Download Presentation

Lecture 11




Presentation Transcript

Lecture 11 l.jpg

Lecture 11

Space Invaders

Space invaders a simple video game l.jpg

Space invaders: a simple video game

  • The display of the space invaders is depicted in the following figure.

Space invaders conti l.jpg

Space invaders (Conti.)

  • The spaceship can be moved around the screen using the cursor keys.

  • Pressing the space bar on the keyboard launches a missile from the spaceship.

  • Missiles move up the display and appear as white arrows on the display.

  • Aliens depicted as spheres, drop from the top of the screen and explode when hit by a missile.

  • When an alien collides with the spaceship, an explosion occurs and the shield strength of the spaceship is reduced.

  • The game terminates when the shield strength drops to zero.

  • The objective is to shoot as many aliens as possible.

Sprites l.jpg


Video games involve many active entities, called

sprites, which move around independently and concurrently.

A sprite has a screen representation and a behavior.

Sprites may interact when they collide. In Space Invaders,

The sprites are the spaceship, aliens, missiles and

Explosions. Sprites are concurrent activities, which we

should implement as threads. However, this will result in

a game with poor performance. A much better scheme is to

implement sprites as timed objects. Each sprite can move

once per clock cycle. It is simple to synchronize screen

updates with sprite activity. We simply reprint the screen

per clock cycle.

Space invaders model l.jpg

Space Invaders Model

The following composite process models a game that,

in addition to the spaceship, permits an alien and

a missile to appear on the screen. However, since

sprites are defined as having cyclic behavior that

models recreation, the alien can reappear in different

start positions and spaceship can launch another

missile as soon as the previous one has left the screen.


(alien:ALIEN || spaceship:SPACESHIP

|| missile:MISSILE || COLLIDE(alien, spaceship)

|| COLLIDE(missile, alien))



Model elaboration process definitions l.jpg

model elaboration - process definitions

SPRITEThe behavior of the spaceship, missiles and aliens is defined using this process.

const MAX = 4

range D = 0..MAX

set Coord = {[D][D], undef} //(x,y)


(create[x:D][y:D] -> SPRITE[x][y]

| tick -> SPRITE

| pos.undef -> SPRITE),

SPRITE[x][y] =

(pos[x][y] -> SPRITE[x][y]

| tick ->

(north -> if y>0 then SPRITE[x][y-1] else END

|south -> if y<MAX then SPRITE[x][y+1] else END

|west -> if x>0 then SPRITE[x-1][y] else END

|east -> if x<MAX then SPRITE[x+1][y] else END

|{rest,action[x][y] -> SPRITE[x][y]),

END = (end -> SPRITE).

Model elaboration process definitions7 l.jpg

model elaboration - process definitions

ALIENThe An alien is a sprite that moves down the screen.

We can specify its behavior by constraining the movement of

the sprite process.

ALIEN_CONSTRAINT = (create[D][0] -> MOVE).

MOVE = (south -> MOVE | end -> ALIEN_CONSTRAINT)



Model elaboration process definitions8 l.jpg

model elaboration - process definitions

SPACESHIP A The spaceship has more complex behavior. It is constructed to move horizontally at the bottom of the screen, either east or west, or staying in the same position, rest. The spaceship can perform an action, which is used to create a missile.


(create[MAX/2][MAX} -> MOVE[MAX/2]),

MOVE[x:D] =

( when (x>0) west -> MOVE[x-1]

| when (x<MAX) east -> MOVE[x+1]

| rest -> MOVE[x]

| action[x][MAX} -> MOVE[x] ) + Sprite.


Model elaboration process definitions9 l.jpg

model elaboration - process definitions

COLLIDE A Collision detection is modeled by the COLLIDE process which, after a tick, queries the position of two sprites and signals a collision through the action explode if their positions coincide.

COLLIDE(A=‘a,B=‘b) =

(tick -> [A.pos[p1:Coord] -> [B].pos[p2:Coord]

-> if (p1==p2 && p1 != undef && p2 != undef)

then ([A][B].explode -> COLLIDE)

else COLLIDE).

Model analysis l.jpg

No deadlocks/errors

model analysis

Deadlock? Safety?


Safety analysis of SPACE_INVADERS does not detect a time-stop and progress analysis demonstrates that TIME progress property is satisfied. Further, the following progress properties are satisfied:

Progress SHOOT_ALIEN={missile.alien.explode}

Progress ALIEN_SHIP={alien.spaceship.explode}

Model sample traces l.jpg

model - sample traces

To gain the understanding of the operation of the model,

We can produce sample traces by using the safety property

as follows. Suppose we wish to find a trace that the

results in a collision between an alien and a missile.

We specify a safety property that the action (collision)

should not occur and analyze the system with respect to

this property.

Property ALIEN_HIT = STOP + {missile.alien.explode}.


Model safety properties l.jpg

model - safety properties

Space invaders implementations l.jpg

Space Invaders Implementations

The implementation of Space Invaders program is large

in comparison with the example programs presented

before. We describe only the structure of the program

using class diagrams. The translation from timed

processes to timed objects in Java should be clear

from the previous example, the parcel router.

Three class diagrams will be depicted in the following

slides. You are encouraged to read the Java code for

each of the classes in order to know the detailed


Sprite and spritecanvas l.jpg

Sprite and SpriteCanvas

The display for Space Invaders program is handled by

The two classes depicted in the following figure.

Collisiondetector l.jpg


The collision detector maintains a list of alien sprites

and missile sprites and a reference to the spaceship

Sprite. It is depicted in the following figure.

Spaceinvaders l.jpg


The SpaceInvaders applet class creates the spaceship,

the alien generator, the missile launcher and the

score board in addition to the display, time manager

and collision detector. It is depicted in the following


Summary l.jpg


We described an implementation approach for timed systems

that is event-based rather than thread-based. In this

approach, each model process that has tick in its alpha-

bet is translated into a timed object.

The advantage of using timed objects rather than threads

to implement timed processes is concerned with runtime

efficiency. Timed objects have lower overhead than context

switching threads. Since in the two-phases scheme, the

pre-tick and tick methods run sequentially, there is no

synchronization overhead to ensure mutual exclusion.

The model-based approach to concurrent programming permits

a designer the flexibility to use either an event-based

or a thread-based implementation scheme or a hybrid.

  • Login