Wayfinder, an alternate route finder package

Share your scripts and packages with other Mudlet users.
Post Reply
Smurf
Posts: 9
Joined: Sat Jul 18, 2020 1:16 pm

Wayfinder, an alternate route finder package

Post by Smurf »

I'm not happy with the built-in route finder in Mudlet, so I wrote my own.

The attached package contains one function: "findWayToRoom(sourceRoom, checkFn)".
The check function gets four arguments (distance, roomToBeChecked, roomlist, directionlist). It is responsible for saving its arguments if the room matches. It can return true (stop searching), false (continue but not through this room), nil (continue as usual) or a number (added to the distance of further ways through this room).
Return value: true if your check function ever returned "true". The room+direction lists are not returned, your checkFn is responsible for saving them if required.

So what can we do with this?
- really-shortest-route finding (Mudlet's A* algorithm doesn't understand "go 20 rooms *away* from your destination, then enter the teleport")
- way to the next XXX (bank, church, weapons store)
- even better: ways to the next five XXXes, collected all at once, then let the player click on which they want to use
- list the ten closest rooms with un-explored exits
- conditional routes (can't swim through the lake while shlepping the heavy plate mail, can't walk the narrow mountain path when severely injured)
- your imagination here.

Speed: runs through 10k rooms in a tenth of a second on my somewhat-underpowered desktop. YMMV and depends mainly on the complexity of the check function.

Update: now includes support for Mudlet 4.10's custom speedwalking.
Attachments
Wayfinder.mpackage
(2.27 KiB) Downloaded 94 times

Lucky24
Posts: 52
Joined: Sun Sep 12, 2010 1:50 am

Re: Wayfinder, an alternate route finder package

Post by Lucky24 »

This solved all the issues I had with the A* algorithm, thanks!

This algorithm seems to properly use the shortest number of hops to get to a location, even if that direction meanders away from the destination for a bit, instead of taking a more direct path that has more hops. (Room weights alone don't fully map the problem domain properly when you have rooms of different sizes. Thus, for maps with lots of different sized rooms, this algorithm can almost halve the time of walking).

I've attached a version that also adds skipping paths if the direction is locked, or if the destination room is locked. I also swapped 'ways' and 'rooms' assignment when custom mapper is disabled, so now ways = speedWalkDir instead of speedWalkPaths, which seems to be more correct and similar to what the default getPaths() spits out into speedWalkDir, I think.
Attachments
WayfinderWithExitLocks.mpackage
(510 Bytes) Downloaded 22 times

Smurf
Posts: 9
Joined: Sat Jul 18, 2020 1:16 pm

Re: Wayfinder, an alternate route finder package

Post by Smurf »

@lucky24 Thanks for the enhancements!

Post Reply