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
➜ Programming
➜ General
➜ Finding the shortest path...
|
Finding the shortest path...
|
It is now over 60 days since the last post. This thread is closed.
Refresh page
| Posted by
| Jedhi
(37 posts) Bio
|
| Date
| Tue 06 Oct 2015 03:29 PM (UTC) |
| Message
| Hello,
I am having trouble finding the shortest path between 2 rooms. It is a standard map with each rooms having exits to other rooms. But the map is big, aardwolf has more than 30k rooms.
I tried BFS algorithm, but it is too slow.
How does mushclient do it?
I am using PHP as the scripting language, but that is not that important. | | Top |
|
| Posted by
| Nick Gammon
Australia (23,133 posts) Bio
Forum Administrator |
| Date
| Reply #1 on Tue 06 Oct 2015 08:15 PM (UTC) Amended on Wed 07 Oct 2015 08:30 AM (UTC) by Nick Gammon
|
| Message
| This (fairly long) thread describes the general technique:
|
- Nick Gammon
www.gammon.com.au, www.mushclient.com | | Top |
|
| Posted by
| Fiendish
USA (2,534 posts) Bio
Global Moderator |
| Date
| Reply #2 on Fri 09 Oct 2015 01:30 PM (UTC) |
| Message
| Realistically, since you're asking about Aardwolf, what you want to know is how the Aardwolf MUSHclient mapper works. That's...rather complicated, because it has so many different steps.
But to shortcut the problem, I suspect that when you say "BFS is too slow" you're either not implementing your BFS correctly or you're doing too much disk IO. Are you culling already searched rooms from each next expansion step? Are you looking at the disk for every new room?
Now to try to explain how I do the search for Aardwolf requires a small bit of history...
This is what the search method looked like back in January 2011. I think without looking further that this is the original search function made by Nick. It is a very simple BFS that kinda works, but can't deal with Aardwolf features like handheld portals or recall/home at all.
Quote:
https://github.com/fiendish/aardwolfclientpackage/blob/eb2cdb92740dcc2e8ecba8c3a53a4e6e0562476a/MUSHclient/lua/aardmapper.lua#L806
The next major revision happened here. This is where I added in the ability to route through handheld portals and other from-anywhere commands like recall/home. It's quite ugly and not very efficient, one kinda stupid thing is that it does all of its "visited" bookkeeping with strings, but the key things to note here are that I switch to querying batches of rooms from the SQLite db and that I search backward starting from the destination. This allows for dangling pseudo-room exits (fromuid="*") that you can exit from but not get into. I use these pseudo-rooms as being "from-anywhere". Notice we're now searching for if row.fromuid == src or row.fromuid == "*"
Quote:
https://github.com/fiendish/aardwolfclientpackage/blob/eb2cdb92740dcc2e8ecba8c3a53a4e6e0562476a/MUSHclient/worlds/plugins/aard_GMCP_mapper.xml#L2362
I then change it so that the kinda stupid bookkeeping strings from before use tables instead. At the same time I also made it so that custom exits (we call them "cexits") could be multiple commands instead of just one (a quirk of the pattern matching from before). Because sometimes you want to be able to script the connection between two distant rooms that don't actually share exits.
Quote:
https://github.com/fiendish/aardwolfclientpackage/blob/bb0a256b4241440a2456332d3ddd9df35d4fad34/MUSHclient/worlds/plugins/aard_GMCP_mapper.xml#L2369
Later on I added in the ability to walk away from a noportal/norecall section if it still means that using recall/home or a portal from a connected location is the shortest path. This necessitated differentiating recall/home from handheld portals. I created a new pseudo-room exit with fromuid="**" and added norecall/noportal flags to the room database. The user designates a "bounce portal" to use if the room is norecall but not noportal, a "bounce recall" command to use if the room is noportal but not norecall. If the room is both norecall and noportal, we must walk out.
Quote:
https://github.com/fiendish/aardwolfclientpackage/commit/e91c1c8e9df813909536c3272dfac36984335f4e
Then I made it so that you could level-lock exits in the database. The room lookup sql query in findpath just gets a minor tweak with ...(fromuid not in ('*','**') and level <= mylevel) or (fromuid in ('*','**') and level <= mylevel+(mytier*10)) ...
Then there were small tweaks here and there for things like making it so that you wouldn't use a portal or recall command if the destination is only 1 room away, until we get to what it looks like today. |
https://github.com/fiendish/aardwolfclientpackage | | 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.
13,759 views.
It is now over 60 days since the last post. This thread is closed.
Refresh page
![[Go to top]](/images/gototop.gif)
top
