Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

 
Advanced search

1034347 Posts in 41721 Topics- by 33322 Members - Latest Member: lucas.awoker

August 20, 2014, 02:24:36 PM
TIGSource ForumsDeveloperTechnical (Moderators: Glaiel-Gamer, ThemsAllTook)Enemy crowding
Pages: [1]
Print
Author Topic: Enemy crowding  (Read 661 times)
Ethan_Hall
Level 0
**


View Profile Email
« on: April 02, 2013, 07:04:09 AM »

Hi all!

I'm working on a game akin to LOTZ:LTTP, in C++ and OpenGL. I have some basic collision detection that works great for walls and enemies. The collision REACTION is my problem.

I've noticed that in many games, enemies are allowed to overlap on the screen; there are no collisions between them. I want to allow collision resolution between enemies. I would like them to able to approach the player all at the same time without overlapping; I want to see enemies crowd around the player character.

Right now I don't have a "physics" system in place; all of the movement is done by directly altering player/enemy position information, rather than editing velocity, acceleration, or force. I want to keep everything as simple as possible, so I would like to stick to only editing positional information if I can.

So, my two questions:

Is it possible to have enemy crowding without setting up a more complicated physics scheme?
What kind of simple system would lend itself well to enemy crowding behavior?

Thanks for all help/opinions/advice!
Logged
Martin 2BAM
Level 10
*****


@iam2bam


View Profile WWW Email
« Reply #1 on: April 02, 2013, 08:26:32 AM »

Maybe you can use spring-like reactions, that is: the applied response force to the object is proportional (linearly or logarithmically) to the insertion between the two overlapping shapes.
Tweaking the response function will make them jitter more or less.

If your basic shapes are circles, the insertion is given by the distance between the two centers. If it's higher than the sum of both radii, there is no intersection, otherwise that number is how deep they're intersecting.
Logged

Working on HeliBrawl
ஒழுக்கின்மை
Level 10
*****


Also known as रिंकू.

RinkuHero
View Profile WWW Email
« Reply #2 on: April 02, 2013, 08:30:53 AM »

you can use flocking behavior

http://blog.soulwire.co.uk/laboratory/flash/as3-flocking-steering-behaviors
Logged

nospoon
Level 1
*


View Profile Email
« Reply #3 on: April 02, 2013, 09:13:56 AM »

Springs are a good solution.

Basically :
Code:
if entity1.size+entity2.size < distance(entity1,entity2):
insert constraint between them;

I used this method in my crap as3 game, didnt even optimize it, and it still worked great.
( here's that game if anyone interested)
Logged
Ethan_Hall
Level 0
**


View Profile Email
« Reply #4 on: April 02, 2013, 10:29:50 AM »

I already have something akin to a spring system working. But it doesn't work very well.

I understand how to find the amount of intersection between the 2 boxes I am using to bound my enemies. But I don't understand where/how to move each one.

If two enemies collide, should they each be moved an equal amount in the corresponding directions so they don't intersect anymore? What if one of the enemies is standing still?

I would like to implement flocking behavior for enemies akin to the examples shown in Paul's link, though I don't think I would have time...
Logged
nikki
Level 10
*****


View Profile Email
« Reply #5 on: April 02, 2013, 12:14:04 PM »

Quote
I would like to implement flocking behavior for enemies akin to the examples shown in Paul's link, though I don't think I would have time...

then use an existing library ?
Logged
Martin 2BAM
Level 10
*****


@iam2bam


View Profile WWW Email
« Reply #6 on: April 02, 2013, 12:52:12 PM »

I understand how to find the amount of intersection between the 2 boxes I am using to bound my enemies. But I don't understand where/how to move each one.

If two enemies collide, should they each be moved an equal amount in the corresponding directions so they don't intersect anymore? What if one of the enemies is standing still?

Take into account to apply a force, integrated over time, and not hardly set positions or it won't work.
This will keep shapes overlapping over and over in an unstable equilibrium, meaning they don't want to stay that way for very long. If you don't want these intersections aesthetically, you'll have to figure out a smarter way to flank their obstacles.

If you want enemies to keep still you can define a ratio of "pushability", that makes some objects be more prone to pushing. Infinite means immovable. Actually, this is sort of how "mass" works in physics.

If you want them to flank and round the player, you must implement flocking as Paul suggested.
Logged

Working on HeliBrawl
BleakProspects
Level 4
****



View Profile WWW Email
« Reply #7 on: April 02, 2013, 01:24:18 PM »

I think what you should be noticing here OP is that you can't get around implementing basic velocity/force physics. Flocking won't work without it either. Just do it. It will make your life much easier.
Logged

zhov
Manbaby
*


View Profile Email
« Reply #8 on: April 02, 2013, 01:27:50 PM »

I did a bit of work making OpenSteer less of a hassle to start using. Maybe it'll help with what you want. There are examples and etc.

https://github.com/hovatterz/opensteer
Logged
Ethan_Hall
Level 0
**


View Profile Email
« Reply #9 on: April 02, 2013, 01:54:42 PM »

Thanks for the help/advice everyone!

The main problem is, this is my capstone project, so I'm trying to finish this while holding a small job and doing other schoolwork, and the capstone project must be done in 3 weeks. I was trying to get a simple/quick solution that still looks/feels good.

Right now I am just trying to implement the combat/collision between the player character's sword and the enemies (arguably the most important part of the game). So I just turned off CD between the enemies, allowing them to overlap for the moment. The question is whether or not I want to take the time (or I have the time) to implement velocity/force physics...

The flocking stuff, including the libraries and links above, look super awesome, and if I have enough time I would like to try using them. But given that the project must be 99% done and be damn close to error-free by 3 weeks time, I may not get to it... we still have other outstanding issues.

Thanks again for all the help!
Logged
nospoon
Level 1
*


View Profile Email
« Reply #10 on: April 02, 2013, 02:09:03 PM »

You could implement the constraints in about 10 lines of code (unoptimized, but fast enough).
I was actually pretty amazed on this simple idea works.

Basically :
Code:
for a in entities:
    for b in entities:
        if(a == b): continue;
        doConstraint(a,b);
and then :
Code:
doConstraint(a,b){
float dist = a.distanceTo(b); //calculate distance, you can optimize by not using sqrt
if(dist < a.size+b.size){
//distance is too small, apply constraint
delta = b-a;
rest = a.size+b.size;
diff = (dist-rest)/dist;
a+=delta*0.5*diff;
b-=delta*0.5*diff;
}
}

The code is probably a bit off (wrote it from memory, and i also suck at maths).
I assumed, that a and b are vectors, so a = (x,y) etc.

I learned about the constraints from here : http://www.gamasutra.com/view/feature/131313/advanced_character_physics.php?print=1
and it's really helpful.
Logged
Lee
Level 1
*


View Profile
« Reply #11 on: April 02, 2013, 02:44:25 PM »

Yeah collision resolution is a pain in the bum. Detection is easy. The simplest but cpu costly thing I can think of would be to move the objects back in time when they collide... i.e. move in the opposite direction until they are not colliding (which should be less than the velocity of either object, otherwise they were colliding when they were created and you got a problem).

A simple "brute force" kind of approach:
Code:
//o1 for object 1, o2 for object 2
float vel = max(max(o1->velx,o1->vely),max(o2->velx,o2->vely));
for (int i=0; i<vel; i++){
  float x1 = ((float)o1->velx/vel)*i;
  float y1 = ((float)o1->vely/vel)*i;
  float x2 = ((float)o2->velx/vel)*i;
  float y2 = ((float)o2->vely/vel)*i;
  if (bounding_box(o1->x-x1,o1->y-y1,o1->w,o1->h, o2->x-x2,o2->y-y2,o2->w,o2->h)==false)
  {return;}
}
Basically this keeps moving them back by a fraction of their velocity until they are not colliding (note that it moves in subpixels - at i=vel they will be at their previous position). It's not really efficient but it works and it's easy. But you can't really do it without velocity (knowing how much they moved that frame).

You could of course use the penetration depth Well, hello there! since you already have it it may be better. I think you can just do the above for loop in one by replacing vel with penetration depth:

Code:
float mass_ratio = o1->mass/(o1->mass+o2->mass);
int o1->x += depthx*(1-mass_ratio);
int o1->y += depthy*(1-mass_ratio);
int o2->x -= depthx*mass_ratio;
int o2->y -= depthy*mass_ratio;

basically depth*ratio of masses. The good thing about this is that the heavier object moves less than the smaller object.

But all of this only fixes two objects inter-colliding (overlapping) and it will likely collide again next frame unless you have some kind of collision physics as well. You then need to bounce them off each other using some simplification like reversing velocity (times by mass ratio to have the smaller mass be impacted more than the bigger object), or with proper elastic collision physics.

Having a velocity can be pretty handy for physics stuff. Also moving without a velocity is pretty unstable if you're just doing pos+=number, it will run at different speeds on different computers unless you multiply it by (1/framerate) -e.g. the time per frame.
« Last Edit: March 10, 2014, 08:12:31 AM by Lee » Logged
Lee
Level 1
*


View Profile
« Reply #12 on: April 03, 2013, 11:12:40 AM »

This line of code in nospoon's reply is wrong:
Code:
if(dist < a.size+b.size)
it will produce false collisions, this is because the distance that objects will be colliding depends on where the objects position is defined. If the sprite is positioned by the top left corner (pretty common) then the colliding distance will be the size of the left sprite:
Code:
colliding dist = 6
xxxxxx
'----|'---|
|    ||   |
|----||---|
colliding dist = 5
xxxxx
'---|'----|
|   ||    |
|---||----|
colliding dist is not 6+5, below would be a false positive:
xxxxxxxxxxx
'----| '---|
|    | |   |
|----| |---|
However if the position is defined as the center of the sprite then it's half object 1 + half object 2:
Code:
no collision
   xxxx xxx
|-----| |---|
|  '  | | ' |
|-----| |---|
collision
   xxxxxxx
|-----||---|
|  '  || ' |
|-----||---|
However this only works for balls because the distance to the surface of a ball is the same at any angle, whilst with squares the distance to the surface changes around the perimeter, unless you cut the check into x and y and return as a collision if the x distance and y distance are less than 1/2 width(a+b) and 1/2 height(a+b) respectively... But again this requires their position to be defined as the center of the object and you can do a bounding box check which makes it pointless. The code was probably for particle collisions, which are defined as points.

Sorry if these points seem super obvious but I thought it was worth pointing out.

Here's a good page on spring physics: http://gafferongames.com/game-physics/spring-physics/
Logged
nospoon
Level 1
*


View Profile Email
« Reply #13 on: April 03, 2013, 11:55:24 AM »

This line of code in nospoon's reply is wrong:
Code:
if(dist < a.size+b.size)
it will produce false collisions, this is because the distance that objects will be colliding depends on where the objects position is defined. If the sprite is positioned by the top left corner (pretty common) then the colliding distance will be the size of the left
I think that i forgot to mention that - size is the radius of the sprite, and the position is in the center of the sprite.
It's not pixel-perfect, but it does the job fairly well, and is really easy to implement.

Sprites arent usually ideal rectangles, so circle-circle collision usually works well.
Logged
Noogai03
Level 6
*


WHOOPWHOOPWHOOPWHOOP


View Profile WWW Email
« Reply #14 on: April 05, 2013, 06:03:18 AM »

It was only a few days ago that I had a similar problem regarding collision resolution - in the end I used a method that works ok:
http://www.opentk.com/node/869
http://stackoverflow.com/questions/9090853/top-down-2d-sprite-collision-handling-with-moving-sprites

Also a tutorial by Alex Diener (ThemsAllTook on this forum) that's different
http://sacredsoftware.net/tutorials/Collisions/CollisionsPart1.html
Logged

So long and thanks for all the pi
Pages: [1]
Print
Jump to:  

Theme orange-lt created by panic