Programming Collisions.

[Chesso]

Hello,

I am using Delphi and Asphyre 5 (the current 22 sep release).

More or less I am using Asphyre merely to render the actual images (nothing fancy like a sprite engine etc at this stage), so I am going to try and do the animation and collisioning myself.

But I am unsure of where to start and what are the best practices?

I want to begin by creating a basic 2D platform type game, but only with a fixed screen at this point (no horizontal or vertical scrolling) of 1024x768 pixels, where I will either have maps link one to the other (sort of like when going into houses and stuff but smoother) or just have the player move upward to a goal.

So basically I am worried about collisioning a player, probably some random enemies with very basic paths and of course some platforms (starting off with basic horizontal ones).


Some things that come to mind is, pixel perfect checking (not bounding box), I wouldn't want the player to walk above platforms and such, checking sides and bottom etc.

And also something I thought about, if any given map has say 20 platforms for the player to jump on, should I process the collision check for all the platforms each frame, or rather first check if the player is anywhere near any of them (I presume the later is less intensive)? In other words some kind of management to reduce overall processing stress.

Now I know this little game is probably not going make my computer blow up, but I would like to take a quality but well managed and efficient approach.

So..... anybody know where I should start? :)

[chronozphere]

If the game area is only 1024x768 pixels and you only use 20 or 30 platforms, there is absolutely no need for collision management. Every PC can determine the bounding-box collisions for this game in no-time, as far as i can tell.

What you shouldn't do, is only performing pixel-perfect collision. You should start with simple bounding box collision. If two bounding-boxes overlap, you can start with the pixel-perfect collision detection. Pixel-perfect collision detection is more CPU expensive and you don't want to do it for all the sprites every frame. Only those, whoes bounding boxes intersect.

But who say's you need pixel-perfect collision detection??? I think its sufficient to have simple bounding-box detection. Keep in mind that bounding-boxes do not have to have the same size as the sprite image. Sprite images are often say 64x64 pixels in size. But alot of these pixels are left transparent and only a smaller rectangle contains the visible pixels (e.g 54 x 32). You should define the boundingbox as a box around these visible pixels. You chould even leave some visible pixels outside the boundingbox (you have to fine-tune this). If you use animated sprites, you should only leave the most static bodyparts inside the boundingbox (torso, feet etc). But again... You have to fine-tune this for every sprite....

Hope this helps. :)

[Chesso]

Well the low amount of data on a per map basis was more of a hypothetical situation.

The idea here is for me to start somewhat humble, and then build off what I have and continue to increase it's complexity, mostly for the experience but to actually have an end result of something that is usable and worth the time and effort.

I understand what you mean by a basic collision check before committing to a more complex one.

I am planning on using Records and Record arrays for some manner of object data storage, bounding box data if necessary could be included in these object records also.

[chronozphere]

Well... Even when you have say 150 platforms or sprites, Collision checking would be no problem. A simple optimization would be, to only collision-check the platforms that are on the screen.

But if you divide your game into alot of area's/levels, I don't think you need alot of optimization. And even if you need it, you can probably add that functionality later on.



I am planning on using Records and Record arrays for some manner of object data storage, bounding box data if necessary could be included in these object records also.


Why not using classes? :? You could use all the OOP tricks that aren't possible with records. e.g Make a base sprite class and derive the other sprites/platforms from that one. Good use of classes makes your life a whole lot easier.. I can tell you that. ;)

[Chesso]

I have made and used them in the well, 8 years of scripting and programming I have done.

The furthest I have gone is records in Delphi and they do a great job.

I am using record arrays and merely skipping records in the array that do not have an index > 0 (in other words they are not loaded with anything or not being used).

I also use a repeat rather than for loop with the array so if their is a collision (this is just a basic floor collision) it exits the repeat statement by incrementing the loop variable (if I have a floor collision, there is no point in testing or even checking the existance of any others).

[chronozphere]

All I want to say, is that it's really worthwhile to learn how to use classes and objects. I figure that you are using alot of function/procedures that aren't part of any objects. If you want to make more complex programs and games, It's really beneficial to add more structure to your code. I don't know how much you know about Object-oriented-programming, but you can alway's look here:

http://www.delphibasics.co.uk/Article.asp?Name=OO

I'm using almost all things that Object-Oriented-Programming offers. Just works great. :)

[Memphis]

All I want to say, is that it's really worthwhile to learn how to use classes and objects. I figure that you are using alot of function/procedures that aren't part of any objects. If you want to make more complex programs and games, It's really beneficial to add more structure to your code. I don't know how much you know about Object-oriented-programming, but you can alway's look here:

http://www.delphibasics.co.uk/Article.asp?Name=OO

I'm using almost all things that Object-Oriented-Programming offers. Just works great. :)

i disagree, altho it is easier in some cases, but created objects create a large overhead which you will not have from a block of memory (a record) if you want a really fast optimised game or engine, avoid using OOP at all costs.

;MM;

[jdarling]

Memphis, actually under the hood objects are nothing more than a packed record with method points (VMT). By the time that you write support routines for each record type you might as well have used an object to begin with.

High speed has nothing to do with object vs method based programming. It has to do with the code optimizations you put in place and the compilers ability to optimize the output code.

[jdarling]

Back on topic. When checking large amounts of objects within the world (call it what you want; sprites, platforms, dog poo) you will typically need to setup a routine that can perform a quick sort of all of the objects within the world into a list. Then check nearest neighbors for a collision.

When you update an objects position in the world you update its position within the list and check for new collisions ONLY. You can also test along the way to see if a collision has happened in history (this happens more frequently in high overhead periods).

There are some really really good articles on collision detection, collision forecasting, and collision mediation on http://www.gamedev.net as well as all over the internet.

While you can take the approach of saying "I'm going to have a small world so I don't care" this approach can bite you in the backside later if your game world gets larger.

[Memphis]

Memphis, actually under the hood objects are nothing more than a packed record with method points (VMT). By the time that you write support routines for each record type you might as well have used an object to begin with.

High speed has nothing to do with object vs method based programming. It has to do with the code optimizations you put in place and the compilers ability to optimize the output code.

lol why don't you try put that to the test, i think you will find there is a much larger overheads, using a struct you have much more control over what memory is placed where, a class you are relying on the `delphi` developers todo alot of it for you. not only is it lazy, but it is slower.

btw i develop my own programming language and an assembler atm, so i have studied alot of the ins and outs and what is going on 'under the hood'.


EDIT

take something like this


program Project2;

{$APPTYPE CONSOLE}

uses
Windows;

type
TSomeClass = class
temp: array[0..1023] of byte;
end;

TSomeStruct = record
temp: array[0..1023] of byte;
end;
PSomeStruct = ^TSomeStruct;

var
ss: PSomeStruct;
sc: TSomeClass;

i, v: Cardinal;
begin
v := GetTickCount;
for i := 1 to 100000 do begin
sc := TSomeClass.Create;
end;
WriteLn(GetTickCount - v);

v := GetTickCount;
for i := 1 to 100000 do begin
New(ss);
end;
WriteLn(GetTickCount - v);

sleep(2000);
end.


then run it and find....

objects = 108ms
records = 47ms

and doing a loop of 500000

will give you

594 obj
454 rec

baring in mind this is after your app has used up resources, so lets switch it around and give the struct the benifit this time


v := GetTickCount;
for i := 1 to 500000 do begin
New(ss);
end;
WriteLn(GetTickCount - v);

v := GetTickCount;
for i := 1 to 500000 do begin
sc := TSomeClass.Create;
end;
WriteLn(GetTickCount - v);


now with records:
294ms

with objects
750ms

i rest my case.


@on topic @ chesso



And also something I thought about, if any given map has say 20 platforms for the player to jump on, should I process the collision check for all the platforms each frame, or rather first check if the player is anywhere near any of them (I presume the later is less intensive)? In other words some kind of management to reduce overall processing stress.


as chronzosphere said, and as you have more or less said, a bounding box is your best bet, make the bounding box bigger then the actual object/character/car etc, then once it is inside that barrier, do a "pixel perfect check" - quote

;MM;

[Chesso]

I agree with records, I love them to do death :P.

Really it matters not about structure because unless I take a big break I know the program inside and out with 100 lines of codes or 20 000 spread across multiple units.

If I do take a big break, well I get confused with small things too anyway haha, but it does not take long to pick it up again, I use the same practices always which simplifies things.

I just use bounding box collision, for my purposes it will generally be no problem at all, even with a lot of objects. I just do not bother checking un-used items in an array and if a collision is found I exit the loop, I generally do not need to test more than 1 object at a time, even if 2 collision occur (a wall and floor) it seems to work great.

I am just stuck with an Asphyre specific issue at the moment lol.

[wagenheimer]

What kind of Asphyre specific issue???

Maybe I can help! =)

[VilleK]

Well I'm certainly in favor of classes as I consider them to make larger projects much more readable and maintainable. But that's just my opinion. Each to his own.

About Memphis example, I think that the main difference here is that memory is cleared when a class is created. This should be the only "delphi" stuff going on and you also often want to do that with records too.

So for a fair test it should be something like:


for i := 1 to 100000 do begin
New(ss);
FillChar(ss^,SizeOf(TSomeStruct),0);
end;

[chronozphere]

i disagree, altho it is easier in some cases, but created objects create a large overhead which you will not have from a block of memory (a record) if you want a really fast optimised game or engine, avoid using OOP at all costs.


I'm sure this overhead is nothing to worry about. You should worry about optimizing the actual algorithm's for e.g Collision detection and efficient rendering. They will definitely give you a way larger performance boost than using records over classes.

Like JDarling said, "under the hood" objects are actually records. There is no significant difference in speed, but there is a significant difference in structure and organization. At some point, only using records will prevent you from making more complex programs. Moreover you can more easily seperate different pieces of functionality, which results in more "modulair" code (you can replace pieces of code with other pieces easily).

If you really want to use records for your projects, i'm not going to stop you. Some years ago i thought exactly the same, and i was sceptical about OOP. But once i got used to it, i never regretted learning it. :)

[Memphis]

well actually you are wrong.

lets say, you create a game with many enemies, when an enemy dies, you delete the object, and when one spawns you create an object, reusing could be done, but if you use a record it would be quicker to delete and create a new (and it also depends on the sitation), with an object you will use twice as much time creating that object, then if you created just in a block of memory, ie a simple struct/record.

anyone that has 'real' experience writing large simulations or games will tell you the same. classes do make things more readable, but they do have larger overheads, and when it comes to creating and destroying, a class is much slower, because they are managing things that most of the time do not need to be managed, they should be dealt with by the programmer.

also when writing a game, why would you want to clear memory? infact writing any program, 9 times out of 10, you do not need to clear memory unless writing a specificed size of data to a file. a string you will end with a nullchar, sizes should be params to external procs so they can copy the correct amount of data.

lets just say


v := GetTickCount;
for i := 1 to 1000000 do begin
sc := TSomeClass.Create;
sc.Free;
end;
WriteLn(GetTickCount - v);

v := GetTickCount;
for i := 1 to 1000000 do begin
GetMem(ss, SizeOf(TSomeStruct));
FillChar(ss^, SizeOf(TSomeStruct), 0);
FreeMem(ss, SizeOf(TSomeStruct));
end;
WriteLn(GetTickCount - v);


now you will find

objects = 203ms
records = 110ms


anyways i think this thread needs to get back on topic.

;MM;

[chronozphere]

I ran your code and if you look at the times to allocate/deallocate classes and records, you are right.

My results are:

Classes: 156
Records: 78

Nevertheless, you normally don't create/destroy alot of classes per second. If you look at Meshes, Textures, Shaders, Fonts, GUI-Elements, etc... You'll see that you don't need to rapidly create and destroy them. Moreover most of the creation/destruction happens when a game starts and exits. So the actual gameplay will not be significantly slower, unless you decide to created/destroy hundreds of objects a second.

However, In some cases it can be wise to use records e.g for particles in a particle system. :) I agree with you on that point.



anyways i think this thread needs to get back on topic.


I agree with you on that too. ;)

[Memphis]

My results are:

Classes: 156
Records: 78



sorry offtopic again, but im interested as to knowing why your sample is faster than mine with same code, maybe compiler or something. what version of delphi/fpc did you compile with? i compiled using delphi 7.

what is your processer speed? im running a 2.4 core 2 quad, also what speed is your memory etc? im running 800mhz ddr2 geil (with a very low latency)

thanks in advance.

;MM;

[Chesso]

That's ok, the off topic discussion is very interesting, I am always interested in discussing performance :P.

The Asphyre specific issue I have is with Render Targets of Asphyre 5. I used most of the basic render target example (but I have only 2 instead of 4) and want to use them in my editor.

My first 1024x1024 target is perfect, the second however 320xINFINITE (depending on size of the tile graphic loaded) draws all imagery at a lower scale, and nothing I do seems to correct it.

The developer of Asphyre said textures or something should be power of 2, I don't see why as the identical image draws fine on the first render target lol.

[chronozphere]

Hmmm... That's odd. :shock: Your system seems somewhat faster than mine.

I have an AMD 64X2 5400+ with 2gb of DDR2 RAM (I believe it was 667Mhz or something...). I compiled my code using Delphi 7 and i run Vista ultimate.

I ran your code a few times and these are my average results:

Classes: 200ms
Records: 78ms

The first time I run the code, the classes seem te be significantly faster (150ms)

And you are forgetting something. You might run more applications in the background than me. I believe this will affect the performance too. ;)

[User137]

offtopic:

Why i favor records usually is because of Socket based games or saved data files.

When with records you can simply send/save/read the entire record in 1 go with classes you have to individually process every single variable. However i know classes are packed in memory and you can point them from their first variable and find out size by pointer from last. But that is so nasty way that its not even considerable. Then again, if you put data records in a class, you might have used records to begin with :p

But i do use classes whenever i can on bigger concepts, as controlling mechanism.

[Memphis]

yep true, i do run alot of software in background, i am using windows xp pro, maybe i will try it on vista too, see if there is any difference too.