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

[pascal]
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.
[/pascal]

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

[pascal]
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);
[/pascal]

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;