#include <stdlib.h>
#include <string.h>
+#include "common.h"
#include "config.h"
#include "file.h"
#include "globals.h"
+#include "mt.h"
#include "rocks.h"
-#include "shape.h"
-struct rock_struct {
- float x,y,dx,dy;
- int active;
- SDL_Surface *image;
- struct shape *shape;
- int type_number;
-};
+struct rock rocks[MAXROCKS], *free_rocks;
-struct rock_struct rock[MAXROCKS], *rockptr = rock;
+struct rock **rock_buckets[2];
+int n_buckets;
+// we have two sets of buckets -- this variable tells which we are using.
+int p;
+int bw, bh;
+int grid_size;
-SDL_Surface *surf_rock[NROCKS];
-struct shape rock_shapes[NROCKS];
+static struct rock prototypes[NROCKS];
// timers for rock generation.
-float rtimers[4];
-
-uint32_t rcnt;
+static float rtimers[4];
uint32_t nrocks;
-uint32_t nrocks_timer;
-uint32_t nrocks_inc_ticks = 2*60*1000/(F_ROCKS-I_ROCKS);
+float nrocks_timer;
+float nrocks_inc_ticks = 2*60*20/(F_ROCKS-I_ROCKS);
// constants for rock generation.
-#define KH 32.0 // 32 s for a speed=1 rock to cross the screen horizontally.
-#define KV 24.0 // 24 s for a speed=1 rock to cross the screen vertically.
+#define KH (32*20) // 32 s for a speed=1 rock to cross the screen horizontally.
+#define KV (24*20) // 24 s for a speed=1 rock to cross the screen vertically.
#define RDX 2.5 // range for rock dx values (+/-)
#define RDY 2.5 // range for rock dy values (+/-)
-float rnd(void);
-
-#define crnd() (2*(rnd()-0.5))
-
-
-int
-init_rocks(void)
+static inline struct rock **
+bucket(int x, int y, int p)
{
- int i;
- char a[MAX_PATH_LEN];
- SDL_Surface *temp;
+ int b = (x+grid_size)/grid_size + bw*((y+grid_size)/grid_size);
+ return &rock_buckets[p][b];
+}
- for(i = 0; i<NROCKS; i++) {
- snprintf(a,MAX_PATH_LEN,add_path("sprites/rock%02d.png"),i);
- NULLERROR(temp = IMG_Load(a));
- NULLERROR(surf_rock[i] = SDL_DisplayFormat(temp));
- get_shape(surf_rock[i], &rock_shapes[i]);
+void
+init_buckets(void)
+{
+ int scr_grid_w = (XSIZE+2*grid_size-1) / grid_size;
+ int scr_grid_h = (YSIZE+2*grid_size-1) / grid_size;
+ bw = 1 + scr_grid_w + 1;
+ bh = 1 + scr_grid_h + 1;
+ n_buckets = bw * bh;
+
+ rock_buckets[0] = malloc(n_buckets * sizeof(struct rock *));
+ rock_buckets[1] = malloc(n_buckets * sizeof(struct rock *));
+ if(!rock_buckets[0] || !rock_buckets[1]) {
+ fprintf(stderr, "Can't allocate rock buckets.\n");
+ exit(1);
}
- return 0;
+ p = 0;
+}
+
+void
+transfer_rock(struct rock *r, struct rock **from, struct rock **to)
+{
+ *from = r->next;
+ r->next = *to;
+ *to = r;
}
void
{
int i;
- for(i = 0; i<MAXROCKS; i++) rock[i].active = 0;
+ for(i=0; i<MAXROCKS; i++) rocks[i].image = NULL;
+
+ rocks[0].next = NULL;
+ for(i=1; i<MAXROCKS; i++) rocks[i].next = &rocks[i-1];
+ free_rocks = &rocks[MAXROCKS-1];
+
+ for(i = 0; i<n_buckets; i++) {
+ rock_buckets[0][i] = NULL;
+ rock_buckets[1][i] = NULL;
+ }
+
nrocks = I_ROCKS;
nrocks_timer = 0;
- rcnt = 0;
}
-enum { LEFT, RIGHT, TOP, BOTTOM };
+#define ROCK_LEN sizeof("sprites/rockXX.png")
+
+int
+init_rocks(void)
+{
+ int i;
+ char a[ROCK_LEN];
+ int maxw=0, maxh=0;
+
+ for(i = 0; i<NROCKS; i++) {
+ snprintf(a, ROCK_LEN, "sprites/rock%02d.png", i);
+ load_sprite(SPRITE(&prototypes[i]), a);
+ maxw = max(maxw, prototypes[i].w);
+ maxh = max(maxh, prototypes[i].h);
+ }
+ grid_size = max(maxw, maxh) * 3 / 2;
+ init_buckets();
+ reset_rocks();
+ return 0;
+}
+enum { LEFT, RIGHT, TOP, BOTTOM };
-// compute the number of rocks/seccond that should be coming from each side
-// compute the speed ranges of rocks coming from each side
+// compute the number of rocks/tick that should be coming from each side,
+// and the speed ranges of rocks coming from each side
void
rock_sides(float *ti, float *speed_min, float *speed_max)
{
for(i=0; i<4; i++) ti[i] = 0;
for(i=0; i<4; i++) speed_min[i] = 0;
for(i=0; i<4; i++) speed_max[i] = 0;
- hfactor = nrocks/KH; vfactor = nrocks/KV;
+ hfactor = (float)nrocks/KH; vfactor = (float)nrocks/KV;
dx0 = -RDX - screendx; dx1 = RDX - screendx;
dy0 = -RDY - screendy; dy1 = RDY - screendy;
- if(dx0 != 0) {
- if(dx0 < 0) {
- speed_max[RIGHT] = -dx0;
- if(dx1 < 0) {
- // Rocks moving left only. So the RIGHT side of the screen
- speed_min[RIGHT] = -dx1;
- ti[RIGHT] = -(dx0+dx1)/2;
- } else {
- // Rocks moving left and right
- speed_max[LEFT] = dx1;
- ti[RIGHT] = -dx0/2;
- ti[LEFT] = dx1/2;
- }
+ if(dx0 < 0) {
+ speed_max[RIGHT] = -dx0;
+ if(dx1 < 0) {
+ // Rocks moving left only. So the RIGHT side of the screen
+ speed_min[RIGHT] = -dx1;
+ ti[RIGHT] = -(dx0+dx1)/2;
} else {
- // Rocks moving right only. So the LEFT side of the screen
- speed_min[LEFT] = dx0;
+ // Rocks moving left and right
speed_max[LEFT] = dx1;
- ti[LEFT] = (dx0+dx1)/2;
+ ti[RIGHT] = -dx0/2;
+ ti[LEFT] = dx1/2;
}
+ } else {
+ // Rocks moving right only. So the LEFT side of the screen
+ speed_min[LEFT] = dx0;
+ speed_max[LEFT] = dx1;
+ ti[LEFT] = (dx0+dx1)/2;
}
ti[LEFT] *= hfactor;
ti[RIGHT] *= hfactor;
- if(dy0 != 0) {
- if(dy0 < 0) {
- speed_max[BOTTOM] = -dy0;
- if(dy1 < 0) {
- // Rocks moving up only. So the BOTTOM of the screen
- speed_min[BOTTOM] = -dy1;
- ti[BOTTOM] = -(dy0+dy1)/2;
- } else {
- // Rocks moving up and down
- speed_max[TOP] = dy1;
- ti[BOTTOM] = -dy0/2;
- ti[TOP] = dy1/2;
- }
+ if(dy0 < 0) {
+ speed_max[BOTTOM] = -dy0;
+ if(dy1 < 0) {
+ // Rocks moving up only. So the BOTTOM of the screen
+ speed_min[BOTTOM] = -dy1;
+ ti[BOTTOM] = -(dy0+dy1)/2;
} else {
- // Rocks moving down only. so the TOP of the screen
- speed_min[TOP] = dy0;
+ // Rocks moving up and down
speed_max[TOP] = dy1;
- ti[TOP] = (dy0+dy1)/2;
+ ti[BOTTOM] = -dy0/2;
+ ti[TOP] = dy1/2;
}
+ } else {
+ // Rocks moving down only. so the TOP of the screen
+ speed_min[TOP] = dy0;
+ speed_max[TOP] = dy1;
+ ti[TOP] = (dy0+dy1)/2;
}
ti[TOP] *= vfactor;
ti[BOTTOM] *= vfactor;
float
weighted_rnd_range(float min, float max) {
- return sqrt(min * min + rnd() * (max * max - min * min));
+ return sqrt(min * min + frnd() * (max * max - min * min));
}
void
new_rocks(void)
{
- int i,j;
+ int i, type;
+ struct rock *r, **tmp;
float ti[4];
float rmin[4];
float rmax[4];
if(nrocks < F_ROCKS) {
- nrocks_timer += ticks_since_last;
+ nrocks_timer += t_frame;
if(nrocks_timer >= nrocks_inc_ticks) {
nrocks_timer -= nrocks_inc_ticks;
nrocks++;
rock_sides(ti, rmin, rmax);
- // loop through the four sides of the screen
+ // increment timers
+ for(i=0; i<4; i++) rtimers[i] += ti[i]*t_frame;
+
+ // generate rocks
for(i=0; i<4; i++) {
- // see if we generate a rock for this side this frame
- rtimers[i] += ti[i]*gamerate/20;
while(rtimers[i] >= 1) {
rtimers[i] -= 1;
- j=0;
- while(rockptr->active && j<MAXROCKS) {
- if(++rockptr - rock >= MAXROCKS) rockptr = rock;
- j++;
- }
- if(!rockptr->active) {
- rockptr->type_number = random() % NROCKS;
- rockptr->image = surf_rock[rockptr->type_number];
- rockptr->shape = &rock_shapes[rockptr->type_number];
- switch(i) {
- case RIGHT:
- rockptr->x = XSIZE;
- rockptr->y = rnd()*(YSIZE + rockptr->image->h);
-
- rockptr->dx = -weighted_rnd_range(rmin[i], rmax[i]) + screendx;
- rockptr->dy = RDY*crnd();
- break;
- case LEFT:
- rockptr->x = -rockptr->image->w;
- rockptr->y = rnd()*(YSIZE + rockptr->image->h);
-
- rockptr->dx = weighted_rnd_range(rmin[i], rmax[i]) + screendx;
- rockptr->dy = RDY*crnd();
- break;
- case BOTTOM:
- rockptr->x = rnd()*(XSIZE + rockptr->image->w);
- rockptr->y = YSIZE;
-
- rockptr->dx = RDX*crnd();
- rockptr->dy = -weighted_rnd_range(rmin[i], rmax[i]) + screendy;
- break;
- case TOP:
- rockptr->x = rnd()*(XSIZE + rockptr->image->w);
- rockptr->y = -rockptr->image->h;
-
- rockptr->dx = RDX*crnd();
- rockptr->dy = weighted_rnd_range(rmin[i], rmax[i]) + screendy;
- break;
- }
-
- rockptr->active = 1;
- rcnt++;
+ if(!free_rocks) return; // sorry, we ran out of rocks!
+ r = free_rocks; free_rocks = r->next;
+ type = urnd() % NROCKS;
+ *r = prototypes[type];
+ r->type = type;
+ switch(i) {
+ case RIGHT:
+ r->x = XSIZE;
+ r->y = frnd()*(YSIZE + r->image->h);
+
+ r->dx = -weighted_rnd_range(rmin[i], rmax[i]) + screendx;
+ r->dy = RDY*crnd();
+ break;
+ case LEFT:
+ r->x = -r->image->w;
+ r->y = frnd()*(YSIZE + r->image->h);
+
+ r->dx = weighted_rnd_range(rmin[i], rmax[i]) + screendx;
+ r->dy = RDY*crnd();
+ break;
+ case BOTTOM:
+ r->x = frnd()*(XSIZE + r->image->w);
+ r->y = YSIZE;
+
+ r->dx = RDX*crnd();
+ r->dy = -weighted_rnd_range(rmin[i], rmax[i]) + screendy;
+ break;
+ case TOP:
+ r->x = frnd()*(XSIZE + r->image->w);
+ r->y = -r->image->h;
+
+ r->dx = RDX*crnd();
+ r->dy = weighted_rnd_range(rmin[i], rmax[i]) + screendy;
+ break;
}
+ tmp = bucket(r->x, r->y, p);
+ r->next = *tmp; *tmp = r;
}
}
}
void
move_rocks(void)
{
- int i;
+ int b;
+ struct rock **head;
+ struct rock *r;
// Move all the rocks
- for(i = 0; i < MAXROCKS; i++) {
- if(rock[i].active) {
+ for(b=0; b<n_buckets; b++) {
+ head=&rock_buckets[p][b]; r=*head;
+ while(*head) {
+ r=*head;
+
// move
- rock[i].x += (rock[i].dx-screendx)*gamerate;
- rock[i].y += (rock[i].dy-screendy)*gamerate;
- // clip
- if(rock[i].x < -rock[i].image->w || rock[i].x >= XSIZE
- || rock[i].y < -rock[i].image->h || rock[i].y >= YSIZE) {
- rock[i].active = 0;
- rcnt--;
- }
+ r->x += (r->dx - screendx)*t_frame;
+ r->y += (r->dy - screendy)*t_frame;
+
+ // clip it, or sort it into the other bucket set
+ // (either way we move it out of this list).
+ if(r->x + r->image->w < 0 || r->x >= XSIZE
+ || r->y + r->image->h < 0 || r->y >= YSIZE) {
+ transfer_rock(r, head, &free_rocks);
+ r->image = NULL;
+ } else transfer_rock(r, head, bucket(r->x, r->y, 1-p));
}
}
- // if(rcnt < nrocks) printf("-%d.\n", nrocks-rcnt);
- // else printf("%d.\n", rcnt-nrocks);
+ p = 1-p; // switch current set of buckets.
}
void
draw_rocks(void)
{
int i;
- SDL_Rect src, dest;
+ SDL_Rect dest;
- src.x = 0; src.y = 0;
-
- for(i = 0; i<MAXROCKS; i++) {
- if(rock[i].active) {
- src.w = rock[i].image->w;
- src.h = rock[i].image->h;
-
- dest.w = src.w;
- dest.h = src.h;
- dest.x = (int) rock[i].x;
- dest.y = (int) rock[i].y;
-
- SDL_BlitSurface(rock[i].image,&src,surf_screen,&dest);
+ for(i=0; i<MAXROCKS; i++) {
+ if(!rocks[i].image) continue;
+ dest.x = rocks[i].x; dest.y = rocks[i].y;
+ SDL_BlitSurface(rocks[i].image,NULL,surf_screen,&dest);
+ }
+}
- }
+int
+hit_in_bucket(struct rock *r, Sprite *s)
+{
+ for(; r; r=r->next) {
+ if(collide(SPRITE(r), s)) return true;
}
+ return false;
}
int
-hit_rocks(float x, float y, struct shape *shape)
+hit_rocks(Sprite *s)
{
- int i;
+ int l, r, t, b;
+ struct rock **bucket;
+
+ l = (s->x + grid_size) / grid_size;
+ r = (s->x + s->w + grid_size) / grid_size;
+ t = (s->y + grid_size) / grid_size;
+ b = (s->y + s->h + grid_size) / grid_size;
+ bucket = &rock_buckets[p][l + t*bw];
+
+ if(hit_in_bucket(*bucket, s)) return true;
+ if(l > 0 && hit_in_bucket(*(bucket-1), s)) return true;
+ if(t > 0 && hit_in_bucket(*(bucket-bw), s)) return true;
+ if(l > 0 && t > 0 && hit_in_bucket(*(bucket-1-bw), s)) return true;
+
+ if(r > l) {
+ if(hit_in_bucket(*(bucket+1), s)) return true;
+ if(t > 0 && hit_in_bucket(*(bucket+1-bw), s)) return true;
+ }
+ if(b > t) {
+ if(hit_in_bucket(*(bucket+bw), s)) return true;
+ if(l > 0 && hit_in_bucket(*(bucket-1+bw), s)) return true;
+ }
+ if(r > l && b > t && hit_in_bucket(*(bucket+1+bw), s)) return true;
+ return false;
+}
- for(i=0; i<MAXROCKS; i++) {
- if(rock[i].active) {
- if(collide(x-rock[i].x, y-rock[i].y, rock[i].shape, shape))
- return 1;
- }
+int
+pixel_hit_in_bucket(struct rock *r, float x, float y)
+{
+ for(; r; r=r->next) {
+ if(pixel_collide(SPRITE(r), x, y)) return 1;
}
return 0;
}
+int
+pixel_hit_rocks(float x, float y)
+{
+ int ix, iy;
+ int l, t;
+ struct rock **bucket;
+
+ ix = x + grid_size; iy = y + grid_size;
+ l = ix / grid_size; t = iy / grid_size;
+ bucket = &rock_buckets[p][l + t*bw];
+ if(pixel_hit_in_bucket(*bucket, x, y)) return true;
+ if(l > 0 && pixel_hit_in_bucket(*(bucket-1), x, y)) return true;
+ if(t > 0 && pixel_hit_in_bucket(*(bucket-bw), x, y)) return true;
+ if(l > 0 && t > 0 && pixel_hit_in_bucket(*(bucket-1-bw), x, y)) return true;
+ return false;
+}
+
void
blast_rocks(float x, float y, float radius, int onlyslow)
{
- int i;
+ int b;
+ struct rock *r;
float dx, dy, n;
if(onlyslow) return;
- for(i = 0; i<MAXROCKS; i++ ) {
- if(rock[i].x <= 0) continue;
+ for(b=0; b<n_buckets; b++) {
+ for(r=rock_buckets[p][b]; r; r=r->next) {
+ if(r->x <= 0) continue;
- // This makes it so your explosion from dying magically doesn't leave
- // any rocks that aren't moving much on the x axis. If onlyslow is set,
- // only rocks that are barely moving will be pushed.
- if(onlyslow && (rock[i].dx-screendx < -4 || rock[i].dx-screendx > 3)) continue;
+ // This makes it so your explosion from dying magically doesn't leave
+ // any rocks that aren't moving much on the x axis. If onlyslow is set,
+ // only rocks that are barely moving will be pushed.
+ if(onlyslow && (r->dx - screendx < -4 || r->dx - screendx > 3)) continue;
- dx = rock[i].x - x;
- dy = rock[i].y - y;
+ dx = r->x - x;
+ dy = r->y - y;
- n = sqrt(dx*dx + dy*dy);
- if(n < radius) {
- n *= 15;
- rock[i].dx += 54.0*dx/n;
- rock[i].dy += 54.0*dy/n;
+ n = sqrt(dx*dx + dy*dy);
+ if(n < radius) {
+ n *= 15;
+ r->dx += 54.0*dx/n;
+ r->dy += 54.0*dy/n;
+ }
}
}
}