ENIGMA Forums

General fluff => Announcements => Topic started by: Josh @ Dreamland on December 15, 2008, 07:19:44 PM

Title: ENIGMA Needs a better storage method
Post by: Josh @ Dreamland on December 15, 2008, 07:19:44 PM
I can't decide what to do next, actually.

I made a system that implements depth. The system can have a few different options, each of which has some unappealing drawback, I'm sure.

What I was going to go with was a red-black tree, just like STL uses in their map. (I may break down and just use STL, depending on how angry I am at them when I wake up tomorrow.)

What I designed the system with originally had no conventional sorting method.

Let me explain.

Instances were just added to a standard linked list for simplicity of working with them.
Then I have a list of event types, which point to a list of depths, which point to both a start and end position on a list of instance pointers. The instance pointers will have their corresponding event accessed.

This was so if you had 10,000 instances, three of which had a step event, ENIGMA would execute only the step events of those three.

I believe this is what "other software" does, so I guess I really had no choice.

Okay, now that I typed a page of exposition, here's the breakdown.

Positive: The nodes on the depth list point to the right points on the list of instances with each event just fine. There is no need to change the instance-event list.
Problem 1: The depths are accessed simply by iterating through the list until you find the right depth. So for those of you who say depth=-y, you may just run into a speed problem. (Nothing major, I promise, but it could still be a few milliseconds faster per call. Big deal, ha?)
Problem 2: The reason I'm mad at STL is because "other software" defies the laws of C++ and 'proper coding.' Meaning that when you say instance_destroy(), STL cries, cuz I'd have to delete an instance that God knows how many iterators are pointing at. (There actually should be just one, but I'd feel icky about just moving the iterator so I could defile the map) Knowing this, if I don't do anything, and just delete the instance from the map, the game will crash.

What I did in my tests was just 'orphan' the node. It's a term I coined for unlinking it, then deleting it after all iterations are complete. (At the very, very end of the step, when framerate is calculated, etc)

So yeah, I'm in a pickle.

Really smart people: Gimme suggestions
Everyone else: Just keep in mind I'm fussing over milliseconds here, and don't go whining "zomg enigmaare vap0rawre!11!"

Final thought:
If you post another newspost over my important questions and announcements, a2h, I will poke you with a VERY sharp stick. >=[[ And the new forum look sucks so I'd 'preciate it if you fixed that please and thank you. :3
Title: Re: ENIGMA Needs a better storage method
Post by: RetroX on December 16, 2008, 08:34:14 PM
Don't use SDL; make something of your own.

As for depth, IDK.  How are ENIGMA's instances currently organized (I know a list, but...)?

Would it be possible to modify instance IDs to order them by depth?
Title: Re: ENIGMA Needs a better storage method
Post by: IsmAvatar on December 16, 2008, 09:36:37 PM
In LGM, we solved this problem with something called a WeakReference, but actually created our own called a ResourceReference. The idea is to only have 1 hard reference, so that when that reference goes away, so too does the resource (via the garbage collector in Java), but the WeakReferences remain but resolve to null. I guess this just encourages null checking everywhere.
Title: Re: ENIGMA Needs a better storage method
Post by: Josh @ Dreamland on December 17, 2008, 06:43:16 AM
Ism-- Nope, that certainly wouldn't work here.  At least not well. I'm mostly concerned about speed. Space is an issue to.

For some games, there's only one or two depths, so a tree would be overkill.
For others, there are closer to 41, or even up to 640 different used ones. So a tree would be a little nicer, but still, I can't imagine there really being 640 simultaneously used depths, so...

As for instances, I think a tree would be best bet. That way lookup is really fast, even though removal and creation are slowed.
Title: Re: ENIGMA Needs a better storage method
Post by: RetroX on December 17, 2008, 08:01:03 AM
No matter how much slower it is, it'll still be faster than GM.  And I'd bet my ass that's the way they did it too.
Title: Re: ENIGMA Needs a better storage method
Post by: serprex on December 17, 2008, 07:27:56 PM
I'd think you'd want to have an optimal worst case. The overkill of a tree on a low range of depth is outweighed by the advantage of when it is useful

And Retro, DIY fever kills. You should implement something rather than use the STL when there is more than boasting rights at stake. Also, ID changing would be lame because then you can't have some emulation of an instance pointer through the use of ID
Title: Re: ENIGMA Needs a better storage method
Post by: Fede-lasse on December 18, 2008, 11:10:14 AM
My idea is just that, when you delete an instance from the global list of instances in-game (if you have such a list at all), you just decrease the value of all instances "below" the just-deleted one. Imagine a list of instances like so:

lolz1
lolz2
lolz3
lolz4
lolz5
lolz6

Now, when we delete, say, lolz4, it'd end up like this:

lolz1
lolz2
lolz3
lolz5
lolz6

But, like I said before, we just decrease the ID of the instances - below the just-deleted instance - by just 1, so that they all fit:

lolz1
lolz2
lolz3
lolz4
lolz5

Remember, the Game Maker Manual itself also states, that you should never trust an instance ID for too long; they change reguarly. And so does this method...

Or did I miss something here? Sorry, if I did.
Title: Re: ENIGMA Needs a better storage method
Post by: Josh @ Dreamland on December 19, 2008, 04:20:01 PM
That'd take way too long, and be far too inefficient.