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
➜ 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) Bio
|
| 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.
| | Top |
|
| Posted by
| Nick Gammon
Australia (23,140 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 | | Top |
|
| Posted by
| Nick Gammon
Australia (23,140 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 | | Top |
|
| 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]
| | Top |
|
| Posted by
| Zuhayir
(6 posts) Bio
|
| 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:
[ ] - [ ] - [ ] - [ ] - [ ]
*******|***********|*******
******[ ] - [ ] - [ ]****** | | Top |
|
| Posted by
| Zuhayir
(6 posts) Bio
|
| 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. | | Top |
|
| Posted by
| Nick Gammon
Australia (23,140 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 | | Top |
|
| Posted by
| Nick Gammon
Australia (23,140 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 | | Top |
|
| Posted by
| Zuhayir
(6 posts) Bio
|
| 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.
| | Top |
|
| Posted by
| Nick Gammon
Australia (23,140 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 | | Top |
|
| Posted by
| Nick Gammon
Australia (23,140 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 | | Top |
|
| Posted by
| Zuhayir
(6 posts) Bio
|
| 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 | | Top |
|
| Posted by
| Erendir
Germany (47 posts) Bio
|
| 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. | | Top |
|
| Posted by
| Tsunami
USA (204 posts) Bio
|
| 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? | | 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.
40,125 views.
It is now over 60 days since the last post. This thread is closed.
Refresh page
![[Go to top]](/images/gototop.gif)
top