Transcript Software project Robot Simulation

Robots Battle Project
The project consists of two major parts:
• Parse the robot strategy files
• Simulate the robots battle main flow
–
–
–
–
–
Execute robot strategy
Events
Animation (Interpolation)
Game Rules
Output Results
The Simulator System Diagram
Report error
Exit
Input:
Robot programs
Already
Supplied
Parse
Internal
representation
Simulator
Graphic output
Winner
Lexemes Tokens
• Define the strategy available tokens
For example “TURN” , “ASSIGN”,”PLUS”
etc.
• You need to produce a well known defined
tokens stream as input for the parsing
process.
Parsing
• Parse is one of the major task in the project.
• Use good design in order to make your task
easier.
• Before parsing, you need to lexical analyze the
strategy file to produce a well known tokens
(lexemes)
• The parsing process will convert the tokens
stream into some internal representation.
• A design proposal will presented next.
Design hints (major modules)
• Lexical analyzer
– Input program (ascii)
 tokens
Lexical analyzer
Lexemes
• Parser
– Tokens  Code
• Simulator
Parser
Code
– Code  actions
Simulator
Lexical analyzer
Lex.str
ComputeDistance
{
$x2 = $x * $x
print(“Hello world”)
exit()
}
Lexemes Stream
Lexeme
Value
NAME
ComputeDistance
CURLY_OPEN
VARIABLE
OP_EQUALS
VARIABLE
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
Tokens.h
NAME 1
OP_PLUS 2
OP_TIMES 3
PRINT 4
STOP 5
OPEN 6
CLOSE 7
CURLY_OPEN 8
CURLY CLOSE 9
VARIABLE 10
x2
x
OP_TIMES
VARIABLE
x
PRINT
OPEN
STRING
CLOSE
EXIT
OPEN
CLOSE
CURLY_CLOSE
Hello World
Parsing
• Input a “token’s stream”
• Examine the validity of
the program
• Produce code
Parse.str
ParseSample
{
$x=7
$x2 = $x * $x
$tmp = $x2 > 100
Turn(10)
Move($x2)
}
#
1
2
3
4
5
6
#define
#define
#define
#define
#define
#define
...
Command
Assign
AssignExp
AssignExp
Turn
Move
Return
Commands.h
ASSIGN 1
ASSIGNEXP 2
TURN 3
MOVE 4
RETURN 5
IF 6
P1
$x
TIMES
GREATER
10
$x2
P2
P3 P4
7
$x2 $x $x
$tmp $x2 100
Next
2
3
4
5
6
-1
Parsing if
ParseIf.str
ParseIfSample
{
$x=7
$x2 = $x * $x
$tmp = $x2 > 100
if $tmp
Fire()
endif
print(“Done”)
}
#
1
2
3
4
5
6
7
Command
Assign
AssignExp
AssignExp
If
Fire
PrintString
Return
P1
$x
TIMES
GREATER
$tmp
“Done”
P3
P2
7
$x2 $x
$tmp $x2
6
P4
Next
2
$x
3
100
4
5
6
7
-1
Parsing While
ParseSample
{
$x=7
while $x
$x=$x-1
endwhile
return
}
ParseWhile.str
#
1
2
3
4
Command
Assign
while
AssignExp
Return
P1
$x
$x
MINUS
P2
7
4
$x
P3
P4
$x
1
Next
2
3
2
-1
Parsing function call
Sqr
{
$y=x*x
}
ParseSample
{
$x=7
Sqr()
print($y)
}
ParseFunc.str
#
1
2
3
4
5
6
Command P1
Assign
TIMES
Return
Assign
$x
Call
1
PrintExp $y
Return
Function
Sqr
ParseSample
P2
$y
P3
$x
7
Line
1
3
P4
$x
Next
2
-1
4
5
6
-1
System Simulator
• Main purpose is to simulate the battle flow.
• Execute robots strategy files.
• Simulate motion animation (laser beam,
robots).
• Manage the event system.
Identify the event and call to the relevant
routine handling.
Main Game Loop
• Infinite loop which called every
CLOCK_PER_SECOND_TICK
• Execute robots programs
• Manage the game rules
• Manages the motions of the game
– Collision
– Position
– Events
Main Game Loop Pseudo Code
main loop
tick=1
Forever
For each robot
Execute one instruction
Move robot (If needed)
Move laser beam (If needed)
Check collision, end game?, events calling
Render Scene
++tick
Motion Interpolation
• In order to simulate the motion of the robots and the
laser beam you need to use linear interpolation as
follows:
#define MOVE_SPEED_FACTOR //number of pixels for each tick
#define MOVE_TIME_STEPS(d) 1.0/d * MOVE_SPEED_FACTOR
// center coordinates of the robot
StartPositionX = Robot.x
StartPositionY = Robot.y
// (X,Y) destination coordinates after moving by dist with
//respect to the (0,0)
dest_X = dist*sin(robot.direction*PI/180)
dest_Y = dist*cos(robot.direction*PI/180)
time = [0.0,1.0]
While(time < 1){
time += MOVE_TIME_STEPS(dist)
Robot.x = StartPositionX + dest_X * time
Robot.y = StartPositionY + dest_Y * time
}
Interpolation
T = 1.0
T = 0.5
T = 0.0
Distance To Travel
Software engineering
•
•
•
•
•
•
Modularity
Functionality
Documentation
Naming convention
Data structures
Design-Implement-Test
bad.c
Functionality
• Functions do one “thing”
• Repeated code is a
function
• The name of the function
should be self
explanatory
• Functions are typically
short < 60 lines
• Line length should be <=
80 characters
void fndel(void* item)
{
node* p = root;
while (item != p->value)
p = p->next;
if (p != NULL)
{
p->next->prev = p->prev;
p->prev->next = p->next;
free(p);
}
}
good.c
void RemoveItem(void* item)
{
node* ItemsNode = Find(item);
if (ItemsNode != NULL)
{
Delete(ItemsNode);
}
}
Naming and Documentation
documentation.c
• Document by writing
“good” code
– Naming convention
– Meaningful names
– Simple and working
code
• Remarks when
appropriate
– Module header
– Function header
– Special parts of code
/*
* Description:
*
Search the list for the
*
input item and delete it
*
if the item is in the list
* Input:
*
item - to look for and
*
delete.
* Remarks:
*
May change root to NULL if
*
the list contains one item.
*/
void RemoveItem(void* item)
{
node* ItemsNode = Find(item)
if (ItemsNode != NULL)
{
Delete(ItemsNode);
}
}
Simple Code
unreadable.c
• Simple - working code
is preferable.
– Less bugs
– Easy for others to read
– Easy to maintain
void strcpy(char* d, char* s)
{
for (;*d++=*s++;);
}
simple.c
void strcpy(char* d, char* s)
{
int i;
for (i=0; s[i] != ‘\0’; ++i)
d[i] = s[i];
d[i] = ‘\0’;
}
Modularity
• A set of functions that manage
one entity
Error
handling
Graphics
– List (data structure)
– Parser
• Purpose:
– Design tool, divide a difficult
(large) problem to easier and
smaller problems
– Distribute work among team
members
– No code duplication
• Less code
• Fix a bug in one place
• Ability to change design and
improve incrementally
– Code re-use by writing
standalone modules
Lexical
analyzer
List
Parser
Simulator
Hash
Modularity
Implementation
1. .h module interface
• Data structures of the module that the user uses
• Function prototypes
• Constants
2. .cpp implementation
• Implementation of the functions that were
defined in the .h
• Prototypes, functions and constants that are
internal to the module
Modularity - implementation
#ifndef __MYLIST_H
#define __MYLIST_H
list.h
typedef struct _List
{
struct _List *next;
void *data;
} List;
List* NewList();
void ListInsert(List* head, void
*item);
#include “list.h”
list.c
/*
* Allocates and prepares a new
* list.
* Return: NULL in case of an error
* or a pointer to the head of
* the list.
*/
List* NewList()
{
List* new_list;
new_list=malloc(sizeof(LIST));
void ListDelete(List* head);
if (new_list == NULL)
return NULL;
#endif /* __MYLIST_H */
new_list->next = NULL;
new_list->data = NULL;
return new_list;
}
ds.c
{
Data Structures ...Node* new;
Should be:
• Generic
• Handled through
functions that
manipulate them.
new = malloc(sizeof(Node));
new->item = item;
new->next = list->root
list->root = new;
...
new = malloc(sizeof(Node));
new->item = item2;
new->next = list->root
list->root = new;
}
ds-function.c
{
...
ListInsert(list, item);
...
ListInsert(list, item2);
}
Design-Implement-Test
Design
Implement
• Spend time on design
before starting to code.
• Leave enough time for
debugging and
unexpected design flaws.
Test/
Debug
Suggested schedule
•
•
•
•
•
Design
Implement
integration (port)
Testing
Write Documentation
• Total
1w
4w
2w
2w
[2w] In parallel
------9w
Asserts
array1.c
/*
* Description:
*
Set an array value
* Input:
*
array - pointer to the
*
“array structure”
*
item - to insert
*
* NOTES:
*
assume the position is
*
valid
*/
void Insert(ARRAY* a, int
position, void* item)
{
assert(position >= 0);
assert(position < a->size);
a->data[position] = item;
}
array2.c
/*
* Description:
*
Set an array value
* Input:
*
array - pointer to the array
*
structure
*
item - to insert
*
* NOTES:
*
validate that the position
*
is valid
*/
void Insert(ARRAY* a, int
position, void* item)
{
if ( (position >= 0) &&
(position < a->size) )
{
a->data[position] = item;
}
}
How to use asserts
• For every parameter of a function
– assert (parameter meets assumption)
• For every call to a function
– assert(result meets assumptinos)
• Validate results of computations
• Validate access to NULL points
Using global variables
FileManager.c
#include “FileManager.h”
FilesList* files;
...
FileManager.h
#ifndef __FILEMANAGER_H
#define __FILEMANAGER_H
typedef struct _FilesList
{
. . .
} FilesList;
Process.c
#include “FileManager.h”
{
...
Write(files, 1, data);
...
}
extern FilesList* files;
#endif /* __FILEMANAGER_H */
Common pitfalls
• Plan your time
– Start working early (now)
• Test your project
– Try testing individual modules
Partners
• Choose a partner you can work with
• Meet every week or so
– See you’re both on track
– Things change: synchronize
Unix tools
• Editors:
– emacs
– vi
– pico (easier to learn)
• Development environment
– kdevelop
• Debuggers all based on gdb
– gdb: command line debuger
– ddd: gui to gdb
• Help
– info or tkinfo
– man pages