NWScript function efficiencies

weavejester

I'm a little curious to see if there's any information on how efficient some of the functions in NWScript are. I've heard that local variables are stored on objects as a linked list, for instance, so I'd imagine that GetLocalString and SetLocalString are O(N).

There are a lot of functions in NWScript, so to limit my query down, I'm particularly interested in functions that perform searches of objects or creatures. Specifically:

• GetObjectByTag
  
• GetNearestCreature / GetNearestCreatureToLocaiton
  
• GetFirstObjectInShape / GetNextObjectInShape
  

How efficient is it to find an object by a tag? Do tags get a O(1) hashtable lookup? Some sort of O(log N) tree? Or is it another linked list?

How efficient is it to search for nearest creatures or objects? Is it always an O(N) iteration over all objects in the area? Is it an iteration over a list restricted by type? Is there something more sophisticated like an quadtree lookup?

If a Beamdog dev could weigh in, I'd be very grateful!

Sherincall

weavejester said:

How efficient is it to find an object by a tag? Do tags get a O(1) hashtable lookup? Some sort of O(log N) tree? Or is it another linked list?

O(log(N)). A simple binary tree you traverse comparing the tags. Tags are compared directly, not hashed.

The GetNearest and GetObjectInShape functions only operate on the objects in the current area, and have the worst case complexity of O(N), where N is all objects in that area. But on average they should be O(log(N)) as the objects are sorted by their position on the X axis, so chances are the next/nearest object to you is one that's also close on the X axis, which makes it easier to find.
Worst case would be something if you had objects at these (x,y) positions:

(1,1); (2, 100), (3, 100), (4, 100), (5, 100), (25, 1)

The nearest object to (1,1) is (25,1), but since they're sorted by X, it'll be the last to be checked.

Sherincall

Also, something you didn't ask about but that's very common is mapping Object ID (i.e. the object nwn type) to the (pointer to) actual object. This is done through a hash table of sorts, and is O(N/4096), where N is all objects in the module. So the more objects you have, the slower all scripts are because every lookup takes longer.

weavejester

Your reply is seriously helpful! Thanks so much! For some reason I wasn't notified about replies to this post, so it took me a while to remember to check up on it. I wasn't expecting such an in-depth and comprehensive response.

dTd

So what is the effective difference in efficiency between GetObjectByTag and GetNearestObjectByTag?