Have you ever wanted to know how to get from point A to point B in a game? Have you ever wondered how far away something is, or which direction to go to find it?

Attached is a simple library (and sample code illustrating) that determines paths between rooms. In its simplest form (GetPath), you pass a start room and an end room, and it will return a list of exits that must be traversed to get from start to end. It returns null if a path can not be found. The code is brute-force, but there is little alternative as there are no requirements for the topology of the rooms in a game.

There is a variant of this (GetRestrictedPath) which also takes a max length for the path. If the path has not been found within that length, it returns null. This allows for localized searches.

(There is also a more extended function - GetPathExt - which takes the list of exits to search, but that is for highly specialized sorts of searches. Yes, I have plans.)

Possible uses:
- To determine the path that must be followed, say for a moving NPC or to offer the player directional hints to a target.
- To determine how far apart (exit step wise) two items are.
- To determine if a room is within a certain distance of the player or whether the player is within range of some room or object.

You could use this to plot a path for an NPC to follow (either to a room or the player).

You could use it for environmental messages (e.g. if an object or room produces sound, you could have different messages for what the user hears depending on how far away it is.)

You could combine them both (e.g. "You hear steps approaching from the north. Run quick!")

The sample code is a simple "find the room" game. There are three levels of help: "off'" provides no directional messages, "gps" gives you the next step in your path (like a gps), and "full" shows all the steps in the path you must take. The message is printed after each turn. It also gives you "warm" and "hot" messages as you get close.

Let me know if there are any additions you'd like for this or if you encounter any bugs.

Enjoy!

(Edit: v0.7 attachment deleted)

Updated.

V0.8
- Renamed the functions to proper "lib" form (i.e. "PathLib_*")
- Added some convenience "get distance" functions, which just call GetPath and return the length of the path:
- PathLib_GetDistance(start, end)
- PathLib_GetRestrictedDistance(start, end, maxlength)
- PathLib_GetDistanceExt(start, end, exits, maxlength)

(Edit: v0.8 attachment deleted)

Updated.

v0.9

- Removed (broken) use of created objects.
- Speed optimizations. The code is considerably faster. (Fewer list searches; no created objects.)

Requires Quest 5.4.1.

Dear jaynabonne,

Would this script be compatible in games with multiple paths to a destination? Because I wish to use this code for my upcoming game "Welcome to Dream Valley" as a back-up to if the map system I'm trying to implement doesn't work. I plan on modifying it to where the player can set their destination (that they discovered), then follow the directions to that destination.

The library will find the shortest path from source to target. If there are multiple paths from one place to another, it just finds the first, shortest one. (If that's what you're asking.)

The sample app shows a sort of GPS mode, where at each step, it computes the shortest path and tells you what the next direction is. If you deviate from that and move such a new path is shorter, then you'll get the path instead.

Let me know if I answered your question.

jaynabonne wrote:The library will find the shortest path from source to target. If there are multiple paths from one place to another, it just finds the first, shortest one. (If that's what you're asking.)

The sample app shows a sort of GPS mode, where at each step, it computes the shortest path and tells you what the next direction is. If you deviate from that and move such a new path is shorter, then you'll get the path instead.

Let me know if I answered your question.

You did, and were around ten minutes late for the champagne we outta break out because it works! The destination of the GPS algorithm is set via a menu of locations the player has discovered. The only part I was worried about the time lapse between locations that is dependent on the player's level of agility, but it appears to work great.

Cool! I'm glad it worked for you.

Not sure, how this works? Can you make a sample with a NPC moving automatically from A to final room with just one command and that takes the shortest route?

Thanks Jay!

There is a bare bones sample in the zip that shows how to call the function (you just give it the start and end room and it gives back a list of exits to traverse), but let me see what I can do.

Actually, here is a simple function that steps an NPC toward a target room. You would just call it over and over (e.g. on each turn).

<function name="StepNPCTowardRoom" parameters="npc, targetroom">
   <![CDATA[
    list = PathLib_GetPath(npc.parent, targetroom)
    if (list <> null) {
        exit = list[0]
        npc.parent = exit.to
    }
    ]]>
</function>

Awesome Jay!!! A couple of things, if I create a turnscript there is an error when it reaches the destination because it keeps moving and if i print location in the first move it prints the location before and after moving.

Ah, ok. So when it reaches the end, you can either explicitly check for that (e.g. if npc.parent = targetroom), or you can check if the length of the list is 0. Here's the first way done:

<function name="StepNPCTowardRoom" parameters="npc, targetroom">
   <![CDATA[
    if (npc.parent <> targetroom) {
      list = PathLib_GetPath(npc.parent, targetroom)
      if (list <> null) {
          exit = list[0]
          npc.parent = exit.to
      }
    }
    ]]>
</function>