I’m trying to calculate a value based on all of the rooms on the best route between two rooms. This requires multiple calls to “best route from”. So if the route were A → B → C → D → E, I’d need to calculate best route A → E, best route B → E, etc. That’s abysmal runtime.
My question is whether Inform (or some interpreter) caches best route results (at least those from the current turn) so that my calculation is reasonable.
Edit: And I wish there was a way to limit the length of paths; say, I only want paths up to five steps, otherwise return nothing.
It’s written in Inform 6 and it’s fairly well documented. The “fast route-finding” algorithm is already caching the routes.
The “fast route-finding” algorithm is used for Glulx compilations by default while the “slow route-finding” algorithm is used for Zmachine compilations by default. (But you can specify which to use in your story.)
However… you can do better. From your description, you shouldn’t need multiple calls to “best route from”.
EDIT: I misread something in the I6 code; it doesn’t return the list you want. It’s there in the underlying data, though… let me take a look at this…
OK, so the “fast route-finding” algorithm builds up an entire matrix for every pair of source-room / destination-room, with the “correct first direction to go”, and then just checks this matrix when you call “best route from”.
So if you’re using fast route-finding, there’s practically no cost to calling “best route from”. When you call it once it builds this global matrix and then it’s dirt cheap to call it all subsequent times. You might as well do it the way you were originally describing.
The thing you want to do is to avoid rebuilds of the global matrix. This happens when SignalMapChange is called, which happens when exits are deleted or created, and also when doors are closed/opened/locked or when the light status of rooms changed, etc. – and also when you call with a different condition on the “best route from”. So make sure you call “best route from” with no conditions if you want to keep it fast.
(If you’re doing something where doors open and shut every turn changing the map every turn, then you may want something different.)
It seems like the built-in “number of moves from A to B” function would get you what you’re trying to do, both in terms of getting the length and cutting off results if the number is too high, without a need for any manual looping. See link to docs here.
I learned a bunch of stuff from Nathanael’s post that I didn’t know before about how to assess the ‘power draw’ of the pathfinding. Also I don’t think I was aware of the number of moves function, ala Mike Russo.
I guess the fly I wanted to chuck in the ointment is, before you code up something magnificent, it’s worth checking that the ‘best route’ function is behaving in a way you like with your map. Emphasis on “your”.
For instance, it can be thrown a bit by diagonals, or when there are multiple equally long paths between two rooms. When I say ‘thrown’, it will never accidentally pick a longer path. But it is capable of choosing routes a human would consider weird, like taking a diagonal dog-leg towards a target room that’s reachable by a straight line of walking.
There’s a big topic about this (with possible solutions and workarounds) over here:
Fascinating stuff. This answers my question, actually. I’m resigned to paying a cost every turn (in the case that the map updates), but I wanted to be sure I wasn’t going to pay that cost O(m^2) times more (where m is the length of the path I’m looking at).
Thanks. That’s an interesting thread. Fortunately it shouldn’t be a problem in my case.
