Gammon Forum : MUSHclient : Lua : Find the shortest path that visits the most rooms.

Register forum user name Search FAQ

Gammon Forum

Entire forum

MUSHclient

Lua

Find the shortest path that visits the most rooms.

Find the shortest path that visits the most rooms.

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

Posted by

Zuhayir (6 posts)

Date

Sun 24 Oct 2010 03:08 AM (UTC)

Message

Hey, I've recently begun working on a script that utilizes a branch searching method to find the shortest path to any given destination, but the map I'm utilizing is slightly out-dated, so I decided a script that could visit every room with the least amount of movement (movement is semi-restricted in the mud I play), it could easily be used to update my map.

My problem is thus: a branching method with recursion is insanely intensive. Within 20 rooms of my starting destination, I've generated over 42967 movements, and this is WITH a few smart detections such as particles knowing the last branch they visited, remembering rooms they've already been to, ect.

My question really is, can this be done, if so how, and if it's far too complicated, can I just be pointed in the direction of somebody who's done the leg work?

Thanks!

Note: I've decided to do it on a smaller scale, updating zones one at a time, so the script doesn't have to be super efficient, just.. more so than what I'm working with.

Posted by

Nick Gammon Australia (22,975 posts)

bio Forum Administrator

Date

Reply #1 on Sun 24 Oct 2010 04:00 AM (UTC)

Message

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

Read the whole lot - I think we got it going pretty well.

I use the same system in the MUSHclient mapper module, it updates in about 1/30 of a second, and finds rooms within 30 or 40 rooms of your starting point.

- Nick Gammon

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

Posted by

Nick Gammon Australia (22,975 posts)

bio Forum Administrator

Date

Reply #2 on Sun 24 Oct 2010 04:19 AM (UTC)

Amended on Tue 26 Nov 2013 03:44 AM (UTC) by Nick Gammon

Message

I made a video:

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

Near the end in particular (with the map zoomed out) you can see it updating instantly as you walk around, showing quite a few rooms, which are all dynamically calculated as you walk around using the particle method. Here is a screenshot for example:

- Nick Gammon

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

Posted by Zuhayir (6 posts) bio

Date

Reply #3 on Sun 24 Oct 2010 04:27 AM (UTC)

Amended on Sun 24 Oct 2010 04:46 AM (UTC) by Nick Gammon

Message

Thanks Nick, I'm actually using code based on what I read in there a few months ago :)

My problem is trying to expand it to create a path that visits all rooms at least once, where as your script had the ability to "find the longest path", the path wouldn't fold back on itself, eliminating dead-ends or just physical imposibilities.

This, for instance:


[ ] - [ ] - [ ] - [ ] - [ ]
       |           |
      [ ] - [ ] - [ ]

Your original script would find the longest path as:



[1] - [2] - [ ] - [6] - [7]
       |           |
      [3] - [4] - [5]

Where I would need:



[1] - [2] - [7] - [6] - [9]
       |           |
      [3] - [4] - [5]

Posted by

Zuhayir (6 posts)

Date

Reply #4 on Sun 24 Oct 2010 04:32 AM (UTC)

Message

Can't seem to edit my post, but this is what the diagram was supposed to look like:

[ ] - [ ] - [ ] - [ ] - [ ]
*******|***********|*******
******[ ] - [ ] - [ ]******

Posted by

Zuhayir (6 posts)

Date

Reply #5 on Sun 24 Oct 2010 04:34 AM (UTC)

Message

Grrr. Okay, last try.

Upper:
[ ] - [1] - [ ] - [2] - [ ]

Lower:
[1] - [ ] - [2]

1 to 1, 2 to 2.

Posted by

Nick Gammon Australia (22,975 posts)

bio Forum Administrator

Date

Reply #6 on Sun 24 Oct 2010 04:47 AM (UTC)

Message

Login into the forum to edit your posts, use [code] tags to get monospaced fonts.

- Nick Gammon

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

Posted by

Nick Gammon Australia (22,975 posts)

bio Forum Administrator

Date

Reply #7 on Sun 24 Oct 2010 04:50 AM (UTC)

Message

Zuhayir said:

My problem is trying to expand it to create a path that visits all rooms at least once, where as your script had the ability to "find the longest path", the path wouldn't fold back on itself, eliminating dead-ends or just physical imposibilities.

I think the mapper visits each room, otherwise it wouldn't draw them all.

If I recall correctly, it has a table of visited rooms, so for each room it works out the rooms which lead from it, but excluding rooms which it already dealt with.

- Nick Gammon

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

Posted by

Zuhayir (6 posts)

Date

Reply #8 on Sun 24 Oct 2010 05:01 AM (UTC)

Amended on Sun 24 Oct 2010 05:08 AM (UTC) by Zuhayir

Message

Right, it draws from a global table of explored rooms, because it doesn't need each particle to explore each room, only every room to be explored by at least one particle.

Now, I want to visit each room in a more physical sense (as much as you can get in a mud!), and have my character double-check the data I've got stored in my map, as opposed to virtually drawing it. So, I wish to generate a path that walks around the 8 rooms, for example, and for each room do a check to makes sure the exits, environment, room description, ect, are all correct with the database, and then moves to the next room.

The problem with this is, my character isn't a particle, and can't follow multiple paths at any given time. And the mud I play has a sort of movement statistic that regnerates over time, so moving too much can wind me up in hostile teritory with the ability to move.

Edit:
I'm clearly not explaining this as best I could, but each particle as a memory of its own, personal, explored rooms. So each time a particle reaches an intersection and a choice has to be made, it splits off (as per the original code), creating a duplicate of itself. Then, should that particle reach a room where no choice can be made, it'll look through its own personal memory and find the last intersection, moving towards that intersection, branching off again when it reaches its destination. (EG: A three-way branch creates three particles, one of which hits a dead end and returns to the branch, now creating two particles. So, assuming all three branches were dead ends, you'd end up with 6 paths.)

The goal being that for every choice possible, a new path will be created, and all paths will eventually explore all rooms in the area, and then they will compare themselves against one another (shortest path/highest number of unique rooms) to return the most efficient path.

Posted by

Nick Gammon Australia (22,975 posts)

bio Forum Administrator

Date

Reply #9 on Sun 24 Oct 2010 05:03 AM (UTC)

Message

Zuhayir said:

My problem is thus: a branching method with recursion is insanely intensive. Within 20 rooms of my starting destination, I've generated over 42967 movements, and this is WITH a few smart detections such as particles knowing the last branch they visited, remembering rooms they've already been to, ect.

Your problem is that it is basically going to be an exponential amount of work anyway. For example, if you had each room with 3 exits, and none linked to each other, then to investigate 20 rooms away from the start point would be 3^20 which is 3,486,784,401 rooms.

In practice, rooms interconnect, and the smart particles detect that. Thus your quoted figure is much lower.

I think the particles system will quickly and easily find an optimal route over a smallish distance (eg. from an inn to the edge of town). But unless you prune its investigations (as discussed in that thread) then it will naturally grow very large.

- Nick Gammon

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

Posted by

Nick Gammon Australia (22,975 posts)

bio Forum Administrator

Date

Reply #10 on Sun 24 Oct 2010 05:09 AM (UTC)

Message

Zuhayir said:

The problem with this is, my character isn't a particle, and can't follow multiple paths at any given time. And the mud I play has a sort of movement statistic that regnerates over time, so moving too much can wind me up in hostile teritory with the ability to move.

Ah yes, I see what you mean. When I have been using the mapper on a MUD that doesn't supply its room database in advance, it has been a case of manually walking around (probably not optimally) and having the mapper database being a record, after the event, of what goes where. In that case it lets me get back to somewhere (known) efficiently, but doesn't really help me map efficiently.

In your case probably the most you can do (assuming you are allowed to use bots to map) is let the mapper algorithm find the nearest unmapped room, and find an efficient path to it.

It may turn out, after the event, that there was a more efficient mapping route, but you can't really know that without knowing the layout first, which is the very thing you are trying to determine.

- Nick Gammon

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

Posted by

Zuhayir (6 posts)

Date

Reply #11 on Sun 24 Oct 2010 05:55 AM (UTC)

Message

Well, it's probably a little more painful than that, because I'm not sure which rooms are incomplete/out-of-date. The MUD I play doesn't inform a player when changes have been, so if I know that a change has been made but not where (my explorer ranking goes down), I have to effectively traverse my entire map (the entire world). It's a pain, but I think I'll just have to do it manually and record the path I took.

This expontential problem is too much for my notebook to handle! :D

Posted by

Erendir Germany (47 posts)

Date

Reply #12 on Sun 24 Oct 2010 10:55 AM (UTC)

Message

Zuhayir, i think i know what You want: to solve a TSP, http://en.wikipedia.org/wiki/Travelling_salesman_problem (some special case like maybe Euclidean TSP).

The problem of such problems is, they are NP-hard, i.e. cheap and fast algorithm isn't possible. But the special case we have in MUDs may have a good solution, You need only to find it.

Posted by

Tsunami USA (204 posts)

Date

Reply #13 on Mon 25 Oct 2010 06:59 PM (UTC)

Message

This is a somewhat interesting problem, though you are approaching it from the wrong direction. Djikstra's algorithm, which appears to be what you are using is not suited for this since it only finds paths to a single point. It seems to me you are running Djikstra's in a loop which isn't terribly efficient for this sort of problem.

A greedy algorithm has much quicker calculations, although it doesn't provide the best solution. It doesn't look like you want the best solution though, you just want to visit every room.

For clarification, before I propose a possible solution, are you trying to visit every room the mapper knows of, or are you trying to traverse every connection (exit) the mapper knows of?

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.

34,388 views.

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

Go to topic: Search the forum

Quick links: MUSHclient. MUSHclient help. Forum shortcuts. Posting templates. Lua modules. Lua documentation.

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

Comments to: Gammon Software support
Forum RSS feed ( https://gammon.com.au/rss/forum.xml )