To use this script, the first thing you'll want to do is place a bunch of nodes (a custom entity with a prefix of "node_") on your Solarus map along the routes you want your entities to travel. This would typically be roads or paths in a village, for example. Nodes automatically get connected to other nodes within a radius of 208 pixels (13 tiles), though they must both be on the same layer. Think of nodes as signposts that point to each of the other nearby signposts (though the nodes don't need to be visible to the player).
Once you have an entire network of nodes placed, it now becomes possible to navigate from any point within range of any node to any other point in range of another node (provided both nodes are part of the same network). The entity being moved will first travel directly to a nearby node and then travel node to node until eventually reaching a node nearby the destination, moving directly from the last node to the destination.
Note: It is possible to have multiple and separate node networks within the same map, in which case both function independently of each other and it won't be possible to find a route from one to the other if there aren't nodes linking them together.
These pathfinding scripts do not provide any obstacle avoidance at all, though it shouldn't be too difficult to amend it in with your own script if you really need it. The nodes are all expected to be at fixed positions, so don't make a moving entity a node. If you need to reconfigure the position of the nodes on the map, it is possible to move them (or perhaps disable/enable one to block/open a particular path), in which case you just have to manually rescan all the nodes on the map for the pathways to get updated.
The way the algorithm works is it calculates the total distance from every node to target coordinates in range of at least one node and generates a mapping. If you have two entities that you want to move to the same location, they can share the same mapping (regardless of where they start from as long as both are in range of a node). On the other hand, if you have two entities that each need to be moved to different destinations, then you'll need to generate 2 separate mappings (even if the entities start from the same location).
Step 1: Find all Nodes on Current Map
The script looks for all map entities with the prefix "node_" and stores them in a table. Then it makes connections between nodes with distances that are less than or equal to 13 tiles (208 pixels) apart.
Note: This step is performed automatically each time you load a map. You can re-run it manually if you move the position of any nodes.
Step 2: Mapping the Nodes to a Specified Location
Next you tell it where you want to go by specifying a pair of map coordinates in pixels.
It then calculates the cumulative distance from every node to those coordinates. So if the first node is 8 tiles away, and the second node is 10 tiles from the first, then the second node is considered 18 tiles away from the destination. Maybe there's an alternate route where the second node is 9 tiles away from a third node, and that node is only 7 tiles away from the destination coordinates. In that case, once it checks that alternate route, it will change the cumulative distance for node 2 from 18 to 16 tiles. Then eventually it will have found the shortest cumulative distance for every node to those coordinates, and it stores that data in an internal table.
A more detailed description of the algorithm used can be found here.
A mapping object will be returned that retains the distance calculations associated with these destination coordinates. This mapping object is only useful for finding a route to these specific coordinates. If you later need to go somewhere else, then generate a new mapping object for those new coordinates.
The mapping object will no longer be useful once you switch maps and thus should be discarded.
Step 3: Find the Best Node Leading to the Destination from Your Current Location
The last step is to tell it where you currently are, and it returns the coordinates of the optimal node that you should move to on a route leading to the destination. It also returns the total route distance that this node is away from the final destination.
To determine that node, it first finds all nodes within 13 tiles of your current location. Then among those, it simply returns whichever one has the lowest cumulative distance to the destination.
This is an iterative processes, so once you reach the node it specified, you would call the function again, this time giving your new position. Then a new node is returned which is closer to the destination than the current node. You continue this process until you eventually reach the destination.
Note: The pathfinding script only tells you which node to go to in order to get closer to your destination (and once you've reached that node you ask it which node you should go to next). You are responsible for generating movements to get the entity to the node(s).
Keep in mind that in order to find the next node, your current location and the destination both have to be within range of nodes connected to the same node network.
Note: If you have multiple map entities that you want to move to the same destination coordinates using the node network, then you can share the same mapping object for both.
If you have map entities that you want to move to different coordinates, then you will need to generate separate mapping objects for each entity.
Find entire route upfront
If you want to get the full route to the destination instead of getting one segment of the journey each time, then you can instead call:
Get the total route distance from a node to the final destination
If you want to see how far a specific node is from the final destination coordinates (number in pixels), you can use the following:
Where the mapping object has be set for the desired destination and node is a map entity for one of the nodes.
If the specified node is not connected to the same node network as the destination, then it returns nil.
Iterate through nodes in the same network
To iterate through all the nodes connected to the same node network as the destination coordinates of the mapping object, use the following:
fori,nodeinmapping:iter_nodes()do--add your code hereend
Here i (number, integer, positive) is the index of the node, and node is the map entity for the node. The order of the iteration is starting with the node that has the lowest total route distance to the destination and in ascending order to the farthest one.
If you only want to know the number of nodes in the network then you can simply use:
Special Node Types
Nodes are normally only connected to other nodes that are both in range and on the same layer. Stairs nodes, however, can span multiple layers and are connected to other nodes in range that are on any of those layers.
To designate a node to behave as stairs, add the custom property "layers" and for its value list all the layers that it should be connected to, using commas or spaces (or both) to separate each one (e.g. "1, 2, 3").
When a stairs node is used to change layers, the layer variable returned by node_map:next_node() will be a number giving the new layer to transition to (when the entity being moved is at the stairs node).
Teletransporter nodes provide a way to instantly travel between two nodes regardless of which layer they are on or the distance apart. A teletransporter node is connected to every other teletransporter node on the map.
To designate a node to behave as a teletransporter, add the custom property "node_type" with a value of "teletransporter".
When traveling between two teletransporter nodes, node_map:next_node() will return an action variable with a value of "teletransporter" indicating that the travel to the next node should be instant.