Non-grid pathfinding experiment

Sun, 16 Jun 2019 22:26:07 UTC

dooart_pathfinding

by dooart

[Click to Play]

I couldn't find any pathfinding example for pico-8 that could be used for non-grid movement, so I took this one and built on top it.

The necessity came when I started writing a game that had fluid movement inside a grid map (so rather than moving one tile at a time, the characters move one pixel at a time). Even with a tile-based map system, the collisions still had to be checked again for every pixel.

This cart visually shows how the pathfinding works:

Yellow squares: path found with the grid pathfinding.
White line: path to the next grid tile, found with the pixel pathfinding.

You can move one of the characters using the arrows. By pressing X, you can enable/disable the visualization.

Tiles: https://thkaspar.itch.io/micro-tileset-overworld-dungeon

The strategy is:

Use A* at a tile grid level for long-distance pathfinding to find the shortest path to the target.
Get the closest tile to the character from the shortest path.
Use A* again at a pixel level to find the pixel path to that tile.

Of course it'd be possible to use A* at a pixel level for the whole path, but pico-8 limitations would be hit pretty quickly on a large map with many characters.

I thought I'd post it here to help the next person who needs something similar.

dooart [Lexaloffle Blog Feed]

Non-grid pathfinding experiment