The Fastest list...

[jasonf]

It's optimisation time on my game, I've got a nice and complicated object structure containing lots of lists and it's taking 40ms to process the game logic. Too long by far.

So what I want to know is, what's the fastest type of list available for Pascal. BTW: I'm using Freepascal these days.

Here's the situation.

I'm using StringLists at the mo because they give me Key:Object access and they allow sequential access via an Objects array. But this is probably too slow for real rapid access.

I've wrapped up the string list in my own collection class so I'll be able to make any optimisations accross the board.

I need both sequential, indexed and keyword access to the collection.
I want the best of all worlds.

Any suggestions?

[savage]

A few of my Lists are now based on TObjectList or TList, which I believe is optimised under both Delphi and FreePascal ( please correct me if I am wrong ).

If these are not fast enough, you may want to look into linked lists and possibly red-black trees and the like.

[cairnswm]

I have read that TCollection is more optimised than the various lists.

Also I have seen in a few places people indicating they have better performance based lists. I think DelphiX also has this claim and includes either a list of collection that is better optimised.

[savage]

Keep in mind that Delphi's TCollection inherits from TPersistent so factor that in when deciding whether it is usefull or not.

[Sly]

I'm a big fan of linked lists and trees.

But there may be a better method to speed up your game logic. Does every item in your list need to be updated every frame? Along the same lines of "the quickest polygon is the one you don't draw", you can say that "the quickest object is the one you don't update".

In our games, we have a maximum draw distance for each object as well as a maximum update distance. If objects are further than the maximum update distance from the camera, then they do not get updated.

[jasonf]

Well, There aren't really that many active in-game objects in my game, not on the current test level anyway, But I wholly agree with what you're saying. Don't do work if it's not required, save those precious CPU cyucles for something else.

I've broken up my level structure into:

Sectors()-->Layers()-->Entities()
Only entities on the same layer in the same sector can collide or interact in any way.

Each of these collections need to be accessed in order, so a linked list is perfect.. I tried to implement linked list capability into my Collection object, but it doesn't work.. probably some stoopid mistake on my part.

These objects need to be accessed with a key as well.


I also have resource managers which handle the real time loading of stuff from disk. They load the resources on the fly and dispose of them after a set period if no longer used. They control the actual SDL surfaces and so on so multiple objects can use the same resources.

Graphics
Music
Sounds
Animations

These need to be accessed using a key, generally not accessed in order.

I thought that if I created a do-all collection, I could create a linked list within my collection to reference the objects as they are added so I get both kinds of access... the best of both worlds.

Because there are so many collections in my game, I thought it would be a good place to squeeze as much speed out of as possible.

All in all, this structure works quite well and is generic enough for any 2D game (well that was the idea anyway)

[Sly]

It looks like you're on the right track.