Pages: 1
  Print  
Author Topic: ENIGMA Needs a better storage method  (Read 2229 times)
Offline (Male) Josh @ Dreamland
Posted on: December 15, 2008, 07:19:44 PM

Prince of all Goldfish
Developer
Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2955

View Profile Email
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
« Last Edit: December 16, 2008, 04:16:13 PM by Josh @ Dreamland » Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Offline (Male) RetroX
Reply #1 Posted on: December 16, 2008, 08:34:14 PM

Master of all things Linux
Contributor
Location: US
Joined: Apr 2008
Posts: 1055
MSN Messenger - classixretrox@gmail.com
View Profile Email
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?
Logged
My Box: Phenom II 3.4GHz X4 | ASUS ATI RadeonHD 5770, 1GB GDDR5 RAM | 1x4GB DDR3 SRAM | Arch Linux, x86_64 (Cube) / Windows 7 x64 (Blob)
Quote from: Fede-lasse
Why do all the pro-Microsoft people have troll avatars? :(
Offline (Female) IsmAvatar
Reply #2 Posted on: December 16, 2008, 09:36:37 PM

LateralGM Developer
LGM Developer
Location: Pennsylvania/USA
Joined: Apr 2008
Posts: 886

View Profile Email
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.
Logged
Offline (Male) Josh @ Dreamland
Reply #3 Posted on: December 17, 2008, 06:43:16 AM

Prince of all Goldfish
Developer
Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2955

View Profile Email
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.
Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Offline (Male) RetroX
Reply #4 Posted on: December 17, 2008, 08:01:03 AM

Master of all things Linux
Contributor
Location: US
Joined: Apr 2008
Posts: 1055
MSN Messenger - classixretrox@gmail.com
View Profile Email
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.
Logged
My Box: Phenom II 3.4GHz X4 | ASUS ATI RadeonHD 5770, 1GB GDDR5 RAM | 1x4GB DDR3 SRAM | Arch Linux, x86_64 (Cube) / Windows 7 x64 (Blob)
Quote from: Fede-lasse
Why do all the pro-Microsoft people have troll avatars? :(
Offline (Female) serprex
Reply #5 Posted on: December 17, 2008, 07:27:56 PM
Smooth ER
Developer
Joined: Apr 2008
Posts: 106

View Profile WWW
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
Logged
Post made December 18, 2008, 11:10:14 AM was deleted at the author's request.
Offline (Male) Josh @ Dreamland
Reply #7 Posted on: December 19, 2008, 04:20:01 PM

Prince of all Goldfish
Developer
Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2955

View Profile Email
That'd take way too long, and be far too inefficient.
Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Pages: 1
  Print