liblashgame

Pathfinder and path decision making library for 2D tile game
git clone git://holbrook.no/liblashgame.git
Info | Log | Files | Refs

lash_game_standard.c (15910B)


      1 #include <stdlib.h>
      2 #include <math.h>
      3 
      4 #include "lash_game_standard.h"
      5 
      6 
      7 #define LASH_M_PI_DOUBLE (M_PI * 2)
      8 
      9 // http://stackoverflow.com/questions/4003232/how-to-code-a-modulo-operator-in-c-c-obj-c-that-handles-negative-numbers
     10 // modulus must be handled differently for negatives 
     11 
     12 unsigned char lash_getQuadrant(const float rads) {
     13 	int mod, quad;
     14 	mod = (int)floor(rads / M_PI_2);
     15 	quad = mod % 4;
     16 	
     17 	if (mod < 0)
     18 		if (quad != 0)
     19 			quad += 4;
     20 	
     21 	return quad + 1;
     22 }
     23 
     24 unsigned char lash_getQuadrantFromCartesian(const int dx, const int dy) {
     25 	if (dx > 0) {
     26 		if (dy > 0) {
     27 			return 1;
     28 		} else {
     29 			return 4;
     30 		}
     31 	} else {
     32 		if (dy > 0) {
     33 			return 2;
     34 		} else {
     35 			return 3;
     36 		}
     37 	}
     38 	return 0;
     39 }
     40 
     41  
     42 enum lash_anglespan_compare lash_compareAngleSpan(float old_rad_min, float old_rad_max, float new_rad_min, float new_rad_max) {
     43 	double full_circle = 2 * M_PI;
     44 	
     45 	if (old_rad_max > full_circle) {
     46 		// if new angle is fully contained by the old, and the old angles are on each side of 2π
     47 		if (new_rad_min + full_circle < old_rad_max && new_rad_min + full_circle > old_rad_min) {
     48 			new_rad_min += full_circle;
     49 			new_rad_max += full_circle;
     50 		}
     51 	} else if (new_rad_max > full_circle && old_rad_max <= full_circle && old_rad_min < full_circle) {
     52 		// if the new angle are on each side of 2π, and the old min is inside the span
     53 		//if (new_rad_min < old_rad_max + full_circle && new_rad_min > old_rad_min + full_circle) {
     54 			old_rad_min += full_circle;
     55 			old_rad_max += full_circle;
     56 		//}	
     57 	}
     58 	
     59 	enum lash_anglespan_compare result = LASH_ANGLESPAN_NONE;
     60 	if (new_rad_max < old_rad_max && new_rad_min > old_rad_min) {
     61 		result = LASH_ANGLESPAN_SPLIT;
     62 	} else {
     63 		if (new_rad_max >= old_rad_max && new_rad_min <= old_rad_max)
     64 			result = LASH_ANGLESPAN_MAX;
     65 		if (new_rad_min <= old_rad_min && new_rad_max >= old_rad_min)
     66 			result = result == LASH_ANGLESPAN_MAX ? LASH_ANGLESPAN_BOTH : LASH_ANGLESPAN_MIN;
     67 	}
     68 	return result;
     69 }
     70 
     71 int lash_getContainedAngleOnly(const double x, const double y, const double m, const double w_container, const double h_container, const int buf_top, const int buf_right, const int buf_bottom, const int buf_left, double *angle_min, double *angle_max) {
     72 	double n = 0.f;
     73 	return lash_getContainedAngle(x, y, m, w_container, h_container, buf_top, buf_right, buf_bottom, buf_left, angle_min, angle_max, 0, &n, &n, &n, &n);
     74 }
     75 
     76 int lash_getContainedAngle(const double x, const double y, const double m, const double w_container, const double h_container, const int buf_top, const int buf_right, const int buf_bottom, const int buf_left, double *angle_min, double *angle_max, const int include_dcoords, double *x_min, double *y_min, double *x_max, double *y_max) {
     77 	// any left
     78 	if (x - m < buf_left) {
     79 		// topleft
     80 		if (y - m < buf_top) {
     81 			double min_mod = M_PI;
     82 			double max_mod = 2 * M_PI;
     83 			*angle_min = min_mod + acos((x - buf_left) / m);
     84 			*angle_max = max_mod + asin((y - buf_top) / m);
     85 			if (include_dcoords) {
     86 				/* *x_min = buf_left;
     87 				*y_min = y + floor(sin(*angle_min - min_mod) * m);
     88 				*x_max = x + floor(cos(*angle_max - max_mod) * m);
     89 				*y_max = buf_top; */
     90 				*x_min = buf_left;
     91 				*y_min = y + (sin(*angle_min - min_mod) * m);
     92 				*x_max = x + (cos(*angle_max - max_mod) * m);
     93 				*y_max = buf_top;
     94 			}
     95 			return 0;
     96 		// bottomleft
     97 		} else if (y + m > h_container - buf_bottom) {
     98 			double min_mod = 3 * M_PI_2;
     99 			double max_mod = 5 * M_PI_2;
    100 			*angle_min = min_mod + acos((x - buf_left) / m);
    101 			*angle_max = max_mod + asin((h_container - buf_bottom - y) / m);
    102 			if (include_dcoords) {
    103 				/* *x_min = x + floor(sin(*angle_min - min_mod) * m);
    104 				*y_min = h_container - buf_bottom;
    105 				*x_max = buf_left;
    106 				*y_max = y - floor(cos(*angle_max - max_mod) * m); */
    107 				*x_min = x + (sin(*angle_min - min_mod) * m);
    108 				*y_min = h_container - buf_bottom;
    109 				*x_max = buf_left;
    110 				*y_max = y - (cos(*angle_max - max_mod) * m); 
    111 			}
    112 			return 0;
    113 		} else {
    114 		// left
    115 			double tmp_angle = acos((x - buf_left) / m);
    116 			*angle_min = M_PI + tmp_angle;
    117 			*angle_max = (3 * M_PI) - tmp_angle;
    118 			if (include_dcoords) {
    119 				//int tmp_side = floor(sin(tmp_angle) * m);
    120 				int tmp_side = (sin(tmp_angle) * m);
    121 				*x_min = buf_left;
    122 				*y_min = y + tmp_side;
    123 				*x_max = buf_left;
    124 				*y_max = y - tmp_side;
    125 			}
    126 			return 0;
    127 		}
    128 	// any right
    129 	} else if (x + m > w_container - buf_right) {
    130 		// top right
    131 		if (y - m < buf_top) {
    132 			double min_mod = M_PI_2;
    133 			double max_mod = 3 * M_PI_2;
    134 			*angle_min = min_mod + acos((y - buf_top) / m);
    135 			*angle_max = max_mod + asin((w_container - buf_right - x) / m);
    136 			if (include_dcoords) {
    137 				/* *x_min = x - floor(sin(*angle_min - min_mod) * m);
    138 				*y_min = buf_top;
    139 				*x_max = w_container - buf_left;
    140 				*y_max = y + floor(cos(*angle_max - max_mod) * m); */
    141 				*x_min = x - (sin(*angle_min - min_mod) * m);
    142 				*y_min = buf_top;
    143 				*x_max = w_container - buf_left;
    144 				*y_max = y + (cos(*angle_max - max_mod) * m);
    145 			}
    146 			return 0;
    147 		// bottom right
    148 		} else if (y + m > h_container - buf_bottom) {
    149 			//double min_mod = 0;
    150 			double max_mod = M_PI;
    151 			*angle_min = acos((w_container - buf_right - x) / m);
    152 			*angle_max = max_mod + asin((h_container - buf_bottom - y) / m);
    153 			if (include_dcoords) {
    154 				/* *x_min = w_container - buf_left;
    155 				*y_min = y - floor(sin(*angle_min) * m);
    156 				*x_max = x - floor(cos(*angle_max - max_mod) * m);
    157 				*y_max = h_container - buf_bottom;*/
    158 				*x_min = w_container - buf_left;
    159 				*y_min = y - (sin(*angle_min) * m);
    160 				*x_max = x - (cos(*angle_max - max_mod) * m);
    161 				*y_max = h_container - buf_bottom;
    162 			}
    163 			return 0;
    164 		// right
    165 		} else {
    166 			//angle min has no modifier
    167 			//double tmp_angle = acos((h_container - buf_right - x) / m);
    168 			*angle_min = acos((w_container - buf_right - x) / m);
    169 			*angle_max = (2 * M_PI) - *angle_min;
    170 			if (include_dcoords) {
    171 				//int tmp_side = floor(sin(*angle_min) * m);
    172 				int tmp_side = (sin(*angle_min) * m);
    173 				*x_min = w_container - buf_right;
    174 				*y_min = y - tmp_side;
    175 				*x_max = w_container - buf_right;
    176 				*y_max = y + tmp_side;
    177 				
    178 			}
    179 			return 0;
    180 		}
    181 	// top (only)
    182 	} else if (y - m < buf_top) {
    183 		double tmp_angle = acos((y - buf_top) / m);
    184 		*angle_min = M_PI_2 + tmp_angle;
    185 		*angle_max = (5 * M_PI_2) - tmp_angle;
    186 		if (include_dcoords) {
    187 			//int tmp_side = floor(sin(tmp_angle) * m);
    188 			int tmp_side = (sin(tmp_angle) * m);
    189 			*x_min = x - tmp_side;
    190 			*y_min = buf_top;
    191 			*x_max = x + tmp_side;
    192 			*y_max = buf_top;
    193 		}
    194 		return 0;
    195 	// bottom (only)
    196 	} else if (y + m > h_container - buf_bottom) {
    197 		double tmp_angle = acos((h_container - buf_bottom - y) / m);
    198 		*angle_min = (3 * M_PI_2) + tmp_angle;
    199 		*angle_max = (7 * M_PI_2) - tmp_angle;
    200 		if (include_dcoords) {
    201 			//int tmp_side = floor(sin(tmp_angle) * m);
    202 			int tmp_side = (sin(tmp_angle) * m);
    203 			*x_min = x + tmp_side;
    204 			*y_min = h_container - buf_bottom;
    205 			*x_max = x - tmp_side;
    206 			*y_max = h_container - buf_bottom;
    207 		}
    208 		return 0;
    209 	}
    210 	
    211 	// default; no limit
    212 	*angle_min = 0.f;
    213 	*angle_max = 2 * M_PI;
    214 	if (include_dcoords) {
    215 		*x_min = h_container - buf_right;
    216 		*y_min = y;
    217 		*x_max = h_container - buf_right;
    218 		*y_max = y;
    219 	}
    220 	return 0;
    221 }
    222 
    223 float lash_cartesianMagnitude(const int target_x, const int  target_y, const int source_x, const int source_y) {
    224 	return sqrt(pow(target_x - source_x, 2) + pow(target_y - source_y, 2));
    225 }
    226 
    227 // self.h = abs((targetindex % map.w) - (index % map.w)) + abs(math.floor(targetindex / map.w) - math.floor(index / map.w))
    228 int lash_getManhattanMagnitudeFromCartesian(const lash_game_coords_t targetcoords, const lash_game_coords_t sourcecoords) {
    229 	//return abs((target_idx % *w) - (source_idx % *w)) + abs(floor(target_idx / *w) - floor(source_idx / *w));
    230 	return abs(targetcoords.y - sourcecoords.y) + abs(targetcoords.x - sourcecoords.x);
    231 }
    232 
    233 int lash_polarToCartesian(const float radians, const float radius, const int source_x, const int source_y, int *target_x, int *target_y) {
    234 	*target_x = source_x + floor(cos(radians) * radius);
    235 	*target_y = source_y + floor(sin(radians) * radius);
    236 	return 0;
    237 }
    238 
    239 int lash_cartesianToPolar(const int source_x, const int source_y, const int target_x, const int target_y, float *radians, float *radius, const int inv_x, const int inv_y) {	
    240 	
    241 	float tmp_radians;
    242 	
    243 	int x = target_x - source_x;
    244 	if (inv_x != 0)
    245 		x *= -1;
    246 
    247 	int y = target_y - source_y;
    248 	if (inv_y != 0)
    249 		y *= -1;
    250 			
    251 	*radius = sqrt(pow(x, 2) + pow(y, 2));
    252 	tmp_radians = atan2((float)y, (float)x);
    253 	if (tmp_radians < 0) 
    254 		tmp_radians += 2 * M_PI;
    255 		
    256 	*radians = tmp_radians;
    257 	
    258 	return 0;
    259 }
    260 
    261 int lash_cartesianToIndex(unsigned long int *index, const unsigned int *w, const unsigned int *h, unsigned int *unit_size, const lash_game_coords_cartesian_t *coords) {
    262 	
    263 	if (coords->x > *w - 1 || coords->y > *h - 1)
    264 		return 1;
    265 	
    266 	//*index = coords->x;
    267 	//*index += floor(coords->y * *w);
    268 	*index = coords->x / *unit_size;
    269 	*index += floor((coords->y * *w) / *unit_size);
    270 	
    271 	return 0;
    272 }
    273 
    274 int lash_indexToCartesian(lash_game_coords_cartesian_t *coords, const unsigned int *w, const unsigned int *h, unsigned int *unit_size, const lash_game_map_index_t *index) {
    275 	
    276 	if ((*index) >= *w * *h)
    277 		return 1;
    278 		
    279 	if (*unit_size < 1)
    280 		*unit_size = 1;
    281 	
    282 	coords->x = (unsigned int)((*index % *w) * *unit_size);
    283 	coords->y = (unsigned int)(floor(*index / *w) * *unit_size);
    284 	
    285 	return 0;
    286 }
    287 
    288 int lash_cartesianToFloat(lash_game_coords_float_t *coords_float, const unsigned int *w, const unsigned int *h, const lash_game_coords_cartesian_t *coords_cartesian) {
    289 	coords_float->x = (float)coords_cartesian->x / *w;
    290 	coords_float->y = (float)coords_cartesian->y / *h;
    291 	return 0;
    292 }
    293 
    294 int lash_linearIntersect(const lash_game_line_t a, const lash_game_line_t b, lash_game_coords_float_t *coords) {
    295 	
    296 	coords->x = (b.c - a.c) / (a.m - b.m);
    297 	coords->y = (a.m * coords->x) + a.c;
    298 	if (isinf(coords->x) || isinf(coords->y))
    299 		return 1;
    300 	return 0;
    301 	
    302 }
    303 
    304 int lash_cartesianToLinear(const lash_game_coords_float_t src, const lash_game_coords_float_t target, lash_game_line_t *result) {
    305 	if (target.x == src.x) {
    306 		result->m = INFINITY;
    307 		result->c = INFINITY;
    308 		return 1;
    309 	} else if (target.y == src.y) {
    310 		result->m = NAN;
    311 		result->c = NAN;
    312 		return 1;
    313 	} else {
    314 		result->m = (target.y - src.y) / (float)(target.x - src.x);
    315 		result->c = ((-result->m) * src.x) + src.y;
    316 	}
    317 	return 0;
    318 }
    319 
    320 float lash_distanceToRadians(const float distance, const float radius) {
    321 	return LASH_M_PI_DOUBLE * (distance / (LASH_M_PI_DOUBLE * radius));
    322 }
    323 
    324 float lash_normalizeRadians(float radians) {
    325 	char rotations = floor(radians / (2 * M_PI));
    326 	if (rotations != 0)
    327 		radians -= LASH_M_PI_DOUBLE * rotations;
    328 	else if (radians < 0)
    329 		radians += LASH_M_PI_DOUBLE;
    330 	return radians;
    331 }
    332 
    333 float lash_normalizeQuadrantRadians(float radians) {
    334 	float rotations = floor(radians / M_PI_2);
    335 	if (rotations != 0)
    336 		radians -= (float)M_PI_2 * rotations;
    337 	else if (radians < 0)
    338 		radians += M_PI_2 + (float)(M_PI_2 * rotations);
    339 	return radians;
    340 }
    341 
    342 // calculates at the point of impact. 
    343 /// \todo resultquad calculation should resolve to being able to use resultquad for the objrad calculation below
    344 void lash_collisionSurfaceDeflectSimple(float *objvel, float *objrad, const float surfacerad, float bounce) {
    345 	
    346 	
    347 	if (bounce < 0.f)
    348 		bounce = 0.0;
    349 	else if (bounce > 1.f)
    350 		bounce = 1.f;
    351 		
    352 	float resultquad; // the angle of impact
    353 	float direction; // the difference of objrad and surfacerad
    354 	float xvel, yvel; // the resulting velocities after bounce is calculated
    355 	float objradnormal, surfaceradnormal, objradquad, surfaceradquad, radmod;
    356 	char surfacequadrant, objquadrant; // quadrant the surface and object angles belong to
    357 	
    358 	objradnormal = lash_normalizeRadians(*objrad);
    359 	surfaceradnormal = lash_normalizeRadians(surfacerad);
    360 	
    361 	radmod = 0.f; // bounce angle
    362 	
    363 	surfacequadrant = floor(surfaceradnormal / M_PI_2); 
    364 	objquadrant = floor(objradnormal / M_PI_2);
    365 
    366 	objradquad = objradnormal - (objquadrant * (float)M_PI_2); // object rads normalized within quadrant
    367 	surfaceradquad = surfaceradnormal - (surfacequadrant * (float)M_PI_2); // surface rads normalized within quadrant
    368 	
    369 	if (objquadrant % 2 != surfacequadrant % 2)
    370 		direction = surfaceradquad + (M_PI_2 - objradquad);
    371 	else
    372 		direction = surfaceradquad - objradquad;
    373 	
    374 	
    375 	if (direction < 0.f)
    376 		resultquad = M_PI + direction;
    377 	else //if (direction < M_PI_2)
    378 		resultquad = M_PI - direction;
    379 	//else
    380 		//resultquad = direction;
    381 
    382 
    383 	if (direction < 0.f)
    384 		xvel = cos(-direction) * *objvel;
    385 	else
    386 		xvel = cos(direction) * *objvel;
    387 	
    388 	yvel = sin(direction) * *objvel * bounce;
    389 
    390 	if (resultquad != M_PI_2)
    391 		radmod = atan(yvel / xvel);
    392 		
    393 	if (radmod < 0.f)
    394 		radmod = -radmod;
    395 	
    396 	if (direction < 0.f)
    397 		*objrad = *objrad + direction - radmod;
    398 	else if (direction > M_PI_2)
    399 		*objrad = *objrad - resultquad - radmod;
    400 	else
    401 		*objrad = *objrad + direction + radmod;
    402 		
    403 	*objvel = sqrt(pow(xvel, 2) + pow(yvel, 2));
    404 		
    405 }
    406 
    407 
    408 // if want intersect coords, pass both as pointers, if NULL the coords are not resolved
    409 char lash_collisionCheckCircleLine(const lash_game_coords_float_t circle_centre, const float circle_radius, const lash_game_line_t slope, lash_game_coords_float_t *intersect_coords_1, lash_game_coords_float_t *intersect_coords_2) {
    410 	return lash_collisionCircleLine(circle_centre, circle_radius, slope, intersect_coords_1, intersect_coords_2);
    411 }
    412 
    413 char lash_collisionCircleLine(const lash_game_coords_float_t circle_centre, const float circle_radius, const lash_game_line_t slope, lash_game_coords_float_t *intersect_coords_1, lash_game_coords_float_t *intersect_coords_2) {	
    414 	float a, b, c, discriminant;
    415 	char intersections = 0;
    416 	
    417 	// quadratic equation to resolve intersections from circle and line equation (substitute the line into circle, expand and collect equal terms)
    418 	// binomial: (m²+1)x²+2(mc−mq−p)x+(q²−r²+p²−2cq+c²)=0.
    419 	// discriminant: -2(mc−mq−p) +/- sqrt(pow(2(mc-mq-p), 2) - (4 * ((m*m)+1) * ((p*p)-(r*r)+(q*q)-(2*c*q)+(c*c))))
    420 	// taken from http://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle
    421 	a = (slope.m * slope.m) + 1;
    422 	b = 2 * ((slope.m * slope.c) - (slope.m * circle_centre.y) - circle_centre.x);
    423 	c = (circle_centre.x * circle_centre.x) + (circle_centre.y * circle_centre.y) - (2 * slope.c * circle_centre.y) + (slope.c * slope.c) - (circle_radius * circle_radius);
    424 	
    425 	discriminant = (b * b) - (4 * a * c);
    426 	if (discriminant > 0)
    427 		intersections = 2;
    428 	else if (discriminant == 0)
    429 		intersections = 1;
    430 	
    431 	if (intersections == 0) {
    432 		intersect_coords_1 = NULL;
    433 		intersect_coords_2 = NULL;
    434 	} else if (intersect_coords_1 != NULL && intersect_coords_2 != NULL) {
    435 		intersect_coords_1->x = (-b - sqrt(discriminant)) / (2 * a);
    436 		intersect_coords_1->y = (slope.m * intersect_coords_1->x) + slope.c;
    437 		if (intersections  == 2) {
    438 			intersect_coords_2->x = (-b + sqrt(discriminant)) / (2 * a);
    439 			intersect_coords_2->y = (slope.m * intersect_coords_2->x) + slope.c;
    440 		}
    441 	}
    442 		
    443 	return intersections;
    444 }
    445 
    446 
    447 /*
    448 /// \todo check if this is faster with circle/line intersect check
    449 void lash_collisionCheckCircleLine(const lash_game_coords_float_t c_coords, const float c_r, const lash_game_coords_float_t l_coords_1, const lash_game_coords_float_t l_coords_2, float *intersect_perp) {
    450 	float l_reverse_vx, l_reverse_vy;
    451 	lash_game_line_t l_slope, l_reverse_slope;
    452 	lash_game_coords_float_t intersect_coords;
    453 	lash_cartesianToLinear(l_coords_1, l_coords_2, &l_slope);
    454 	reverse_vy = l_coords_1.x - l_coords_2.x;
    455 	reverse_vx = l_coords_1.y - l_coords_2.y;
    456 	l_reverse_slope.m = (reverse_vy / reverse_vx) * -1;
    457 	l_reverse_slope.c = c_coords.y - (l_reverse_slope.m * c_coords.x);
    458 	lash_linearIntersect(l_slope, l_reverse_slope, &intersect_coords);
    459 }
    460 */
    461 
    462 /*
    463 int lash_isBigEndian() {
    464 	if (_lash_endian == -1) {
    465 		union {
    466 			uint32_t i;
    467 			char[4] c;
    468 		} bint = (0x01020304);
    469 		if (bint.c[0] == 1)
    470 			_lash_endian = 1;
    471 		else
    472 			_lash_endian = 0;
    473 	}
    474 	return _lash_endian;
    475 }
    476 */