Jump to content

  • Log In with Google      Sign In   
  • Create Account


Questions about code efficiency and collision detection


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 Aurioch   Crossbones+   -  Reputation: 1303

Like
0Likes
Like

Posted 04 December 2012 - 01:50 PM

Hello again Posted Image

Well, I continued working on my project. I'm glad that I can say I implemented Game State Machine... maybe not optimized nor pretty but it works. That's enough for me for now.

Main menu works perfectly, and I'm working on my main part from scratch (done most of it, now only bullet collision and AI). I also began to look more on code efficiency and to use structures, classes and methods I didn't use before. In addition to that, I wrote fresh code and didn't use code from prototype since it was inefficient. When I looked at prototype code after these 2-3 weeks, I was going "Why did I do that" whole time and scrapped it in favor of better code (like splitting tank logic, bullet logic and AI logic from one into 3 separate classes).

So, after introduction, time for my questions. It's my habit to have them numbered etc. for ease of reading. Please keep in mind that, despite going through university education, I'm studying this on my own because my university doesn't have classes specialized for this field (especially NOT object oriented programming), so sorry if some questions are dumb or "dooh, you should know that" type. Also, on some questions I already assumed answers, I just want to see if I understand that correctly Posted Image

1) Public declared class variables vs class properties. For example, I'm using class Tank which holds all data about its status in the game. So, technically speaking, what's the difference between those two:
public Rectangle BoundingBox
{
	get { return tileRectangle; }
	set { tileRectangle = value; }
}
//
Rectangle tileRectangle;
//
// vs
public Rectangle boundingBox;

2) Methods with multiple parameters vs overloaded methods. In my prototype (which I can upload, no problem) I wrote collision in a method which required 3 parameters which then covered and properly handled all possibilities. Now I'm using 2 methods with same name but with slighly different parameters and behaviour (method overload). Performance wise, which is better and why?

Method definitions:
[source lang="csharp"]// Prototype method, I think it's self explanatorypublic bool Collision(Rectangle Object, bool isProjectile, bool isPlayerTank);//// Current, overloaded method (Tank and Bullet are custom classes)bool Collision(Tank Object)bool Collision(Bullet Object)[/source]

3) Another "battle" question: List<T> vs Array. In prototype I used arrays to hold object information and sometimes it was pain in the a** to manage it. Now I'm using Lists which made my life a lot easier (I don't need to skip that pesky Player2 slot if Player 2 doesn't exist), but still, what is better to use in which situations performance wise?

4) Events and event handler. I've used them now but still, I don't quite understand them, so can somebody give me a brief explanation? I understand that event is a piece of code which triggers automatically (like interrupt) when certain conditions are met (eg. MouseClick) and uses its handler method to deal with the situation.

5) And final, my most important question: collision detection. I'm using combination of Bounding Box method and Pixel Perfect method; reason is that while most world objects are static and won't change - meaning Bounding Box method is sufficient for collision detection (check if tank's and tile's hitboxes overlap and if yes, reset the position of tank to previous one) - there are also destructible objects which can have only part destroyed. I know the general idea of it and I tried to reproduce it on my own in order to learn it better. It works for now but I didn't test it on situation I need to because I didn't get to that part; but even now, I'm worried about efficiency of code. I already made a stupid mistake which ended calling one line of code 16 milion times, so I'm quite worried because it will need to run up to 10 times in one cycle (2 player tanks and 8 enemy tanks) which not only could but will cause lag. Even worse when bullets come into play.
[source lang="csharp"] bool PixelPerfectCollision(Tank Object, List<Tile> Wall) { Rectangle tankBox = Object.GetRectangle(); int totalWidth = Math.Max(Wall[0].BoundingBox.Width, tankBox.Width) * 2; int totalHeight = Math.Max(Wall[0].BoundingBox.Height, tankBox.Height) * 2; Color[,] wallColor = new Color[totalWidth, totalHeight]; Color[,] tankColor = new Color[totalWidth, totalHeight]; Point[] location = new Point[Wall.Count]; Point offset; for (int x = 0; x < Wall.Count; x++) location[x] = Wall[x].BoundingBox.Location; // Get starting point via offset offset = location[0]; for (int x = 1; x < Wall.Count; x++) { if (location[x].X < offset.X) offset.X = location[x].X; if (location[x].Y < offset.Y) offset.Y = location[x].Y; } if (tankBox.X < offset.X) offset.X = tankBox.X; if (tankBox.Y < offset.Y) offset.Y = tankBox.Y; // Clear matrixes for (int x = 0; x < totalWidth; x++) for (int y = 0; y < totalHeight; y++) { wallColor[x, y] = Color.Transparent; tankColor[x, y] = Color.Transparent; } // Combine walls into single wall foreach (var tile in Wall) { Color[,] a = tile.GetColorMatrix(); for (int x = tile.BoundingBox.Left - offset.X; x < tile.BoundingBox.Right - offset.X; x++) for (int y = tile.BoundingBox.Top - offset.Y; y < tile.BoundingBox.Bottom - offset.Y; y++) wallColor[x, y] = a[x / 5, y / 5]; } // Prepare tank for comparsion Color[,] n = Object.GetColorMatrix(); for (int x = tankBox.Left - offset.X; x < tankBox.Right - offset.X; x++) for (int y = tankBox.Top - offset.Y; y < tankBox.Bottom - offset.Y; y++) tankColor[x, y] = n[x * 2 / 5, y * 2 / 5]; // Comparsion for collision for (int x = tankBox.Left - offset.X; x < tankBox.Right - offset.X; x++) for (int y = tankBox.Top - offset.Y; y < tankBox.Bottom - offset.Y; y++) if (wallColor[x, y].A != 0 && tankColor[x, y].A != 0) return true; return false; }[/source]
I've already though about some improvements like looking only where there is collision instead of looking through whole tank but I'd still like more recommendations. I can get to the solution on my own (more research and some trial&error) but I'd rather do the right thing immediately.

Thanks for sparing some time to read this.
I hope I'm not bothering anyone and I don't like to ask others much, I prefer to figure out things on my own but for some things it's better and faster if I ask someone to explain. Also, if you need some more information please ask me to provide it.

Sponsor:

#2 de_mattT   Members   -  Reputation: 308

Like
2Likes
Like

Posted 04 December 2012 - 05:05 PM

1) Public declared class variables vs class properties
Hopefully you've encountered Encapsulation and information hiding. As is described in the link, your first approach allows objects to control access to their data, which allows the object to ensure that the data is only ever set to valid values. In your "set" property you could perform some validation checks on value before updating tileRectangle. Also if you decided to change how the bounding box is stored, in the second method you would have to update every piece of code which uses bounding box, whereas in your first example you would only need to change the properties. This is related to Once and Only Once (DRY).

Note in your first example it would be good to declare tileRectangle as private. It may be by default but it's always good to be expressive.

2) Methods with multiple parameters vs overloaded methods.
Your first approach may cause issues with maintainability. If you decided to add other game object types that are also subject to collision checks (perhaps you add a Soldier class), you would have to add a new parameter to 'Collision' for each new game object type. Your parameter list could get very long. Even worse, every time you add a new collidable game object type you would have to modify every call to 'Collision' to specify the value for the new parameter (e.g. FALSE). Your second approach avoids this problem. I would probably go one step further though and give my methods more expressive names like "isTankColiding" and "isProjectileColiding".

3) Another "battle" question: List<T> vs Array
I would tend to use arrays only for very simple tasks. Anything slightly complicated requiring data structure management (e.g. inserting, sorting, removing an element in the middle of the structure) and I would use a list. Favor keeping your code simple and expressive over performance. Write good clean code first and then only change it if testing / profiling show that that piece of code is not fast enough. In 99% of cases the List will do just fine. Don't waste valubale time re-inventing the wheel, keep it simple.

4) Events and event handler.
Events are a way for a class to signal to other interested classes that something has happened. The Observer pattern is an example of a simple event handling architecture.
C# contains an event construct which makes it simple to create your own events. Maybe there are lots of classes in your game which will need to know when the bounding box of a tank is updated. Those classes can implement an event handler method (perhaps called boundingBoxUpdateHandler) to describe what they will do when they hear about the BoundingBoxUpdated event, and then can register this event handler method with the tank object which contains the bounding box. Then when the bounding box is updated, the tank object can loop through all the registered event handlers and let them know that the event has occurred.

5) And final, my most important question: collision detection.
I'm a bit confused on the way that you're calculating the offset variable. If the Tank is more than the totalWidth or totalHeight from the origin, won't your x and y indexes go out of range? E.g. in the following loop if tankBox.left > offset.X + totalWidth, x will not be a valid index for wallColor and tankColor. I've probably missed something, it's late :)

// Comparsion for collision
    for (int x = tankBox.Left - offset.X; x < tankBox.Right - offset.X; x++)
	    for (int y = tankBox.Top - offset.Y; y < tankBox.Bottom - offset.Y; y++)
		    if (wallColor[x, y].A != 0 &amp;&amp; tankColor[x, y].A != 0)
			    return true;

If your PixelPerfectCollision method is a problem performance-wise then you could combine the first two for loops together, and you could combine the last two for loops together.

I haven't done pixel-perfect collision detection before but I would start by comparing bounding boxes to check that the tank is colliding with a particular wall segment, and if the bounding boxes are colliding only check the area where the two bounding boxes overlap for a collision. Also I would check one wall at a time so that if you find a collision early on you can return true and don't have to check the other walls.

Hope this is useful

Matt

Edited by de_mattT, 04 December 2012 - 05:12 PM.


#3 Aurioch   Crossbones+   -  Reputation: 1303

Like
0Likes
Like

Posted 04 December 2012 - 06:17 PM

Wow, thank you very much for detailed explanations. I had a vague understanding of it, now it's everything more clear Posted Image
And honestly, if I ever did encounter encapsulation that would be in my "old" VB.NET book. On university, while we're allowed to use common languages (C# being one of them), we actually never studied about object-oriented programming at all, only procedural ( C ). I was baffled when my friend told me that one of his teammates for Project class wrote a finite state machine in C# completely procedural without usage of object methods and classes. So, explanations like your are pure gold for me.

I haven't done pixel-perfect collision detection before but I would start by comparing bounding boxes to check that the tank is colliding with a particular wall segment, and if the bounding boxes are colliding only check the area where the two bounding boxes overlap for a collision. Also I would check one wall at a time so that if you find a collision early on you can return true and don't have to check the other walls.


I already did that ;) There is no need to perform pixel-perfect collision for objects that won't be modified over the course of the game like water tiles (unpassable for tanks). A code will make that more clear:
[source lang="csharp"] bool Collision(Tank Object) { List<Tile> collided = new List<Tile>(); Rectangle objectRect = Object.GetRectangle(); if (!playableArea.Contains(objectRect)) return true; foreach (var tank in Tanks) if (!Object.Equals(tank) &amp;&amp; objectRect.Intersects(tank.GetRectangle())) return true; foreach (var tile in waterTile) if (objectRect.Intersects(tile.BoundingBox)) return true; foreach (var tile in metalTile) if (objectRect.Intersects(tile.BoundingBox)) return true; foreach (var tile in brickTile) if (objectRect.Intersects(tile.BoundingBox)) collided.Add(tile); if (collided.Count > 0) return PixelPerfectCollision(Object, collided); return false; }[/source]
As you can see, I structured collision checks so that the check for collision with brick wall (destructible) is last, enabling the function to exit early if it find collision with objects that don't need the pixel-perfect collision check.

I'm a bit confused on the way that you're calculating the offset variable. If the Tank is more than the totalWidth or totalHeight from the origin, won't your x and y indexes go out of range? E.g. in the following loop if tankBox.left > offset.X + totalWidth, x will not be a valid index for wallColor and tankColor. I've probably missed something, it's late Posted Image


I've taken care of it too. There are 2 reasons why that won't happen (unless I'm gravely mistaken which I'll find out after I change resolution):
  • Pixel-perfect collision check is ran if Bounding Box collision check is positive, meaning that tank and walls will always be inside 2*2 tile (80*80 pixel at 800*600 resolution) area, hence
    int totalWidth = Math.Max(Wall[0].BoundingBox.Width, tankBox.Width) * 2;
    				int totalHeight = Math.Max(Wall[0].BoundingBox.Height, tankBox.Height) * 2;
    Incidentally, if tankBox.left > offset.X + totalWidth pixel-perfect collision check won't be invoked since it will fail on bounding box collision check.
  • Vector2 offset is simply a location of top left pixel whose usage is to ease the iteration through 2D array. I used it specifically to cover the situation where the tank is on the left and/or above the top-left wall tile (I can draw all possible situations).

If your PixelPerfectCollision method is a problem performance-wise then you could combine the first two for loops together, and you could combine the last two for loops together.


Combining last 2 double loops I didn't notice Posted Image Thanks for suggestion. Originally it was from 0 to totalWidth/totalHeight but when I debugged it I saw I didn't cover few cases and added offset into calculation, resulting in equality of those two loops.

Well, off to the sleep, and tomorrow I'm continuing with my work. To quote Natsu from Fairy Tail: "I'm all fired up!"

Edited by Aurioch, 04 December 2012 - 06:25 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS