Quest 6 technical suggestion - Make iterations for certain types of object more efficient, with subsets of world/w

Kln

I have always noticed that Quest 6 iterates often in the world dictionary w, where all the items are stored. Sometimes several times during a turn.

I think it would be a good practice to isolate specific types of objects in sub-dictionaries. Looping on specific elements, such as rooms or NPCs, would be much faster and less ressource consuming.

The process would basically be:
createRoom()
Instead of going into w, the function populates a roomDict dictionary instead. Every reference to w in the code would become a reference to roomDict, which would skip the iteration over non-room items, for instance when drawing a map.

createItem()
After w is built, do a single loop on the dictionary. Using the flag identifying the type of the item (npc=true for instance), instanciate a new dictionary and populate it. The functions related to this specific type of object can now reference this dictionary instead of w

Useful standard subsets to have around

  • Rooms
  • NPCs
  • Wearables
  • Keys

How to manage loc properties
Locations can be either a room or a npc. In which case the solution is simple: check both the room and npc subsets, instead of the w subset. Even if it is two subsets instead of a single larger one, their combined sum of elements will be either inferior or equivalent to w.
To make it even more efficient, you could also add a flag indicating whether the item is currently in a room or in a NPC's inventory.

Custom subsets
While there would be a limited number of standard dictionaries from the onset, such as roomDict or npcDict, the player/developer could create its own custom dictionaries, for its custom rules and scripts.
The player would call a specific settings function. Each line of the function would look like this, for instance
monsterDict = populateSubWorld("isMonster", true )
The populateSubWorld function would be defined as such:

populateSubWorld(propertyName, propertyCondition) {
let newDict = {}
for (let key in w) {
  if (w[key][propertyName] == propertyCondition) {
    newDict[key] = w[key]
]
return newDict
}

With a little more brainstorming, there might be a possibility to give more conditions to test.
These custom subsets are implied to be for the player/dev's use only, and are not supported by the standard functions of the framework.


If you want to access something by name, there's no benefit to having a separate array. monsterDict["troll4"] is no faster than w["troll4"], and having everything in the same dictionary means there's less chance of some library author producing code that doesn't work properly with other object types.

Looping over a list, however, is a valid use. But for something like that, there's no need to make it a dictionary. It's faster to loop over an array (unless they've optimised it since the last time I checked).

So why not make your subworlds simple arrays?

Then you don't really need to create a new function for something JS already does well. But if you really want a function like the one you suggested (just returning an array rather than a dict, you could do:

function populateSubWorld(propertyName, propertyCondition) {
  return w.values().filter(a => a[propertyName] == propertyCondition)
}

although I'd be more likely to write it as:

function populateSubWorld(propertyName, propertyCondition) {
    return w.values().filter(
      (propertyCondition === undefined) ?
        (a => propertyName in a) :
        (a => a[propertyName] == propertyCondition
      )
    )
}

so that monsterList = populateSubWorld("isMonster") with a single parameter will get a list of everything that has that property, a little faster than checking for a specific value.


Kln

What I want to solve is functions like "isHereNotHeld" or "map.update()" who iterate over the whole w dictionary, to find the comparatively much smaller list of items fitting the criterium of the function (respectively anything which has this.loc == player.loc, and items where if (room.mapRegion !== region && room.mapRegion !== true)

If you have just four rooms and ten items, this is relatively quick, but imagine if, after two years of development, you have sixty rooms, fifty NPCs, and a hundred fifty items of different types.

Arrays could be another solution, considering that this is an attempt to solve a loop issue.

But what I want to push is that I think that there may be optimization issues with turn scripts down the line, with everything being stored in a single dictionary, and thinking with subsets of world would be something to consider.


Sorry for the long response… I've been thinking way too hard about program efficiency today, as I've been working on a very slow piece of code today. Waiting for my computer to loop over an array of billions of objects gets tedious very fast; so on a project like that, every tiny change to improve efficiency makes a difference.

Now I just can't get my mind out of efficiency mode, trying to work out what's the "best" way to do something.

What I want to solve is functions like "isHereNotHeld" or "map.update()" who iterate over the whole w dictionary, to find the comparatively much smaller list of items fitting the criterium of the function (respectively anything which has this.loc == player.loc, and items where if (room.mapRegion !== region && room.mapRegion !== true)

I think that having a separate list for things like that could make a search faster… but you'd have to remember to update those lists every time an object moves, or every time the player moves. It's easier to make a mistake; as well as being extra operations. Which is more efficient could well vary from one project to another; it's hard to say.

If you have just four rooms and ten items, this is relatively quick, but imagine if, after two years of development, you have sixty rooms, fifty NPCs, and a hundred fifty items of different types.

I like to make my code more efficient if I can (for example, a 20% time saving by using an array rather than a dictionary). But I am well aware that in most situations it really doesn't matter, because a function like that will appear to be instant to a human observer unless the number of objects in your game is very large (For simple filter functions like the ones you reference, it's likely to be "faster than the eye can see" until you get to around fifty thousand objects. Or a million on a really fast PC)

If you want to optimise the code, it's probably better to look at the functions that are O(N²); they'll slow down at much lower numbers.


Kln

Thanks for your input.
Waiting times around lists and loops is something I encountered in every project I worked on myself, and one of the issues where a single change has the most dramatic effects, as you say. For instance, searching for an element among many in a set rather than a list can make the duration of a program go from hours down to minutes. Same for using a fork/join to traverse your array instead of a single iterator.


Log in to post a reply.

Support

Forums