X-Git-Url: https://jasonwoof.com/gitweb/?p=vor.git;a=blobdiff_plain;f=rocks.c;h=86c76e7691cac5abe7b45507b57eb3ab633aa612;hp=ca921cf22522e6435c827acd811b23c8d06ebb7d;hb=0d415d88f7ecd55273b09b619170078f7d35a910;hpb=d96cae8368715101e2bf3f9ff8900dc171c70b2f

diff --git a/rocks.c b/rocks.c
index ca921cf..86c76e7 100644
--- a/rocks.c
+++ b/rocks.c
@@ -3,150 +3,250 @@
 #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];
+Sprite *free_rocks;
 
-struct rock_struct rock[MAXROCKS], *rockptr = rock;
+Sprite **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];
-int nrocks;
+static float rtimers[4];
+
+uint32_t nrocks;
+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);
+static inline Sprite **
+bucket(int x, int y, int p)
+{
+	int b = (x+grid_size)/grid_size + bw*((y+grid_size)/grid_size);
+	return &rock_buckets[p][b];
+}
 
-#define crnd() (2*(rnd()-0.5))
+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);
+	}
+	p = 0;
+}
 
+static inline void
+insert_sprite(Sprite **head, Sprite *this)
+{
+	this->next = *head;
+	*head = this;
+}
 
-int
-init_rocks(void)
+static inline Sprite *
+remove_sprite(Sprite **head)
+{
+	Sprite *this = *head;
+	*head = this->next;
+	return this;
+}
+
+void
+reset_rocks(void)
 {
 	int i;
-	char a[MAX_PATH_LEN];
-	SDL_Surface *temp;
 
-	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]);
+	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 = SPRITE(&rocks[MAXROCKS-1]);
+
+	for(i = 0; i<n_buckets; i++) {
+		rock_buckets[0][i] = NULL;
+		rock_buckets[1][i] = NULL;
 	}
-	nrocks = 41;
-	return 0;
+
+	nrocks = I_ROCKS;
+	nrocks_timer = 0;
 }
 
-void
-reset_rocks(void)
+#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<MAXROCKS; i++) rock[i].active = 0;
+	for(i = 0; i<NROCKS; i++) {
+		snprintf(a, ROCK_LEN, "sprites/rock%02d.png", i);
+		load_sprite(SPRITE(&prototypes[i]), a);
+		prototypes[i].type = ROCK_SPRITE;
+		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/tick that should be coming from each side,
+// and the speed ranges of rocks coming from each side
 void
-rock_timer_increments(float *ti)
+rock_sides(float *ti, float *speed_min, float *speed_max)
 {
 	float dx0,dx1, dy0,dy1;
 	float hfactor, vfactor;
 	int i;
 
 	for(i=0; i<4; i++) ti[i] = 0;
-	hfactor = nrocks/KH; vfactor = nrocks/KV;
+	for(i=0; i<4; i++) speed_min[i] = 0;
+	for(i=0; i<4; i++) speed_max[i] = 0;
+	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) {
-			if(dx1 < 0) ti[RIGHT] = -(dx0+dx1)/2;
-			else {
-				ti[RIGHT] = -dx0/2;
-				ti[LEFT] = dx1/2;
-			}
-		} else ti[LEFT] = (dx0+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 left and right
+			speed_max[LEFT] = dx1;
+			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) {
-			if(dy1 < 0) ti[BOTTOM] = -(dy0+dy1)/2;
-			else {
-				ti[BOTTOM] = -dy0/2;
-				ti[TOP] = dy1/2;
-			}
-		} else ti[TOP] = (dy0+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 up and down
+			speed_max[TOP] = dy1;
+			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 + frnd() * (max * max - min * min));
+}
+
 void
 new_rocks(void)
 {
-	int i,j;
+	int i, type;
+	struct rock *r;
 	float ti[4];
+	float rmin[4];
+	float rmax[4];
+
+	if(nrocks < F_ROCKS) {
+		nrocks_timer += t_frame;
+		if(nrocks_timer >= nrocks_inc_ticks) {
+			nrocks_timer -= nrocks_inc_ticks;
+			nrocks++;
+		}
+	}
 
-	rock_timer_increments(ti);
+	rock_sides(ti, rmin, rmax);
 
+	// increment timers
+	for(i=0; i<4; i++) rtimers[i] += ti[i]*t_frame;
+
+	// generate rocks
 	for(i=0; i<4; i++) {
-		rtimers[i] += ti[i]*gamerate/20;
-		if(rtimers[i] >= 1) {
-			j=0;
-			while(rockptr->active && j<MAXROCKS) {
-				if(++rockptr - rock >= MAXROCKS) rockptr = rock;
-				j++;
-			}
-			if(!rockptr->active) {
-				rtimers[i] -= 1;
-				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);
-						break;
-					case LEFT:
-						rockptr->x = -rockptr->image->w;
-						rockptr->y = rnd()*(YSIZE + rockptr->image->h);
-						break;
-					case BOTTOM:
-						rockptr->x = rnd()*(XSIZE + rockptr->image->w);
-						rockptr->y = YSIZE;
-						break;
-					case TOP:
-						rockptr->x = rnd()*(XSIZE + rockptr->image->w);
-						rockptr->y = -rockptr->image->h;
-						break;
-				}
-
-				rockptr->dx = RDX*crnd();
-				rockptr->dy = RDY*crnd();
-
-				rockptr->active = 1;
+		while(rtimers[i] >= 1) {
+			rtimers[i] -= 1;
+			if(!free_rocks) return;  // sorry, we ran out of rocks!
+			r = (struct rock *) remove_sprite(&free_rocks);
+			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;
 			}
+			insert_sprite(bucket(r->x, r->y, p), SPRITE(r));
 		}
 	}
 }
@@ -154,85 +254,135 @@ new_rocks(void)
 void
 move_rocks(void)
 {
-	int i;
+	int b;
+	Sprite *r, **head;
 
 	// 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;
-			}
+			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) {
+				insert_sprite(&free_rocks, remove_sprite(head));
+				r->image = NULL;
+			} else insert_sprite(bucket(r->x, r->y, 1-p), remove_sprite(head));
 		}
 	}
+	p = 1-p;  // switch current set of buckets.
 }
 
 void
 draw_rocks(void)
 {
 	int i;
-	SDL_Rect src, 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_Rect dest;
 
-			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(Sprite *r, Sprite *s)
+{
+	for(; r; r=r->next) {
+		if(collide(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;
+	Sprite **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(Sprite *r, float x, float y)
+{
+	for(; r; r=r->next) {
+		if(pixel_collide(r, x, y)) return 1;
 	}
 	return 0;
 }
 
+int
+pixel_hit_rocks(float x, float y)
+{
+	int ix, iy;
+	int l, t;
+	Sprite **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;
+	Sprite *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;
+			}
 		}
 	}
 }