[i7] pathfinding and memory usage

I have a few instances of pathfinding (i.e., “best route from X to Y”) in my current work. Although the map is pretty large (>100 rooms), the area where pathfinding happens is relatively small – it’s all within a defined region, where the distance between X and Y is never more than 2 or 3 moves (EDIT: okay, maybe 5 moves, max). Nevertheless, I’ve been noticing a significant lag every time pathfinding is invoked. I’m guessing the large map size is responsible for this, regardless of how close together X and Y are.

Anyone have any suggestions for how to counteract this? Is there a way to, I don’t know, “wall off” a region so that pathfinding doesn’t waste time chasing down routes all over the map? Or am I offbase about why the lag is happening?

If the map doesn’t change, you could precompute the routes and embed them in the program at compile time. You’d want the equivalent of a 2D array where you can lookup the next direction to go given the current room and the destination room as input. (I think the problem is VM “cpu” usage rather than memory as the size of the graph grows. This solution would trade off memory to hold the precomputed table against cpu at runtime.)

I haven’t speed-tested this, but try

the best route from the Kitchen to the Pantry through rooms in DefinedRegion;

That might limit the map-routing.

If that doesn’t work, you might have to hand-code your own pathfinding.

It just occurred to me that this shouldn’t be a taxing problem on the VM. I have no idea what the path finding logic looks like, but if I were implementing this, I’d copy the map off to some separate data structure and run the logic against that. We know the list of all locations.

Wait…is it because every move has to be tested for viability and that’s a relative thing. It’s entirely possible a location could be closed until the player moves somewhere other than where they are. Blah.

Has to be a better way.

EDIT: Sorry, there was no particular reason to make this a reply to Vince… originally I was thinking of something else.

Are you using fast route-finding (default for Glulx), and does the map change? If I’m not mistaken, fast route-finding computes and stores every map connection the first turn (or the first time it tries to find a route)… but if the map changes it has to recompute and store every map connection, which is slower. Whereas slow route-finding just calculates the route you want. So, somewhat paradoxically, if none of other stuff works maybe you might want to “Use slow route-finding” and see if that works.

In the following 100-room project with a changing map:

[spoiler][code]Rock1 is a room.
Rock2 is west of Rock1.
Rock3 is west of Rock2.
Rock4 is west of Rock3.
Rock5 is west of Rock4.
Rock6 is west of Rock5.
Rock7 is west of Rock6.
Rock8 is west of Rock7.
Rock9 is west of Rock8.
Rock0 is west of Rock9.
Rock11 is north of Rock1.
Rock12 is west of Rock11.
Rock13 is west of Rock12.
Rock14 is west of Rock13.
Rock15 is west of Rock14.
Rock16 is west of Rock15.
Rock17 is west of Rock16.
Rock18 is west of Rock17.
Rock19 is west of Rock18.
Rock10 is west of Rock19.
Rock21 is north of Rock11.
Rock22 is west of Rock21.
Rock23 is west of Rock22.
Rock24 is west of Rock23.
Rock25 is west of Rock24.
Rock26 is west of Rock25.
Rock27 is west of Rock26.
Rock28 is west of Rock27.
Rock29 is west of Rock28.
Rock20 is west of Rock29.
Rock31 is north of Rock21.
Rock32 is west of Rock31.
Rock33 is west of Rock32.
Rock34 is west of Rock33.
Rock35 is west of Rock34.
Rock36 is west of Rock35.
Rock37 is west of Rock36.
Rock38 is west of Rock37.
Rock39 is west of Rock38.
Rock30 is west of Rock39.
Rock41 is north of Rock31.
Rock42 is west of Rock41.
Rock43 is west of Rock42.
Rock44 is west of Rock43.
Rock45 is west of Rock44.
Rock46 is west of Rock45.
Rock47 is west of Rock46.
Rock48 is west of Rock47.
Rock49 is west of Rock48.
Rock40 is west of Rock49.
Rock51 is north of Rock41.
Rock52 is west of Rock51.
Rock53 is west of Rock52.
Rock54 is west of Rock53.
Rock55 is west of Rock54.
Rock56 is west of Rock55.
Rock57 is west of Rock56.
Rock58 is west of Rock57.
Rock59 is west of Rock58.
Rock50 is west of Rock59.
Rock61 is north of Rock51.
Rock62 is west of Rock61.
Rock63 is west of Rock62.
Rock64 is west of Rock63.
Rock65 is west of Rock64.
Rock66 is west of Rock65.
Rock67 is west of Rock66.
Rock68 is west of Rock67.
Rock69 is west of Rock68.
Rock60 is west of Rock69.
Rock71 is north of Rock61.
Rock72 is west of Rock71.
Rock73 is west of Rock72.
Rock74 is west of Rock73.
Rock75 is west of Rock74.
Rock76 is west of Rock75.
Rock77 is west of Rock76.
Rock78 is west of Rock77.
Rock79 is west of Rock78.
Rock70 is west of Rock79.
Rock81 is north of Rock71.
Rock82 is west of Rock81.
Rock83 is west of Rock82.
Rock84 is west of Rock83.
Rock85 is west of Rock84.
Rock86 is west of Rock85.
Rock87 is west of Rock86.
Rock88 is west of Rock87.
Rock89 is west of Rock88.
Rock80 is west of Rock89.
Rock91 is north of Rock81.
Rock92 is west of Rock91.
Rock93 is west of Rock92.
Rock94 is west of Rock93.
Rock95 is west of Rock94.
Rock96 is west of Rock95.
Rock97 is west of Rock96.
Rock98 is west of Rock97.
Rock99 is west of Rock98.
Rock90 is west of Rock99.

Every turn:
say “Rock90 is [best route from Rock0 to Rock90] from Rock0.”

After jumping:
let first room be a random room;
let second room be a random room;
change the southeast exit of the first room to the second room.

[Use slow route-finding.][/code][/spoiler]

each “jump” command took about three seconds in the IDE on a pretty new MacBook, but when “Use slow route-finding” was commented out there wasn’t any appreciable lag.

Before I added the bit where jumping changed the map connections, the first turn took three seconds but subsequent turns were instantaneous, as you’d expect if it was only computing all the routes once.

It’s a graph problem with a well-known solution (this assumes all edges have the same weight; we’d use a different algorithm like Dijkstra or Bellman-Ford if not), and the algorithm’s runtime increases as a function of the size of the map.

A question is whether we can run the algorithm once at compile time/game startup, or if we have to recompute the results every turn because the map is changing dynamically. If there were only a single dynamic passage (like a locked door), it might even make sense to precompute it both ways (at the cost of increased memory usage) and swap which precomputed data is used when the dynamic connection is opened or closed.

(matt w posted in the interim. What he said, also.)

This worked, by the way. Notable improvement. Thanks.