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 ➜ MUSHclient ➜ Suggestions ➜ Shortest Path Speedwalking

Shortest Path Speedwalking

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


Pages: 1 2  3  

Posted by Belshazzar   (9 posts)  Bio
Date Sun 21 Mar 2004 10:54 PM (UTC)
Message
I migrated to MUSHClient from a MacOS 9 client called Rapscallion. Rapscallion had this great speedwalking feature where you could choose your current location and destination from drop down menus and it would speedwalk you to your destination. I loved it! The drop down menus were a little cumbersome when you had a lot of locations.

My feature request is for a shortest path algorithm to be applied to speedwalk aliases. I am not sure which S.P.A would be best for a normal mudder with 100 or so defined locations. I know some paths change depending on what time it is or are unusable by certain character classes. That would have to be dealt with, perhaps by a weighted graph algorithm.

Top

Posted by Meerclar   USA  (733 posts)  Bio
Date Reply #1 on Sun 21 Mar 2004 11:02 PM (UTC)
Message
To do this Nick would also need to write in a way to associate which paths start where in relation to other paths or the algorythm is pretty much garbage. Don't know how much you know about coding, but this is a seriously signifigant request on the code side to make it work any kind of well.

Meerclar - Lord of Cats
Coder, Builder, and Tormenter of Mortals
Stormbringer: Rebirth
storm-bringer.org:4500
www.storm-bringer.org
Top

Posted by Belshazzar   (9 posts)  Bio
Date Reply #2 on Mon 22 Mar 2004 12:07 AM (UTC)
Message
You would not necessarily have to alter the paths themselves. You could simply add another data type, call it Location or something, representing a Node on the directed graph. It could use your existing speedwalk paths as edges, with the weight determined by Speedwalk length. (I think we already have a function for speedwalk length.)
Top

Posted by Nick Gammon   Australia  (23,158 posts)  Bio   Forum Administrator
Date Reply #3 on Mon 22 Mar 2004 01:07 AM (UTC)
Message
The problem is really knowing where you are. Some MUDs in particular like to keep pretty quiet about that, to cut down on automated walking.

I can see it might work, if you had a way of knowing your precise location, and what paths led to/from it.

If any script writer wants to write a pilot to demonstrate how it is done, by all means. ;)

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by Belshazzar   (9 posts)  Bio
Date Reply #4 on Mon 22 Mar 2004 01:52 AM (UTC)
Message
The way Rapscallion did it was to have you select both your location and destination from combo box type widget things. They didn't have those little triangle submenu things so they got reallly long. That being said, you could always make triggers to recognize your more unique locations and auto-set the location.
Top

Posted by Nick Gammon   Australia  (23,158 posts)  Bio   Forum Administrator
Date Reply #5 on Mon 22 Mar 2004 06:11 AM (UTC)

Amended on Mon 22 Mar 2004 06:12 AM (UTC) by Nick Gammon

Message
Well, it is an interesting challenge, so I have made a start on it. This is very preliminary, but is a way of building up the data required for a more complex solution.

It seems to me that as you explore a place you have "important" points (ones you want to go back to), such as an inn, shop, central square, and other places, which are really just enroute points.

The plugin below is designed to allow you to collect "checkpoints" into an array (using the new array functions just released). Thus, you need to have the latest version, 3.46 to try it.

The general idea is to concentrate on mapping your way around, and then do this:


  1. Clear and mark a checkpoint: cc

  2. Wander around and find somewhere interesting (eg. a shop)

  3. Checkpoint this place: cp

  4. Go somewhere else (eg. a fountain)

  5. Checkpoint the new place: cp


Then when you want to go somewhere from a checkpointed place, type "cl" (checkpoint list), and you will see something like this:


Current room believed to be [Darkhaven Square]
  1: Atop the Battlements (4n 4w u )
  2: Darkhaven Academy (3e 3s 4w 4s 7e s d )
  3: Entrance to the Academy ({auto} 3e s)
  4: Inside the Northern Gate ({auto} 5n)
  5: The Darkhaven Inn (2w s )
  6: The Western Hall (w s )
  7: Vertic Avenue ({auto}  n)


Then type "cg x" where x is a number in the list (eg. cg 5) and it will generate the appropriate speedwalk.

The "{auto}" entries are generated automatically as reverse speedwalks, hoping that this will correctly take you back where you came from.

Now there is a fair bit that would need tweaking to get this perfect, for one thing I have custom coded how room names are recognised in SMAUG - a line containing bold text, red on black. Already I have found a problem with some system messages being in that colour, so I have put one in as a trigger with lower priority (so it fires first) and thus doesn't get considered as a room name.

Also, I found that I got room names at the end of prompts if you walked quickly, so I did another "prompt" trigger that does a GetStyleInfo to detect if the line consists of 2 styles, and the second one is bold red on black.

Another issue again is that it relies on speedwalks being generated, and it turns out you can't turn on automapping automatically, so this is added in version 3.47.

You also need to customise the "can't go in that direction" string for you own MUD, so the automapper recognises when you have done a false turn.

However as far as it goes, it is a nice way of quickly generating paths from one spot to another.


<?xml version="1.0" encoding="US-ASCII"?>
<!DOCTYPE muclient>
<!-- Saved on Monday, March 22, 2004, 4:43 PM -->
<!-- MuClient version 3.47 -->

<!-- Plugin "Automap" generated by Plugin Wizard -->

<muclient>
<plugin
   name="Automap"
   author="Nick Gammon"
   id="23a544e6b6eeb7ea26c29b7d"
   language="VBscript"
   purpose="Creates speedwalks from one checkpoint to another one"
   save_state="y"
   date_written="2004-03-22 16:38:10"
   requires="3.46"
   version="1.0"
   >
<description trim="y">
<![CDATA[
cp - add a checkpoint
cl - list checkpoints from this location
cg x  - go to checkpoint x (eg. cg 5)
cc - clear current speedwalk - start new checkpoint

Automap:help - this description


]]>
</description>

</plugin>


<!--  Get our standard constants -->

<include name="constants.vbs"/>

<!--  Triggers  -->

<triggers>
  <trigger
   back_colour="8"
   bold="y"
   enabled="y"
   match="*"
   match_back_colour="y"
   match_bold="y"
   match_inverse="y"
   match_italic="y"
   match_text_colour="y"
   send_to="9"
   sequence="100"
   text_colour="9"
   variable="room"
  >
  <send>%1</send>
  </trigger>
  <trigger
   enabled="y"
   match="&lt;*&gt;*"
   script="OnGetRoomFromPrompt"
   sequence="100"
  >
  </trigger>
  <trigger
   back_colour="8"
   bold="y"
   enabled="y"
   match="The reddish sun sets past the horizon."
   match_back_colour="y"
   match_bold="y"
   match_inverse="y"
   match_italic="y"
   match_text_colour="y"
   sequence="90"
   text_colour="9"
  >
  </trigger>
</triggers>

<!--  Aliases  -->

<aliases>
  <alias
   script="OnClearcheckpoint"
   match="cc"
   enabled="y"
   sequence="100"
  >
  </alias>
  <alias
   script="OnCheckpointlist"
   match="cl"
   enabled="y"
   sequence="100"
  >
  </alias>
  <alias
   script="OnCheckpoint"
   match="cp"
   enabled="y"
   sequence="100"
  >
  </alias>
  <alias
   script="OnCheckpointgoto"
   match="cg *"
   enabled="y"
   sequence="100"
  >
  </alias>
</aliases>

<!--  Script  -->


<script>
<![CDATA[
'
'  Load mapping array
'

Sub OnPluginInstall

  ArrayCreate "map"
  ArrayImport "map", GetVariable ("map"), ","

  ArrayCreate ""  ' work array

'
' turn auto-mapping on
'  

'  EnableMapping vbTrue  ' (NOT IN THIS VERSION - use in version 3.47 up)

End Sub

'
' The plugin is saving its state
'
sub OnPluginSaveState

'
' Save mapping array
'
  SetVariable "map", ArrayExport ("map", ",")

end sub

'
'  helper routine to add a new path to the array
'

Sub AddPath (from_location, to_location, speedwalk)
dim currspeedwalk, currpath, newpath
  
  newpath = EvaluateSpeedwalk (speedwalk)

  ArrayClear ""  ' get rid of previous stuff

'
'  get current entries into work array
'
  ArrayImport "", ArrayGet ("map", from_location), ","

'
'  see what the current path there is
'
  currspeedwalk = ArrayGet ("", to_location)

  If currspeedwalk <> "" Then
    currpath = EvaluateSpeedwalk (currspeedwalk)
    If Len (newpath) > Len (currpath) Then
      ColourNote "white", "red", "New path is: " & speedwalk
      ColourNote "white", "red", "Old path is: " & currspeedwalk
      ColourNote "white", "red", "Retaining older, shorter, path."
      Exit Sub
    End If ' new path longer
  End If  ' have an old path

'
'  note path from last checkpoint
'
  ArraySet "", to_location, speedwalk

  ColourNote "white", "blue", "Path from '[" & _
             from_location & "] to [" & _
             to_location & "] noted as " & _
             speedwalk
'
'  put back new destinations
'
  ArraySet "map", from_location, ArrayExport ("", ",")

End Sub	' AddPath 


Sub OnCheckpoint (name, line, wildcards)
Dim room, checkpoint, mapstring


'
'  get into variables to save time and confusion
'
room = trim (GetVariable ("room"))
checkpoint = trim (GetVariable ("checkpoint"))
mapstring = GetMappingString 

If Mapping Then
  If checkpoint <> "" And _
     room  <> "" And _
     mapstring <> "" Then

    AddPath checkpoint, room, mapstring

'
'  now add reverse path
'

    AddPath room, checkpoint, "{auto}" & ReverseSpeedwalk (mapstring)

  End If  ' already have a checkpoint
'
'  note new checkpoint
'
  SetVariable "checkpoint", room
'
'  start mapping again from here
'
  DeleteAllMapItems

  ColourNote "white", "blue", "New checkpoint started at: " _
     & room

Else
  ColourNote "white", "red", "Auto-mapper not active"
End If ' mapping 

End Sub  ' OnCheckpoint 

Sub OnClearcheckpoint (name, line, wildcards)

'
'  clear checkpoint (start from here)
'
  SetVariable "checkpoint", GetVariable ("room")
'
'  start mapping again from here
'
  DeleteAllMapItems

  ColourNote "white", "blue", "New checkpoint started at: " _
     & GetVariable ("room")

End Sub ' OnClearcheckpoint 

Sub OnCheckpointlist (name, line, wildcards)
Dim room, destinations, count, k

  room = trim (GetVariable ("room"))
  count = 0

  ColourNote "white", "blue", "Current room believed to be [" & _
           room & "]"

'
'  get current entries into work array
'
   ArrayClear ""  ' get rid of previous stuff
   ArrayImport "", ArrayGet ("map", room), ","
  
   destinations = ArrayListKeys ("")

   If Not IsEmpty (destinations) Then
  
    For Each k In destinations
      count = count + 1
      world.ColourNote "white", "blue", "  " & _
          CStr (count) & ": " & k & " (" & _
          ArrayGet ("", k) & ")"
    Next

   Else
     ColourNote "white", "blue", "No known destinations from here"
   End If

End Sub ' OnCheckpointlist 

Sub OnCheckpointgoto (name, line, wildcards)
Dim room, destinations, which

  room = trim (GetVariable ("room"))
  which = CInt (wildcards (1)) - 1 ' which choice, make zero-relative

'
'  get current entries into work array
'
   ArrayClear ""  ' get rid of previous stuff
   ArrayImport "", ArrayGet ("map", room), ","
  
   destinations = ArrayListKeys ("")

   If Not IsEmpty (destinations) Then
  
     If which < lbound (destinations) or _
        which > ubound (destinations) Then
       ColourNote "white", "red", "Destination " & wildcards (1) & _
           " out of range " & CStr (lbound (destinations) + 1) & " to " & _
           CStr (ubound (destinations) + 1)
       Exit Sub
     End If

'
'  go there :)
'
     Send EvaluateSpeedwalk (ArrayGet ("", destinations (which)))

   Else
     ColourNote "white", "blue", "No known destinations from here"
   End If

End Sub ' OnCheckpointgoto 

Sub OnGetRoomFromPrompt (name, line, wildcards)
dim lines, styles, text

  line = GetLinesInBufferCount
  styles = GetLineInfo (line, 11)

'
'  Should be 2 styles, the prompt and the room name
'
  If Styles <> 2 Then Exit Sub

'
'  Room name is bold
'
  If Not GetStyleInfo (line, 2, 8) Then Exit Sub

'
'  Room name is red text
'
  If Not GetStyleInfo (line, 2, 14) = BoldColour (2) Then Exit Sub

'
'  Room name is black background
'
  If Not GetStyleInfo (line, 2, 15) = NormalColour (1) Then Exit Sub

'
'  Get name
'

  SetVariable "room", GetStyleInfo (line, 2, 1)
  

End Sub ' OnGetRoomFromPrompt 


]]>
</script>


<!--  Plugin help  -->

<aliases>
  <alias
   script="OnHelp"
   match="Automap:help"
   enabled="y"
  >
  </alias>
</aliases>

<script>
<![CDATA[
Sub OnHelp (sName, sLine, wildcards)
  world.Note world.GetPluginInfo (world.GetPluginID, 3)
End Sub
]]>
</script> 

</muclient>



- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by Nick Gammon   Australia  (23,158 posts)  Bio   Forum Administrator
Date Reply #6 on Mon 22 Mar 2004 06:19 AM (UTC)
Message
In my example above, one of the walks was wrong:


2: Darkhaven Academy (3e 3s 4w 4s 7e s d )


If it makes a mistake (because you have taken the long way around), just go back to the start, type "cc" (checkpoint clear), take a shorter route, and then type "cp" (checkpoint) again at the destination.

It tries to not overwrite a short path with a longer one, for instance you might see this:


New path is: 4n 4e 4s w s d
Old path is: 3e s d
Retaining older, shorter, path.

New path is: {auto} u n e 4n 4w 4s
Old path is: {auto} u n 3w
Retaining older, shorter, path.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by Nick Gammon   Australia  (23,158 posts)  Bio   Forum Administrator
Date Reply #7 on Mon 22 Mar 2004 06:26 AM (UTC)
Message
Another thing that would be helpful would be to clear the current map sequence if you end back where you started, otherwise you can get a length map sequence, leading from A to A, whereas it should be empty.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by Belshazzar   (9 posts)  Bio
Date Reply #8 on Mon 22 Mar 2004 08:05 AM (UTC)
Message
I've been reading up on shortest path algorithms. If we represent each important location as a Node on a graph, the paths between these vertexes are the edges, and the length of these paths are weights. Weights could be adjusted for different terrain as well. Paths can be one way or reversible, so this graph is called a directed, weighted graph. The problem of finding the shortest path between two points on such a graph is called the "single source shortest path" problem and is solved by Djikstra's algorithm for non-negative weights. (I don't see how negative weights would apply to a MUD.) Djikstra is kind of complex to code since it requires a priority queue data structure to deal with the weights.
Top

Posted by Poromenos   Greece  (1,037 posts)  Bio
Date Reply #9 on Mon 22 Mar 2004 02:12 PM (UTC)
Message
If this does what i think i read it does, I'm impressed. I will go check it out right now.

Vidi, Vici, Veni.
http://porocrom.poromenos.org/ Read it!
Top

Posted by Nick Gammon   Australia  (23,158 posts)  Bio   Forum Administrator
Date Reply #10 on Mon 22 Mar 2004 08:09 PM (UTC)

Amended on Mon 22 Mar 2004 08:10 PM (UTC) by Nick Gammon

Message
A priority queue is actually easy to do in STL, so that isn't totally out of our reach.

Conceptually the whole thing is quite interesting.

For one thing, even if you are not at a "node" you are probably close by. The next step would be for it to automatically recognise nodes, and reset itself to "at node X".

Then as you walk away it knows how far you are from X. At that point, if you wanted to go to "The Darkhaven Inn" (2w 1s from Darkhaven Square), and you were 1 north of Darkhaven Square, then it could compute 1s (to return) and then add on the "2w 1s" to generate the complete speedwalk.

Similarly if you were already 1w of the Square it would generate "1e 2w 1s", and then by eliminating backtracking (reduce 1e 2w to 1w) it could reduce the steps.

I didn't use the MXP room names here, and in fact if a MUD supports MXP it makes it somewhat simpler because the room names are unambiguously sent as MXP tags. However I left that out to make a more general solution.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by Poromenos   Greece  (1,037 posts)  Bio
Date Reply #11 on Mon 22 Mar 2004 08:28 PM (UTC)
Message
I don't understand Rapscallion's speedwalking feature. How did you set these directions? Was it just a speedwalk list, or did it actually map the area and walk you in it?
Also, I have been reading on pathfinding algorithms (mostly A*) because I want to make a plugin that walks you wherever on its own, and i realised that those algorithms do not apply to MUDs. You can just have a recursive algorithm that traverses every path and returns the shortest one, and besides, those algorithms only work on grids, MUD areas can be connected however they want...

Vidi, Vici, Veni.
http://porocrom.poromenos.org/ Read it!
Top

Posted by Shadowfyr   USA  (1,791 posts)  Bio
Date Reply #12 on Mon 22 Mar 2004 08:51 PM (UTC)
Message
Not really Poromenos. A version of Dijkstra's Algorithm is used in the TradeWars companion that provided a client to the TradeWars 2002 game from back in the days of 486 machines. The universes in tradewars had as many as 10,000 'sectors' each with 1-6 exits, each exit completely random and some one way. The algorythm could generally find shortest path in 1-2 seconds on a 486, some paths being 20-30 links in length.

The biggest issue I have it that if you are going to do something so complicated, you may as well build an entire mapping system. With enough paths to search between, it becomes almost as complex to design the path search as it takes to design a mapper, that just happens to include such a path finder. lol
Top

Posted by Belshazzar   (9 posts)  Bio
Date Reply #13 on Mon 22 Mar 2004 10:23 PM (UTC)
Message
Poromenos, I will attempt to describe Rapscallion's speedwalking feature in more detail. You defined a number of "locations" in a location configuration panel. For instance, I had locations for Grey Havens, Bree, and Bywater. You then used an automapper very similar to MUSHClient's automapper to track your steps. When saving the speedwalk thusly generated, you also specified which two locations it was a path between, and if it were valid for all your characters or just one. There was also a mechanism for generating reverse paths if it was not a one-way kind of path. There was no full graphical grid-type mapper like the new zMUD mapper thing.

I had probably 50-100 important locations defined, some with only one connection, and some with as many as 5 or 6 connections.

Once your locations and connecting speedwalks were defined, there were combo boxes for selecting your current location and destination, and a Start button to begin the speedwalk. The nice thing was that you could select a location, say Minas Tirith, and a destination, say Bree, and it would construct one long speedwalk consisting of the shortest path to the destination. I don't know if they used Breadth First search, Djikstra, A*, or what. From what I understand, A* is more useful in a situation where you know the entire map and need to deal with different terrain movement costs.
Top

Posted by Poromenos   Greece  (1,037 posts)  Bio
Date Reply #14 on Mon 22 Mar 2004 11:19 PM (UTC)
Message
Ah, i see... Then again, it could just string the various dirs that matched together and select the shortest one. I don't think you can use pathfinding algorithms if you don't have the entire map (or at least many paths), and it's easier to count directions than parse them and run an algorithm... It's essentially the travelling salesman problem, so it probably uses an algorithm for that... I think that Nick's plugin went a long way to doing that, now the only thing left is to connect the checkpoints to each other... I'll take a look at it and try to improve it...

Vidi, Vici, Veni.
http://porocrom.poromenos.org/ Read it!
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.


94,480 views.

This is page 1, subject is 3 pages long: 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.