Using best route to find intersection of paths

I’m using best route to move an NPC toward a goal:

let heading be the best route from location of npc to destination;
try silently npc going heading;

The NPC has the ability to wait for the player character before moving forward. Or if the player is in the next room, the NPC will proceed.

let next_room be the room heading from location of npc;
if player is in next_room:
    [do catch up action/comments]
    follow the action_catching_up of this_journey;
    [move npc]
    try silently npc going heading;

There are some more conditionals in there about whether the NPC is visible, and what they say/do if you keep them waiting too long, etc.

In general, if you are behind the NPC, they should wait, and if you are ahead, they should proceed. The way I have it now (using next_room) if you move beyond next_room, the NPC will just wait when they should move ahead.

Is there an efficient way to tell if the next_room the NPC would move to is on the best route from the player to the NPC?

Inform’s built-in pathfinding is both a wonderful thing and (occasionally) just a little more limiting than I want, and I’ve found myself banging my head against best route calculations a fair number of times in the thing I’m working on right now, thinking “if I could only …”.

In any case, there are a couple of things that suggest themselves to me as possible responses to the situation your characters are in. One, perhaps the simplest, would be to have the NPC slavishly follow the PC wherever s/he goes instead of independently seeking the same goal. You can use phrases like the best route from the location of Carlos to the player (if your NPC is named Carlos, of course) to calculate what the NPC’s route should be. This might solve the larger problem in a way that makes your specific concern unnecessary to deal with.

On the other hand, it may be narratively unsatisfying, too, and you really might want to have an NPC chomping at the bit but who will wait if s/he is ahead of you. The problem here is that Inform doesn’t give you an easy way to see the entire list of moves that would be needed to get from A to B. (And there are reasons why this is a good choice in many circumstances: after all, the best route might change if the map is rearranged or if doors in between get locked or for any number of reasons.) But if I were solving this problem in, say, Python, that’s what I’d want to do: cobble together the whole list of moves and then see whether the PC’s current location appears in that list. This would be a more difficult task in Inform, though not impossible. (The code I’m sketching out in my head seems like it would be prohibitively slow, though.)

What might be easier, though, is just to see whether the PC is closer to the goal, in the sense of fewer moves being required, than the relevant NPC is. This assumes that they’re moving toward the same goal, but it sounds like that’s what’s going on in your particular situation. You can find the number of moves between two locations using, appropropriately enough, Inform’s the number of moves from ... to ... phrase.

So you might try something like this:

Reactor Core is a room. Core Entrance Chamber is south of Reactor Core. Decontamination is south of Core Entrance Chamber. Suit Storage is south of Decontamination. Control Booth is south of Suit Storage. Visitor's Gift Shop is south of Control Booth.

The player is in Decontamination. Useless Fred is a man in Control Booth.

Reactor Meltdown is a scene. Reactor Meltdown begins when the player is in Suit Storage.

When Reactor Meltdown begins, say "A loud alarm goes off! The reactor is overheating!".

Every turn during Reactor Meltdown:
	say "Oh no! The reactor is overheating!";
	let f be the number of moves from the location of Useless Fred to Reactor Core;
	let p be the number of moves from the location of the player to Reactor Core;
	if p is less than f:
		let the way be the best route from the location of Useless Fred to Reactor Core;
		if the way is a direction:
			 try Useless Fred going the way;
	otherwise if Useless Fred can see the player:
		say "'Hurry the aitch ee double-hockey-sticks up!' yells Fred. 'That reactor ain't waitin' on no one nohow!'". 

(You can also shorten the location of the player to just the location, but I think it’s easier to leave the expanded form in for demonstration purposes.) This would of course require plenty of cleanup, but kind of illustrates what you might theoretically do.

Notice that checking the number of moves required is really just a heuristic for whether the paths intersect, which you’re definitely not checking here. However, if the PC and NPC are likely to be close together anyway, and the paths overlap substantially, then this may be good enough.

1 Like

Another option could be having an invisible ‘testerperson’ who you put in the room with the character, then move from room to room until they reach the destination, checking all along if they reach the other character anywhere, then teleporting the testerperson away at the end.

This isn’t as nice as Patrick’s answer because the invisible person can create some problems if you have any code that randomly selects people. But it’s a trick I’ve used a couple of times for various things.

If you do use an invisible person, it’s better to move them from room to room using ‘now testerperson is in’ instead of ‘try testerperson going’ since you don’t want time to pass.

1 Like

“Try foo going dir” does not cause time to pass. It does generate “Foo goes south”, “Foo arrives from the south” messages, so it’s still good advice.

1 Like

Patrick’s post inspired a Good Idea. I was trying to see if the next room was on the path from the player to the NPC. But it is much easier to examine the path from the NPC to the player. Thus if the next room in both cases is the same, then the player is ahead of the NPC on their route.

[find the heading and next room on NPC's journey]
let heading be the best route from location of npc to destination;
let next_room be the room heading from location of npc;
[determine if player is direction of goal]
let player_heading be the best route from location of npc to location of player;
let next_room_to_player be the room player_heading from location of npc;
[if player is ahead of npc]
if next_room is next_room_to_player:
    [move npc]
    try silently npc going heading;
else:
    [npc waits]
1 Like

Here’s a solution for the general case, which finds the earliest point at which two ‘best routes’ will meet if they are ‘stepped through’ one room at a time. If either route is impossible or the two routes don’t intersect, the phrase returns nothing. If used in an actual story, obviously the debugging ‘say…’ phrases announcing the reason for returning nothing should be commented out…

"__Test_Amazing" by PB

[proof of concept- how to find the intersection of two 'best routes' by walking through them and saving the route so far in lists]

Chapter - Scenario

The Verandah is south of the Drawing Room and north of the Terrace. The Dining Room is east of the Verandah and northwest of the Zen Room and west of the Smoking lounge. The Kitchen is north of the Dining Room. It is west of the Butlers Pantry.  A room called the Pantry is north of the Kitchen and south of the Storeroom and southwest of the Dairy and west of the Bakehouse. The Scullery is east of the dairy.  The Blue Hallway is north of the Drawing Room and west of the Pantry. The Entrance Hall is west of the Blue Hallway and east of the Library and north of the Driveway. The Approach is north of the Avenue and south of the Driveway and east of the Walled Garden.  The Greenhouses are southwest of the Walled Garden and east of the Potting Shed. The Japanese Garden is north of the Greenhouses and east of the Pond. The Study is west of the Library and southeast of the Snug. The Wishing Well is a room.

Chapter - Machinery

To decide which object is the intersection of (S1 - a room) to (F1 - a room) and (S2 - a room) to (F2 - a room):
	if the best route from S1 to F1 is nothing:
		say "(no route found [S1] -> [F1]) ";
		decide on nothing; [one or other route not possible]
	if the best route from S2 to F2 is nothing:
		say "(no route found [S2] -> [F2]) ";
		decide on nothing; [one or other route not possible]
	let L1 be a list of rooms;
	let L2 be a list of rooms;
	While 1 is 1:
		add S1 to L1, if absent;
		add S2 to L2, if absent;
		if S1 is listed in L2:
			decide on S1; [intersection found]
		if S2 is listed in L1:
			decide on S2; [intersection found]
		if S1 is F1 and S2 is F2:
			say "(no intersection) : ([L1] : [L2]) ";
			decide on nothing; [both routes traced and no intersection found]
		if S1 is not F1:
			let heading be the best route from S1 to F1;
			now S1 is the room heading from S1;
		if S2 is not F2:
			let heading be the best route from S2 to F2;
			now S2 is the room heading from S2;

Chapter - Testing

Use fast route-finding.		
		
When play begins:
	Repeat through Table of Routes:
		say "[Start 1 entry] -> [Finish 1 entry]  |  [Start 2 entry] -> [Finish 2 entry] <-:-> [the intersection of Start 1 entry to Finish 1 entry  and Start 2 entry to Finish 2 entry].";
	
Table of Routes
Start 1	Finish 1	Start 2	Finish 2
Zen Room	Avenue	Snug	Storeroom
Zen Room	Scullery	Snug	Storeroom
Zen Room	Potting Shed	Snug	Avenue
Zen Room	Terrace	Snug	Smoking Lounge
Zen Room	Terrace	Snug	Butlers Pantry	
Zen Room	Terrace	Snug	Wishing Well	
Zen Room	Wishing Well	Snug	Butlers Pantry	
		
Chapter - Sandbox		
2 Likes