[Home] [Downloads] [Search] [Help/forum]

Gammon Software Solutions forum

See www.mushclient.com/spam for dealing with forum spam. Please read the MUSHclient FAQ!

[Folder]  Entire forum
-> [Folder]  SMAUG
. -> [Folder]  Lua
. . -> [Subject]  Adding path finding command to SMAUG
Home  |  Users  |  Search  |  FAQ
Username:
Register forum user name
Password:
Forgotten password?
Adding path finding command to SMAUG

[Reply to this subject]  Reply to this subject   [New subject]  Start a new subject   [Refresh] Refresh page

Pages: 1 2  

Posted by Nick Gammon   Australia  (18,770 posts)  [Biography] bio   Forum Administrator
Date Sat 07 Jul 2007 04:08 AM (UTC)  [ quote  ]
Message
Now that I have been adding Lua scripting to SMAUG Fuss, I have been experimenting with the path-finding algorithm described in this post:

http://www.gammon.com.au/forum/bbshowpost.php?id=7306

The objective of this was to help newbies find their way around, by listing common locations (eg. baker, repairs, academy), and tell them the way to walk to get there. I am sure I have seen something similar in one of the pay MUDs.

This code is entirely implemented in Lua, except for the 3 lines of code needed to add the command handler into the commands list.

Here is an example of it in operation. First you can type "whereis" to find the known destinations:


whereis

This will show you how to get to commonly-used locations.
Type 'whereis [destination]' to get a suggested route (eg. 'whereis baker').

    Destination : Room name
-------------------------------------------------------
        Academy : Entrance to the Academy
      Alchemist : The Alchemist's
          Baker : The Darkhaven Bakery
   Battleground : Battle Grounds
        Butcher : The Butcher's Shop
Cathedral altar : The Cathedral Altar
       Clothing : Annir's Clothing
          Dairy : The Dairy Tent
      East gate : Inside the Eastern Gate
       Fountain : Darkhaven Academy
   Headmistress : Darkhaven Academy
         Healer : The Academy Healer
            Inn : The Darkhaven Inn
      Languages : Abbigayle's Language Lessons
          Magic : The Wizard's Tent
     North gate : Inside the Northern Gate
        Repairs : The Blacksmith's Tent
        Scrolls : The Scribe's Tent
         Skills : The Laboratory of Skills and Spells
     South gate : Inside the Southern Gate
         Square : Darkhaven Square
         Tailor : Annir's Clothing
         Tavern : The Tavern
        Weapons : Weaponry Shop
      West gate : Inside the Western Gate


The exact list is under your control, as you edit a table of vnums that you want to be made available. Now you can choose one:


whereis repairs

To get to The Blacksmith's Tent walk: 5s 2e (se) 2s e s


This generates the shortest path from the current room to the selected room, using the algorithm mentioned before.

Here is another example:


whereis academy

To get to Entrance to the Academy walk: 5s 2e (se) 3e s


The list of destinations is in the Lua source file, it looks like this:


available_dests = {
   butcher = 21057,
   academy = 21280,
   inn = 21069,
   baker = 21060 ,
   tavern = 21068,
   dairy = 21061,
   alchemist = 21054,
   weapons = 21062,
   square = 21000,
   magic = 21055,
   scrolls = 21051,
   repairs = 21058,
   clothing = 21066,
   headmistress = 10300,
   languages = 10306,
   skills = 10303,
   healer = 10319,
   battleground = 10368,
   fountain = 10300,
   tailor = 21066,
   ["south gate"] = 21074,
   ["north gate"] = 21100,
   ["west gate"] = 21088,
   ["east gate"] = 21113,
   ["cathedral altar"] = 21194,
   
   }


You can customize it to show as many or as few rooms as you want. The room descriptions are looked up, and the list sorted into alphabetic order.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by David Haley   USA  (3,881 posts)  [Biography] bio   Moderator
Date Reply #1 on Sat 07 Jul 2007 07:30 AM (UTC)  [ quote  ]
Message
Cool stuff! One quick question; why are some of the directions parenthesized?
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top
Posted by Nick Gammon   Australia  (18,770 posts)  [Biography] bio   Forum Administrator
Date Reply #2 on Sat 07 Jul 2007 07:58 AM (UTC)  [ quote  ]
Message
With speedwalking in MUSHclient the spaces are optional, so you can write this:


4s2ensw


There is an obvious ambiguity for the "sw" part. Is it southwest, or south, followed by west?

So, MUSHclient uses parentheses for the directions nw, sw, ne,se.

Thus, the generated speedwalks follow the same pattern. You could change the output routine to do it differently, I initially had it like this:


s, s, s, s, s, e, e, se, s, s, e, s


This is clearer, if a bit wordy (note the multiple occurences of "s"), so I changed it to be something that could be copied and pasted into MUSHclient's speedwalks.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by David Haley   USA  (3,881 posts)  [Biography] bio   Moderator
Date Reply #3 on Sat 07 Jul 2007 08:10 AM (UTC)  [ quote  ]
Message
Oh, right, I forgot about that... good reason.

I'm almost done implementing a trie class in Lua -- a map whose keys must be strings, and where the lookup time is proportional to the length of the key, not the number of elements. I'm going to use it for the command table implementation in Lua; I need to do prefix lookup in addition to exact matching.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top
Posted by Gohan_TheDragonball   USA  (183 posts)  [Biography] bio
Date Reply #4 on Sat 07 Jul 2007 09:07 AM (UTC)  [ quote  ]
Message
so you have to physically list every room and where its exits lead to in the table?
[Go to top] top
Posted by Nick Gammon   Australia  (18,770 posts)  [Biography] bio   Forum Administrator
Date Reply #5 on Sat 07 Jul 2007 10:42 AM (UTC)  [ quote  ]
Message
No, it works it out.

As a once-only operation, you run a command that generates a list of rooms and exits, like this:


rooms = {}
rooms [21013] = {
   exits = {s=21014, n=21012, } }
rooms [21021] = {
   exits = {e=21020, w=21022, n=24800, } }
rooms [21029] = {
   exits = {s=21028, n=21030, } }
rooms [21037] = {
   exits = {e=21038, s=21126, w=21036, } }


This is automatically generated from your rooms information.

To find a path the algorithm works out the shortest route, see the thread I posted for the way it works.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by David Haley   USA  (3,881 posts)  [Biography] bio   Moderator
Date Reply #6 on Sat 07 Jul 2007 03:28 PM (UTC)  [ quote  ]
Message
You could also get that information by binding rooms to Lua objects; if you started by binding the current room and all neighboring rooms (which is really all you need anyhow) the memory requirements would be fairly small, and you wouldn't have the issue of pointers becoming invalid because you do the search 'instantly' -- people can't destroy rooms as you search.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top
Posted by Nick Gammon   Australia  (18,770 posts)  [Biography] bio   Forum Administrator
Date Reply #7 on Sat 07 Jul 2007 09:54 PM (UTC)  [ quote  ]
Message
Good idea, David.

I have reworked the algorithm so it no longer needs a separately-generated file of rooms and exits. After all, it has that information available to it.

This also makes it more flexible, you could have it offer a different set of destinations, depending on where you are.

For example, town A could have a list of local places, and town B could have a different list.

So now it is completely automatic - everything is done from the in-memory rooms list.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by Conner   USA  (381 posts)  [Biography] bio
Date Reply #8 on Sat 07 Jul 2007 10:33 PM (UTC)  [ quote  ]
Message
This sounds really nifty, Nick. I'm not sure I follow entirely though, between the five pages of the other thread and the posts in this one, I don't quite see how you've done this. Would it be asking too much to see your actual code for this? It really sounds like a command I'd love to give my players that would get a lot of use on my mud once it's known.
-=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
[Go to top] top
Posted by Nick Gammon   Australia  (18,770 posts)  [Biography] bio   Forum Administrator
Date Reply #9 on Sat 07 Jul 2007 10:34 PM (UTC)  [ quote  ]
Message
I have now allowed for multiple places that offer directions (eg. multiple towns).

There is now a table for each "zone" that you want to offer directions around. By checking the player's room against a vnum range, the appropriate list of directions is offered.

For example, if you move to Redferne's residence and type "whereis" you now get a different list:



    Destination : Room name
-------------------------------------------------------
        Kitchen : The Kitchen of Naris
    Monster pen : The Monster Pen
        Outside : Outside Redferne's residence

Type 'whereis [place]' to get a suggested route (eg. 'whereis kitchen').

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by Conner   USA  (381 posts)  [Biography] bio
Date Reply #10 on Sat 07 Jul 2007 11:44 PM (UTC)  [ quote  ]
Message
That really is cool.. sure wish I could figure out how to add it to my mud... ;)
-=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
[Go to top] top
Posted by Nick Gammon   Australia  (18,770 posts)  [Biography] bio   Forum Administrator
Date Reply #11 on Sun 08 Jul 2007 12:54 AM (UTC)  [ quote  ]
Message
You are welcome to see it, however it relies upon the Lua hooks I mentioned in the earlier posting.

I am tidying up the Lua interface, and adding a much more general "task" system (ie. a quest system).

It is working fairly well, I am just adding some example tasks to demonstrate the whole thing. When that is done I will release the entire code, Lua and C part, and you can see how it is all done.

It should be very simple to add to an existing SMAUG-based MUD.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by Conner   USA  (381 posts)  [Biography] bio
Date Reply #12 on Sun 08 Jul 2007 01:26 AM (UTC)  [ quote  ]
Message
Ok, Nick, I'll be patient then. :)
-=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
[Go to top] top
Posted by Valcados   (15 posts)  [Biography] bio
Date Reply #13 on Tue 24 Jul 2007 12:58 AM (UTC)  [ quote  ]
Message
Forgive the late reply, I just registered for this forum.

Why create this complex LUA pathfinding algorithm when a pathfinding algorithm already exists in track.c? It's fairly straightforward to modify the algorithm in track.c to let you know the whole path, vs. just the first step. After all, it already traces the whole path anyway, then just throws away all the info except the first step.
[Go to top] top
Posted by Nick Gammon   Australia  (18,770 posts)  [Biography] bio   Forum Administrator
Date Reply #14 on Tue 24 Jul 2007 01:59 AM (UTC)  [ quote  ]
Message
I must admit I didn't notice the track skill. It looks like it could be modified to find the path to a room (it currently finds a mob, so presumably finding the room it is in is part of it).

The Lua code isn't particularly complex - I can't see offhand exactly what method the track.c code uses, although it looks similar.

There is certainly more than one way of doing things like that - however to make the code in track.c do exactly what the Lua code does, you would need a few changes - like making a list of destination rooms, showing the possible rooms you can go to, finding the full path, returning it in a nice readable way, and so on.

I was really just trying to show how reasonably complex things can be done in the Lua interface - I don't doubt you could also do them in straight C.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] 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.

7,801 views.

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

[Reply to this subject]  Reply to this subject   [New subject]  Start a new subject   [Refresh] Refresh page

Go to topic:           Search the forum

[Go to top] top

[Home]

Written by Nick Gammon - 5K

Comments to: Gammon Software support
[RH click to get RSS URL] Forum RSS feed ( http://www.gammon.com.au/rss/forum.xml )

[Best viewed with any browser - 2K]    [Internet Contents Rating Association (ICRA) - 2K]    [Web site powered by FutureQuest.Net]