-
Notifications
You must be signed in to change notification settings - Fork 2
/
README
197 lines (153 loc) · 8.88 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
Asteroids Game
==============
Implementing lab 3 of chapter 12 of Head First C.
Dependencies
============
Allegro v5.0.x
GNU compatible make
gcc
Optional
--------
astyle for source formatting
ctags for generating TAG files
Building
========
make && ./asteroids
Controls
========
Movement with the arrow keys. Space to shoot. Escape to pause.
Implementation
==============
Game - game.{c,h}
-----------------
The Game type contains either the value of, or references to the state of the
game. For explanation of how the asteroids, particlemanager, ship and
bulletmanager fields work, see their respective explanations below.
The size field is the size of the display screen. This is set when the
ALLEGRO_EVENT_DISPLAY_RESIZE event is caught from allegro.
The rest of the game module is best discussed in the same context as the main
function (in main.c). All input is in terms of events, other than keyboard input
which is checked each frame. The structure goes something like this:
1) The main function catches events
2) Events are then passed to handler functions in the game module. i.e.
handle_key_status, handle_key_event, update_game
3) Handler functions then dispatch to other functions based on game state. i.e.
draw_paused when game->status == Paused, update_asteroids when
game->status == Playing
4) When all events have been handled or ignored and the game state fully
updated, the game is drawn to the screen via draw_game
Asteroid - asteroid.{c,h}
-------------------------
Asteroids are implemented as non-concave non-regular dodecagons. The position of
an asteroid is represented by the "center" vector, with the vertexes being
stored as vectors relative to the center. For this reason, "center" is a mostly
meaningless name; the "center" is simply a point in the asteroid. The vertexes
do not change after the asteroid has been created, so we keep the angle that the
asteroid is rotating at in a seperate field "angle". This means we can use a
matrix transformation to rotate the points at the time of drawing; the fact that
the Allegro library supplies such functionality makes this much easier than
rotating the verticies manually each frame. There is also a "direction" field
which stores the Asteroid's velocity. This is added to the "center" value every
time the asteroid is updated.
The asteroid also has an "invincible" field. If this value is non-zero, then the
asteroid is said to be invincible, i.e. bullets do not destroy it. This was
implemented to stop more than one bullet fired in rapid succession destroying an
asteroid and all of it's children, instead of just the asteroid that was
initially hit. The "generation" field is how many times asteroids have been
split to reach the current asteroid, i.e. when the game starts, all asteroids
are gen0, when one is hit, two new asteroids are made with gen1. When an
asteroid is hit with generation > MAX_GENERATION, no new asteroids are created.
Collision detection against asteroids is done in the function
`bool point_in_asteroid(Vector, Asteroid*)`. Collision detection is done in two
parts:
1) Rough detection
To save the overhead of doing full detection, we do rough detection,
treating the asteroid as a circle. This is where the "radius_squared"
field of the asteroid comes into play. The radius_squared of the asteroid is
the largest distance from the center to a vertex, squared. This means that
we can check if the point is in the rough area of the asteroid very quickly;
calculating the magnitude squared of a vector is very cheap. However, it is
not precise; modeling asteroids as circles is hardly perfect.
2) Precise detection
If a point passes rough detection, we do precise detection. This is done by
splitting the asteroid into a series of triangles between the center, and
two adjecent vertexes. We then check that the point does not collide with
any of the triangles. This is done by converting the point (relative to a
vertex) into barycentric coordinates, which allow us to very simply check if
the point is within the triangle. I learnt this technique from the following
webpage: http://www.blackpawn.com/texts/pointinpoly/default.html
As we need to create and delete many asteroids, and access them only
sequentially, a linked list makes sense. The linked list is not intrusive, and
is implemented in the `AsteroidNode` struct. It is doubly linked, and really
very simple. Several functions are provided that work on the list type:
-) `bool is_list_consistent(AsteroidNode*)`
This function checks for basic consistency. Mostly that node->next->prev ==
node and similar invariants.
-) `void insert_in_asteroid_list(AsteroidNode**, AsteroidNode*)` and
`void remove_from_asteroid_list(AsteroidNode**, AsteroidNode*)`
Inserts the node in the list. The list is represented as an AsteroidNode**
as if the list is empty, a pointer to NULL will be passed as the first
paramater, and we need to be able to change the reference, not just the
value.
-) `int count_asteroids(AsteroidNode*)`
Returns the length of the asteroid list. O(n) performance.
-) `AsteroidNode* point_collides(AsteroidNode*, Vector)`
While this function may seem a little less independant than the other
functions, this simply maps collision detection over the list, and
returns the first node that collides. The AsteroidNode* is returned rather
than the Asteroid as we do not want to have to traverse the list again to
find the collides AsteroidNode to remove it, and giving our algorithm
potentially quadratic performance.
Gameplay functions are a little more interwined with the rest of the game,
however there is still a certain amount of independant work to be done.
The "entry" function is `void update_asteroid(AsteroidNode*, Vector)`. This
function is called every frame, and updates the asteroid positions and angles,
and decrements the invicible counter where neccissary. The Vector argument
passed is the size of the screen; the size may change midway through the game
and I thought it best not to rely on global state to pass the information. The
information is needed as asteroid's positions cannot be off the screen; we use
the wrap function provided by the vector library to do this.
There is one other function that implements game logic:
`void split_asteroid(AsteroidNode**, AsteroidNode*)`. This is called when a
bullet hits an asteroid, and the hit asteroid must be deleted, and two new
asteroids created. The asteroid list is also required to deal with the case that
there is only one asteroid on the screen, and no new asteroids are to be
created, in which case the asteroid list must be set to NULL.
`void draw_asteroids(AsteroidNode*)` simply maps through the asteroids and
draws them to the screen with the correct roation, position etc.
Ship - ship.{c,h}
-----------------
The ship has a position, a velocity and an angle. This allows for the classic
asteroids style of movement, where we can turn and accellerate fluidly. It
also has an "invincible" field which serves a purpose similar to the invincible
field on the Asteroid type.
Particles - particles.{c,h}
---------------------------
The particle manager is simply an array of particles and a "current_frame"
value. The current_frame field is used as a reference for the age of the
particle, i.e. when a new particle is created, the "created" field is set to
the manager's current_frame value. The rest of the manager is pretty self
explanitory. The only interesting function is
`void add_particle(ParticleManager*, Vector, Vector, uint)`. To avoid allocation
of memory for every new particle created (as allocation is slow and new
particles generally come in bursts), we use a fixed size array, and then replace
the first "dead" particle we find, or otherwise the oldest particle. This allows
us to always add a particle, no matter the number of particles already on
screen, as old particles will be "deleted" first.
Bullets - bullet.{c,h}
----------------------
The bullet manager is implemented as a layer over a particle manager. We limit
the rate of fire of the ship by setting the last_shot field to the current_frame
field of the particle manager every time we emit a bullet, and then if we are
asked to emit a bullet before the SHOT_DELAY has passed, we simply ignore it.
The bullet manager also has a function
`AsteroidNode* bullet_hit(BulletManager*, AsteroidNode*)` which returns the
asteroid hit by a bullet if any, and NULL otherwise.
Vector - vector.{c,h}
---------------------
All of the collision detection mathematics is based on vectors, and having a
vector type makes managing positions and velocities very easy. The vector
library implements all of the basic operations on vectors; addition,
subtraction, scalar multiplication, dot and cross product. It also adds some
less mathmatical operations, such as wrap and rotate. The in_triangle function
implements the triangle collision detection discussed in the Asteroids section.