ID:1298342
 
This is mainly a question for Tom and Lummox, although anyone with experience in the field may be helpful.

I've been working on a 2D C++ game engine recently and I've just been thinking about all of the wasted processing power I might be doing after working on the aforementioned engine modules.

What kind of algorithm does BYOND use for it's collision detection and screen rendering? Does it test collisions for all objects in the world? Only the objects around it? If so, how?

Right now I've just been using a vector container for all entities in the world and testing collisions using a modified brute force algorithm that copies the contents of the master vector into a temporary vector, then takes the first entity and compares it's bounds to every other solid object on the vector.

It then removes the tested object from the list and starts anew with the next object, which prevents two objects from every being collision tested more than once.

As far as screen rendering, I've just been using the basic pixel blitting that comes standard with the SDL library, drawing all objects from back to front, whether they're completely covered by other images or not.

What does BYOND use for these functions and would they be faster than the ones I'm already using? I know pre-optimization is the root of all evil, but I just want to make sure that at least the big functions are somewhat efficient and can handle the assumed loads.
Solomn Architect wrote:
I know pre-optimization is the root of all evil


What?

I've always been lead to believe the opposite of this.

Premature optimisation is pretty much poo.

As it goes, selection of an appropriate algorithm here isn't really premature, provided you have a general idea of the number of entities you'll have on screen under "heavy" load. BYOND did used to bit blit via GDI, which traditionally has had patchy hardware acceleration. For instance, WDDM in Vista meant that bitblt wasn't hardware accelerated for various Vista setups, particularly ones where an XP driver was being used. I'm not sure if this is still being used? If so, it might go some way to explaining the fact some users simply cannot hardware accelerate for love nor money.

My recommendation would be to use SDL's OpenGL support to render hardware sprite sheets instead.
In response to Rushnut
Rushnut wrote:
Solomn Architect wrote:
I know pre-optimization is the root of all evil


What?

I've always been lead to believe the opposite of this.

He's talking about the fact that spending all of your time optimizing something that will have little to no effect on performance is not as productive as writing code that does something. Of course, you should be writing good and meaningful code in the first place but you should only be spending optimization time on your big performance-breaking bottlenecks. Otherwise, you'll never make or finish anything!
Does SDL OpenGL naturally provide rendering optimization? What I've been looking at is actually drawing icons from front to back, generating layer masks based on the images in front of it, preventing pixels from being written more than once unless there's an alpha channel involved.

I guess you're right, Stephen. Picking the right algorithm for the job isn't really considered pre-optimization.

On the note of collision detection, I've found that the Quadtree algorithm seems to be the most solid collision detection model I've seen. It's 10 times more efficient than even the slimmest brute forcers. I've been doing a lot of reading on that and am actually in the process of transcribing Java code into C++ to get it working.

It's really complicated to explain the process involved without actually looking at the code, weird enough.
Well, OpenGL is (assuming you have a hardware accelerated driver .... which 99.9% of people probably do) hardware accelerated, so you're loading the textures up into the graphics card's memory and performing all the rendering operations there.

With pixel blitting, the buffer is usually held in main RAM, and composited by the CPU, so .. software rendered. Some implementations will be smart and do some hand-off ... which I'm going to assume SDL probably does. As you usually damage areas in the process (this is your optimisation I suppose, trying to minimise the damage) you end up performing the operation twice.

With OpenGL you'd just write a number of layers, back to front, and not particularly care about layer masks as the card will handle that for you. So your own code only needs to do one pass. As it's all on the card (or small instructions to the card) also, the pass is considerably faster.
Hmm... that's quite interesting. I have an OpenGL framework with SDL for the engine because I thought I might need it for something, and now I'm quite glad I've done that. It saves a lot of work for me in the long run.
Solomn Architect wrote:
What kind of algorithm does BYOND use for it's collision detection and screen rendering? Does it test collisions for all objects in the world? Only the objects around it? If so, how?

Collision detection is only done for objects as they move. This is why we have Bump(), but we have no concept of a simple "no-fault" collision; one object is moving, the other may or may not be.

Prior to the advent of pixel movement, collision tests were done in a very straightforward way with Enter(). Only the destination turf (and area, if it differed) had to be tested, and Bump() would be called for the appropriate object if so. The default turf/Enter() returned 0 if the mover would collide with a dense obj or mob on the turf. We also had Exit() used for leaving turfs and areas.

With pixel movement, we now look for which turfs and/or areas the mover will be entering, and which movables are on any of those turfs. Movables that have no danger of an overlap are ignored. Enter() is called for the turfs and areas, and Cross() for the objs and mobs. If a collision occurs with a closer object, farther objects are ignored. It is now also possible to bump into multiple items this way.

When an object is moving faster per tick than its physical size, the movement is broken up into smaller pieces to avoid skipping past obstacles.

Right now I've just been using a vector container for all entities in the world and testing collisions using a modified brute force algorithm that copies the contents of the master vector into a temporary vector, then takes the first entity and compares it's bounds to every other solid object on the vector.

I would recommend going with something more along the lines of a quadtree. You can quickly break any area into quadrants and only mark which objects touch each quadrant. Quadrants are subdivided so you can get a very small area to test, which may have only one or two objects to test against rather than all of them.

As far as screen rendering, I've just been using the basic pixel blitting that comes standard with the SDL library, drawing all objects from back to front, whether they're completely covered by other images or not.

BYOND doesn't account for completely covered icons either; it isn't efficient to do so.
Alright, that makes sense. And in a later post, I did point out the fact that I had stumbled across the quadtree algorithm and have actually made great headway into setting it up for my engine. By the looks of many benchmarks, it's extremely efficient, well more than anything else I've seen.