Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 27 Nov 2009
Offline Last Active May 17 2012 08:21 AM

#4810352 Delta time & Collision Detection problems

Posted by on 13 May 2011 - 12:15 PM

What about setting a max limit on the deltaTime? If it goes over a certain amount (say 0.066 for 15fps) then you cap it at 0.066. So you might see a judder in the game when your pc lags but you shouldn't get jumps that are big enough for an entity to pass through another.


#4810143 composite design question

Posted by on 13 May 2011 - 03:53 AM

When it comes to collisions between entities, and how to deal with those in components, I found the best way personally was to keep the system as generic as possible.

If a projectile collides with an entity, then specifically calls that entity's takedamage method, then you're hardwiring the rule that a collision will always give damage. What if later you decide to add a shield to that entity, or want to make it invincible to certain projectiles? If the code is hardwired into the projectile then you don't have flexibility.

There's also the possibility that the entity which was hit by the projectile does not have health or a damagable component (an indestructable wall?) , therefore it wouldn't have a takedamage method.

Here's the way I do it.

My Entity does very little, it simply holds an array of Components, either one or zero of each type being allowed. All components regardless of type have a standard init, deinit, move, update, render, and handleEvent. Each update, the entity simply loops through its components and passes through the init, move, update, render information for that frame, and on a message being sent, just passes it through to all components' handleEvent method.

I currently have about 7 component types, but the ones relevant here are CollisionComponent and LifeComponent. These are just abstract classes/interfaces, the ones which do the actual work will subclass these.

Bullets have a BulletCollisionComponent. On each update, it asks the world to give it a list of all colliding Entities. If any, it generates a takeDamage event containing the bullet id, the bullet type, the damage factor, and also the id of the entity which fired the bullet originally. It posts that event out to each Entity and then forgets about it.

The receiving Entity will pass this event through to all components which will eventually reach the LifeComponent. The LifeComponent, depending on its type, can hold information about the entity's strength, or shields, or how long it has left until self destruct (ie: bullets have a lifetime).

In this case, it's a ShipLifeComponent since I'm working with spaceships here. In it's handleEvent method, it'll respond to takeDamage events by working out if the bullet is a type which damages this ship, work out the damage after shields are taken into account, etc, then decrement the strength if necessary. When strength reaches zero it'll spawn a nice particle explosion and tell the parent entity that it's time to deinit.

If I have a PowerUpLifeComponent I'd simply ignore takedamage events, unless I want to be able to shoot them down.

As for your question about the barrel vs. enemy collision code being exactly the same.. in the above example the receiving entity's collision code is never called so it's not a problem.. only the entities which perform actions do any work in their collision code. The ones which respond to actions do the work in their lifecomponent. In this case, the enemy lifecomponent would simply decrement the life until it reaches zero. The barrel lifecomponent would do the same, but upon reaching zero would send out its own takedamage event to all entities in range. (I assume the explosive barrel is going to hurt things when it dies).


#4808072 What happened to the pc game industry?

Posted by on 08 May 2011 - 07:30 AM

You could say I've been living under a rock, so forgive me for this question.

When I graduated some years ago there was a pretty decent PC game industry. I could walk into a game or music shop and find walls of new and older PC titles plus a healthy pre-owned section.

When I left uni I dropped out of the computing scene pretty much altogether and spent my time on other things. Only recently I started getting the urge to get back into gaming and programming.

Yesterday, I decided to take a wad of cash into town and see what games I could buy. In the three game shops I tried, one did not have ANY pc titles, the other two had one row of shelves with about 15 different games, and no preowned section whatsoever. The places were full of console games.

I feel like I'm stepping back in time to the death of the Spectrum or the Amiga, when you couldn't buy new software anywhere.

Yet as far as I know the majority of people own PCs.. far more than do consoles. So I don't really get it.

So, I left with my bank balance intact and probably will continue to do so. The only game that really caught my eye was Fallout New Vegas (yeah I haven't played it yet..). I was all for giving them the huge amount of cash they were asking, but then I noticed the red box on the back about Steam. I suppose this is for another thread, but I already vowed never to buy another steam game, for so many reasons.


#4804366 [C++] Holy cow are string streams slow

Posted by on 29 April 2011 - 03:32 AM

In your next function:
stream = stringstream( line );

should you not use..

stream << line ;

I haven't read every line of the code but I'm not sure you need to be creating a new stringstream on each read.

#4796774 Burn-out!

Posted by on 10 April 2011 - 01:33 PM

What do you do when you get burnt our doing something you love?

Take a break, but the right kind of break. I like to go hillwalking, or trekking for a few days in the wilderness. I come back tired but refreshed, but more importantly I find it increases my brain power. It also temporarily stops the feeling of needing to escape!

Ironically I used to spend every weekend in the wilderness building a landscape photography portfolio, and eventually that gave me burn out. My break was to start programming!

Change the work environment, listen to different music, drink different coffee, do Nomadic Programming.

Meditate. If you can't stand the thought, go somewhere quiet and just relax and Clear Your Mind. Fits in with #1.

Get some good sleep. The unconscious mind is surprisingly good at rearranging things automatically. Sometimes you'll wake up and just 'know' how to do something without having consciously thought about it.

Write. It doesn't matter what. Quite often I find my writing eventually returns to the subject at hand. Sometimes I'm burned out because I have too many temporary thoughts in my head. Making them permanent helps clear the backlog and get the flow going.

When all else fails I change my visual studio code colour scheme. Can't believe the spark that gives me sometimes! Posted ImagePosted Image


#4794274 SetCursorPos() freezes my application

Posted by on 04 April 2011 - 10:41 AM

Is there a chance that resetting the cursor is re-sending the mousemoved event? If so, there'd be a feedback loop.

What about resetting the cursor once per frame, that way you just total up all the movements per frame?


#4793855 Problem writing string array's to text file.

Posted by on 03 April 2011 - 10:05 AM

Ok, I don't know C#, but I'm assuming that calling ToString() on an array (your 'contents' object) isn't going to print out the actual contents of the array, rather it seems to be just saying 'i'm telling you it's an array, but I don't know how to print what's inside'.

At a guess, you should probably create a for loop to go over each array element, then write contents[n] to the file individually.


#4789194 String IDs for objects, events etc.

Posted by on 22 March 2011 - 11:20 AM

How is your custom hashtable implemented? I mean just the basic principle of it. You say you use the hash directly as an array index? You cannot have such a huge almost empty array if using 4 bytes long hash values.

1. you allocate an array of whatever size you think would suit the situation. It can be 10 (ie: guns in an entity) or 1000 (ie: list of everything in the game) entries depending on where you use it.

2. when passed a string, you can generate its hash, which gives you a 4 byte int. You then use hash%sizeoftable to get the array index of this table. Of course if you have already generated the hash at program load, you can just skip the potentially expensive hashing step and use hash%sizeoftable.

3. Sometimes hash%sizeoftable will map two different hashes to the same index (a collision). I store both objects at the same location by linking them with a next pointer like a linked list. When a collision happens it slows down lookups and storage slightly but the trick is in choosing a hash function that distributes everything evenly to limit this situation. Using a bigger table than necessary also helps.

Your choice of hash function determines how well it works. Usually it's a balance of speed of generating vs avoiding collisions. I use MurmurHash2 (link) but you can find plenty of algorithms and comparisons kicking about.

I recommend dumping table contents often at runtime to see how well the distribution is working, then you can tweak table size and hash function until you get the right balance.


#4789079 String IDs for objects, events etc.

Posted by on 22 March 2011 - 06:39 AM

I found hash tables to be the way forward for this particular thing.
I use a custom hashtable and StringHandle class, that avoids re-calculating any hashes at runtime, except for say when you need to load in new resources.

Here's roughly how it works

HashTable table(1000);
GameObject* myObject = new GameObject(blah blah blah);

StringHandle handle = table.add("some kind of object", myObject);

StringHandle then contains the original string plus the original full hash value. You could store that inside the GameObject so you can quickly grab it back at any point.

then later somewhere else I can do...


The get function uses the original hash value as an index straight into an array so it's nice and quick.

I also found it useful to store the hash function I use inside the StringHandle class so that I can do:

handle = "name of some object";

Which automatically calculates the hash value for that string and stores it, so that it can be generated before it is added to any tables and held for the whole lifetime of the object. The hash value should be compatible with any table in the game of any size since I use the same hash function everywhere.

I also added the possibility to do

handle = anotherHandle

using operator overloading, which again avoids calculating a hash since it just copies the existing one over.


#4787139 2D Map System

Posted by on 17 March 2011 - 01:52 PM

There are a few revisions you might make:

Using a whole integer + a bool to store tile index plus a flag for walkability is kind of wasteful. You might consider simply reserving some bits of the integer to represent tile properties such as walkability.

Perhaps, although for the purpose of learning, debugging and readability I think the int+bool helps clarity which is a very good move for a beginner. If this were my first project I wouldn't want to dabble with bit filddling. If storage space is an issue (which it normally won't be at this level) you could make tile id a short int or even a byte if you're not going to have that many tiles, and still keep the seperate bool. That keeps you at 16 bits per tile and you've still got the seperate variables for readability.

As for Where to store entity data: don't store it in the tile -- certainly not for anything that moves. Anything that moves will cross a tile bounder every couple frames, which would lead to a huge amount of removing and insterting (and the associated memory management) that could kill your performance. Its better to keep entities on a separate list and just query for those inside the active area (also, you don't want entities to stop moving around when they are off screen, or your world will feel artificial). This is sufficient for most simple scenarios, but if you're concerned about efficiency you want to look into a spacial partitioning system, such as a quad tree or storing the map in "chunks" of 4x4 (or some other smallish power of two" tiles.

True also, but I say first make it work, then make it fast. A quadtree is probably overkill for this kind of app unless there's going to be boatloads of colliding particles for example, or very large entities. For an RPG or diablo style game you're probably talking less than 10 collidable entities on the screen at a time.

The seperate list is a must for updating/moving, but why re-build a grid system when the tile system is there already? For each entity you could find out which tile it is on, and then extract the entities located on that tile plus surrounding tiles, and only check collisions against those. Your problem would be with very large entities (say taking up 5 or 6 tiles at a time). Then a Quadtree is a good move. But you still have the associated removing and inserting, which becomes more complicated with a QT.

It's likely all hardware the game will run on is capable of actually doing a brute force checking of all entities versus all entities every frame without reaching slowdown.. if you get that far you can always go back and make it faster if or when you feel the need.


#4786422 Representation of objects on tracks? (railroads/traffic/etc)

Posted by on 16 March 2011 - 03:34 AM

I'm not yet sure how I'll go about solving "exact collisions" in curves with rectangular objects of varying size (to avoid edges overlapping)...

There should be a number of quick ways to do this as the space is already 'partitioned' for you since the objects reside on rails. You could probably assume that objects whose wheels share the same rail as another object's wheels are potential candidates for collision.

A simple technique could be to test to see if any objects sharing the same track section have their start or end points within another object's start or end points (plus a margin of error for overhang). If that test passes, you could then go on to do a more expensive but accurate test like an OBB, convex hull or poly-poly.

If the objects are covering say two or three track sections at a time then the design of linking track sections together comes into play. You can simply start at one wheel/end, scan the track section, then leap to the next, scan it, and so on until you reach the other end wheel. Any objects found occupying those sections should be investigated further. You may be able to skip this step entirely as the likelihood of objects colliding in the middle of other objects should be very small providing they are added to the rails in sequence! Most of the collisions will happen at the end points (wheels).

To be honest, depending on the amount of objects you have and the target hardware you could even just do simple collision detection (sphere or AABB) on all objects then something more accurate if that passes. A Quadtree works wonders for cutting down large chunks of tests too.

... an idea you gave me though is to actually store the connections between all "track sections", even if logic decides which one should be used, could really simplify a bunch of things, especially "exact collisions" and housekeeping of the "track sections".

My reason for doing this was so that I could leap onto the next track section as if it were the next entry in a linked list.. no calculation or lookup required. It also allows you to create 'switches' : just hold a pointer to the track section that is set as the current route, and it'll automatically send objects that way

Also I'm not yet sure how I'll implement the synchronization for the "center- and back-wheels", either by having the objects push "track transitions" to a queue that the other wheels query as they move along (objects could potentially be longer than a "track section", and simply querying the front might not be sufficient... although it could!)... or by keeping a value in the "track pieces" that remembers "the last assigned track" for the last front-wheel that passed. Perhaps the "per object queue" is only worthwhile if objects can move both forward and backwards.

I'm not sure if I understand correctly but... my solution was just to ensure both the front and back wheels have the same velocity (which is one dimensional.. you can only move forwards or backwards). Then each update they move at the same speed along the rail, so they always stay the same distance apart. The actual object which sits on top of the wheels is just positioned at the midpoint of the two.

Of course all of the above post might be null and void if your objects are not entirely constrained to the tracks.. ie: if you're wanting them to drive along a road, but not exactly to the set track.


#4786218 Representation of objects on tracks? (railroads/traffic/etc)

Posted by on 15 March 2011 - 03:52 PM

I implemented this as a sort of railway simulation a while back, and found it interesting. I arranged the structure like this. (Similar to your approach)

Rail : contains start point, end point, a function for querying a point in space given a distance along the track. Also stores a list of pointers to other rail objects which are connected to this object's start and end points.

Wheel: stores a pointer to the rail which this wheel is currently sitting on. Also stores the distance (>0..<1) along the current rail. Its absolute position can be computed by querying Rail

Bogie: This has two Wheel objects, one at each end seperate by a length. Position is exactly at the midpoint between the two wheels. Rotation is calculated from angle between the two.

Stock: Two Bogie objects, one at each end seperated by a length. Position is always at the exact midpoint between the two bogies, Rotation is calculated from angle betwteen the two.

Train : A number of Stock objects seperated by their own lengths.

If a position query on a Rail lies over the end of that rail (ie: you pass <0 or >1 ) it will calculate for you the new rail on which the wheel resides, the new distance along that rail, and the absolute position. This is the part where you'll have to work out whether switches are involved, whether the rails are connected all in the same sequence (start->end->start->end) etc.. etc..

Moving a train involves giving it a velocity. On each update that then cascades down to each Wheel which alters its current rail distance, then queries its absolute position from Rail. Then, the absolute position and heading of each item of stock on the train can be calculated.

Collision detection should be easy. If the Rails can store pointers to which Wheels are currently sitting on it (updated as necessary when a wheel moves), then a query can be made to see which vehicles occupy that section of track. If any, then you can perform collision detection between them. Zones may be a little harder, but you could just go all-out and use some kind of spatial partitioning like a quadtree or octree then you can do fairly inexpensive queries on arbritary areas of the world.

<edit: "Bogie" might be a British term, but basically it's one of the wheelsets that the body of the coach/locomotive/truck sits on. A coach will normally have two, one at each end of the coach. Ie: Here>