Object handling optimization

[BlazeHedgehog]

I'll warn you now, I might get kind of confusing in this because I am nowhere near as smart as Dami or any of the other geniuses. But, well, that's why I'm posting. Chances are there's a much more simple way to do this that I'm missing.

Something I've noticed - at least in my fangames - is that poor framerates in MMF games primarily stem from one source:

Too many frickin' active objects in a level. Specifically, rings.

Doesn't matter if it's Shadow of Chaos, TFH, Sonic 2k6 2D or what, if I put in a button that destroys all the rings in a level, the framerate will practically double. I've tried the settings: "Load On Call", etc. All that stuff. None of it really seems to improve the framerate a whole lot. And it's not like the rings are terribly complex in themselves; often they have maybe ten events dedicated to collision with the player, with no fastlooping or anything.

One concept to fix this I came up with would be an external editor, built so you could hand-place active objects, with the coordinates stored in a separate file. This file would then be read according to the player's position in a level, and would only spawn objects close to the player. This would essentially give you the freedom to have 10,000 active objects in a level, with much, much greater performance (assuming all 10,000 objects weren't on screen at the same time).

Recently, I realized: I don't need the separate editor. I can record all the data I need, using objects already placed in MMF's frame editor. At the start of the frame, I simply, one-by-one, delete all of one type of object. All the rings, etc. But the key here is to delete them one at a time - and before deleting them, recording their X and Y position to an ini file. This gives you a database of all the objects in a given level.

From there, it would simply be a matter of reading from the database and spawning objects at their correct location as the player approached them. I decided I would test this theory in Sonic 2k6 2D, as that is currently the game with the worst framerate problems. And so, I got to work.

For one second at the start of the level, 200 loops would be launched for every frame. At 50 frames per second, that's 10000 loops. 10000 loops for a maximum of 10000 objects. Though this is a lot of loops and slows the game down, it only occurs for one second at the start of the frame, a fair trade off, in my mind. At first, I thought I could spread a value across all the objects I wanted (eg: each object can be identified by a unique number). Then I'd just compare that value to the loop index to get the object's X/Y. But that didn't work (MMF doesn't like that, never has - too vague for it, I guess).

So I simply decided: I'd pick an object at random, record it's X/Y, and then destroy it. This would mean I could record all the objects in a level, because as I destroyed them, there would be fewer options to pick from at random - eventually leading to the destruction of all the objects, but also giving me the X/Y coordinates to all objects. And so, this is how I built the database of all the objects in a given level. I started with rings, because those are often what cause the slowdown the most - often 250+ individual rings per level.

Okay, so, I got a database of objects in a level. In the INI itself, it reads something like:

[271,137]

itemtype=1

The group being the X/Y coordinates, the item being "itemtype", and the value being what type of item it is. 1 being a singular ring, 0 being no object at all.

Being as there are a lot of rings in White Acropolis Act 2, the ini file ends up roughly 2kb in size. Not big compared to an MP3, but when you consider there's just text in there - that's a lot of text.

So everything is recorded to a database. Now what? Now is the part where my entire concept falls apart, and is the part where I need help.

I decided I needed four fast loops. Two for X, two for Y.

X Left

X Right

Y Top

Y Bottom

These loops decide if an object passes in to the "zone" in which they should be appearing on screen. These loops check every pixel within a certain range. Basically, the best I can describe it as this:

X Left is checking. Using the INI object and fastloop, it checks the left side of the screen, minus 64. at X Left Side - 64, it checks the Y axis between, we'll say as an example, 434 and 804. This equals to 368 loops. It checks every pixel starting from 434 down to 804 using the loop index as an increment.Now imagine the rest of the loops doing this for X Right, Y Top, and Y Bottom. Let's set this up as an example, then:

We have a ring. It's X is 2133 and it's Y is 1098. In the INI this is written as

[2133,1098]

itemtype=1

The loops go around and check the X and Y of the borders of the screen, checking each pixel, by looking for an object at [x,y]. This looks something like:

If GroupItemValue( "Ini 2", Str$(X Left Frame-64)+","+Str$(Y Top Frame-64+LoopIndex("X Check Left")), "itemtype") = 1[/CODE]

Should itemtype equal one, it spawns an object at the appropriate X and Y coordinates and then deletes it's entry in the INI file. (Should the object leave the screen again, it's entry will be re-added to the INI file and the object itself will be destroyed from the frame.)

This all equals something ludicrous like 1700 loops total per frame. Yeah, some of you are wincing right now, and I don't blame you. That is way more loops than should be a safe number. Upon running the frame with all of this installed, I get less than a single frame per second, because it's running 1700 loops per frame.

What am I doing wrong? Is this idea even feasible? Or did I simply miss an easy option to get this running smooth without all this extra hubub (very possible, I have a knack for doing things the hard way).

[DimensionWarped]

Dami and I were talking about doing something a lot like this just the other day.

I have this file somewhere that Dami programmed, and basically what it does is it allows you to store objects in an array and load different quadrants on them all based on a single qualifier.

Adding destructables of course would require you to go an additional step by deleting them from the array afterwards, but that shouldn't be hard at all.

If I can remember where I put the damn thing, I'll post it in this topic.

[LarkSS]

That's an interesting idea and all, but since you need to run a loop every frame to check for rings in range, it's just going to make the game run slower. =/

Did you try making all the rings invisible to see if there's any performance improvement? If it does help a bit, try comparing the rings position if it's out of the screen or not and if it is, make it invisible and reappear it when it gets back into view. This is possible to do without a fastloop too.

Also, try setting Fine Collision off since imo it's not really necessary for that to be enabled for rings.

Btw, Load on Call and Discardable are frame specific things rather than something run during runtime. What I mean is Load on Call doesn't load an object when it comes into view; if checked it means to only load the object when you reach that specific frame rather than at the beginning of the game. Discardable works similarly being that after the frame is finished, the loaded data for the object is deleted. This stuff is only good if there's an object that's unique only for that frame and nowhere else in the game.

[DimensionWarped]

This on the other hand will be better. Because rather than checking individual objects, it simply loads them based on which quadrant Sonic is in.

Essentially it divides a level into chunks (preferably window size) and then saturates a each chunk's array segment with object data for all of the objects in the area. You can then load the objects how you want.

In order to use it in a level, you'll have to load a the following segment, the previous segment, and the segments above/below/diagonally at any time and if you have loaded segments that aren't a part of that, you need to clear them of all clearable objects.

[Serephim]

This is a great idea, but i dont think its needed anymore.

For example, Ive been working on tons of new engine addons for my game, Tails Adventure 2.

For some of the magic effects and other attacks (Homing Attack specifically), i took abour 3 hours and came up with a custom build group of events that actully picks objects that are close to you in order.

When my friend asked me to implement it into his (hes using MMF2), i kept declining because i had to brush it up.

Just so happens when i brush it up to my liking (and homing attack works now, without any use of ANY actives but my mask), he comes up and tells me that MMF2 gives an auto event that can do it by itself, as well as the second closest and third as well.

So while im pretty much pissed off that MMF2 has just made me 50 points less awesome (i was going to post the tutorial later), i realize that we need to actully start using it. >_>;

[BlazeHedgehog]

Did you try making all the rings invisible to see if there's any performance improvement?

Doesn't do anything.

Also, try setting Fine Collision off since imo it's not really necessary for that to be enabled for rings.

That doesn't do anything, either.

Thanks DW, I'll check it out later.

[LarkSS]

Did you try making all the rings invisible to see if there's any performance improvement?

Doesn't do anything.

Clickteam must have been smart enough to make objects not be drawn offscreen then.

Also, try setting Fine Collision off since imo it's not really necessary for that to be enabled for rings.

That doesn't do anything, either.

I guess that's because the collision box is checked before fine collision. I can't really test this stuff since I don't have a game running slow at this point.

@DW: That's interesting, but I'm still a bit confused at how it works. You're saying it splits it into quadrants, but doesn't a loop still have to be ran to check every pixel within that quadrant or am I utterly mistaken? Also, I'd like to see if it really works since I don't see anything that retrieves the quadrant the screen is within and also I think the quadrants should be 512x256 since the X screen size is past 256.

Edit: Reread your post and that answered a few questions, although I'm still a bit confused at how its process works. Looking at the way it's programmed didn't help either. =/

@All: Would replacing the ring when it's off screen with a less complex object like a 1x1 invisible dot speed things up by any? I honestly have no idea since I don't know how Clickteam programmed object handling offscreen.

[DimensionWarped]

Thats because all it does is catalogue the items into quadrants and restore them right now. There isn't any code in place to actually pick which quadrants to load and destroy right now.

[ssbfalcon]

The loading the level entities as you go along seems to be a nice idea. I was actually considering something similar to your original idea back in the day when TGF was still king... And I still like the concept of loading parts of a level as you go along it should be the ideal way of doing it...

DW's method of basically loading the level in blocks, (kinda like how the Virtual memory paging works) seems to be the nicest way of implementing the loading method...

But I think I have found a simple option in MMF a long time ago that helped with that...

For MMF, with the much higher object limit, I found that the rings caused the most framerate lag...

Since the rings were only to be collected and nothing else (magnet shield created special homing rings), I found that when setting "inactivate when far from window" to a solid check I'd get the performance speed boost I needed. MMF 2 appears to have that option too... And I believe it works just as well there too...

How can I be so sure? I was developing on a Celeron 366Mhz, and needed every performance optimization I could get... And that one setting increased performance by a lot... I then moved from 320x240 to 400x300, which was previously vlagtastic. I doubt that anyone who played Velocity ever had so much as a slight framerate drop thanks to that... Because of that option I was also able to extend the level sizes to double what they were... (though at that time, the sizes really weren't as large as what I consider large now...)

Basically, what that option does is ignore the object when they aren't visible. That means you couldn't make the same rings magnetized otherwise if you move too fast, they just stop working...

In MMF 1.5 it's in rightclick->scrolling>Inactivate if far from window.

In MMF 2.0 it's in runtime Options, Inactivate if too(far from window)[Yes]

[Serephim]

MMF2 has almost NO slowdown when it comes to too many actives.

Unlike on TGF and MMF where doing it would actully fuck with your game's engine movement, MMF2 seems to handle it tons better.

[DimensionWarped]

Its really only important to use my method when you have a large number of objects with a need to consistently check for collisions and have operations performed on them. Now that gimmicks are becoming more popular in fangames along with more complex AI, we are probably going to be seeing more need for optimization like this.

[Damizean]

MMF2 has almost NO slowdown when it comes to too many actives.

Unlike on TGF and MMF where doing it would actully fuck with your game's engine movement, MMF2 seems to handle it tons better.

Tell that to BF or Euan

[DimensionWarped]

Or Slingerland for that matter.

[Epon]

It shouldn't be that labor intensive if the parsing of this database happened in a constant, O(1) time. In other words, you somehow index these objects differently. Instead of linearly progressing thru your INI each frame and comparing each object's location to Sonic's current location, you store them in a table of sorts.

I use the word "table" very loosely, as we're not storing hashes here, but rather indexing each object by it's X variable... um, lemme explain better.

You have your database. Objects, whatever they may be, are indexed and grouped by X-location (Y seems like it wouldn't work for my example...) You then jump to that index once per frame (but you can then keep track if you're still there a frame later, cutting down on time), parse the database for that location, and get the objects.

I know this sounds exactly like what you're saying, but in concept, it'd cut down the time dramatically. Think of it like this, Blaze. Instead of having a FOR loop running thru a list searching until you find that specific object, you just instantly jump to that object based on an index. I dunno if this is making sense to you; I didn't perform super-well in my Algorithms/Data Structures course, but the concept of O(x) time is basically what we're talking about here.

I can't give you a definitive solution, but you seem to be on the right track. Just don't loop thru the ENTIRE database each cycle, only jump to the specific index(s) you need.

[Felik]

Sorry for upping the thread but where can I download those example? Why don't you put it to the main site?

[BlazeHedgehog]

As far as I know nothing was ever made out of this. It was all theoretical, and whatever was done wasn't ever finished. I'm actually still fooling around with methods to use in TFH, but I still don't have anything concrete and working.

[rogueyoshi]

you should talk to dami about his grid spatial indexing extension for GM. you could get some details that could help you port it to MMF2.

[BlazeHedgehog]

I don't know C++ to do so. And it would probably require C++ to write a proper MMF extension rather than just writing events for it.

And Dami seems to hate MMF...