Page 1 of 1

Wayfinder, an alternate route finder package

Posted: Sat Jul 25, 2020 11:33 am
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.

Re: Wayfinder, an alternate route finder package

Posted: Wed Nov 04, 2020 9:52 am
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.

Re: Wayfinder, an alternate route finder package

Posted: Tue Nov 10, 2020 7:51 am
by Smurf
@lucky24 Thanks for the enhancements!