TLpath

About

TLpath adds pathfinding to LÖVE! It uses an optimized implementation of the excellent A* search algorithm used in many commercial games. It comes with a demo which demonstrates its ability to find optimal paths in as little as 0.015 seconds in mazes comprised of over fifty nodes. TLpath uses threading, meaning it will only work in Love2D version 0.7.1 or higher, and requires TSerial (included).

It's under the ZLIB license.

Download

Direct from Dropbox

Contact

• Forum thread
• Taehl - SelfMadeSpirit@gmail.com

Setup

Everything in the module is contained in the TLpath namespace, so don't worry about it messing with your global variables. It does its work in a separate thread, allowing the host game to continue running normally.

1. Put TLpath.lua and TSerial.lua in your game's folder
2. At the top of main.lua, add the line require"TLpath"
3. In love.update(), add the line TLpath.update()

FAQ

Q) What are nodes?

A) A*, like nearly every pathfinding algorithm, uses nodes for increased speed. They are simply points which have connections to other nodes. In TLpath, they are expected to be a list of tables, for example, {{x=1,y=1}, {x=5,y=3}, {x=2,y=8}, {x=9,y=6}}. Technically speaking, nodes don't need x and y values, but may contain any relevant information. Nodes may also have a dests table, which contains the indexen of reachable nodes and the g-factor of that connection.

Q) What's a g-factor? An h-factor? An f-factor?

A) I would highly recommend you read about the A* algorithm on the Wikipedia for an explanation.

Q) Can TLpath use different functions to calculate g- and h-factors?

A) Yes, with TLpath.setGfunction() and TLpath.setHfunction()

Q) My game has node relationships which are too complex to calculate in one function. Can I set them myself?

A) Yes. If you TLpath.calcNodes() a list of nodes which already have dests tables, the tables will be left alone. Dests are required to be in form of node.dests = {neighbor_index = g_factor_number}.

Q) What's the difference between dynamic and static nodes?

A) Static nodes pre-calculate the node graph and g-factors, allowing all pathfinding calculations to be faster, but this calculation may take a moment to complete (your game won't freeze during this time). Dynamic nodes don't have this delay, but it will take longer to find paths. Static mode is generally preferable, unless your game frequently changes nodes and/or their connections.

Q) How do I know what TLpath is doing? What happens if it has an error?

A) TLpath updates the string TLpath.status with messages detailing what it's doing (including timing information if love.timer is available). If TLpath or its thread has an error, it will summon the standard Love2D error screen.

Functions

TLpath.calcNodes

TLpath.calcNodes(nodes, dynamic)

This function updates the node graph that TLpath uses. Use it whenever the nodes or their connections change. Non-dynamic nodes take a moment to calculate, but are generally preferable to dynamic ones.

table nodes

A list of nodes. For example: {{x=1,y=1}, {x=5,y=3}, {x=2,y=8}, {x=9,y=6}}

boolean dynamic

If true, node relationships won't be pre-calculated, allowing paths to start being calculated instantly and under changing conditions, but take longer than static nodes. Non-dynamic nodes are recommended.

TLpath.setGfunction

TLpath.setGfunction(f)

This function is used to specify the g-function. The g-function is called to determine whether a node can reach another, and how "expensive" the resulting path will be. This will likely need to be changed to suit your game.

string f

A string which is Lua code for a function that will be called when calculating the node graph. The function is passed two nodes as parameters and is expected to return either nil (if a path can't extend from the first to the second) or a number (the g-factor of the path). By default, it is [[local d = ((b.x-a.x)^2+(b.y-a.y)^2)^0.5 return d<=100 and d or nil]], which means that nodes can only be traveled between if they're less than 100 pixels apart.

TLpath.setHfunction

TLpath.setHfunction(f)

Much like TLpath.setGfunction(), except for calculating the heuristic factor of a node to the goal. This function must return a number which is less than or equal to (NOT greater than) the actual cost of a path from the node to the goal. The closer the h-factor is to the real cost of the path, the faster pathfinding calculations will be. The default h-function simply calculates the distance between the node and the goal, which is fast and should be fine for most games.

string f

Defaults to [[return ((goal.x-a.x)^2+(goal.y-a.y)^2)^0.5]].

TLpath.findPath

TLpath.findPath(ent, goal)

This function tells TLpath to calculate a path from ent to goal, where ent is a table that includes a path list, and goal is a node index. Paths are calculated one at a time in the order they're requested, and may take a little bit of time to find, so there may be a small delay between requesting a path and receiving it. When a path is found, the path table of ent will be updated. If the goal isn't able to be reached from ent's current position, ent.path.unreachable will equal true and the ent's current path will be left unchanged.

table ent

A table which includes a paths table which lists at least one node index (i.e., where the ent is currently located).

number goal

The index of the goal node (that is, nodes[goal] = the desired node).

TLpath.cancelPathfinding

TLpath.cancelPathfinding()

Calling this will empty the pathfinding queue and cancel any currently-processing searches. TLpath.calcNodes automatically calls it to prevent bizarre behavior that emerges from changing the node graph while in the middle of finding a path.

TLpath.update

TLpath.update()

Call this in love.update() to handle TLpath's events (path request spooling, receiving data from thread, etc.).