[Home] [Downloads] [Search] [Help/forum]


Register forum user name Search FAQ

Gammon Forum

[Folder]  Entire forum
-> [Folder]  Programming
. -> [Folder]  General
. . -> [Subject]  Finding the shortest path...

Finding the shortest path...

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


Posted by Jedhi   (37 posts)  [Biography] 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.
[Go to top] top

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] 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:

Template:post=7306 Please see the forum thread: http://gammon.com.au/forum/?id=7306.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Fiendish   USA  (2,514 posts)  [Biography] 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 == "*"
as indication of a completed path. Also note that this is still BFS.

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
[Go to top] 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.


12,247 views.

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

Go to topic:           Search the forum


[Go to top] top

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.

[Home]


Written by Nick Gammon - 5K   profile for Nick Gammon on Stack Exchange, a network of free, community-driven Q&A sites   Marriage equality

Comments to: Gammon Software support
[RH click to get RSS URL] Forum RSS feed ( https://gammon.com.au/rss/forum.xml )

[Best viewed with any browser - 2K]    [Hosted at HostDash]