Best route and diagonal shortcutting

I’ve got a square grid of rooms, all connected by NSEW as well as the diagonals.

I find sometimes the “best route” pathfinding dodges rooms in the middle of the grid. The overall journey’s not taking more moves, but it is preferring to take a zigzag path instead of the (more logical to a human) straight line one.

Consider this finely drawn diagram:

Summary

If I’m at A and want to get to C, I want the path chosen for me to be ABC. But the best route in my game prefers ADC. I wonder if somewhere in the pathfinding is some logic saying, “Well, normally it’d be two moves to go from A to D, but I can do it in one by going northeast from A, so let’s do that and double our travel power!”

The upshot is, I never want it to zigzag when it can go in a straight line. Is there a way I can enforce this?

-Wade

It doesn’t look like Inform 7’s path finding functions let you specify connection weights. This means you shouldn’t picture the path finding as comparing the sides of a right angled triangle, but instead the sides of an equilateral triangle.

Maybe if you change the order the rooms are defined in the source code it might pick the path you want?

Otherwise you could define a room property to mark the unfavourable places and use the best route from (object) to (object) through (description of objects) phrase. But then the pathfinding would never choose those rooms, even if they are the best or only option.

You could write your own path finding implementation from scratch that would favour the cardinal directions, but that would be a lot of work of course.

1 Like

Thanks for the ideas. Yeah, I had considered playing with the order in the source code, or which rooms are defined in which ways, but it’s a long compile each time so I figured I’d ask first. EDIT - I’ve cut out the room definitions and put them in a test project so I can recompile fast.

-Wade

You could always make a hidden copy of all the rooms with only NESW connections, and a hidden copy of the player you move around with the player (or even just a rock that mimics the players movements).

Then every time you find the best route for the player, you can see if a best route exists for the rock and use that route instead. That way, if a best route using straight lines exists you’ll always find it. It’s annoying but works (I’ve used a similar trick for an invisible elevator attendant).

3 Likes

New game idea: “Is Inform 7 smarter than a rock?”

Thanks, this is a pretty cool backup idea. I sort of hope I won’t have to resort to it, though. And this is coming from me, who often considers no kludge too kludgey.

I have to say initial tests with rearranging room appearance order in the source code look promising, but I won’t know til tomorrow 'cos it’s my bedtime now.

-Wade

1 Like

This tweak to the template allows route-finding to be restricted to NSEW moves only if the global variable use-diagonals is set to true- but with the disadvantage that if diagonal moves (or up/down/in/out) occur in the only route possible (or the definitive shortest route) they won’t be discovered:

Use slow route-finding.
Use-diagonals is a truth state that varies.	
The use-diagonals variable translates into I6 as "use_diagonals".

Include (-
Global use_diagonals = true ;
-) after "Definitions.i6t".

Include (-

! ==== ==== ==== ==== ==== ==== ==== ==== ==== ====
! Relations.i6t: Slow Route-Finding
! ==== ==== ==== ==== ==== ==== ==== ==== ==== ====


#ifndef FAST_ROUTE_FINDING;
[ SlowRouteTo from to filter use_doors  obj dir in_direction progressed sl through_door;
	if (from == nothing) return nothing;
	if (to == nothing) return nothing;
	if (from == to) return nothing;
	objectloop (obj has mark_as_room) obj.vector = 0;
	to.vector = 1;
	!print "Routing from ", (the) from, " to ", (the) to, "^";
	while (true) {
		progressed = false;
		print "Pass begins^";
		objectloop (obj has mark_as_room)
			if ((filter == 0) || (filter(obj)))
				if (obj.vector == 0)
				!  ######## alteration starts here
					objectloop (dir ofclass K3_direction && (use_diagonals || (dir == DirectionObject_0 || dir == DirectionObject_3 || dir == DirectionObject_6 || dir == DirectionObject_7))) {
				!  ######## alteration finishes here
						in_direction = Map_Storage-->((obj.IK1_Count)*No_Directions + dir.IK3_Count);
						if (in_direction == nothing) continue;
						print (the) obj, " > ", (the) dir, " > ", (the) in_direction, "^";
						if ((in_direction)
							&& (in_direction has mark_as_room)
							&& (in_direction.vector > 0)
							&& ((filter == 0) || (filter(in_direction)))) {
							obj.vector = dir | WORD_HIGHBIT;
							print "* ", (the) obj, " vector is ", (the) dir, "^";
							progressed = true;
							continue;
						}
						if (use_doors && (in_direction ofclass K4_door) &&
							((use_doors & 2) ||
							 (in_direction has open) ||
							 ((in_direction has openable) && (in_direction hasnt locked)))) {
							sl = location; location = obj;
							through_door = in_direction.door_to();
							location = sl;
							print "Through door is ", (the) through_door, "^";
							if ((through_door)
								&& (through_door has mark_as_room)
								&& (through_door.vector > 0)
								&& ((filter == 0) || (filter(through_door)))) {
								obj.vector = dir | WORD_HIGHBIT;
								print "* ", (the) obj, " vector is ", (the) dir, "^";
								progressed = true;
								continue;
							}
						}
					}
		objectloop (obj has mark_as_room) obj.vector = obj.vector &~ WORD_HIGHBIT;
		if (from.vector) return from.vector;
		if (progressed == false) return from.vector;
	}
];

[ SlowCountRouteTo from to filter use_doors obj i;
	if (from == nothing) return -1;
	if (to == nothing) return -1;
	if (from == to) return 0;
	if (from has mark_as_room && to has mark_as_room) {
		obj = MapRouteTo(from,to,filter,use_doors);
		if (obj == nothing) return -1;
		i = 0; obj = from;
		while ((obj ~= to) && (i<NUM_ROOMS)) { i++; obj = MapConnection(obj,obj.vector); }
		return i;
	}
	return -1;
];
#ENDIF;

-) instead of "Slow Route-Finding" in "Relations.i6t".

You can find the number of moves to trace a route with use-diagonals as true and again with use-diagonals as false, and if the number of moves is the same either way, prefer the orthogonally-traced route.

I can see it now: IFCOMP 2021 will have 9 games with “The Rock” somewhere on the title. :rofl:

1 Like

Here’s a more fleshed out version, which excludes only diagonal moves when use-diagonals is false (i.e. it allows NSEW, up/down/in/out) and also allows the author to specify values of distance for orthogonal (default=5) and diagonal (default=7) moves in order to calculate the length of best routes including/excluding diagonal moves using a phrase analogous to ‘the number of moves from…’ i.e. ‘the distance from…’

NB ‘the best route’ used in calculating distances, whether using diagonals or not, will still be the one with fewest moves, not necessarily the shortest distance

"____Test_Diagonals" by PB

Chapter - Scenario

Section - Locale

The Lab is a Room.  Northeast of the Lab is a room called The Storeroom. East of the Lab is a room called The Dispensary. East of the Dispensary is a room called the Cold Prep. The Storeroom is north of the Cold Prep.
A red flask is a thing in the Lab.  a blue flask is a thing in the lab. A retort is  a  thing in the lab. The cupboard is an opaque openable enterable container. It is in the Lab.

Section - Testing

When play begins:
	say "the best way using diagonals is [best route from the Lab to The Storeroom] - distance [distance from the Lab to the Storeroom] metres.";
	now use-diagonals is false;
	say "the best way orthogonally is [best route from the Lab to The Storeroom]- distance [distance from the Lab to the Storeroom] metres.";
	now orthogonal-length is 10;
	now diagonal-length is 14;
	now use-diagonals is true;
	say "the best way using diagonals is [best route from the Lab to The Storeroom] - distance [distance from the Lab to the Storeroom] paces.";
	now use-diagonals is false;
	say "the best way orthogonally is [best route from the Lab to The Storeroom]- distance [distance from the Lab to the Storeroom] paces.";
	

Chapter - Setup

Section - I7

Use slow route-finding.

Use-diagonals is a truth state that varies.	
The use-diagonals variable translates into I6 as "use_diagonals".
Diagonal-length is a number that varies.
The diagonal-length variable translates into I6 as "diagonal_length".
Orthogonal-length is a number that varies.
The orthogonal-length variable translates into I6 as "orthogonal_length".
To decide which number is distance from (R1 - object) to (R2 - object),
	using doors or using even locked doors:
	(- SlowLengthRouteTo({R1},{R2},0,{phrase options}) -).
To decide which number is distance from (R1 - object) to (R2 - object) through
	(RS - description of objects),
	using doors or using even locked doors:
	(- SlowLengthRouteTo({R1},{R2},{RS},{phrase options}) -).

Section - I6
	
Include (-
Global use_diagonals = true ;
Global diagonal_length = 7;
Global orthogonal_length = 5;
-) after "Definitions.i6t".

Include (-

! ==== ==== ==== ==== ==== ==== ==== ==== ==== ====
! Relations.i6t: Slow Route-Finding
! ==== ==== ==== ==== ==== ==== ==== ==== ==== ====


#ifndef FAST_ROUTE_FINDING;
[ SlowRouteTo from to filter use_doors  obj dir in_direction progressed sl through_door;
	if (from == nothing) return nothing;
	if (to == nothing) return nothing;
	if (from == to) return nothing;
	objectloop (obj has mark_as_room) obj.vector = 0;
	to.vector = 1;
	! print "Routing from ", (the) from, " to ", (the) to, "^";
	while (true) {
		progressed = false;
		! print "Pass begins^";
		objectloop (obj has mark_as_room)
			if ((filter == 0) || (filter(obj)))
				if (obj.vector == 0)
				!  ######## alteration starts here
					objectloop (dir ofclass K3_direction && (use_diagonals || (dir ~= DirectionObject_1 && dir ~= DirectionObject_2 && dir ~= DirectionObject_4 && dir ~= DirectionObject_5))) {
				!  ######## alteration finishes here
						in_direction = Map_Storage-->((obj.IK1_Count)*No_Directions + dir.IK3_Count);
						if (in_direction == nothing) continue;
						! print (the) obj, " > ", (the) dir, " > ", (the) in_direction, "^";
						if ((in_direction)
							&& (in_direction has mark_as_room)
							&& (in_direction.vector > 0)
							&& ((filter == 0) || (filter(in_direction)))) {
							obj.vector = dir | WORD_HIGHBIT;
							! print "* ", (the) obj, " vector is ", (the) dir, "^";
							progressed = true;
							continue;
						}
						if (use_doors && (in_direction ofclass K4_door) &&
							((use_doors & 2) ||
							 (in_direction has open) ||
							 ((in_direction has openable) && (in_direction hasnt locked)))) {
							sl = location; location = obj;
							through_door = in_direction.door_to();
							location = sl;
							! print "Through door is ", (the) through_door, "^";
							if ((through_door)
								&& (through_door has mark_as_room)
								&& (through_door.vector > 0)
								&& ((filter == 0) || (filter(through_door)))) {
								obj.vector = dir | WORD_HIGHBIT;
								! print "* ", (the) obj, " vector is ", (the) dir, "^";
								progressed = true;
								continue;
							}
						}
					}
		objectloop (obj has mark_as_room) obj.vector = obj.vector &~ WORD_HIGHBIT;
		if (from.vector) return from.vector;
		if (progressed == false) return from.vector;
	}
];

[ SlowCountRouteTo from to filter use_doors obj i;
	if (from == nothing) return -1;
	if (to == nothing) return -1;
	if (from == to) return 0;
	if (from has mark_as_room && to has mark_as_room) {
		obj = MapRouteTo(from,to,filter,use_doors);
		if (obj == nothing) return -1;
		i = 0; obj = from;
		while ((obj ~= to) && (i<NUM_ROOMS)) { i++; obj = MapConnection(obj,obj.vector); }
		return i;
	}
	return -1;
];

[ SlowLengthRouteTo from to filter use_doors obj i d;
	if (from == nothing) return -1;
	if (to == nothing) return -1;
	if (from == to) return 0;
	if (from has mark_as_room && to has mark_as_room) {
		obj = MapRouteTo(from,to,filter,use_doors);
		if (obj == nothing) return -1;
		i = 0; d=0; obj = from;
		while ((obj ~= to) && (i<NUM_ROOMS)) { if (obj.vector == DirectionObject_1 || obj.vector == DirectionObject_2 || obj.vector == DirectionObject_4 || obj.vector == DirectionObject_5) d=d+diagonal_length; else d=d+orthogonal_length; i++; obj = MapConnection(obj,obj.vector); }
		return d;
	}
	return -1;
];
#ENDIF;

-) instead of "Slow Route-Finding" in "Relations.i6t".
1 Like

Thanks Peter. I’ve run an experiment with your code in a 4 x 4 grid that’s connected orthogonally and diagonally. I found a square where it gives the wrong advice, but in the equivalent square on the other axis, it gives the correct advice - and other anomalies - making me think that either (a) there’s something about the order the rooms or connections are defined in the source that’s still affecting things, or (b) I don’t quite understand how your code works.

I’ve pasted the source here:

Summary
AA is a Room. AB is east of AA. AC is east of AB. AD is east of AC.

BA is a Room. BB is east of BA. BC is east of BB. BD is east of BC.
BA is north of AA. BB is north of AB. BC is north of AC. BD is north of AD.

CA is a Room. CB is east of CA. CC is east of CB. CD is east of CC.
CA is north of BA. CB is north of BB. CC is north of BC. CD is north of BD.

DA is a Room. DB is east of DA. DC is east of DB. DD is east of DC.
DA is north of CA. DB is north of CB. DC is north of CC. DD is north of CD.

BB is northeast of AA. BB is northwest of AC.
BC is northeast of AB. BC is northwest of AD.

CB is northeast of BA. CB is northwest of BC.
CC is northeast of BB. CC is northwest of BD.

DB is northeast of CA. DB is northwest of CC.
DC is northeast of CB. DC is northwest of CD.

DA is northwest of CB. DD is northeast of CC.
BA is northwest of AB. BD is northeast of AC.

CA is northwest of BB. CD is northeast of BC.



TARGET is initially DD.[set this variable to the room you want the game to track you towards.]

Section - Testing

When play begins:
	follow the distance meter rule;

Every turn (this is the distance meter rule):
	now use-diagonals is true;
	say "the best way to [TARGET] using diagonals is [best route from the location to TARGET] - distance [distance from the location to TARGET] metres.";
	now use-diagonals is false;
	say "the best way to [TARGET] orthogonally is [best route from the location to TARGET]- distance [distance from the location to TARGET] metres.";

Chapter - Setup

Section - I7

Use slow route-finding.

Use-diagonals is a truth state that varies.	
The use-diagonals variable translates into I6 as "use_diagonals".
Diagonal-length is a number that varies.
The diagonal-length variable translates into I6 as "diagonal_length".
Orthogonal-length is a number that varies.
The orthogonal-length variable translates into I6 as "orthogonal_length".
To decide which number is distance from (R1 - object) to (R2 - object),
	using doors or using even locked doors:
	(- SlowLengthRouteTo({R1},{R2},0,{phrase options}) -).
To decide which number is distance from (R1 - object) to (R2 - object) through
	(RS - description of objects),
	using doors or using even locked doors:
	(- SlowLengthRouteTo({R1},{R2},{RS},{phrase options}) -).

Section - I6
	
Include (-
Global use_diagonals = true ;
Global diagonal_length = 7;
Global orthogonal_length = 5;
-) after "Definitions.i6t".

Include (-

! ==== ==== ==== ==== ==== ==== ==== ==== ==== ====
! Relations.i6t: Slow Route-Finding
! ==== ==== ==== ==== ==== ==== ==== ==== ==== ====


#ifndef FAST_ROUTE_FINDING;
[ SlowRouteTo from to filter use_doors  obj dir in_direction progressed sl through_door;
	if (from == nothing) return nothing;
	if (to == nothing) return nothing;
	if (from == to) return nothing;
	objectloop (obj has mark_as_room) obj.vector = 0;
	to.vector = 1;
	! print "Routing from ", (the) from, " to ", (the) to, "^";
	while (true) {
		progressed = false;
		! print "Pass begins^";
		objectloop (obj has mark_as_room)
			if ((filter == 0) || (filter(obj)))
				if (obj.vector == 0)
				!  ######## alteration starts here
					objectloop (dir ofclass K3_direction && (use_diagonals || (dir ~= DirectionObject_1 && dir ~= DirectionObject_2 && dir ~= DirectionObject_4 && dir ~= DirectionObject_5))) {
				!  ######## alteration finishes here
						in_direction = Map_Storage-->((obj.IK1_Count)*No_Directions + dir.IK3_Count);
						if (in_direction == nothing) continue;
						! print (the) obj, " > ", (the) dir, " > ", (the) in_direction, "^";
						if ((in_direction)
							&& (in_direction has mark_as_room)
							&& (in_direction.vector > 0)
							&& ((filter == 0) || (filter(in_direction)))) {
							obj.vector = dir | WORD_HIGHBIT;
							! print "* ", (the) obj, " vector is ", (the) dir, "^";
							progressed = true;
							continue;
						}
						if (use_doors && (in_direction ofclass K4_door) &&
							((use_doors & 2) ||
							 (in_direction has open) ||
							 ((in_direction has openable) && (in_direction hasnt locked)))) {
							sl = location; location = obj;
							through_door = in_direction.door_to();
							location = sl;
							! print "Through door is ", (the) through_door, "^";
							if ((through_door)
								&& (through_door has mark_as_room)
								&& (through_door.vector > 0)
								&& ((filter == 0) || (filter(through_door)))) {
								obj.vector = dir | WORD_HIGHBIT;
								! print "* ", (the) obj, " vector is ", (the) dir, "^";
								progressed = true;
								continue;
							}
						}
					}
		objectloop (obj has mark_as_room) obj.vector = obj.vector &~ WORD_HIGHBIT;
		if (from.vector) return from.vector;
		if (progressed == false) return from.vector;
	}
];

[ SlowCountRouteTo from to filter use_doors obj i;
	if (from == nothing) return -1;
	if (to == nothing) return -1;
	if (from == to) return 0;
	if (from has mark_as_room && to has mark_as_room) {
		obj = MapRouteTo(from,to,filter,use_doors);
		if (obj == nothing) return -1;
		i = 0; obj = from;
		while ((obj ~= to) && (i<NUM_ROOMS)) { i++; obj = MapConnection(obj,obj.vector); }
		return i;
	}
	return -1;
];

[ SlowLengthRouteTo from to filter use_doors obj i d;
	if (from == nothing) return -1;
	if (to == nothing) return -1;
	if (from == to) return 0;
	if (from has mark_as_room && to has mark_as_room) {
		obj = MapRouteTo(from,to,filter,use_doors);
		if (obj == nothing) return -1;
		i = 0; d=0; obj = from;
		while ((obj ~= to) && (i<NUM_ROOMS)) { if (obj.vector == DirectionObject_1 || obj.vector == DirectionObject_2 || obj.vector == DirectionObject_4 || obj.vector == DirectionObject_5) d=d+diagonal_length; else d=d+orthogonal_length; i++; obj = MapConnection(obj,obj.vector); }
		return d;
	}
	return -1;
];
#ENDIF;

-) instead of "Slow Route-Finding" in "Relations.i6t".

You start at AA (bottom left) and it tells you the target details for going to DD every turn. So you can move around and read its advice. Check the world map to verify the connections are OK.

I found that in square AC, it recommends a move northwest if you want to use diagonals. Here, the shortest path is actually northeast, then north, then north.

Au contraire, in square CA, it’s happy to send you on a path of east, east, northeast, which is a logical one.

Similar happy situation in DA, where the diagonals advice is to go east.

But in AD - the advice for diagonals is again to go northwest. I suppose this gels with your original advice on using this code which was compare the orthoganal (ugh, typing that word!..) distance to the diagonal, and take the orthogonal if it’s shorter. But sometimes the advice using diagonals is an orthogonal direction anyway, and the logical one, so I don’t get it.

-Wade

As a PS to my original post, I’ve now discovered that compiling the very same project (my actual project, not any of the examples in this thread) with or without slow route-finding can change when it will zig or zag diagonally on its way to a target that’s in a straight line!

When I don’t use slow route-finding, it zigs around the centre square on a vertical journey, but not a horizontal one.

When I do use slow route-finding, it zigs around the centre square on a horizontal journey, but not a vertical one.

-Wade

This isn’t true- there are a number of equally short paths of 3 moves:
AC->BD->CD->DD
AC->BD->CC->DD
AC->BC->CD->DD
AC->BC->CC->DD
AC->BB->CC->DD

It is a recognised ‘feature’ of Inform’s route-finding that the route it returns as ‘the best’ when there are a number of equally short routes is officially undefined. Similarly, since the algorithm is different, the ‘best route’ returned by slow and fast route-finding may not be the same, although they will be the same number of moves. ‘Using diagonals’ does not suggest that a route including or starting with diagonals will be returned- you have to assume that any ‘equal shortest’ route might be returned.

Oh, you’re talking about number of moves, not distance. Okay.

I hoped the spirit of my mission was clear from the first post, but perhaps it hasn’t been. I don’t like that northwest move from AC because to a human’s eyes, we moved away from the target (west), when the target is to the east, and we had a choice where another path with the same number of moves didn’t do that human-illogical thing.

If the target’s to the east and we’re in a grid like this demo one, I never want a western move. And similarly, if the target can be reached in an orthogonally straight line, I never want a diagonal move. These are the problems I’m querying if it’s possible to solve by fiddling with Inform’s pathfinding.

-Wade

Not without a wholesale rewrite of route-finding: the algorithms Inform uses don’t work in that way. They think only in terms of minimising moves.

You can, by the method I suggested, choose an orthogonal route if it’s available, which will also by the nature of orthogonal routes always tend to move toward the target when it’s possible, but including diagonals all bets are off I fear.

If you think of your map grid as being like the London Underground map, where the positions of the stations on the map reveals only a little about their actual spatial arrangement and proximity above-ground, and therefore the quickest way to walk from one to another, it may make that northwest move feel less painful!

1 Like

Ha! That gave me a good laugh. Thanks for the overview though.

Not all of my game is going to be as troubled by this as the grid. So for instance in my first chapter, I already kludge my way around that ‘dancing around the centre square’ problem I’ve been talking about. I may be able to do a bit of that later, and also make use of your orthoganl code here, to continue to tackle the issue.

-Wade

My only other thought to reduce your angst is to change your grid to a hexagonal one, where north and south are not mapped:


      A - B - C
     / \ / \ / \ 
    D - E - F - G
     \ / \ / \ /
      H - I - J

That way the shortest route is always towards the target (as a human would see it)

OK, test this.

After a bit of research I have found an easy way to modify the fast route-finding algorithm so that it weights diagonal moves and orthogonal moves (by default, 7 & 5 respectively- but you can change this by changing global variables diagonal-length and orthogonal-length (integers only)). Setting both diagonal-length and orthogonal-length to 1 will replicate normal fast route-finding behaviour.

NB 1: if compiling for Z-machine, this will limit the maximum path length you can trace to a few hundred rooms (choosing smaller values for diagonal-length and orthogonal-length will increase this, and vice versa).

NB 2: ‘the number of moves from X to Y’ will now return (orthogonal_length x orthogonal moves) + (diagonal_length x diagonal_moves) rather than the number of discrete moves from room to room.

NB 3: This presently has an uncomfortable hard-coded dependency on diagonal directions being the 2nd, 3rd, 5th & 6th to be declared in the template, which is true for 6M62, but may break with updates or modification to “Output.i6t: Object Tree”.

With a bit more work this dependency could be removed, and a system even set up whereby named directions had individual and/or dynamically updateable weightings- for example, to dissuade from route-finding in northerly directions in a snowstorm…

"________Diagonals" by PB

AA is a Room. AB is east of AA. AC is east of AB. AD is east of AC.

BA is a Room. BB is east of BA. BC is east of BB. BD is east of BC.
BA is north of AA. BB is north of AB. BC is north of AC. BD is north of AD.

CA is a Room. CB is east of CA. CC is east of CB. CD is east of CC.
CA is north of BA. CB is north of BB. CC is north of BC. CD is north of BD.

DA is a Room. DB is east of DA. DC is east of DB. DD is east of DC.
DA is north of CA. DB is north of CB. DC is north of CC. DD is north of CD.

BB is northeast of AA. BB is northwest of AC.
BC is northeast of AB. BC is northwest of AD.

CB is northeast of BA. CB is northwest of BC.
CC is northeast of BB. CC is northwest of BD.

DB is northeast of CA. DB is northwest of CC.
DC is northeast of CB. DC is northwest of CD.

DA is northwest of CB. DD is northeast of CC.
BA is northwest of AB. BD is northeast of AC.

CA is northwest of BB. CD is northeast of BC.



TARGET is initially DD.[set this variable to the room you want the game to track you towards.]

Section - Testing

When play begins:
	follow the distance meter rule;

Every turn (this is the distance meter rule):
	say "the best way to [TARGET]  is [best route from the location to TARGET] in [the number of moves from the location to TARGET] paces.";


Chapter - Setup

Section - I7

Use fast route-finding.

Diagonal-length is a number that varies.
The diagonal-length variable translates into I6 as "diagonal_length".
Orthogonal-length is a number that varies.
The orthogonal-length variable translates into I6 as "orthogonal_length".

Section - I6
	
Include (-
Global diagonal_length = 7;
Global orthogonal_length = 5;
-) after "Definitions.i6t".

Include (-
Replace MapRouteTo;
-) after "Definitions.i6t".
	

Include (-			

[ MapRouteTo from to filter use_doors count  oy oyi ds;
	! print "^   (new MapRouteTo called with count=",count,")...^";
	!for (ds=0: ds<No_Directions: ds++) {
	!	oyi=0; objectloop (oy ofclass K3_direction) {
	!	if (oyi== ds) print ds, ": ",(name) oy;
	!	oyi++;
	!	}
	!}
	if (from == nothing) return nothing;
	if (to == nothing) return nothing;
	if (from == to) return nothing;
	if ((filter) && (filter(from) == 0)) return nothing;
	if ((filter) && (filter(to) == 0)) return nothing;
	if ((last_filter ~= filter) || (last_use_doors ~= use_doors)) map_has_changed = true;
	oyi = 0;
	objectloop (oy has mark_as_room) {
		if ((filter == 0) || (filter(oy))) {
			if (oy.room_index == -1) map_has_changed = true;
			oy.room_index = oyi++;
		} else {
			if (oy.room_index >= 0) map_has_changed = true;
			oy.room_index = -1;
		}
	}
	oyi = 0;
	objectloop (oy ofclass K4_door) {
		ds = false;
		if ((use_doors & 2) ||
			(oy has open) || ((oy has openable) && (oy hasnt locked))) ds = true;
		if (DoorRoutingViable->oyi ~= ds) map_has_changed = true;
		DoorRoutingViable->oyi = ds;
		oyi++;
	}
	if (map_has_changed) {
		#ifdef FAST_ROUTE_FINDING; ComputeFWMatrix(filter, use_doors); #endif;
		map_has_changed = false; last_filter = filter; last_use_doors = use_doors;
	}
	#ifdef FAST_ROUTE_FINDING;
	if (count) return FastCountRouteTo(from, to, filter, use_doors);
	return FastRouteTo(from, to, filter, use_doors);
	#ifnot;
	if (count) return SlowCountRouteTo(from, to, filter, use_doors);
	return SlowRouteTo(from, to, filter, use_doors);
	#endif;
];

-) after "Output.i6t".

Include (-

! ==== ==== ==== ==== ==== ==== ==== ==== ==== ====
! Relations.i6t: Fast Route-Finding
! ==== ==== ==== ==== ==== ==== ==== ==== ==== ====

#ifdef FAST_ROUTE_FINDING;
Array FWMatrix --> NUM_ROOMS*NUM_ROOMS;

[ FastRouteTo from to filter use_doors diri i dir oy;
	if (from == to) return nothing;
	i = (FWMatrix-->(from.room_index*NUM_ROOMS + to.room_index))/No_Directions;
	if (i == 0) return nothing;
	diri = (FWMatrix-->(from.room_index*NUM_ROOMS + to.room_index))%No_Directions;
	i=0; objectloop (dir ofclass K3_direction) {
		if (i == diri) return dir;
		i++;
	}
	return nothing;
];

[ FastCountRouteTo from to filter use_doors  k;
	if (from == to) return 0;
	k = (FWMatrix-->(from.room_index*NUM_ROOMS + to.room_index))/No_Directions;
	if (k == 0) return -1;
	return k;
];

[ ComputeFWMatrix filter use_doors  oy ox oj axy ayj axj dir diri nd row w; ! #### w for weighting direc tions
	objectloop (oy has mark_as_room) if (oy.room_index >= 0)
		objectloop (ox has mark_as_room) if (ox.room_index >= 0)
			FWMatrix-->(oy.room_index*NUM_ROOMS + ox.room_index) = 0;

	objectloop (oy has mark_as_room) if (oy.room_index >= 0) {
		row = (oy.IK1_Count)*No_Directions;
		for (diri=0: diri<No_Directions: diri++) {
			ox = Map_Storage-->(row+diri);
			if ((ox) && (ox has mark_as_room) && (ox.room_index >= 0)) {
			!##### modifed code begins
				if (diri == 1 || diri == 2 || diri == 4 || diri == 5) w=diagonal_length; else w=orthogonal_length; 
			!##### this depends on diagonal directions being the 2nd, 3rd, 5th & 6th to be declared
				FWMatrix-->(oy.room_index*NUM_ROOMS + ox.room_index) = No_Directions*w + diri;
			!#### modified code ends
				continue;
			}
			if (use_doors && (ox ofclass K4_door) &&
				((use_doors & 2) || (DoorRoutingViable->(ox.IK4_Count)))) {
				@push location; location = oy;
				ox = ox.door_to();
				@pull location;
				if ((ox) && (ox has mark_as_room) && (ox.room_index >= 0)) {
			!##### modifed code begins
				if (diri == 1 || diri == 2 || diri == 4 || diri == 5) w=diagonal_length; else w=orthogonal_length; 
			!##### this depends on diagonal directions being the 2nd, 3rd, 5th & 6th to be declared
					FWMatrix-->(oy.room_index*NUM_ROOMS + ox.room_index) = No_Directions*w + diri;
			!#### modified code ends
					continue;
				}
			}
		}	
	}

	objectloop (oy has mark_as_room) if (oy.room_index >= 0)
		objectloop (ox has mark_as_room) if (ox.room_index >= 0) {
			axy = (FWMatrix-->(ox.room_index*NUM_ROOMS + oy.room_index))/No_Directions;
			if (axy > 0)
				objectloop (oj has mark_as_room) if (oj.room_index >= 0) {
					ayj = (FWMatrix-->(oy.room_index*NUM_ROOMS + oj.room_index))/No_Directions;
					if (ayj > 0) {
						!print "Is it faster to go from ", (name) ox, " to ",
						!   (name) oj, " via ", (name) oy, "?^";
						axj = (FWMatrix-->(ox.room_index*NUM_ROOMS + oj.room_index))/
							No_Directions;
						if ((axj == 0) || (axy + ayj < axj)) {
							!print "Yes^";
							FWMatrix-->(ox.room_index*NUM_ROOMS + oj.room_index) =
								(axy + ayj)*No_Directions +
								(FWMatrix-->(ox.room_index*NUM_ROOMS + oy.room_index))%
									No_Directions;
						}
					}
				}
		}
];
#ENDIF;

-) instead of "Fast Route-Finding" in "Relations.i6t".

1 Like

Thanks Peter. I’ve had various delays, but also (ironically, or maybe not) my fiddling with this stuff has caused me to fiddle with other systems in my project, and right now I want to stick with my one case kludge over the global system I actually asked for. However, obviously it’s very cool that you’ve developed this and it’s going to help me and or others.

-Wade

2 Likes

Fair enough. It’s been an interesting diversion and I’ve learned things about I7, the template and topology along the way. An extension regarding enhanced route-finding beckons if I can find the time…

1 Like