This forum is a read-only archive of the Gammon Software forum (2000–2026). No new posts can be made. Search the archive.

Shortest Path Speedwalking

Posted by Belshazzar on Sun 21 Mar 2004 10:54 PM — 37 posts, 124,742 views.

Belshazzar #0
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.

Meerclar USA #1
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.
Belshazzar #2
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.)
Nick Gammon Australia Forum Administrator #3
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. ;)
Belshazzar #4
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.
Nick Gammon Australia Forum Administrator #5
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>


Amended on Mon 22 Mar 2004 06:12 AM by Nick Gammon
Nick Gammon Australia Forum Administrator #6
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 Australia Forum Administrator #7
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.
Belshazzar #8
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.
Poromenos Greece #9
If this does what i think i read it does, I'm impressed. I will go check it out right now.
Nick Gammon Australia Forum Administrator #10
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.
Amended on Mon 22 Mar 2004 08:10 PM by Nick Gammon
Poromenos Greece #11
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...
Shadowfyr USA #12
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
Belshazzar #13
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.
Poromenos Greece #14
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...
Nick Gammon Australia Forum Administrator #15
Quote:

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.


In that case, I have gone a fair way down that track already. My plugin detects the room names, and generates the reverse path (you don't have to use it of course).

What it doesn't do at present is take you to the nearest node, although I think that bit would be pretty trivial, or to go multiple legs. One approach would be to simply always go back to a central spot - within reason - and then set out again for somewhere else. This might work OK in a smallish town.
Belshazzar #16
Poromenos,

Actually the traveling salesman problem is orders of magnitude more difficult. It is what is called an "NP-Complete" problem. (http://www.pcug.org.au/~dakin/tsp.htm) which means nobody has figured out a good algorithm to solve it for large values of n.

This problem, by comparison, is a single-source shortest path problem which can easily be solved in a finite amount of time for large numbers of nodes using serveral well known algorithms.
Nick Gammon Australia Forum Administrator #17
I am having fairly good results by playing with a bit of recursion.

What I am doing so far is looking at the paths from A to B, and then for each B looking for all paths *from* B (eg. to C) and so on, until we run out of paths. So far this has been fairly quick, although I suspect it will get out of hand soon enough.

The debugging displays show the process in action ...


Darkhaven Square
You are standing within the expanse of the famous Darkhaven Square.  
A stone statue of occupies the square's center, surrounded by gardens of shrubbery 
which enhance the air of serenity and peace here in the center of the city.  
The main road lead away in the cardinal directions, 
while to the northeast and northwest are forested paths.  
The spires of a cathedral can be seen rising to the northwest.  
Exits: north east south west up northeast northwest.

<33/33 hp 100/100 m 110/110 mv>
Current room believed to be [Darkhaven Square]
finding destinations from Darkhaven Square prefix 
considering Darkhaven Academy path {auto} 3e s d
existing = 
** addding destination Darkhaven Academy path = {auto} 3e s d
recursing to find walks from Darkhaven Academy with prefix {auto} 3e s d
  finding destinations from Darkhaven Academy prefix {auto} 3e s d
  considering Entrance to the Academy path {auto} u
  existing = 
  ** addding destination Entrance to the Academy path = {auto} 3e s d{auto} u
  recursing to find walks from Entrance to the Academy with prefix {auto} 3e s d{auto} u
    finding destinations from Entrance to the Academy prefix {auto} 3e s d{auto} u
    considering Darkhaven Academy path d 
    existing = {auto} 3e s d
considering Entrance to the Academy path 3e s 
existing = {auto} 3e s d{auto} u
considering The Darkhaven Inn path 2w s 
existing = 
** addding destination The Darkhaven Inn path = 2w s 
recursing to find walks from The Darkhaven Inn with prefix 2w s 
  finding destinations from The Darkhaven Inn prefix 2w s 
  considering The Tavern path n w s 
  existing = 
  ** addding destination The Tavern path = 2w s n w s 
  recursing to find walks from The Tavern with prefix 2w s n w s 
    finding destinations from The Tavern prefix 2w s n w s 
    considering The Darkhaven Inn path {auto} n e s
    existing = 2w s 
considering The Tavern path {auto} 3w s
existing = 2w s n w s 

  1: Darkhaven Academy ({auto} 3e s d)
  2: Entrance to the Academy ({auto} 3e s d{auto} u)
  3: The Darkhaven Inn (2w s )
  4: The Tavern (2w s n w s )


Result at the end in bold.

The interesting ones here are "Entrance to the Academy" where it went down into the Academy and up again, and "The Tavern" where it went into the Inn and out again.

Now with some removal of redundant paths (eg. merging The Tavern so that it becomes 3w s) it might give fairly good results.
Amended on Tue 23 Mar 2004 04:30 AM by Nick Gammon
Nick Gammon Australia Forum Administrator #18
OK now, this is all working pretty well. :)

I put in the code to remove backtracks from the generated path, and now get results like this:


Current room believed to be [The Tavern]
  1: Darkhaven Academy (n 6e s (down) )
  2: Darkhaven Square (n 3e )
  3: Entrance to the Academy (n 6e s )
  4: The Academy Healer (n 6e s (down) 6n )
  5: The Darkhaven Inn (n e s )


So I type cg 5 (go to Inn) and when I get there:


Current room believed to be [The Darkhaven Inn]
  1: Darkhaven Academy (n 5e s (down) )
  2: Darkhaven Square (n 2e )
  3: Entrance to the Academy (n 5e s )
  4: The Academy Healer (n 5e s (down) 6n )
  5: The Tavern (n w s )


Let's go to the Academy Healer (cg 4) and see what we see ...


Current room believed to be [The Academy Healer]
  1: Darkhaven Academy (6s )
  2: Darkhaven Square (6s (up) n 3w )
  3: Entrance to the Academy (6s (up) )
  4: The Darkhaven Inn (6s (up) n 5w s )
  5: The Tavern (6s (up) n 6w s )


Yes, it all seems pretty symmetric.
Nick Gammon Australia Forum Administrator #19
I have now added one more node (from '[Entrance to the Academy] to [The Young Adventurer's Necessities]') - a single walk east, and now when I go back to the Tavern, it factors it in (as three legs: 1) go to Darkhaven Square, 2) go to the Entrance to the Academy. 3) go to The Young Adventurer's Necessities).


Current room believed to be [The Tavern]
  1: Darkhaven Academy (n 6e s (down) )
  2: Darkhaven Square (n 3e )
  3: Entrance to the Academy (n 6e s )
  4: The Academy Healer (n 6e s (down) 6n )
  5: The Darkhaven Inn (n e s )
  6: The Young Adventurer's Necessities (n 6e s e )


This is pretty cool stuff. And fast, I don't notice any time taken to evaluate it.
Amended on Tue 23 Mar 2004 04:30 AM by Nick Gammon
Nick Gammon Australia Forum Administrator #20
For anyone that wants to play with it, the plugin is currently this:


<?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.47"
   version="1.1"
   >
<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
  ArrayCreate "dest"  ' destinations array

'
' turn auto-mapping on
'  

  EnableMapping vbTrue  

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 

'----------------------------------------------------------
'  Make a checkpoint (node)
'----------------------------------------------------------
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
'
  OnClearcheckpoint "", "", ""

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

End Sub  ' OnCheckpoint 

'----------------------------------------------------------
' Clear a checkpoint
'----------------------------------------------------------
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 

'----------------------------------------------------------
'  Remove backtracks from a speedwalk
'----------------------------------------------------------
Function RemoveBacktracks (path)
dim topkey, topitem, w, k, result, count, prev

  RemoveBacktracks = ""
  ArrayCreate "q"
  ArrayCreate "walk"
  ArrayClear "q"
  ArrayClear "walk"

  w = Split (EvaluateSpeedwalk (path), vbCrLf)

  If IsEmpty (w) Then Exit Function

    for each k in w   

    if ArraySize ("q") > 0 then
 
'
'  what is currently at top of queue? (actually a stack)
'
      topkey = CInt (ArrayGetLastKey ("q"))
      topitem = ArrayGet ("q", topkey)

'
'  If we are about to add inverse direction, just discard both
'
      if (topitem = "n" and k = "s") _
      or (topitem = "s" and k = "n") _
      or (topitem = "e" and k = "w") _
      or (topitem = "w" and k = "e") _
      or (topitem = "ne" and k = "sw") _
      or (topitem = "sw" and k = "ne") _
      or (topitem = "nw" and k = "se") _
      or (topitem = "se" and k = "nw") _
      or (topitem = "up" and k = "down") _
      or (topitem = "down" and k = "up") Then
         ArrayDeleteKey "q", topkey
      Else
         ArraySet "q", topkey + 1, k
      End If

    Else
'
'  Nothing in queue - just add it
'
        ArraySet "q", 1, k
    end if  ' anything in queue

  next

'
'  now we have the cleaned up walk in the queue, pull it out again
'   and turn back into a speedwalk string
'
  w = ArrayListValues ("q")

  If IsEmpty (w) Then Exit Function

  result = ""
  prev = ""

  for each k in w

    k = trim (k)
    
    if k <> "" then
   
'
'  multiple length movements must be put in brackets, if not already 
'   (eg. up, down, ne, nw)
'
      if len (k) > 1 and InStr (k, "(") = 0 then
        k = "(" & k & ")"
      end if

      if k = prev Then
        count = count + 1
      else
        if prev <> "" then
          if count > 1 then
            result = result & CStr (count) & prev & " "
          else
            result = result & prev & " "
          end if ' more than 1
        end if  ' having a previous one
        prev = k
        count = 1
      end if   ' change in k
    end if ' not blank k
  next  ' processing each one

'
'  do final one
'

  if prev <> "" then
    if count > 1 then
      result = result & CStr (count) & prev & " "
    else
      result = result & prev & " "
    end if ' more than 1
  end if  ' having a previous one

  RemoveBacktracks = result

End Function  ' RemoveBacktracks 

'----------------------------------------------------------
'   Add destinations to "dest" array from location "from"
'----------------------------------------------------------
Sub GetDestinations (orig, from, speedwalk, indent, level)
dim d, k, existing, path

'debug   Note indent & "finding destinations from " & from & " prefix " & speedwalk

   ArrayCreate level
   ArrayClear level  ' get rid of previous stuff
   ArrayImport level, ArrayGet ("map", from), ","

'
'  check each one
'
   d = ArrayListKeys (level)

   If IsEmpty (d) Then Exit Sub
  
   For Each k In d

   if k <> orig then

     path = ArrayGet (level, k)
     existing = ArrayGet ("dest", k)

'debug     Note indent & "considering " & k & " path " & path
'debug     Note indent & "existing = " & existing

     If existing = "" Then

       ArraySet "dest", k, speedwalk & path
'debug       Note indent & "** addding destination " & k & " path = " & speedwalk & path

'
'  recurse to get destinations from *this* destination
'
   
       If k <> from Then
'debug         Note indent & "recursing to find walks from " & k & " with prefix " & speedwalk & path
         GetDestinations orig, k, speedwalk & path, indent & "  ", level + 1
       End If 
     End If	' not already having a path there

   End If  ' not going to where we started

   Next	' end of doing each destination

End Sub ' GetDestinations 

'----------------------------------------------------------
'  List available checkpoints
'----------------------------------------------------------
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 "dest"
   GetDestinations room, room, "", "", 1
  
   destinations = ArrayListKeys ("dest")

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

    Next

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

End Sub ' OnCheckpointlist 

'----------------------------------------------------------
' go to a checkpoint
'----------------------------------------------------------
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 "dest"
   GetDestinations room, room, "", "", 1
  
   destinations = ArrayListKeys ("dest")

   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 (RemoveBacktracks (ArrayGet ("dest", destinations (which))))

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

End Sub ' OnCheckpointgoto 

'----------------------------------------------------------
' deduce room name if on same line as prompt
'----------------------------------------------------------
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 Australia Forum Administrator #21
Cute though this algorithm is, it doesn't actually find the shortest path, it finds *a* path, especially if multiple nodes are involved. It really needs modifying (probably only a couple of lines) to make it choose the shorter of two alternatives when comparing paths, at present it just takes the first.
Nick Gammon Australia Forum Administrator #22
A bit more exploring, and I can't really fault the path generation (apart from not really testing to find the shortest). Now I have this lot:


Current room believed to be [The Young Adventurer's Necessities]
  1: Darkhaven Academy (w (down) )
  2: Darkhaven Square (w n 3w )
  3: Entrance to the Academy (w )
  4: Outside the Tower of Sorcery (w n w s )
  5: Quills and Parchments (w n 3w 2s w s )
  6: The Academy Healer (w (down) 6n )
  7: The Alchemist's (w n 3w 2s 2w n )
  8: The Darkhaven Courier (w n 3w 2s 2w s )
  9: The Darkhaven Inn (w n 5w s )
  10: The Scribe's Tent (w n 3w 2s 3w n )
  11: The Shining Emerald (w n 3w 2s 3w s )
  12: The Tavern (w n 6w s )
  13: The Wizard's Tent (w n 3w 2s w n )


I have added another alias "ci" (checkpoint info) so we can see what is generating all this stuff. So far it is:


Darkhaven Academy
  Darkhaven Square = u n 3w 
  Entrance to the Academy = {auto} u
  The Academy Healer = 6n 
Darkhaven Square
  Darkhaven Academy = {auto} 3e s d
  Entrance to the Academy = 3e s 
  Outside the Tower of Sorcery = 2e s 
  Quills and Parchments = 2s w s 
  The Alchemist's = 2s 2w n 
  The Darkhaven Inn = 2w s 
  The Tavern = {auto} 3w s
  The Wizard's Tent = 2s w n 
Entrance to the Academy
  Darkhaven Academy = d 
  Darkhaven Square = {auto} n 3w
  The Young Adventurer's Necessities = e 
Outside the Tower of Sorcery
  Darkhaven Square = {auto} n 2w
Quills and Parchments
  Darkhaven Square = {auto} n e 2n
The Academy Healer
  Darkhaven Academy = {auto} 6s
The Alchemist's
  Darkhaven Square = {auto} s 2e 2n
  The Darkhaven Courier = 2s 
The Darkhaven Courier
  The Alchemist's = {auto} 2n
  The Shining Emerald = n w s 
The Darkhaven Inn
  Darkhaven Square = {auto} n 2e
  The Tavern = n w s 
The Scribe's Tent
  The Shining Emerald = {auto} 2s
The Shining Emerald
  The Darkhaven Courier = {auto} n e s
  The Scribe's Tent = 2n 
The Tavern
  Darkhaven Square = n 3e 
  The Darkhaven Inn = {auto} n e s
The Wizard's Tent
  Darkhaven Square = {auto} s e 2n
The Young Adventurer's Necessities
  Entrance to the Academy = {auto} w


The outdented lines are the nodes, the indented ones the nodes you can get to directly from them, and the path to do so.
Amended on Tue 23 Mar 2004 04:13 AM by Nick Gammon
Belshazzar #23
I installed the Automap plugin, and after some tweaking to recognize Two Towers (towers.angband.com) style room names, it seems to work for rooms with unique names. It has trouble dealing with multiple checkpointed rooms named the same thing. Probably because A. they have the same hash key and B. it's hard to tell them apart programmatically anyway.

Was there a feature to add a Special move to a speedwalk by typing in #(Action/Reverse)? It does not work for me anymore. (Whether or not I have the Automap plugin loaded)


The following regexp worked to match t2t room names which are all something like:
The front room of the Half-Mast House(stairs and out)
or
Inside the river gate of the city(s, sw, guardhouse, ne, e, out and nw)

match="^([^ ].*)\(.*\)$"
Nick Gammon Australia Forum Administrator #24
They are not hashed, it literally stores the room name.

Yes, I can't see how it can tell two different rooms that happen to have the same name, unless you changed it to save a name you supply (eg. you might make it take your supplied name rather than the derived name).

I didn't test unusual speedwalks, the technique you mentioned is not supported. Try going into the Mapper dialog and adding a special direction.

This is all still pretty preliminary, however it is gratifying to see it works as well as it does.

If you used it for a while I think the number of possible destinations would rise quite quickly, so probably the "cl" alias would need to be altered to take an argument, eg. "cl shop".
Nick Gammon Australia Forum Administrator #25
I haven't had much comment on this so far, but it is working pretty well as far as I am concerned. The only problem I see is that it will soon need pruning because the number of destinations will keep rising.

After wandering around Darkhaven for a while, and then going back to the main square, this is what I get:


cl
Current room believed to be [Darkhaven Square]
  1: A Corridor in the Abandoned Mansion (4s 3w n)
  2: Abbigayle's Language Lessons (3e s (down) n w)
  3: Annir's Clothing (4s 2w n)
  4: Armory (2s 2e s)
  5: Darkhaven Academy (3e s (down))
  6: Entrance to the Academy (3e s)
  7: Entrance to the Darkhaven Art Gallery (4s w n)
  8: Intersection of Horizon Road and Falcon Road (4w)
  9: Intersection of Vertic Avenue and Law Avenue (4s)
  10: Intersection of Vertic Avenue and Market Street (2s)
  11: Outside the Tower of Sorcery (2e s)
  12: Quills and Parchments (2s w s)
  13: The Academy Healer (3e s (down) 6n)
  14: The Alchemist's (2s 2w n)
  15: The Blacksmith's Tent (2s e s)
  16: The Butcher's Shop (2s e n)
  17: The Dairy Tent (2s 3e n)
  18: The Darkhaven Bakery (2s 2e n)
  19: The Darkhaven Courier (2s 2w s)
  20: The Darkhaven Inn (2w s)
  21: The Guild of Thieves (3s 2w n)
  22: The Laboratory of Skills and Spells (3e s (down) n e)
  23: The Scribe's Tent (2s 3w n)
  24: The Shining Emerald (2s 3w s)
  25: The Tavern (3w s)
  26: The Wizard's Tent (2s w n)
  27: The Young Adventurer's Necessities (3e s e)
  28: Weaponry Shop (2s 3e s)


You can now filter the places listed by adding a wildcard string (eg. square, shop, tent), like this:


cl tent
Current room believed to be [Darkhaven Square]
  1: The Blacksmith's Tent (2s e s)
  2: The Dairy Tent (2s 3e n)
  3: The Scribe's Tent (2s 3w n)
  4: The Wizard's Tent (2s w n)


You can analyse the raw data collected by checkpointing the various rooms, by typing "ci" (checkpoint info) ...


ci
N1. A Corridor in the Abandoned Mansion
  P1. Annir's Clothing = s e n 
  P2. The Guild of Thieves = {auto} s w n 2e n
N2. Abbigayle's Language Lessons
  P3. Darkhaven Academy = {auto} e s
  P4. The Laboratory of Skills and Spells = 2e 
N3. Annir's Clothing
  P5. A Corridor in the Abandoned Mansion = {auto} s w n
  P6. Entrance to the Darkhaven Art Gallery = s e n 
N4. Armory
  P7. The Dairy Tent = n e n 
  P8. The Darkhaven Bakery = {auto} 2n
N5. Darkhaven Academy
  P9. Abbigayle's Language Lessons = n w 
  P10. Entrance to the Academy = {auto} u
N6. Darkhaven Square
  P11. Entrance to the Academy = 3e s 
  P12. Intersection of Vertic Avenue and Market Street = {auto} 2s
  P13. Outside the Tower of Sorcery = 2e s 
  P14. The Darkhaven Inn = 2w s 
N7. Entrance to the Academy
  P15. Darkhaven Academy = d 
  P16. Darkhaven Square = {auto} n 3w
  P17. The Young Adventurer's Necessities = e 
N8. Entrance to the Darkhaven Art Gallery
  P18. Annir's Clothing = {auto} s w n
  P19. Intersection of Vertic Avenue and Law Avenue = s e 
N9. Intersection of Horizon Road and Falcon Road
  P20. The Scribe's Tent = 2s e n 
  P21. The Tavern = {auto} e s
N10. Intersection of Vertic Avenue and Law Avenue
  P22. Entrance to the Darkhaven Art Gallery = {auto} w n
  P23. Intersection of Vertic Avenue and Market Street = 2n 
N11. Intersection of Vertic Avenue and Market Street
  P24. Darkhaven Square = 2n 
  P25. Intersection of Vertic Avenue and Law Avenue = {auto} 2s
  P26. Quills and Parchments = {auto} w s
  P27. The Blacksmith's Tent = e s 
  P28. The Guild of Thieves = s 2w n 
N12. Outside the Tower of Sorcery
  P29. Darkhaven Square = {auto} n 2w
N13. Quills and Parchments
  P30. Intersection of Vertic Avenue and Market Street = n e 
  P31. The Wizard's Tent = {auto} 2n
N14. The Academy Healer
  P32. The Laboratory of Skills and Spells = {auto} 5s e
N15. The Alchemist's
  P33. The Darkhaven Courier = 2s 
  P34. The Shining Emerald = {auto} s w s
N16. The Blacksmith's Tent
  P35. Intersection of Vertic Avenue and Market Street = {auto} n w
  P36. The Butcher's Shop = 2n 
N17. The Butcher's Shop
  P37. The Blacksmith's Tent = {auto} 2s
  P38. The Darkhaven Bakery = s e n 
N18. The Dairy Tent
  P39. Armory = {auto} s w s
  P40. Weaponry Shop = 2s 
N19. The Darkhaven Bakery
  P41. Armory = 2s 
  P42. The Butcher's Shop = {auto} s w n
N20. The Darkhaven Courier
  P43. The Alchemist's = {auto} 2n
  P44. The Wizard's Tent = n e n 
N21. The Darkhaven Inn
  P45. Darkhaven Square = {auto} n 2e
  P46. The Tavern = n w s 
N22. The Guild of Thieves
  P47. A Corridor in the Abandoned Mansion = s 2w s e n 
  P48. Intersection of Vertic Avenue and Market Street = {auto} s 2e n
N23. The Laboratory of Skills and Spells
  P49. Abbigayle's Language Lessons = {auto} 2w
  P50. The Academy Healer = w 5n 
N24. The Scribe's Tent
  P51. Intersection of Horizon Road and Falcon Road = {auto} s w 2n
  P52. The Shining Emerald = 2s 
N25. The Shining Emerald
  P53. The Alchemist's = n e n 
  P54. The Scribe's Tent = {auto} 2n
N26. The Tavern
  P55. Intersection of Horizon Road and Falcon Road = n w 
  P56. The Darkhaven Inn = {auto} n e s
N27. The Wizard's Tent
  P57. Quills and Parchments = 2s 
  P58. The Darkhaven Courier = {auto} s w s
N28. The Young Adventurer's Necessities
  P59. Entrance to the Academy = {auto} w
N29. Weaponry Shop
  P60. The Dairy Tent = {auto} 2n


The identifying codes at the front are for making deletions. For instance, if you find that a path is incorrect, you can delete it:


cdel p60
Path from [Weaponry Shop] to [The Dairy Tent] deleted.


This might happen because you had to flee combat, or were transported there somehow other than normal walking.
Nick Gammon Australia Forum Administrator #26
The interesting thing about the database listing is that from (say) the Scribe's tent we only know of 2 (direct) destinations:


...
N24. The Scribe's Tent
  P51. Intersection of Horizon Road and Falcon Road = {auto} s w 2n
  P52. The Shining Emerald = 2s 
...


However by typing "cl tent" when we are there it deduces all the others:


cl tent
Current room believed to be [The Scribe's Tent]
  1: The Blacksmith's Tent (s 4e s)
  2: The Dairy Tent (s 6e n)
  3: The Wizard's Tent (s 2e n)

Amended on Wed 24 Mar 2004 12:51 AM by Nick Gammon
Nick Gammon Australia Forum Administrator #27
Quote:

Was there a feature to add a Special move to a speedwalk by typing in #(Action/Reverse)? It does not work for me anymore.


See Game menu -> Do Mapper Special (Ctrl+Alt+D).
Poromenos Greece #28
The plugin works fine for me too, although the mapper gets confused when i recall... Maybe I should change it so that it will store the current room, and when I type a destination it will move to it if the current room is a known one it will walk to the destination, or prompt me to walk to a known room...
Nick Gammon Australia Forum Administrator #29
Yes, it would get confused by things like recall which move you in a non-standard way.

In fact, while mapping I would avoid:

  • Using 'recall' or movement spells
  • Fleeing combat
  • Auto-following another player
  • Moving quickly (as the "You can't move that way" message can be associated with the wrong direction command)
  • Being transported by another player (eg. an admin) from one place to another


However if any of those things *do* happen just type "cc" (checkpoint clear) to reset the mapping from the current room.

Also be cautious with one-way moves (eg. doors that need opening, one-way portals etc.).

The latest version of the "shortest path" plugin, which I will upload later today, has some extra features:

  • It auto-resets the mapper when you enter a known room (this is to stop tortuous paths being stored when you are really only a couple of moves from a known node)
  • You can add a one-way move ("cp nr" - checkpoint no-reverse) - this stops it generating the reverse path
  • You can delete wrongly-entered moves, so you can tidy up the moves database.
  • You can type "cn" (checkpoint node) which will take you to the most recently-visited known node. It does this by simply taking the mapping direction from the last node and reversing it.
  • You can filter when doing a "cl" (checkpoint list) - eg. "cl shop" - this restricts the displays to lines with that word in them
  • You can manually define a room (eg. "cr Hotel") - this can be useful if you are in an area with lots of rooms with the same name.


I just want to add a final feature - to save/load areas so that you can keep the nodes database down to a manageable size when visiting different areas.
Rojan QDel USA #30
I'm wondering if the newest version of this has been posted? And if not, could it be? I'm also wondering how we could automatically get the room name when it's not a specific color scheme...
Nick Gammon Australia Forum Administrator #31
So far the code has been largely experimental. It works, and nicely too, if you know where the rooms are, and where you are.

However deducing the room name especially if there are no particular colour codes is the tricky bit. Plus, as mentioned earlier, if multiple rooms happen to have the same name.
Rojan QDel USA #32
Could you post the most recent version you have of the plugin so I could experiment with it? Thanks :)
Nick Gammon Australia Forum Administrator #33
I don't have a plugin personally. The code I posted earlier on in this thread is my latest attempts to solve the shortest path analysis, assuming you already have all the room data in memory. I did it, as decribed there, by pulling in the room data from the "rlist" command as a MUD administrator.
Nick Gammon Australia Forum Administrator #34
Whoops! I thought this was another thread:

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

My latest plugin (which I forgot I had) is posted earlier in this thread.

The other thread mentioned above gives a different way of solving the shortest-path problem. Now if you could combine them, you might have a pretty good solution. :)
Nick Gammon Australia Forum Administrator #35
Unfortunately my plugin (in this thread) is in VBscript, and the shortest path algorithm (in the other thread) is in Lua, but you will be able to take the general ideas and do something with them.
Nick Gammon Australia Forum Administrator #36
Well, this is the version I have on disk, it looks more extensive than the earlier post. I can't say if I know whether it works, I forgot I had it ...


<?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.47"
   version="1.2"
   >
<description trim="y">
<![CDATA[
cp [nr] - add a checkpoint - optional "nr" argument specifies "no return"
cl - list checkpoints from this location
cl x - lists checkpoints, filtered by x (eg. cl tavern)
cg x  - go to checkpoint x (eg. cg 5)
cc - clear current speedwalk - start new checkpoint
cr x - manually define room name (eg. cr Outside East Gate)
ci - checkpoint info - lists all known paths in the database
cdel x - checkpoint delete - deletes a path or node identified in the "ci" list
cdel all - deletes all map info
cn - go to last node (ie. one we just left)
csave - save the database, in case of a crash

chelp - this description


]]>
</description>

</plugin>


<!--  Get our standard constants -->

<include name="constants.vbs"/>

<!--  Triggers  -->

<!-- red = 9, green = 10 -->

<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"
   sequence="100"
   text_colour="10"
   script="OnRoomFromFirstStyle"
  >
  </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\.|The sun slowly disappears in the west\.|The sun's radiance dims as it sinks in the sky\.|The sky turns a reddish orange as the sun ends its journey\.|You are carrying\:)$"
   match_back_colour="y"
   match_bold="y"
   match_inverse="y"
   match_italic="y"
   match_text_colour="y"
   regexp="y"
   sequence="90"
   text_colour="9"
  >
  </trigger>
</triggers>

<!--  Aliases  -->

<aliases>
  <alias
   script="OnClearcheckpoint"
   match="cc"
   echo_alias="y"
   enabled="y"
   sequence="100"
  >
  </alias>
  <alias
   script="OnCheckpointlist"
   match="^cl( .*)?$"
   echo_alias="y"
   enabled="y"
   regexp="y"
   sequence="100"
  >
  </alias>
  <alias
   script="OnCheckpointinfo"
   match="ci"
   echo_alias="y"
   enabled="y"
   sequence="100"
  >
  </alias>
  <alias
   match="csave"
   enabled="y"
   send_to="12"
   sequence="100"
  >
  <send>SaveState
ColourNote &quot;white&quot;, &quot;green&quot;, &quot;Database saved&quot;</send>
  </alias>
  <alias
   script="OnCheckpointGotoNode"
   match="cn"
   echo_alias="y"
   enabled="y"
   sequence="100"
  >
  </alias>
  <alias
   script="OnCheckpointDelete"
   match="cdel *"
   echo_alias="y"
   enabled="y"
   sequence="100"
  >
  </alias>
  <alias
   script="OnCheckpoint"
   match="^cp( nr)?$"
   echo_alias="y"
   enabled="y"
   regexp="y"
   sequence="100"
  >
  </alias>
 <alias
   script="OnCheckpointRoom"
   match="cr *"
   echo_alias="y"
   enabled="y"
   sequence="100"
  >
  </alias>
  <alias
   script="OnCheckpointgoto"
   match="cg *"
   echo_alias="y"
   enabled="y"
   sequence="100"
  >
  </alias>
</aliases>

<!--  Script  -->


<script>
<![CDATA[
'----------------------------------------------------------
'  Load mapping array
'----------------------------------------------------------
Sub OnPluginInstall

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

  ArrayCreate ""  ' work array
  ArrayCreate "dest"  ' destinations array
  ArrayCreate "cl"  ' current listed destinations array
  ArrayCreate "cin"  ' ci - nodes
  ArrayCreate "cip"  ' ci - paths

  SetVariable "known_room", ""
  SetVariable "known_checkpoint", ""
  SetVariable "known_mapstring", ""
 
  SetVariable "clroom", ""

'
' turn auto-mapping on
'  

  EnableMapping vbTrue  

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 (RemoveBacktracks (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 = RemoveBacktracks (ArrayGet ("", to_location))

  If currspeedwalk <> "" Then
    currpath = EvaluateSpeedwalk (currspeedwalk)
    If Len (newpath) > Len (currpath) Then
      ColourNote "white", "red", "New path is: " & RemoveBacktracks (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 

'----------------------------------------------------------
'  Make a checkpoint (node)
'----------------------------------------------------------
Sub OnCheckpoint (name, line, wildcards)
Dim room, checkpoint, mapstring


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

'
'  if they stumbled across a known node, the "room change" routine
'   clears the map info, however we needed that to checkpoint the room
'
if room = GetVariable ("known_room") Then
  checkpoint = trim (GetVariable ("known_checkpoint"))
  mapstring = GetVariable ("known_mapstring")
Else
  checkpoint = trim (GetVariable ("checkpoint"))
  mapstring = GetMappingString 
End If

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

    AddPath checkpoint, room, mapstring

'
'  now add reverse path - if wanted
'

    If trim (wildcards (1)) <> "nr" Then
      AddPath room, checkpoint, "{auto}" & ReverseSpeedwalk (mapstring)
    End If

  End If  ' already have a checkpoint
'
'  note new checkpoint
'
  OnClearcheckpoint "", "", ""

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

End Sub  ' OnCheckpoint 

'----------------------------------------------------------
' Clear a checkpoint
'----------------------------------------------------------
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 


'----------------------------------------------------------
'   Add destinations to "dest" array from location "from"
'----------------------------------------------------------
Sub GetDestinations (orig, from, speedwalk, indent, level)
dim d, k, existing, path

'debug Note indent & "finding destinations from " & from & " prefix " & speedwalk

   ArrayCreate level
   ArrayClear level  ' get rid of previous stuff
   ArrayImport level, ArrayGet ("map", from), ","

'
'  check each one
'
   d = ArrayListKeys (level)

   If IsEmpty (d) Then Exit Sub
  
   For Each k In d

   if k <> orig then

     path = ArrayGet (level, k)
     existing = ArrayGet ("dest", k)

'debug      Note indent & "considering " & k & " path " & path
'debug      Note indent & "existing = " & existing

     If (len (EvaluateSpeedWalk (RemoveBacktracks (existing))) > _
         len (EvaluateSpeedWalk (RemoveBacktracks (speedwalk & path)))) Or _
        (existing = "") Then

       ArraySet "dest", k, speedwalk & path
'debug       Note indent & "** addding destination " & k & " path = " & speedwalk & path

'
'  recurse to get destinations from *this* destination
'
   
       If k <> from Then
'debug         Note indent & "recursing to find walks from " & k & " with prefix " & speedwalk & path
         GetDestinations orig, k, speedwalk & path, indent & "  ", level + 1
       End If 
     End If	' not already having a path there

   End If  ' not going to where we started

   Next	' end of doing each destination

End Sub ' GetDestinations 

'----------------------------------------------------------
' cl -  List available checkpoints
'
' You can specify a filter, eg. cl tavern  
'----------------------------------------------------------
Sub OnCheckpointlist (name, line, wildcards)
Dim room, destinations, count, k, path, filter

  filter = trim (Lcase (wildcards (1)))
  room = trim (GetVariable ("room"))
  SetVariable "clroom", room  ' note what room we were in
  count = 0

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

'
'  get current entries into work array
'
   ArrayClear "dest"
   GetDestinations room, room, "", "", 1
   ArrayClear "cl"

   destinations = ArrayListKeys ("dest")

   If Not IsEmpty (destinations) Then
  
    For Each k In destinations
      If (filter = "") or (instr (lcase (k), filter) <> 0) Then
        count = count + 1
        path = RemoveBacktracks (ArrayGet ("dest", k))
        world.ColourNote "white", "blue", "  " & _
            CStr (count) & ": " & k & " (" & path & ")"
        ArraySet "cl", count, path
      End If
    Next

    if (count = 0) and (filter <> "") then
      ColourNote "white", "blue", "No destinations matching filter: " & filter
    end if

   Else
     ColourNote "white", "blue", "No known destinations from here"
     If GetVariable ("checkpoint") <> "" And _
        trim (GetMappingString) <> "" Then
       ColourNote "white", "blue", "You were last at [" & _
           GetVariable ("checkpoint") & "] (" & _
           trim (ReverseSpeedwalk (GetMappingString)) & ")"
       ColourNote "white", "blue", "Type 'cn' to go there"
     End If
   End If

End Sub ' OnCheckpointlist 

'----------------------------------------------------------
' go to a checkpoint
'----------------------------------------------------------
Sub OnCheckpointgoto (name, line, wildcards)
Dim room, destinations, which

  if ArraySize ("cl") = 0 then
    ColourNote "white", "red", "You have not done a 'cl' or there were no rooms listed"
    Exit Sub
  end if
    
  room = trim (GetVariable ("room"))

  if room <> GetVariable ("clroom") then
    ColourNote "white", "red", "You have changed rooms since doing a 'cl'"
    ColourNote "white", "red", "You were in    [" & GetVariable ("clroom") & "]"
    ColourNote "white", "red", "You are now in [" & room & "]"
    Exit Sub
  end if

  which = CInt (wildcards (1)) ' which choice

  if not ArrayKeyExists ("cl", which) then
    ColourNote "white", "red", "Destination " & which & _
       " was not on the list"
    exit sub
  end if

'
'  go there :)
'

  Send EvaluateSpeedwalk (RemoveBacktracks (ArrayGet ("cl", which)))

End Sub ' OnCheckpointgoto 


'----------------------------------------------------------
'  Show node info
'----------------------------------------------------------
Sub OnCheckpointinfo (name, line, wildcards)
Dim nodes, k, dests, j, nodenum, destnum
  
   nodenum = 0
   destnum = 0
   ArrayClear "cin"  ' ci - nodes
   ArrayClear "cip"  ' ci - paths

   nodes = ArrayListKeys ("map")

   If IsEmpty (nodes) Then
    ColourNote "white", "blue", "No mapping points known."
   Else
  
    For Each k In nodes
     
      nodenum = nodenum + 1
      ArraySet "cin", "N" & nodenum, k

      ColourNote "white", "darkgreen", "N" & Cstr (nodenum) & ". " & k

'
'  Get destinations from this node
'
      ArrayClear "dest"
      ArrayImport "dest", ArrayGet ("map", k), ","

      dests = ArrayListKeys ("dest")
 
      If Not IsEmpty (dests) Then

      For Each j in dests
      
        destnum = destnum + 1
        ArrayClear ""
        ArraySet "", "node", k
        ArraySet "", "dest", j

        '  save both node and path here
        ArraySet "cip", "P" & destnum, ArrayExport ("", ",")

        ColourNote "limegreen", "black", "  P" & _
                   CStr (destnum) & ". " & _
                   j & " = " & ArrayGet ("dest", j)

      Next ' dest
      End If

    Next  ' next node

   End If

End Sub ' OnCheckpointinfo

'----------------------------------------------------------
' delete a checkpoint node or path
'----------------------------------------------------------
Sub OnCheckpointDelete (name, line, wildcards)
dim which, k, node, nodes

  which = UCase (trim (wildcards (1)))

  if which = "ALL" then
    ArrayClear "map"
    ArrayClear "cin"
    ArrayClear "cip"
    ArrayClear "cl"
    ColourNote "white", "red", "ALL mapping points deleted."
    OnClearcheckpoint "", "", ""
    SetVariable "known_room", ""
    SetVariable "known_checkpoint", ""
    SetVariable "known_mapstring", ""
    Exit Sub
  end if

  If left (which, 1) = "N" Then  ' delete node
    
    If not ArrayKeyExists ("cin", which) Then
       ColourNote "white", "red", "Node number " & which & " does not exist"
       Exit Sub
    End If

    node = ArrayGet ("cin", which)

    if not ArrayKeyExists ("map", node) Then
       ColourNote "white", "red", "Map checkpoint [" & node & "] does not exist"
       Exit Sub
    End If

    ArrayDeleteKey "map", node

    ColourNote "white", "blue", "Map checkpoint [" & node & "] deleted."

    nodes = ArrayListKeys ("map")

    If Not IsEmpty (nodes) Then
  
      For Each k In nodes
     
'
'  Get destinations from this node
'
        ArrayClear ""
        ArrayImport "", ArrayGet ("map", k), ","

        If ArrayKeyExists ("", node) Then
          ArrayDeleteKey "", node
          ColourNote "white", "blue", "Path from [" & k & "] " & _
                     "to [" & node & "] deleted."
          ArraySet "map", k, ArrayExport ("", ",")
        End If
 
      Next  ' next node

    End If

    Exit Sub  ' all done
  End If  ' deleting node

  If left (which, 1) = "P" Then  ' delete path
    
    If not ArrayKeyExists ("cip", which) Then
       ColourNote "white", "red", "Path number " & which & " does not exist"
       Exit Sub
    End If

'
'  we stored the path as a node,destination pair
'
    ArrayClear ""
    ArrayImport "", ArrayGet ("cip", which), ","
    node = ArrayGet ("", "node")
    k = ArrayGet ("", "dest")

    if not ArrayKeyExists ("map", node) Then
       ColourNote "white", "red", "Map node [" & node & "] does not exist"
       Exit Sub
    End If

    ArrayClear ""
    ArrayImport "", ArrayGet ("map", node), ","

    If ArrayKeyExists ("", k) Then
      ArrayDeleteKey "", k
      ColourNote "white", "blue", "Path from [" & node & "] " & _
                 "to [" & k & "] deleted."
      ArraySet "map", node, ArrayExport ("", ",")
    End If

    Exit Sub  ' all done
  End If  ' deleting node

  ColourNote "white", "red", "Node number must start with N or P"

End Sub ' OnCheckpointDelete

'----------------------------------------------------------
' room has changed - are we at an existing node?
'----------------------------------------------------------
Sub RoomChanged
dim room

  room = GetVariable ("room")

  If ArrayKeyExists ("map", room) then
'
'  we are at a known node - delete map items so
'  we do not take some tortuous path from here to here
'  

'
'  first, however, save them in case they re-checkpoint this room
'
    SetVariable "known_room", room
    SetVariable "known_checkpoint", GetVariable ("checkpoint")
    SetVariable "known_mapstring", GetMappingString 
   
    DeleteAllMapItems
    ColourNote "white", "blue", "Now at known map node [" & room & "]"
    SetVariable "checkpoint", room
 
  End If

End Sub ' RoomChanged

dim roomnamestyle 
  roomnamestyle = 6

'----------------------------------------------------------
' deduce room name if on same line as prompt
'----------------------------------------------------------
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 < roomnamestyle Then Exit Sub

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

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

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

'
'  Get name
'

  SetVariable "room", GetStyleInfo (line, roomnamestyle, 1)
  Call RoomChanged
  

End Sub ' OnGetRoomFromPrompt 

'----------------------------------------------------------
' pull in room name from first style on line
'----------------------------------------------------------
Sub OnRoomFromFirstStyle (name, line, wildcards)
dim lines, styles

  line = GetLinesInBufferCount
  styles = GetLineInfo (line, 11)

'
'  Get name
'

  if (trim (GetStyleInfo (line, 1, 1)) <> "") and _
     (GetStyleInfo (line, 1, 2) = 58) then
    SetVariable "room", trim (GetStyleInfo (line, 1, 1))
    Call RoomChanged
  end if
  
End Sub ' OnRoomFromFirstStyle

'----------------------------------------------------------
' cr (room) - manually set room name
'----------------------------------------------------------
Sub OnCheckpointRoom (name, line, wildcards)

  SetVariable "room", trim (wildcards (1))
  ColourNote "white", "blue", "Room name set to " & GetVariable ("room")
  Call RoomChanged

End Sub	' OnCheckpointRoom 

'----------------------------------------------------------
' room change (from trigger)
'----------------------------------------------------------
Sub OnRoomChange (name, line, wildcards)

  SetVariable "room", trim (wildcards (1))
  Call RoomChanged

End Sub	' OnCheckpointRoom 

'----------------------------------------------------------
' use mapper to backtrack to  last node
'----------------------------------------------------------
Sub OnCheckpointGotoNode (name, line, wildcards)
dim mapstring
  
  mapstring = trim (GetMappingString)

  if mapstring = "" then
    colournote "white", "red", "No map path available"
    exit sub
  end if

'
'  try to go back
'
  ColourNote "white", "blue", "Attempting to go to [" & _
     GetVariable ("checkpoint") & "]"

  Send EvaluateSpeedwalk (ReverseSpeedwalk (mapstring))

End Sub ' OnCheckpointGotoNode

]]>
</script>


<!--  Plugin help  -->

<aliases>
  <alias
   script="OnHelp"
   match="chelp"
   enabled="y"
  >
  </alias>
</aliases>

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

</muclient>