On Sun, 19 Jan 2003, Anarchangel wrote: > Hello, > > I've been giving some thought to changing the resistance system from a > simple is_set or not is_set to a number between -100 (meaning take double > damage) to 100 (meaning immune), and 0 being taking normal damage. This > means I could theoretically get rid of immunities altogether. > > The problem is the only way I can think of accomplishing this would be to > make about 30 entries in mob_index_data (one for each resistance) rather > than just one as it is currently (res_flags). > > This seems overly messy to me, especially since about 30 thousand mobs > would be using it and most of them don't even have more than one or two > resistances. > > Anyone ever done this in an efficient manner?
No, I haven't done it. But I can give you some input. Rather than creating separate entries, such as res_summon, res_charm, etc., it would be easier to create an array. You could change the defines of the resistance types to 1, 2, 3, etc, and reference the individual members as ch->resist[RES_SUMMON], for example. Since you want to go from -100 to 100, using a byte for each entry would give you the range you want, without wasting much space at all (unsigned char). Now... About the efficiency of doing this. In stock ROM, the resistances take up 3 long ints = 12 bytes per character. Stock ROM has 23 immunity/resistance/vulnerability types by my count. So by merely converting to an array of unsigned characters, you'll add approximately 11 bytes per character (which will probably end up 12 bytes with padding) To put it in perspective, in stock ROM, the CHAR_DATA structure is 288 bytes long. The PC_DATA structure is 444 bytes long. The DESCRIPTOR_DATA structure is 1592 bytes long. These are just the sizes of the structures themselves. If you count all the strings (name, short description, long description, etc.), you'll end up with a much larger number. As far as computational efficiency, an array is very efficient. Accessing a random resistance value is an O(1) operation. Now let's look at some other ways of doing it. How about a linked list? They are more efficient than an unused array, right? On a 32-bit system, you'll have 4 bytes for the head of the list. Then you'll have at least 6 bytes of data per node. (a pointer, the type of resistance it is, and the value). When you add in alignment requirements, you'll need 8 bytes per node. And the cost to search the list? O(n), where n is the number of resistances on the mob. How about some type of tree data structure? For a binary tree, you'll need 4 bytes to hold a pointer to the root node. Then each internal node will have 2 pointers, plus the resistance type, and the value. Add in some more if you want a more advanced tree, such as a red-black tree. (You'll need some way to get a balanced tree. Adding to a binary tree in sorted order gives you a linked list, with more memory wasted). So at a minimum, you have 10 bytes per node, 12 when it's aligned. The cost to search the list is O(lg n). So in summary: Stock: 12 bytes. O(1) search. Array: 24 bytes. O(1) search. Linked list: 4 + 8/resistance bytes. O(n) search. Tree: 4 + 12/resistance bytes. O(lg n) search. It really depends on how many resistances you want to have. With an average of between 0 or 1 resistances per character, a linked list or tree would take less space. At an average of 2 resistances per character, a linked list will take less space. At 3 or more per character, an array is the most efficient data structure. Of course, if you add more resistances, the size of the array type will increase accordingly, so take that into account. With a flexible system like this, you'll have the option of specifying a 5 or 10% resistance to something, so you might end up with a whole lot more than you have now. So take that into account when you try to figure out how many resistances you think you'll have. As far as ease of use, I doubt I have to point out how much easier an array would be to use than a more advanced data type. In summary, my suggestion is to use an array of unsigned characters. Dennis
