Jump to content

  • Log In with Google      Sign In   
  • Create Account

Finalspace

Member Since 29 Mar 2012
Offline Last Active Today, 11:24 AM

#5275761 2d Circle different ARC's Collision detection

Posted by Finalspace on 15 February 2016 - 09:58 AM

If you got the local closest point on the circle, just use arctan2 to get the angle for that point.

Secondly bring that angle into range 0 - 2*PI (google: normalize angle radians)

Detect region/arc from that normalized angle. Done.




#5274230 To use tiles or pre rendered images for game graphics

Posted by Finalspace on 04 February 2016 - 07:27 AM

 

In my own game - which is a 2D overhead RPG - I have multiple different layer types, and each layer type can go into any position.

 

However, you might not need that flexibility/complexity. Instead, I'd start with something like this and tweak it as I go:

//Pseudocode:
struct World
{
     Array<Layer> layers;
};
 
struct Layer
{
     Backdrop backdrop; //Drawn first.
     Tilemap tilemap; //Drawn second. Can collide with.
     Array<Decal> decals; //Draw third.
 
     Array<Entity> activeEntities;

     //This controls player-movement-related scrolling. i.e. you multiply this against the player's position to get the layer's scroll position.
     //For example, you may want a layer FIXED to the viewpoint with NO scrolling no matter how much the player moves. Like sun rays.
     Vector2f parallax;
};

//What I call a large repeating image that scrolls, and can be UNDER (i.e. background) or OVER (i.e. foreground) a player
struct Backdrop
{
     ImageID appearance;

     //This is the scrolling that occurs automatically, without the player moving. Things like clouds or mist.
     Vector2f scrollSpeed;
};

//What I call a freely-placed, freely-rotated, freely-scaled image
struct Decal
{
     Position position;
     float scale;
     float rotation;
     ImageID appearance;
};
 
struct Tile
{
     Shape collisionShape;
     ImageID appearance;
};
 
struct Tilemap
{
      Grid<Tile> tiles; //Note: Breakable/interactive tiles are entities pretending to be tiles, as are invisible triggers, movable doors, and so on.
};

[Edit:] Forgot to include the Backdrop definition.

Why use structs and not a class?

 

 

These seems to be just data structures - so structs are the best way to define those. No need for classes which is great ;-)




#5271731 Resolving collisions with enums

Posted by Finalspace on 18 January 2016 - 12:27 PM

Hey all, just looking for some suggestions on how to resolve collisions in my game engine. 

 

Here's what I'm working with:

 

I have a spatial partition of GameObjects, where I do my collision detection. If a collision is detected, A Resolution object is returned with the following format:

 

struct Resolution{

  unsigned int colBoxA;   //Index of collision box within object

  unsigned int colBoxB;

  //One or two trival members not important here

};

 

1. I iterate through all the Partition buckets to test for collisions.

 

2. I have a Map container which stores all the Resolution objects. To ensure each collision is unique they key for the map is

   a pair of both GameObject_ID's, and the value is the Resolution object. 

 

3. colBoxA and colBoxB are indices to AABB's that reside in each object. Let's say ObjectA has two collision boxes: A hitbox and a shield, while ObjectB has a single collision box: a projectile. So an entry in my Resolution container has information on which two objects are colliding, and on which respective collisionbox.

 

4.  Each Collisionbox has an enumerated type associated with it (Wall,projectile,hitbox,melee) etc.....

 

I want to resolve the collision based on both the types associated with the collision, and apply the result correctly to each object. I've looked around,  and it seems like I should be using some type of Strategy Pattern. By not using this, it looks like I am facing nested switches (not going to happen). Even with the Strategy Pattern, I am unsure on how to implement this.

 

Any advice or similar documentation would be greatly appreciated smile.png

 

A simple solution would be to use a 2d array for the collision type. This can be a const fixed array or a dynamic array created on the game initialization process. This would look like this (I use this for my contact generators - copied from my java source):

public final class ContactGeneratorFactory {
	private final int MAX_GENERATORS_PER_SHAPE = ShapeType.COUNT.id;
	private final ContactGenerator[][] generators = new ContactGenerator[MAX_GENERATORS_PER_SHAPE][MAX_GENERATORS_PER_SHAPE];
	
	public ContactGeneratorFactory() {
		generators[ShapeType.Plane.id][ShapeType.Circle.id] = new PlaneCircleContactGenerator();
		generators[ShapeType.Plane.id][ShapeType.Box.id] = new PlaneEdgeContactGenerator();
		generators[ShapeType.Plane.id][ShapeType.Polygon.id] = new PlaneEdgeContactGenerator();
		generators[ShapeType.LineSegment.id][ShapeType.Circle.id] = new EdgeCircleContactGenerator();
		generators[ShapeType.LineSegment.id][ShapeType.Box.id] = new EdgeEdgeContactGenerator();
		generators[ShapeType.LineSegment.id][ShapeType.Polygon.id] = new EdgeEdgeContactGenerator();
		generators[ShapeType.Box.id][ShapeType.Circle.id] = new EdgeCircleContactGenerator();
		generators[ShapeType.Box.id][ShapeType.Box.id] = new EdgeEdgeContactGenerator();
		generators[ShapeType.Box.id][ShapeType.Polygon.id] = new EdgeEdgeContactGenerator();
		generators[ShapeType.Polygon.id][ShapeType.Circle.id] = new EdgeCircleContactGenerator();
		generators[ShapeType.Polygon.id][ShapeType.Polygon.id] = new EdgeEdgeContactGenerator();
		generators[ShapeType.Circle.id][ShapeType.Circle.id] = new CircleCircleContactGenerator();
	}
	
	public int generate(Transform transformA, Transform transformB, Shape shapeA, Shape shapeB, int offset, Contact[] contacts, ContactAcceptor acceptor) {
		int result = 0;
		
		// Sort shape types
		boolean flip = false;
		ShapeType typeA = shapeA.type;
		ShapeType typeB = shapeB.type;
		if (typeA.id > typeB.id) {
			ShapeType temp = typeA;
			typeA = typeB;
			typeB = temp;
			flip = true;
		}
		
		// Find generator by both shape type id´s
		ContactGenerator generator = generators[typeA.id][typeB.id];
		if (generator != null) {
			// do something with the found generator
		}
	}
}

You just create classes based on some simple CollisionResponse interface and create instances for every possible pairs.

 

Important: The order of your object collision enumeration matters, see:

public enum ShapeType {
	Plane(1),
	LineSegment(2),
	Box(3),
	Polygon(4),
	Circle(5),
	COUNT(6);
	
	public final int id;
	
	private ShapeType(int id) {
		this.id = id;
	}
}



#5271305 Understanding cross product without delving too much on Linear algebra

Posted by Finalspace on 15 January 2016 - 11:26 AM

 


This means there is an infinite number of vectors that are parallel to a plane, so all three of the edges of a triangle are parallel to the plane of the triangle.

Still confuse about this. so that means this plane is also the surface? That means in 2D, this plane is facing up or facing to any direction? But let say if the plane is pointing up, does that mean the vertices as well?

 

 

A plane does not have any vertices at all - a plane is just either a point + a unit vector or the plane is defined as a unit vector and some signed distance (scalar) to the origin. And in 2D a plane is just a line with infinite width.

 

Try to imagine just a point in some world and some arrow from the point to a specific direction - Thats the easiest way to understand the concept behind it.

 

For a triangle in 3D, vertices can be seen as planes as well. Each 3D Vertex in world space can also be defined as a unit normal with a distance to the origin. Each vertex may have its own normal overriden, so each point can face in a different direction - this is important when you want some smoothness for lightning as a example.




#5266772 Tilebased Platformer prototype

Posted by Finalspace on 17 December 2015 - 08:31 AM

I am not sure where this post belong, but i want to give something back to this awesome community - so i made a tiny tile-based platformer prototype using a robust physics system based on speculative contacts - including pushing of blocks and stacking ;-)
 
Here is the full javascript commented sourcecode without any dependencies at all - you can do whatever you want with it.
 
 
Its far from complete, but here are some easy additions you can make:
 
- Apply friction to get a real platformer experience
- More solver iterations / accumulate impulses to get a more robust experience (Faster convergence for dynamic vs dynamic)
- Edit tilemap while you are playing
- Load and save tilemap (would require at least a simple webservice to call on)
- Jump through platforms
- Elevators
- Enemies
- Ladders
- Spikes
- Doors
- Rendering sprites
 
Much harder, but really useful additions:
 
- Support for circles
- Support for line segments
- Support for polygons
- Support for local rotations
- Switch to a real rigid body dynamics simulation - requires to generate two contacts in some cases
 
Merry christmas,
Finalspace



#5264561 Simple 2D collision detection for a platform game (easiest solution possible...

Posted by Finalspace on 02 December 2015 - 03:25 AM

Does the collisionRectangle contains the integrated velocity? If yes you need to use the prev position and project the movement against the tiles - otherwise it will never be stable for fast objects like bullets or jumppads. Or a much simpler solution, you limit the velocity to a certain amount so you never pass through tiles.

 

Another approach would be using real contact resolution and use a speculative contacts solver: this has the advantage of fixing the bullet-through-paper problems in a very simple way -> When the projected relative velocity is greater than the signed closest distance between the bodies/rectangles divided by the timestep, you just have to remove the velocity so that its just touching each other. Really easy, but powerful technique and is simple to implement when you dont need rotation dynamics - which you mostly dont need in 2D-Platformers.

 

If you need more informations, paul has a really great tutorial for this: http://www.wildbunny.co.uk/blog/2011/12/11/how-to-make-a-2d-platform-game-part-1/

And the best benefit of this you get "real" physics! So stacking and pushing of objects will work out-of-the-box ;-)

But there are two downsides of this technique which you need to keep in mind: Ghost collisions and internal edge issues can happen, but for a tilebased game this can be easily fixed.




#5263788 Lerp vs fastLerp

Posted by Finalspace on 27 November 2015 - 04:21 AM

They are exactly the same thing, just different forms to write it.

 

http://www.wolframalpha.com/input/?i=a+*+%281+-+t%29+%2B+b+*+t+

 

For numerical calculation in a CPU, the second form should  be better for two reasons, less numerical error (probably not noticeable in normal use) and faster execution.

 

Thats the point - when does the first form produces a different result than the second form? I never had any issues using the simpler form for all my math stuff (physics engine, data visualizations, games, enterprise-applications).




#5256571 Contact points confuses me

Posted by Finalspace on 10 October 2015 - 02:00 PM

I am trying to understand how the contact generation works, so i have disassembled box2d lite and visualized the contacts, normals and the clipping planes.
 
From my understanding of contact point generation it goes like this:
 
- Find the axis of minimum penetration either on A or B
- Find the reference face by axis of minimum penetration (reference face is always on A)
- Find the incident face (negative axis of minimum penetration)
- Clip incident face against reference face side planes
- Keep points which are behind the reference face plane
 
Which bugs me a lot, when the minimum penetration axis is found on B then the contact points are sitting on B - not A.
I always though that contact points should be consistent and the contact points does always sit on A but can be projected back to B using (point + normal * distance) when needed.
 
Image contacts sits on B: (minimum penentration axis is found on B)
 
Contacts4.png
 
Image contacts sits on A (minimum penentration axis is found on A):
 
Contacts3.png
 
This really confuses me, so i have some questions:
 
- What are proper contact points? When sits there on A and when sits there on B
- Why does box2d lite works with just one contact point (rA and rB is just rA = point - posA and rB = point - posB)?
- Why does box2d lite use two clipping operations?
- What does the following code do? (I know that it determines the face, but what is relativeTol and absolutTol)?
	const float relativeTol = 0.95f;
	const float absoluteTol = 0.01f;

	if (faceA.y > relativeTol * separation + absoluteTol * hA.y)
	{
		axis = FACE_A_Y;
		separation = faceA.y;
		normal = dA.y > 0.0f ? RotA.col2 : -RotA.col2;
	}

Can you guys shed light into my darkness?
 
For completeness i attached the modified box2d lite source - for contact visualization.
 
Thanks,
Final

Attached Files




#5256267 Fluid simulation on Bullet Physics

Posted by Finalspace on 08 October 2015 - 01:47 PM

I'm looking for some way to simulate fluids on Bullet Physics, but it doesn't seem to offer support to this kind of simulation. So how can I do it? It needs to be efficient and have decent quality, use OpenCL (for better compatibility with different GPU brands) or run on CPU (I prefer this because it would be the best for compatibility, but I don't know if it's possible) and work fine for big simulations like rivers and small ones like bottles.

 

Does anyone know what could I do? Is there any library for that or am I going to need to do it all by myself?

 

There was afaik a tryout in the past to get "Fluidsv2" running in bullet, but there was several issues with that and it may be somewhere around.

But i think it was just dropped...

 

So you basically have no other choice but to do it yourself.

 

Its not that "hard" getting a fine fluid simulation up and running, but integrating with an existing physics system is very challenging!

But the most painful work you always need to do in fluid-simultions is the parameter tweaking - its just a p i t a....

 

A very simple paper which may gets you started is "Particle based viscoelastic fluids by clavet"... Easy to implement and gets results very fast.




#5229412 I already have a game, but I want to make a new engine from scratch for it. T...

Posted by Finalspace on 17 May 2015 - 01:26 AM

TheBennyBox is a great source for engine development - but only for the 3D Stuff:

https://www.youtube.com/user/thebennybox

 

Also there is a book called "Game Engine Archtecture" from one of the uncharted developers which is really good. But i give you fairly good warning: This book is high-level and is not suitable for beginners!

http://www.amazon.com/Engine-Architecture-Second-Jason-Gregory/dp/1466560010/ref=sr_1_1?ie=UTF8&qid=1431847590&sr=8-1&keywords=game+engine+architecture




#5220432 "Guide to implement a platformer" only issues :-(

Posted by Finalspace on 31 March 2015 - 01:49 AM

I tried another technique i was thinking about.

Using line segment intersections and find the smallest time when the player hits a tile and use this to adjust the movement delta.

 

This basically should work... but its not... my computed min time explodes and increase magically when the player was moving, even when player stands still.

 

I dont see any mistakes right now, basically what i do is to find the tile center for any tile i test against, find the min and max corner of the tile using the grown tile size with the player size included and then just divide by the player delta vector. This should give me some sort of barycentric coordinates if i remember correctly, but its not :-(

 

For simplicity i just added the left side test of the test to see what happens.

 

Can someone look into it please?

http://jsfiddle.net/2fbd72vb/5/




#5219089 2D AABB Collision resolution and collision system/class design

Posted by Finalspace on 25 March 2015 - 10:07 AM

@CC Ricers

Hmm I think I tried something like that and a few things didn't work out, thats why I switched to calculating the "time of impact" instead of penetration amount checking.

One of the things was the same thing that's being adressed in the article: Wrong resolutions. But I'm not sure If I tried it with the correct ordering.

Maybe I could try swapping the techniques around and do it with the least penetration amount technique again.

 

I'm kind of sick of fiddling around with it. For two years I am stuck with this problem now and I'm making next to no progress... soooooo frustrating argh...

But of course I didn't work 2 years non-stop on it. Otherwise I would already have gone insane rolleyes.gif

Have been procrastinating a lot because I have absolutely no idea what to do anymore and I'm kind of lazy and demotivated.

 

I know that feeling... it was the same for me for a other game prototypes i made.

 

But regarding platformer physics, i got pretty good results using technique called speculative contacts with sonics sensors for the entities.

 

The core idea behind that technique is use sensor points on the left/right edges and top/bottom edges for every entity to determine which tiles needs to be checked.

This is your broadphase if you will, then grow every tile with the entity half-size (minkowski difference) and determine the closest point against that fatten tile aabb. This closest point is extremly simple to determine of your sensors include the separating normal as well - so its just a simple vector projection. Lastly you get the difference between entity position and the closest point. Then you project this difference against the separating normal from the sensor and create a contact for it including its distance even when positive. At final stage, you just need to solve this contact using the speculative contacts approach descriped here: 

http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/

 

This technique works for non-tile shapes as well, you just need a way to calculate the closest point and the distance between the centers using minkowski difference.

Of course for non-aabb cases, the sensor approach may not work, but i never tried it.

 

The only downside to this technique you cannot control how a wall bounces you off. Bouncing will be solved by automatically when you include its in the solver as well. But you cannot control how the object bounces - like in box2d for example, where you can specifiy the coeffecient of restitution. Therefore this technique is mostly suited for platformer - just to give you an example: Little big planet use this technique and is therefore extremely stable.

 

But the main benefit of this technique is to not worry about TOI at all and get continous collisions out-of-the-box - the system finds a global state very fast and can be used for rigidbody physics as well.

 

If you need further explanations, check out the link i posted in the block above.

 

Greetings,

Final




#5207626 Rendering 2D game w/ orthographic projection

Posted by Finalspace on 30 January 2015 - 01:25 AM

If you resize the window you should resize the viewport aka glViewport() to fit the new screen size.

Regards the orthographic projection, this depends on the game you are working on.

In a pong clone you may want a fixed orthographic projection which never change - this will automatically scale up/down based on the viewport.

If you also want to preserve the aspect ratio you need to calculate the offsets and sizes yourself and pass this to the glviewport (Letterbox Aspect Ratio).

 

In some other games, you may update your orthographic projection to fit the window size, but these would require you just have to scale your game entirely yourself.

 

Modern games use mostly a perspective matrix and setup a camera to fit the level portion in, even in a 2D scenario because you dont have to deal with aspect ratio / stretching at all.




#5204433 Player Input System

Posted by Finalspace on 15 January 2015 - 03:44 AM

I use a state based singleton class for keyboard, gamepad and mouse input. The states are polled at the start for every frame.

Important is that i record the previous state - to differentiate between key down (Continues) and key press (Single key).

 

In my player class i can then do something like that in its update method (Jump example):

if (Input.isKeyPressed(Input.KEY_UP)) {
	if (!jumpRequested && onGround) {
		// Jump key is pressed initially
		jumpRequested = true;
		jumpForce = maxJumpForce;
	} else {
		// Jump key is hold down
		jumpForce -= stepJumpForce;
		if (jumpForce <= 0f) {
			jumpForce = 0f;
		}
	}
} else {
	if (jumpRequested) {
		// Jump key is released
		jumpRequested = false;
	}
}

// Apply force impulse when there is some jump force left
if (jumpRequested && jumpForce > 0f) {
	Vec2 f = new Vec2(0f, bodyMass * jumpForce);
	Vec2 c = body.getPosition();
	body.applyLinearImpulse(f, c, true);
}



#5201102 How to create a particle system on the GPU?

Posted by Finalspace on 01 January 2015 - 02:29 AM

So transform feedback seems the way i need to go and has some advantages:

 

- No need to encode/decode positions from textures so its much easier to access particle position/velocity etc.

- No need to upload the modified positions into the VBO from the CPU - everything except initialization is done on the GPU

 

but also i found some drawbacks:

 

- Use of random seems like a real pain

- Hard to create multiple emitters, cause it works on the vertex level which processes every particle - even its active or inactive - require a completely different thinking, are there some "discard" function to skip certain vertices?

- Collisions seems to be limited maybe? (Passing array pointers via Uniforms, there are some limitation in the max length of array in GLSL right?, so i need to make a multi-pass system so that collision contacts are being splitted to passes based on the limitations)

- Is there some "Null" fragment shader i can create to ignore any rendering at all? - For multipass systems i want to render at the very end, but process a few times some sort of GLSL shaders which operates on the particles only.

 

But most importantly i have no idea how to detect neighbor particles. On the CPU i had used a dynamic two-dimensional hashmap to store the particle in a dynamic grid with a bucket index-list to particle in the cell, also every particle has stored its current x/y on the dynamic grid - may change once per frame.

 

How the hell do i integrate something like that with GLSL? I heart about radix sort and some hash based algorythmn to access neighbors, but seesm to be very complex...

 

What about compute shader? I heard this is now part of opengl 4.x? Are this some sort of cuda like thing, but based on GLSL only???






PARTNERS