Simple Pathfinding Tutorial in Lua / LÖVE

Path finding and navigation in Lua can be tricky. But there is no need to reinvent the wheel or create your own algorithm. You can however choose from the existing algorithms you will be using – whether it’s A* (A star), Dijkstra, Breadth-first search (BFS) or others.

If you are developing a game in Lua or LÖVE 2D engine, just use Roland Yonaba’s well-tested Jumper library. This library provides you with a simple API – a couple of functions that will cover all your path finding needs for any of your games.

What algorithms Jumper supports?

It support the following algorithms:

A* (A star)
Dijkstra
Theta* (Theta star)
Breadth-first search (BFS)
Depth-first search (DFS)
Jump point search (JPS)

You can read about their differences on Wikipedia, but usually Jump point or A star will work for most of the games.

Bi-directional or diagonal movement?

Jumper supports both types of movement. Bi-directional is coded as ORTHOGONAL, diagonal is DIAGONAL.

Tutorial with simple example

You can just hardcode a walkable value like this for a simple map:

walkable=' ' -- space character is passable in our grid, others are not

Then create your grid object, a simple Lua table with a two dimensional matrix of values that contain paths and walls. For our use walls will be marked as * and paths as ” ” (space character).

-- create grid with 9 rows and 8 columns
grid={
    {'*',' ','*','#',' ','*','*','*'},
    {'*',' ','*','*','*',' ','*','#'},
    {'*',' ',' ',' ','*',' ',' ','*'},
    {'*','*','*',' ','*','*',' ','*'},
    {'*',' ','*',' ',' ','*',' ','*'},
    {'*',' ','o','o',' ',' ',' ',' '},
    {'*',' ','*','*','#','*','*',' '},
    {'*',' ',' ',' ',' ',' ',' ',' '},
    {'*','*','*','*','#','*','*','*'},
}
-- create grid object for Jumper
grid_object = Grid(grid, walkable)
-- create a pathfinder with Jump point search algorithm
finder = Pathfinder(grid_object, 'JPS', walkable)
-- test a path between two Y,X points with bi-directional movement
path = finder:setMode('ORTHOGONAL'):getPath(1, 2, 8, 8)

Please note that getPath function accepts Y, X coordinates for both starting and ending points. It took me a couple of hours to find out when I first tested with X, Y and was getting weird results.

Now you will have path computed in your path variable. Looping over gives you your walkable path with all steps:

for node, count in path:nodes() do
    print('#'.. count ..': x='.. node.x ..', y='.. node.y)
end

Example with a callback function

For a more complicated example we will use a callback isWalkable function and diagonal movement. You will need to create and provide a callback function that will return simple 0 (wall)/1 (path) based on walkability first.

You can use a complicated map (matrix) with many values. I am using simple ‘path’ here, but you can have water, rail, road, path, bridge, house etc. From these rail, road, path and bridge can be walkable, but water and house are not. You will need to code additional map cell types into your isWalkable function. I am using just a path cell type here:

function isWalkable(sector)
    if sector=='path' then -- rail, road etc.
        return true
    else -- others such as house, water
        return false
    end
end

You can also have multiple if-> else if-> else conditions for multiple map surfaces (cell types) also depending on different game variables such as using boat (water is walkable / passable) etc., having a key (house is walkable/passable) etc.

-- create grid object for Jumper
grid_object = Grid(your_grid, true) -- boolean true is used when surface is walkable
-- create a pathfinder with Jump point search algorithm
finder = Pathfinder(grid_object, 'JPS', isWalkable)
-- test a path between two Y,X points with diagonal movement
path = finder:setMode('DIAGONAL'):getPath(start_y, start_x, end_y, end_x)

Using different algorithm for pathfinding

Using pathfinder object with an A* algorithm:

finder = Pathfinder(grid_object, 'ASTAR', isWalkable)

You can see all available pathfinding algorithms in Jumper code.

I have been using Jumper for years and it works well, has a good performance and provides easy pathfinding.