NAME

Game::TileMap::Pathfinding - BFS pathfinding for Game::TileMap

SYNOPSIS

use Game::TileMap::Pathfinding;

my $pf = Game::TileMap::Pathfinding->new(map => $game_tilemap_object);
my $result = $pf->find_path($start_x, $start_y, $end_x, $end_y);

die 'no path available'
	unless defined $result;

say 'required steps: ' . $result->step_count;
while (my ($x, $y) = $result->next_step) {
	say "next step is $x:$y";
}

DESCRIPTION

This module is a fast Breadth-First Search pathfinding for Game::TileMap. For speed, the core algorithm is implemented in XS.

Pathfinding instances can be reused indefinetly, but they don't actively track changes on a map. They follow "check_can_be_accessed" in Game::TileMap function to build a map of accessible terrain at object construction - building that map is much more expensive than pathfinding itself. Moreover, all types of terrain have the exact same movement cost, though this may be changed in the future.

Interface

new

$pf = $class->new(%options)

This constructs a new pathfinding instance for a Game::TileMap object. %options can be any of:

• map

  This is a mandatory instance of a map. Location of inaccessible terrain should not change after creating a pathfinding instance - if it does, it's best to get rid of the pathfinding object and create a new one.

• diagonal_movement

  This is an optional flag used for enabling finding paths by moving diagonally. If enabled, one path step is allowed to cause a change in both x and y at the same time.

  Moving like this is only possible if an obstacle is not touched by both tiles, for example, it's not possible to move from 1 to 2 in below examples, since it would require touching the wall (#):

  ____  ____  ____
  _1#_  _1__  _1#_
  __2_  _#2_  _#2_
  ____  ____  ____

  Diagonal movement allows more natural paths in open environment - instead of moving across the border, a more centered path will be chosen. The cost of moving diagonally is multiplied by sqrt(2) compared to moving orthogonally.

find_path

$result = $pf->find_path($start_x, $start_y, $end_x, $end_y)

This method finds the shortest valid path from start to end. If no such path is available, undef is returned. If it is, an instance of Game::TileMap::Pathfinding::Result is returned.

Path is always returned as a series of steps to take to reach the end location. Start location coordinates are never included in this path, so if start and end location is the same, the result will have 0 steps (but will not be an undef). First step is always the closest to the start location.

SEE ALSO

Game::TileMap

AUTHOR

Bartosz Jarzyna <bbrtj.pro@gmail.com>

COPYRIGHT AND LICENSE

Copyright (C) 2026 by Bartosz Jarzyna

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.