Pathfinding Experiment

[llamazing]

I've been working on an experiment in pathfinding that has given good results. It uses a network of "navigation beacon" entities distributed on a map and calculates an optimal path to get from point A to B assuming both are in range of beacons connected in the same network.

I still have some ideas to develop things further, but it's far enough along to make a playable demo, so I thought I'd share. Screenshots won't do this one justice, so check it out if it sounds like something that would interest you.

Solarus v1.6 is required (and it indeed makes use of some cool new features ).

https://gitlab.com/llamazing/pathfinder

[llamazing]

The project gitlab page wiki describes how the algorithm works here.

A top-level overview of the node_map.lua script can be found here. This is the one script you'll want to copy to your own quest to implement the pathfinding.

To implement in your own quest, import the scripts/node_map.lua script. Then add a network of nodes in the map you want to try it on. They can be any entity with the prefix "node_", but you'll want to use something stationary. I find custom entities with the default size and origin work well.

Nodes get linked to other nearby nodes automatically if they are on the same layer. They must be within 13 tiles (208 pixels) to be linked, although you can change this value (MAX_RANGE) in node_map.lua if you want. I created the node_range sprite to aid in determining the max distance away. Center it on an existing node to see how far away another node can be placed and still be linked. You can delete it once all your nodes are placed.

Then use the script like this:

Code (lua) Select Expand


local node_map = require"scripts/node_map"
local mapping = node_map:new_mapping(dst_x, dst_y, dst_layer) --these are the coordinates of the final destination
local next_x, next_y, next_layer, distance, action = mapping:next_node(x, y, layer) --these are the starting coordinates, returns intermediate destination for this segment of the route

So you'd call mapping:next_node() with the current position of the entity you want to move. First move the entity to the layer returned (which may be different than the present layer if currently at a "stairs" node). Then setup a target movement to the returned coordinates, unless the value of action returned is "teletransporter", in which case you'd want to instantly move the entity to the returned coordinates. The return value for action is normally nil. The distance return gives the total route distance remaining (in pixels) until reaching the final destination.

Once the entity finishes the movement, call mapping:next_node() again, this time giving the entity's (new) current position and repeat until the entity arrives at the final destination.

For it to work, the entity has to be within range of a node that's also on its current layer, and the destination has to be within range of another node in that same network (also on the same layer as that node). It's possible to have multiple groups of nodes on the same map that are not connected to each other if none of their nodes are in range of each other. A route between separate node networks will not be found unless there happens to be a teletransporter node present in both networks.

[llamazing]

I discovered that running this quest on a new machine produces an error because it expects a "maps" directory to exist in the quest write directory, which won't be there on a fresh install.

If anyone was getting this error, it should be fixed now (the script now explicitly creates the directory it needs).

[llamazing]

I added teletransporter nodes to the master branch. Seeing the path drawn on the map while a teletransporter is used in the route is so cool!

All teletransporter type nodes get linked with every other teletransporter node on the map regardless of the layer or distance apart. To add one to your own map, simply add the custom property "node_type" with a value of "teletransporter" to an existing node (any entity with the prefix "node_").

I also added "stairs" nodes that link multiple layers. For these add the custom property "layers" with the value being a list of layers that they bridge (separated by commas, spaces or both), e.g. "1, 2". Stairs do not use the "node_type" custom property (so it's possible for a node to be both a teletransporter and stairs). Stairs are not used in my example quest and have only limited testing.

The second post is updated to give info about using the script in your own quest as well as some details about how the algorithm works.