Skip to content

NWScript function efficiencies

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!

Comments

  • SherincallSherincall Member Posts: 387

    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.
    pscythe
  • SherincallSherincall Member Posts: 387
    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.
    pscythe
  • weavejesterweavejester Member Posts: 10
    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.
  • dTddTd Member Posts: 182
    So what is the effective difference in efficiency between GetObjectByTag and GetNearestObjectByTag?
Sign In or Register to comment.