Jump to content

  • Log In with Google      Sign In   
  • Create Account

Finalspace

Member Since 29 Mar 2012
Offline Last Active Jun 22 2016 11:29 AM

#5296962 C Queue Linked List madness

Posted by Finalspace on 17 June 2016 - 08:59 AM

I got it working for a single producer, single consumer.

 

- Fixed size queue

- No pointer chasing (Free-list)

- Atomic operations for locks

- Plain C

- Supports returning data instead of putting

 

Here is the code:

typedef struct QueueItem {
	U8 *data;
	QueueItem *next;
} QueueItem;

typedef struct Queue {
	U8 *memory;
	U32 capacity;
	U32 used;
	volatile U32 lock;
	QueueItem *first;
	QueueItem *last;
	QueueItem *firstFree;
	QueueItem *lastFree;
} Queue;

void QueueInit(MemoryArena *arena, Queue *queue, U32 maxCount) {
	memory_index size = maxCount * sizeof(QueueItem);
	U8 *memory = PushSize(arena, size);
	queue->memory = memory;
	queue->capacity = maxCount;
	queue->used = 0;
	queue->first = 0;
	queue->firstFree = (QueueItem *)memory;
	QueueItem *cur = (QueueItem *)memory;
	QueueItem *prev = 0;
	for (U32 i = 0; i < maxCount; ++i) {
		cur->data = 0;
		cur->next = 0;
		if (i < maxCount - 1) {
			QueueItem* next = cur + 1;
			cur->next = next;
			cur = cur->next;
		}
	}
	queue->lastFree = (QueueItem *)(memory + sizeof(QueueItem) * (maxCount - 1));
	assert(queue->lastFree->next == 0);
}

B32 QueueHasItems(Queue *queue) {
	B32 result = queue->first != 0;
	return result;
}

B32 QueueCanPush(Queue *queue) {
	B32 result = queue->firstFree != 0;
	return result;
}

void QueueLock(Queue *queue) {
	U32 cmp = queue->lock;
	U32 cur;
	while ((cur = AtomicCompareExchangeU32(&queue->lock, 1, cmp)) == 1) {
		Sleep(1);
		cmp = cur;
	}
}

void QueueUnlock(Queue *queue) {
	queue->lock = 0;
}

U8 *QueuePush(Queue *queue, U8 *data) {
	U8 * result = 0;

	// Peek item from head of the list
	assert(queue->firstFree);
	QueueItem *item = queue->firstFree;

	// Pop item from the tail of the free list
	QueueItem *nextFreeItem = item->next;
	queue->firstFree = nextFreeItem;
	if (!queue->firstFree)
		queue->lastFree = 0;

	// Set data fields
	if (data)
		item->data = data;
	item->next = 0;
	result = item->data;

	// Pop item from head of the list
	if (queue->first == 0 && queue->last == 0) {
		queue->first = queue->last = item;
	} else {
		assert(queue->last);
		queue->last->next = item;
		queue->last = item;
	}

	++queue->used;

	return result;
}

U8 *QueuePop(Queue *queue) {
	// Pop item from the head of the list
	assert(queue->first);
	QueueItem *item = queue->first;
	U8 *result = item->data;
	QueueItem *next = item->next;
	if (next) {
		queue->first = next;
	} else {
		queue->last = 0;
		queue->first = 0;
	}

	// Clear data fields
	item->next = 0;

	// Push item to the tail of the free list
	QueueItem *lastFree = queue->lastFree;
	if (lastFree) {
		lastFree->next = item;
		lastFree = item;
	} else {
		queue->firstFree = item;
		queue->lastFree = item;
	}

	// Decrease used by one
	--queue->used;

	return result;
}

#define QUEUE_ADD(queue, data) (QueuePush((queue), (U8 *)(data)))
#define QUEUE_PUSH(queue, type) ((type *)QueuePush((queue), 0))
#define QUEUE_POP(queue, type) ((type *)QueuePop((queue)))

Have fun.




#5296722 C Queue Linked List madness

Posted by Finalspace on 15 June 2016 - 02:32 PM

Sleeping mode, but i got it..... NOT...

 

Changed the following:

inline B32 QueueIsFull(Queue *queue) {
	U32 used = AtomicCompareExchangeU32(&queue->used, 0, 0);
	B32 result = used >= queue->maxCount;
	return result;
}
 
inline B32 QueueHasItems(Queue *queue) {
	U32 used = AtomicCompareExchangeU32(&queue->used, 0, 0);
	B32 result = used > 0;
	return result;
}

to:

inline B32 QueueIsFull(Queue *queue) {
	B32 result = queue->firstFree == 0;
	return result;
}

inline B32 QueueHasItems(Queue *queue) {
	B32 result = queue->first != 0;
	return result;
}

Does still does not work :-(




#5290102 Is making game with c possible?

Posted by Finalspace on 04 May 2016 - 12:06 PM

There is no need to use c++ for making games. You can make games in plain C as well - just using structs and unions.

But there are a few features from the c++ compiler which makes life much easier - operator overloading and zero struct initialization. Thats it.




#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






PARTNERS