System Level Design Specification

Project Report And Design Specification

Hominoid State Model LCP

Design of Hominoid Game using GEN, LCP & BDE

Document Number : Project Report CS91-201-522

Advisor : Bob Lechner

Authors : Suren Karavettil

: Sharath Channageri

Revision Number : 1.1

Issue Date : May 7th 2002

Rev. Date: : Aug 23 , 2003 - RJL

Department Of Computer Science

University of Massachusetts

Lowell, MA – 01854

Document History

Rev	Date	Author	Comments
1.0	April 30 2002	Suren Karavettil Sharath Channageri	Initial Draft
1.1	May 6, 2002		Updated
1.2	Aug 23, 2003	R Lechner	Slight revisions to clarify material.

Preface

This project presents the design & implementation of the hominoid game in different phases using GEN, BDE & LCP architecture as a part of our OOAD course requirement.

We whole heartedly thank Prof. Lechner and the teams involved in the development of GEN, BDE & LCP tools in providing us this opportunity to use them and understand the concepts of OOAD & project implementation.

Table of Contents

1. Introduction

1.1 Purpose

1.2 Scope

1.3 Acronyms and Abbreviations

2. Project Description

2.1 Navigation Algorithm

2.2 Hominoid Grid Path

3 Diagrams

3.1. UML Class Diagram

3.1.1. Hominoid state model life cycle prototyping

3.1.2. Hominoid with BDE representation

3.2. Object Communication Diagram

3.3. Sequence Diagram

3.3.1. Sequence Diagram based on Navigation Algorithm

3.3.2. Sequence Diagram based on State Model

3.4. State Diagram

3.4.1. Sub State Model (SM) Diagram for Direction

3.4.2. Sub State Model (SM) Diagram for Location

4. Tools Requirements

5. Document and Text Requirements

6. BDE implementation

Appendix A Source Code

Appendix B Schema

Appendix C View Definitions

Appendix D Make file

Appendix E Test Data Input / Output

Appendix F Script Output

Introduction

This document describes design specification and implementation of Hominoid Game using State Model representation, Life Cycle Prototyping (LCP), Block diagram Editor (BDE) and CHGEN. In this game a hominoid is placed on to a starting grid cell and it should find its way to the end cell to win the game. It can choose any desired path on the grid searching for the end cell.

1.1 Purpose

The purpose of this document is to specify the design considerations for Implementation of Hominoid Game using State Model representation. It also gives information about what to expect from the game and how it is played.

1.2 Scope

This document contains information to code the Hominoid Game. It specifies the navigation algorithm design and implementation. It also gives us information about the design implementations using Life cycle prototyping and block diagram editor.

1.3 Acronyms and Abbreviations

BDE: Block Diagram Editor

LCP: Life cycle Prototyping
GEN: Schema Generator


HD: Hominoid Direction
LH: Hominoid Location
GR: Grid
SQ: Square	SM: State Model
	AC: Active Class
	AI: Active Instance
HG: Hgraph	ST: State
HN: Hnode	TR: Transition
HL: Hominoid Location	ET: Event Type
HA: Hominoid Attribute	EN: Event Enabling
CG: Graph Caption	EI: Event Instance
GX: Graph Text

2 Project Description

The objective of this project is to design and develop the Hominoid game in multiple phases. The phases of development includes generating the ERD model (schema) for the game using chgen. The development using this schema definition along with the schemas for the BDE & LCP encompass the next two phases. In all we have tried to address the complete software development life cycle, starting from analysis through the static model to the dynamics of the game. The design includes the static (ERD/Class Diagram) and dynamic (OCD & Sequence Diagrams) view of the game.

During the process of implementation we addressed the pre and post conditions that controls the movement of the hominoid (Robot) with in the specified grid cells.

Pre & Post Conditions:

1. Enter dimension of Grid

2. Enter start and finish positions.

3. If the start and finish points are the same make sure you don’t finish right away.

4. All except the path is a wall, it includes even outside the dimension of the grid (boundary conditions).

5. Hominoid can move only one cell at a time in any direction.

The development phase that integrated the hominoid schema with BDE schema provided a log output that can then be used for BDE replay that would visually show the movement of the hominoid in BDE. The development phase that integrated the hominoid schema with the LCP schema also produced the similar log output that can be used for BDE replay. But the latter used the state transition model to provide the implementation for the same.

2.1 Navigation Algorithm

The hominoid game is based on the following navigation algorithm proposed by Meilir Page-Jones (FOOD in UML).

navigate(Hominoid hominoid)

{

// The hominoid begins to search and move within

// the grid path, initialize itself in the right direction first

while ( hominoid.isfacingWall ( ) )

hominoid.turnLeft ( );

// Algorithm:

while ((hominoid.getPosition() != grid.getFinishPosition())

{

// check if hominoid is facing the wall

if (hominoid.isFacingWall())

{

hominoid.turnLeft();

//display current direction of the Hominoid

if (hominoid.isFacingWall())

{

hominoid.turnRight();

//display current direction of the Hominoid

hominoid.turnRight();

//display current direction of the Hominoid

}

//now that its in correct direction, advance Hominoid by one cell.

hominoid.advance();

//display current position and direction of the Hominoid

}

Based on this algorithm recommended by Page-Jones, the hominoid always checks to see if its Facing Wall. If it faces the wall then it has option of turning left by 90 degrees. If it still faces the wall then it turns right twice. Once any of this is done then it is ready to advance (unless it has reached a dead end). This goes on until it reaches the destination.

2.2 Hominoid Grid Path Directions

The following diagram shows the (single) paths that the Hominoid could traverse to reach its destination. An arbitrary starting point and direction must also be defined. The objective is to return to the starting point.

(0,0)	(1,0)	(2,0)	(3,0)	(4,0)
(0,1)				(4,1)
(0,2)				(4,2)
(0,3)				(4,3)
(0,4)	(1,4)	(2,4)	(3,4)	(4,4)

Here are the start position <2,0> (top center) and subsequent positions for the hominoid traversal path. We can assume that the initial facing direction of the hominoid is <North>. The path followed by the hominoid is shown here below along with the path-assigner methods. Note how the state changes one component at a time and avoids advancing into a wall.

Sequence	State <X, Y, D>	Transition Method
1	<2,0,N> --Start	TurnLeft
2	<2,0,W>	Advance
3	<1,0,W>	Advance
4	<0,0,W>	TurnLeft
5	<0,0,S>	Advance
6	<0,1,S>	Advance
7	<0,2,S>	Advance
8	<0,3,S>	Advance
9	<0,4,S>	Turnleft
10	<0,4,E>	Advance
11	<1,4,E>	Advance
12	<2,4,E>	Advance
13	<3,4,E>	Advance
14	<4,4,E>	Turnleft
15	<4,4,N>	Advance
16	<4,3,N>	Advance
17	<4,2,N>	Advance
18	<4,1,N>	Advance
19	<4,0,N>	Turnleft
20	<4,0,W>	Advance
21	<3,0,W>	Advance
22	<2,0,W> --finish

3. Diagrams

3.1 UML Class Diagram

This section describes EERD (Class) diagrams used to define the static model representation of the entities involved in the course of the hominoid project.

3.1.1. Hominoid state model life cycle prototyping

The diagram above shows the static model for the integration of the Hominoid with the OLC architecture. This addresses the State Transition Model for the hominoid as it goes through the different states based on the events (TL, TR, AD). This model here represents Loosely-coupled Event-driven architecture. The events are generated based on the path assigner’s navigation algorithm and the action performed by the Hominoid in a given state. Note that there are two instances of the LH entity, one for X and one for Y,

This OLC architecture for the State Transition is based on the Moore model, the Action is performed when the Hominoid arrives at a particular State.

3.1.2. Hominoid representation with BDE

0..1

0..*

1..*

1..1

0..1

1..1

2..2

1..1

1..1

This ERD merges two sub-schemas with disjoint table-type acronyms to integrate the Hominoid view (PA, GR, SQ, HD, LH) with the BDE view. Here the Grid Squares (SQ) can have a relation to the BDE’s nodes (HN) on the graph (HG). The HA attribute gives the current location of hominoid as a HN and the current direction of HD. During the phase of the project we generated the log output indicating the various HA records that is possible based on the hominoid’s navigation algorithm. This output can be provided as input to the BDE replay that then displays the hominoid path graphically.

[RJL: This application can be generalized - e.g., let bde capture the sequence of moves made by the path assigner (or an operator who add links to traverse a maze), for later playback.. A maze requires path generation, which could be an offline program, sequential node creation editing process. Links that define an adjacency relation with a directional attribute can be used to regenerate the diagram of gridded cells from an abstract graph representation.]

3.2. Object communication Diagram

This object communication diagram for Hominoid project provides a graphical summary of event communication between state model types like HD and HL and entities like assigner PA. The events communicated to HD by PA are turnleft( ) turnright( ) and advance( ). These are dealt as event communication between two subsystems. HD actions generate increment ( ) and decrement ( ) events to two separate 'Active Instances' of the HL state model .

3.3. Sequence Diagram

3.3.1. Sequence Diagram based on Navigation Algorithm

The interaction between the objects emphasizes the temporal sequence over static object relationships. The body of the diagram shows the activated operations, sized to reflect their approximate duration. Here the time increases downward along the vertical axis, and the list of objects that will receive messages extends along the horizontal axis.

3.3.2. Sequence Diagram based on state model

The sequence diagram based on state model is as shown above. Here the horizontal axis represents the list of objects (PA, HD, HX, HY, GD) that will receive messages. The transition message received are advance( ), turnleft( ), turnright( ), increment( ) and decrement( ). The vertical axis shows the X,Y co-ordinates along with the direction <D>.

3.4. State Diagrams

3.4.1. Sub State Model (SM) Diagram for Direction

The diagram shown below represents state transition sub diagram for hominoids location component. There exists two such state models for X and Y. Only one counter can change at a time, neither x nor y changes when the direction changes. And this has to respect the boundary conditions.

3.4.2 Sub State Model (SM) Diagram for Direction

The sub-state model diagram above represents the different states for the direction and their transitions based on the events TL, TR and AD. Here EAST = 0, NORTH = 1, WEST = 2 and SOUTH = 3 represents the different states.

4. Tools Requirements

LCP stands for Life Cycle Prototyping

LCP is a generic table-driven State Model (SM) interpreter which simulates concurrent event-driven behavioral prototypes. Its State-Event Model inputs represent Active Classes.

BDE stands for Block Diagram Editor

BDE is a generic diagram editor. Historically, BDE evolved first as a C program interfaced to INGRES It ran under Unix and used X11/Motif as its GUI. Then BDE was rewritten in C++ and was adapted to take advantage of GEN.

GEN stands for database code GENerator

GEN supplies database code libraries by which BDE and LCP can import/export, maintain and navigate an arbitrary normalized EERD database.

Description

All three tools read ASCII-text-based tables that can be manually text-edited and converted to EERD or State-Event Model (SM) diagrams for BDE display. However, BDE simplifies the use of GEN and LCP because users can draw block diagrams (static information models and dynamic behavior models) interactively and save them in a persistent relational database as ASCII text. These tables subsume graphic layout information as well as semantics of user-defined types.

BDE and LCP both take advantage of customized GEN-supplied code libraries which can import/export, maintain and navigate tables of an arbitrary normalized relational data model. A GEN-supported database application maintains surrogate primary/foreign (p/f) keys to simplify access.

5. Document and Text Requirements

· Meilir Page-Jones: "Fundamentals of OO Design in UML", A-W 2000

· Shlaer & Mellor: "Object Life Cycles: Modeling the World in States", P-H 1992

· Sanders: "Data Modeling", B-F/Thompson 1995

· CHGEN Reference Manual

· CHGEN Version - ‘/usr/proj3/case/gen/ver_12/sjaganat/executables/alpha/chgen12’

· OLC Code $CASE/95s522/95solc/JPsim/olc

· Block Diagram Editor User guide 2k0504/ 2k0606

· Block Diagram Editor Source code for BDE Replay –‘/usr/cs/fac1/lechner/bde2alpha_rl/sandbox/bde/src’

BDE Implementation

The following enclosed code has to be integrated with the hominoid project described above to enable BDE to replay the hominoid path. In the log output that is generated we have command "SR" which is a pre-condition verified by pr_load.

Steps to follow:

1. bde.cc has the main() where the control flow starts which invokes init()

int main (unsigned int argc, char **argv) //logHMSM.txt as input file

2. init.cc has the method init() that takes the input log file that was given in CmdLine.

void init(unsigned int argc, char **argv)

3. This then setups the callback function Keypress(..) event from fileio.cc

void Keypress(Widget w, XtPointer input, XEvent *event, Boolean *continue_dispatch)

4. fileio.cc has a Keypress() callback routine that calls replay_log()

int replay_log(void); //in bdereplay.cc

5. replay_log() looks for the command SR that makes sure that this file can be loaded. Once SR is identified it can do the replay.

6. The HA attributes in the log are then read next one after the other which helps to move the Hominoid from one state to the next. This is because after the SR command there exists a WA command (Wait) that controls read speed for the log file for HA’s.

void encode_token(char *token, int *command)

32-bit to 64-bit pointer resolution for State Functions

During the first implementation of the hominoid project using OLC the function for the state were resolved in a very simple manner. By having this method & its prototype and then invoking this from the DoTransition method of the Processevent.c

FUNCTION(void StateFunctionMapper)

{

if (strcmp("EAST", StateGetName(STid)) == 0) {

HdAction0(EIid);

} else if (strcmp("NORTH", StateGetName(STid)) == 0) {

HdAction1(EIid);

} else if (strcmp("WEST", StateGetName(STid)) == 0) {

HdAction2(EIid);

} else if (strcmp("SOUTH", StateGetName(STid)) == 0) {

HdAction3(EIid);

} else if (strcmp("0", StateGetName(STid)) == 0) {

HlAction0(EIid);

} else if (strcmp("1", StateGetName(STid)) == 0) {

HlAction1(EIid);

} else if (strcmp("2", StateGetName(STid)) == 0) {

HlAction2(EIid);

} else if (strcmp("3", StateGetName(STid)) == 0) {

HlAction3(EIid);

} else if (strcmp("4", StateGetName(STid)) == 0) {

HlAction4(EIid);

}

There are several other means to resolve this issue. One of which is to have another i4 field inside the ST table schema.

State ST /* states */

{

STid StateId c8 1 /* the primary key */

SMid StateAStateOfThisStateMachine c8 1 /* The state machine*/

ActName StatesActionRoutineName t32 0 /*Action RoutineName*/

ActFunc StatesActionRoutinePointerLSB i4 0 /*C pointerto fun*/

ActFunc1 StatesActionRoutinePointerMSB i4 0 /*C ptr to fun*/

Name StatesName t80 0 /* The name of state*/

}

Here ActFunc1 is the additional variable. Then StateFunctionMapper() is modified to handle the two I4 fields.

The processevent.c has the DoTransition method modified to be as shown below

LSB = (unsigned int)StateGetActFunc(STid);

MSB = (unsigned int) StateGetActFunc1(STid); //this methods are defined in state.c as macros

actionRoutinePtr = MSB;

actionRoutinePtr = (actionRoutinePtr | LSB);

actionRoutine = (ActionRoutine *)actionRoutinePtr; //thus now the ptr is 64-bit

FUNCTION(void StateFunctionMapper)

{

unsigned long sarPtr = 0;

table_loop("HMSMView", ST)

{

if (strcmp("EAST", STcurr->Name) == 0) {

sarPtr = (unsigned long)HdAction0;

printf("HdAction0 Ptr : %x\n", sarPtr);