1 /*
2 C-Dogs SDL
3 A port of the legendary (and fun) action/arcade cdogs.
4 Copyright (C) 1995 Ronny Wester
5 Copyright (C) 2003 Jeremy Chin
6 Copyright (C) 2003-2007 Lucas Martin-King
7
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21
22 This file incorporates work covered by the following copyright and
23 permission notice:
24
25 Copyright (c) 2013-2015, 2017-2018, 2021 Cong Xu
26 All rights reserved.
27
28 Redistribution and use in source and binary forms, with or without
29 modification, are permitted provided that the following conditions are met:
30
31 Redistributions of source code must retain the above copyright notice, this
32 list of conditions and the following disclaimer.
33 Redistributions in binary form must reproduce the above copyright notice,
34 this list of conditions and the following disclaimer in the documentation
35 and/or other materials provided with the distribution.
36
37 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
38 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
39 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
40 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
41 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
42 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
43 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
44 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
45 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
47 POSSIBILITY OF SUCH DAMAGE.
48 */
49 #include "collision.h"
50
51 #include "actors.h"
52 #include "algorithms.h"
53 #include "campaigns.h"
54 #include "config.h"
55 #include "minkowski_hex.h"
56 #include "objs.h"
57
TileCacheInit(CArray * tc)58 static void TileCacheInit(CArray *tc)
59 {
60 CArrayInit(tc, sizeof(struct vec2i));
61 }
TileCacheReset(CArray * tc)62 static void TileCacheReset(CArray *tc)
63 {
64 CArrayClear(tc);
65 }
TileCacheTerminate(CArray * tc)66 static void TileCacheTerminate(CArray *tc)
67 {
68 CArrayTerminate(tc);
69 }
70 static void TileCacheAddImpl(
71 CArray *tc, const struct vec2i v, const bool addAdjacents);
TileCacheAdd(CArray * tc,const struct vec2i v)72 static void TileCacheAdd(CArray *tc, const struct vec2i v)
73 {
74 TileCacheAddImpl(tc, v, true);
75 }
TileCacheAddImpl(CArray * tc,const struct vec2i v,const bool addAdjacents)76 static void TileCacheAddImpl(
77 CArray *tc, const struct vec2i v, const bool addAdjacents)
78 {
79 if (!MapIsTileIn(&gMap, v))
80 {
81 return;
82 }
83 // Add tile in y/x order
84 CA_FOREACH(const struct vec2i, t, *tc)
85 if (t->y > v.y || (t->y == v.y && t->x > v.x))
86 {
87 CArrayInsert(tc, _ca_index, &v);
88 break;
89 }
90 else if (svec2i_is_equal(*t, v))
91 {
92 // Don't add the same tile twice
93 return;
94 }
95 CA_FOREACH_END()
96 CArrayPushBack(tc, &v);
97
98 // Also add the adjacencies for the tile
99 if (addAdjacents)
100 {
101 struct vec2i dv;
102 for (dv.y = -1; dv.y <= 1; dv.y++)
103 {
104 for (dv.x = -1; dv.x <= 1; dv.x++)
105 {
106 if (svec2i_is_zero(dv))
107 {
108 continue;
109 }
110 const struct vec2i dtv = svec2i_add(v, dv);
111 TileCacheAddImpl(tc, dtv, false);
112 }
113 }
114 }
115 }
116
117 CollisionSystem gCollisionSystem;
118
CollisionSystemInit(CollisionSystem * cs)119 void CollisionSystemInit(CollisionSystem *cs)
120 {
121 CollisionSystemReset(cs);
122 TileCacheInit(&cs->tileCache);
123 }
CollisionSystemReset(CollisionSystem * cs)124 void CollisionSystemReset(CollisionSystem *cs)
125 {
126 cs->allyCollision = ConfigGetEnum(&gConfig, "Game.AllyCollision");
127 }
CollisionSystemTerminate(CollisionSystem * cs)128 void CollisionSystemTerminate(CollisionSystem *cs)
129 {
130 TileCacheTerminate(&cs->tileCache);
131 }
132
CalcCollisionTeam(const bool isActor,const TActor * actor)133 CollisionTeam CalcCollisionTeam(const bool isActor, const TActor *actor)
134 {
135 // Need to have prisoners collide with everything otherwise they will not
136 // be "rescued"
137 // Also need victims to collide with everyone
138 if (!isActor || (actor->flags & (FLAGS_PRISONER | FLAGS_VICTIM)) ||
139 IsPVP(gCampaign.Entry.Mode))
140 {
141 return COLLISIONTEAM_NONE;
142 }
143 if (actor->pilotUID != actor->uid && actor->pilotUID >= 0)
144 {
145 // Vehicles use the collision of its pilot
146 actor = ActorGetByUID(actor->pilotUID);
147 }
148 if (actor->PlayerUID >= 0 || (actor->flags & FLAGS_GOOD_GUY))
149 {
150 return COLLISIONTEAM_GOOD;
151 }
152 return COLLISIONTEAM_BAD;
153 }
154
IsCollisionWithWall(const struct vec2 pos,const struct vec2i size2)155 bool IsCollisionWithWall(const struct vec2 pos, const struct vec2i size2)
156 {
157 const struct vec2i size = svec2i_scale_divide(size2, 2);
158 if (pos.x - size.x < 0 || pos.y - size.y < 0 ||
159 pos.x + size.x >= gMap.Size.x * TILE_WIDTH ||
160 pos.y + size.y >= gMap.Size.y * TILE_HEIGHT)
161 {
162 return true;
163 }
164 if (HitWall((int)pos.x - size.x, (int)pos.y - size.y) ||
165 HitWall((int)pos.x - size.x, (int)pos.y) ||
166 HitWall((int)pos.x - size.x, (int)pos.y + size.y) ||
167 HitWall((int)pos.x, (int)pos.y + size.y) ||
168 HitWall((int)pos.x + size.x, (int)pos.y + size.y) ||
169 HitWall((int)pos.x + size.x, (int)pos.y) ||
170 HitWall((int)pos.x + size.x, (int)pos.y - size.y) ||
171 HitWall((int)pos.x, (int)pos.y - size.y))
172 {
173 return true;
174 }
175 return false;
176 }
177
178 // Check collision with a diamond shape
179 // This means that the bounding box could be in collision, but the bounding
180 // "radius" is not. The diamond is expressed with a single "radius" - that is,
181 // the diamond is the same height and width.
182 // This arrangement is used so that axis movement can slide off corners by
183 // moving in a diagonal direction.
184 // E.g. this is not a collision:
185 // x
186 // x x
187 // x x
188 // x x
189 // x x
190 // x x wwwww
191 // x w
192 // w
193 // Where 'x' denotes the bounding diamond, and 'w' represents a wall corner.
IsCollisionDiamond(const Map * map,const struct vec2 pos,const struct vec2i size2)194 bool IsCollisionDiamond(
195 const Map *map, const struct vec2 pos, const struct vec2i size2)
196 {
197 const struct vec2i mapSize =
198 svec2i(map->Size.x * TILE_WIDTH, map->Size.y * TILE_HEIGHT);
199 const struct vec2i size = svec2i_scale_divide(size2, 2);
200 if (pos.x - size.x < 0 || pos.x + size.x >= mapSize.x ||
201 pos.y - size.y < 0 || pos.y + size.y >= mapSize.y)
202 {
203 return true;
204 }
205
206 // Only support wider-than-taller collision diamonds for now
207 CASSERT(size.x >= size.y, "not implemented, taller than wider diamond");
208 const float gradient = (float)size.y / size.x;
209
210 // Now we need to check in a diamond pattern that the boundary does not
211 // collide
212 // Top to right
213 for (int i = 0; i < size.x; i++)
214 {
215 const float y = (-size.x + i) * gradient;
216 const struct vec2 p = svec2_add(pos, svec2((float)i, y));
217 if (HitWall(p.x, p.y))
218 {
219 return true;
220 }
221 }
222 // Right to bottom
223 for (int i = 0; i < size.x; i++)
224 {
225 const float y = i * gradient;
226 const struct vec2 p = svec2_add(pos, svec2(size.x - (float)i, y));
227 if (HitWall(p.x, p.y))
228 {
229 return true;
230 }
231 }
232 // Bottom to left
233 for (int i = 0; i < size.x; i++)
234 {
235 const float y = (size.x - i) * gradient;
236 const struct vec2 p = svec2_add(pos, svec2((float)-i, y));
237 if (HitWall(p.x, p.y))
238 {
239 return true;
240 }
241 }
242 // Left to top
243 for (int i = 0; i < size.x; i++)
244 {
245 const float y = -i * gradient;
246 const struct vec2 p = svec2_add(pos, svec2((float)-size.x + i, y));
247 if (HitWall(p.x, p.y))
248 {
249 return true;
250 }
251 }
252 return false;
253 }
254
AABBOverlap(const struct vec2 pos1,const struct vec2 pos2,const struct vec2i size1,const struct vec2i size2)255 bool AABBOverlap(
256 const struct vec2 pos1, const struct vec2 pos2, const struct vec2i size1,
257 const struct vec2i size2)
258 {
259 // Use Minkowski addition to check overlap of two rects
260 const struct vec2 d =
261 svec2(fabsf(pos1.x - pos2.x), fabsf(pos1.y - pos2.y));
262 const struct vec2i r = svec2i_scale_divide(svec2i_add(size1, size2), 2);
263 return d.x < r.x && d.y < r.y;
264 }
265
CollisionIsOnSameTeam(const Thing * i,const CollisionTeam team,const bool isPVP)266 static bool CollisionIsOnSameTeam(
267 const Thing *i, const CollisionTeam team, const bool isPVP)
268 {
269 if (gCollisionSystem.allyCollision == ALLYCOLLISION_NORMAL)
270 {
271 return false;
272 }
273 CollisionTeam itemTeam = COLLISIONTEAM_NONE;
274 if (i->kind == KIND_CHARACTER)
275 {
276 const TActor *a = CArrayGet(&gActors, i->id);
277 itemTeam = CalcCollisionTeam(true, a);
278 }
279 return team != COLLISIONTEAM_NONE && itemTeam != COLLISIONTEAM_NONE &&
280 team == itemTeam && !isPVP;
281 }
282
283 static bool CheckParams(
284 const CollisionParams params, const Thing *a, const Thing *b);
285
286 static void AddPosToTileCache(void *data, struct vec2i pos);
287 static bool CheckOverlaps(
288 const Thing *item, const struct vec2 pos, const struct vec2 vel,
289 const struct vec2i size, const CollisionParams params,
290 CollideItemFunc func, void *data, CheckWallFunc checkWallFunc,
291 CollideWallFunc wallFunc, void *wallData, const struct vec2i tilePos);
OverlapThings(const Thing * item,const struct vec2 pos,const struct vec2 vel,const struct vec2i size,const CollisionParams params,CollideItemFunc func,void * data,CheckWallFunc checkWallFunc,CollideWallFunc wallFunc,void * wallData)292 void OverlapThings(
293 const Thing *item, const struct vec2 pos, const struct vec2 vel,
294 const struct vec2i size, const CollisionParams params,
295 CollideItemFunc func, void *data, CheckWallFunc checkWallFunc,
296 CollideWallFunc wallFunc, void *wallData)
297 {
298 TileCacheReset(&gCollisionSystem.tileCache);
299 // Add all the tiles along the motion path
300 AlgoLineDrawData drawData;
301 drawData.Draw = AddPosToTileCache;
302 drawData.data = &gCollisionSystem.tileCache;
303 BresenhamLineDraw(
304 svec2i_assign_vec2(pos), svec2i_assign_vec2(svec2_add(pos, vel)),
305 &drawData);
306
307 // Check collisions with all tiles in the cache
308 CA_FOREACH(const struct vec2i, dtv, gCollisionSystem.tileCache)
309 if (!CheckOverlaps(
310 item, pos, vel, size, params, func, data, checkWallFunc, wallFunc,
311 wallData, *dtv))
312 {
313 return;
314 }
315 CA_FOREACH_END()
316 }
AddPosToTileCache(void * data,struct vec2i pos)317 static void AddPosToTileCache(void *data, struct vec2i pos)
318 {
319 CArray *tileCache = data;
320 const struct vec2i tv = Vec2iToTile(pos);
321 TileCacheAdd(tileCache, tv);
322 }
CheckOverlaps(const Thing * item,const struct vec2 pos,const struct vec2 vel,const struct vec2i size,const CollisionParams params,CollideItemFunc func,void * data,CheckWallFunc checkWallFunc,CollideWallFunc wallFunc,void * wallData,const struct vec2i tilePos)323 static bool CheckOverlaps(
324 const Thing *item, const struct vec2 pos, const struct vec2 vel,
325 const struct vec2i size, const CollisionParams params,
326 CollideItemFunc func, void *data, CheckWallFunc checkWallFunc,
327 CollideWallFunc wallFunc, void *wallData, const struct vec2i tilePos)
328 {
329 struct vec2 colA, colB, normal;
330 // Check item collisions
331 if (func != NULL)
332 {
333 const CArray *tileThings = &MapGetTile(&gMap, tilePos)->things;
334 CA_FOREACH(const ThingId, tid, *tileThings)
335 Thing *ti = ThingIdGetThing(tid);
336 if (!CheckParams(params, item, ti))
337 {
338 continue;
339 }
340 if (!MinkowskiHexCollide(
341 pos, vel, size, ti->Pos, ti->Vel, ti->size, &colA, &colB,
342 &normal))
343 {
344 continue;
345 }
346 // Collision callback and check continue
347 if (!func(ti, data, colA, colB, normal))
348 {
349 return false;
350 }
351 CA_FOREACH_END()
352 }
353 // Check wall collisions
354 if (checkWallFunc != NULL && wallFunc != NULL && checkWallFunc(tilePos))
355 {
356 // Hack: bullets always considered 0x0 when colliding with walls
357 // TODO: bullet size for walls
358 const struct vec2i sizeForWall =
359 item->kind == KIND_MOBILEOBJECT ? svec2i_zero() : size;
360 if (MinkowskiHexCollide(
361 pos, vel, sizeForWall, Vec2CenterOfTile(tilePos), svec2_zero(),
362 TILE_SIZE, &colA, &colB, &normal) &&
363 !wallFunc(tilePos, wallData, colA, normal))
364 {
365 return false;
366 }
367 }
368 return true;
369 }
370
371 static bool OverlapGetFirstItemCallback(
372 Thing *ti, void *data, const struct vec2 colA, const struct vec2 colB,
373 const struct vec2 normal);
OverlapGetFirstItem(const Thing * item,const struct vec2 pos,const struct vec2i size,const struct vec2 vel,const CollisionParams params)374 Thing *OverlapGetFirstItem(
375 const Thing *item, const struct vec2 pos, const struct vec2i size,
376 const struct vec2 vel, const CollisionParams params)
377 {
378 Thing *firstItem = NULL;
379 OverlapThings(
380 item, pos, vel, size, params, OverlapGetFirstItemCallback,
381 &firstItem, NULL, NULL, NULL);
382 return firstItem;
383 }
OverlapGetFirstItemCallback(Thing * ti,void * data,const struct vec2 colA,const struct vec2 colB,const struct vec2 normal)384 static bool OverlapGetFirstItemCallback(
385 Thing *ti, void *data, const struct vec2 colA, const struct vec2 colB,
386 const struct vec2 normal)
387 {
388 UNUSED(colA);
389 UNUSED(colB);
390 UNUSED(normal);
391 Thing **pFirstItem = data;
392 // Store the first item in custom data and return
393 *pFirstItem = ti;
394 return false;
395 }
396
CheckParams(const CollisionParams params,const Thing * a,const Thing * b)397 static bool CheckParams(
398 const CollisionParams params, const Thing *a, const Thing *b)
399 {
400 // No same-item collision
401 if (a == b)
402 return false;
403 if (!params.AllActors)
404 {
405 // Don't collide if items are on the same team
406 if (CollisionIsOnSameTeam(b, params.Team, params.IsPVP))
407 {
408 return false;
409 }
410 // Pilot / vehicle collision
411 if (a->kind == KIND_CHARACTER && b->kind == KIND_CHARACTER)
412 {
413 const TActor *aa = CArrayGet(&gActors, a->id);
414 const TActor *ab = CArrayGet(&gActors, b->id);
415 if (aa != NULL && ab != NULL)
416 {
417 // Pilots never collide with anything
418 if (aa->vehicleUID != -1 || ab->vehicleUID != -1)
419 {
420 return false;
421 }
422 // Unpiloted vehicles don't collide with other actors
423 if (aa->pilotUID == -1 || ab->pilotUID == -1)
424 {
425 return false;
426 }
427 }
428 }
429 }
430 if (params.ThingMask != 0 && !(b->flags & params.ThingMask))
431 {
432 return false;
433 }
434
435 return true;
436 }
437
GetWallBouncePosVel(const struct vec2 pos,const struct vec2 vel,const struct vec2 colPos,const struct vec2 colNormal,struct vec2 * outPos,struct vec2 * outVel)438 void GetWallBouncePosVel(
439 const struct vec2 pos, const struct vec2 vel, const struct vec2 colPos,
440 const struct vec2 colNormal, struct vec2 *outPos, struct vec2 *outVel)
441 {
442 const struct vec2 velBeforeCol = svec2_subtract(colPos, pos);
443 const struct vec2 velAfterCol = svec2_subtract(vel, velBeforeCol);
444
445 // If normal is zero, this means we were in collision from the start
446 if (svec2_is_zero(colNormal))
447 {
448 // Reverse the vector
449 *outPos = svec2_subtract(pos, vel);
450 *outVel = svec2_scale(vel, -1);
451 return;
452 }
453
454 // Reflect the out position by the collision normal about the collision pos
455 const struct vec2 velReflected = svec2(
456 colNormal.x == 0 ? velAfterCol.x : colNormal.x * fabsf(velAfterCol.x),
457 colNormal.y == 0 ? velAfterCol.y : colNormal.y * fabsf(velAfterCol.y));
458 *outPos = svec2_add(colPos, velReflected);
459
460 // Out velocity follows the collision normal
461 *outVel = svec2(
462 colNormal.x == 0 ? vel.x : colNormal.x * fabsf(vel.x),
463 colNormal.y == 0 ? vel.y : colNormal.y * fabsf(vel.y));
464 }
465