Register forum user name Search FAQ

Gammon Forum

Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to verify your details, confirm your email, resolve issues, making threats, or asking for money, are spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the password reset link.

Due to spam on this forum, all posts now need moderator approval.

 Entire forum ➜ SMAUG ➜ Running the server ➜ Case sensitive skill/spell lookups
Case sensitive skill/spell lookups

It is now over 60 days since the last post. This thread is closed.     Refresh page

Pages: 1  2 3  

Posted by Nick Gammon   Australia  (23,158 posts)  Bio   Forum Administrator
Date Reply #15 on Mon 29 Jan 2007 01:51 AM (UTC)
Message
It might be worth pointing out that you can make maps case-insensitive too. Read my post here:

http://www.gammon.com.au/forum/?id=2902

Search for "Case-insensitive maps" on that page. That shows how you can make a map that automatically uses case-insensitive keys, if that is what you want. The same technique applies to all appropriate STL containers (eg. multimaps, sets, etc.).
- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by Samson   USA  (683 posts)  Bio
Date Reply #16 on Mon 29 Jan 2007 01:48 PM (UTC)
Message
I'll have to look into it all a bit more since changing the skill_table itself in Smaug to a std::map is no small undertaking.

I'll also be taking a look at your case insensitive map since that's probably going to be quite important for keeping sanity :)

I'm assuming that you could do something like this:


skill_type *skill;
skill = skill_map["fireball"];


Where the skill_map is defined as:

std::map<string,skill_type*> skill_map;


Or would I be wrong in that?
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #17 on Mon 29 Jan 2007 02:13 PM (UTC)
Message
Yes, but again, that will create the entry if it doesn't exist already. You might want to define a helper function of some kind that does the map.find call, and returns null if not found or the value if found. (Of course, this means you can't distinguish between not having a key, and having it but containing null, but in this case that shouldn't really matter.)
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #18 on Mon 29 Jan 2007 05:47 PM (UTC)
Message
Samson, and others interested, I figured out why the single bsearch was not working.



Indeed it had to do with how the skill table was sorted.


If you go to tables.c:639 (or thereabouts), function skill_comp, you will see that it does two if checks based on type:

if( skill1->type < skill2->type )
  return -1;
if( skill1->type > skill2->type )
  return 1;


That made the skill table be sorted by skill type in addition to alphabetical order.

To fix this problem, and have the single bsearch calls work, it suffices to comment out those two lines.

Presto...

At some point, I might time this both ways to see what kind of difference this actually made in terms of time. Still, even if it doesn't make a difference with respect to time, it makes the code a whole lot easier to read.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Samson   USA  (683 posts)  Bio
Date Reply #19 on Mon 29 Jan 2007 09:18 PM (UTC)
Message
It's always the simplest things that create the biggest problems :)

That's good to know though. But the timing would have to be pretty well worth it to justify ripping out the rest of the code that depends on the gsn sorting being the way it is now. If you look at stuff like find_spell, find_skill, find_tongue, etc. you'll see what I mean.
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #20 on Mon 29 Jan 2007 09:21 PM (UTC)
Message
Aww, there's not that much to change, really. And besides I would think that the maintainability increase more than justifies the change. If you'd like, I can submit a patch for SMAUGfuss 1.7 to you in the near future.

First, though, I will do the timing, if anything just out of curiosity.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #21 on Tue 30 Jan 2007 12:17 AM (UTC)
Message
My timing results:

Quote:
New version:
Time elapsed: 14 secs, 233422 usecs

Old version:
Time elapsed: 32 secs, 256077 usecs


Basically it's twice as fast.



Now, some details about my testing.....


My "old version" is the case-insensitive version.

My "new version" is that version, except that it sorts the table only according to name (not according to skill type), and it only does one exact bsearch and one prefix bsearch.

My test:

(1) record start time
(2) Pick a random skill 20,000,000 times and look it up in the skill table, making sure it gets found
(3) record end time

The code, inserted into db.c:


   for( x = 0; x < top_sn; x++ )
      if( !gsn_first_spell && skill_table[x]->type == SKILL_SPELL )
         gsn_first_spell = x;
      else if( !gsn_first_skill && skill_table[x]->type == SKILL_SKILL )
         gsn_first_skill = x;
      else if( !gsn_first_weapon && skill_table[x]->type == SKILL_WEAPON )
         gsn_first_weapon = x;
      else if( !gsn_first_tongue && skill_table[x]->type == SKILL_TONGUE )
         gsn_first_tongue = x;

   // BEGIN TEST CODE

   // do some timing tests
   struct timeval startTime;
   gettimeofday(&startTime, NULL);

   // grab 20,000,000 random skills
   int i;
   for (i = 0; i < 20000000; i++)
   {
       int sn = number_range(1, gsn_top_sn-1);

       const char * name = skill_table[sn]->name;

       assert(skill_lookup(name) != -1);
   }

   struct timeval endTime;
   gettimeofday(&endTime, NULL);

   time_t secs = endTime.tv_sec - startTime.tv_sec;
   suseconds_t microsecs = endTime.tv_usec - startTime.tv_usec;

   printf("Time elapsed: %ld secs, %ld usecs\n", secs, microsecs);

   exit(0);

   // END TEST CODE

   log_string( "Loading classes" );
   load_classes(  );
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #22 on Tue 06 Feb 2007 09:08 AM (UTC)
Message
Samson, is there any interest in this change becoming a part of stock SMAUGfuss? Or a patch of any kind?
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Samson   USA  (683 posts)  Bio
Date Reply #23 on Tue 06 Feb 2007 01:16 PM (UTC)
Message
Yes. It would be great to have the skill lookup system simplified.
Top
Posted by Conner   USA  (381 posts)  Bio
Date Reply #24 on Tue 06 Feb 2007 09:19 PM (UTC)
Message
There are definitely a few of us watching this thread to see what will come out of it towards a FUSS fix, Ksilyan. :)
-=Conner=-
--
Come test your mettle in the Land of Legends at telnet://tcdbbs.zapto.org:4000
or, for a little family oriented medieval fun, come join us at The Castle's Dungeon BBS at telnet://tcdbbs.zapto.org
or, if you just want information about either, check our web page at http://tcdbbs.zapto.org
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #25 on Wed 07 Feb 2007 03:08 AM (UTC)
Message
I have finished making what appear to be the necessary modifications; I have not fully tested them, though, because I don't have a full SMAUGfuss distribution available (with lots of areas, players, etc.) I see no real reason why it won't work, though. My main concerns have to do with loading and saving players with affects, and herbs. Slot numbers seem to not be an issue. But even those issues are paranoia; I did look through it all and it looks like it should work.

I will be uploading the patch to the SMAUGfuss forums shortly, and hopefully somebody will be able to confirm that it loads seamlessly into an existing world. When I post it, I'll put the link here.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Gatewaysysop2   USA  (146 posts)  Bio
Date Reply #26 on Thu 08 Feb 2007 02:17 AM (UTC)
Message
Just curious... isn't changing the skill table to NOT be sorted by type going to break the do_practice display? If I remember correctly that depends on the table being in order of type. I don't know anywhere else that relies on this, but that comes to mind.

If that's the only place, and it is indeed a problem, there's probably a decent way around it with this fix.
"The world of men is dreaming, it has gone mad in its sleep, and a snake is strangling it, but it can't wake up." -D.H. Lawrence
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #27 on Thu 08 Feb 2007 05:20 AM (UTC)
Message
Hmm, that probably will be a problem. I'll have to fix my patch then; that's the kind of stuff I might not notice straight away. :)

But yes, that will be relatively easy to fix.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #28 on Sat 10 Feb 2007 08:46 PM (UTC)
Message
Here is the SMAUGfuss forum post for my patch:
http://www.fussproject.org/index.php?a=topic&t=1109

I fixed the 'practice' issue by creating a parallel skill table, that is sorted by type. It seemed like the easiest thing to do. The parallel table is resorted every time the skill table is changed. I figure that the skill table will change very rarely, and it's more efficient to just cache the sorted-by-type table than to iterate over the skill table several times, once per skill type, or to rebuild a sorted table every time, by storing found skills in temp. lists while iterating over the main table.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Conner   USA  (381 posts)  Bio
Date Reply #29 on Sat 10 Feb 2007 09:38 PM (UTC)
Message
For an established world, the skill table probably shouldn't be changing often, and then probably only minor changes such as an adjustment here or there or the addition of a new skill or two now and then, but for a world in development, the skill table could have periods of extensive changes happening at a pretty rapid pace. But I suppose if you cache it when it changes, it'd all be good.
-=Conner=-
--
Come test your mettle in the Land of Legends at telnet://tcdbbs.zapto.org:4000
or, for a little family oriented medieval fun, come join us at The Castle's Dungeon BBS at telnet://tcdbbs.zapto.org
or, if you just want information about either, check our web page at http://tcdbbs.zapto.org
Top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.

89,547 views.

This is page 2, subject is 3 pages long:  [Previous page]  1  2 3  [Next page]

It is now over 60 days since the last post. This thread is closed.     Refresh page

Go to topic:           Search the forum

[Go to top] top

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

Home