Address 11 - PowerPoint PPT Presentation

lecture 11 n.
Skip this Video
Loading SlideShow in 5 Seconds..
Address 11 PowerPoint Presentation
Address 11

play fullscreen
1 / 17
Download Presentation

Address 11

Presentation Transcript

  1. Lecture 11 Space Invaders

  2. Space invaders: a simple video game • The display of the space invaders is depicted in the following figure.

  3. 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.

  4. Sprites 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.

  5. 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. ||SPACE_INVADERS = (alien:ALIEN || spaceship:SPACESHIP || missile:MISSILE || COLLIDE(alien, spaceship) || COLLIDE(missile, alien)) /{spaceship.action/missile.create, tick/{alien,spaceship,missile}.tick}>>{tick}.

  6. 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) SPRITE = (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).

  7. 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) +SPRITE ||ALIEN = ( SPRITE || ALIEN_CONSTRAINT).

  8. 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. SPACE_CONSTRAINT = (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. ||SPACESHIP = (SPRITE || SPACESHIP_CONSTRAINT).

  9. 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).

  10. No deadlocks/errors model analysis Deadlock? Safety? Progress? 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}

  11. 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}. ||FIND_ALIEN_HIT = (SPACE_I(NVADERS || ALIEN_HIT).

  12. model - safety properties

  13. 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 Implementations.

  14. Sprite and SpriteCanvas The display for Space Invaders program is handled by The two classes depicted in the following figure.

  15. CollisionDetector 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.

  16. SpaceInvaders 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 figure.

  17. Summary 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.