GMNav

Pathfinding and navigation framework for GameMaker

Pure GML. No extensions. No DLLs.

GMNav is a complete navigation solution for GameMaker, covering top-down, isometric, hex and side-view platformer games, on flat ground and on terrain that stacks.

Every search is resumable. Instead of blocking the frame, searches run under a global budget shared across all agents, so pathfinding costs the same milliseconds whether you have ten agents or five hundred.

• Resumable A* - Stops mid-search, resumes next frame, never blocks
• Global frame budget - One shared pool of node expansions, not per agent
• Request priorities - Low, normal, high, and immediate with FIFO fairness
• Deterministic - Identical input always returns the identical path

• Orthogonal - Standard square and rectangular grids
• Isometric diamond - Classic 2:1 projection
• Isometric staggered - Offset rows with parity-aware adjacency
• Hexagonal - Pointy-top and flat-top, with cube coordinate rounding
• Anisotropic cost - Logical or visual step cost for non-square tiles

• Height per cell - Climb and drop limits per unit, so a cliff is one-way without a flag
• Stacked walkable surfaces - A bridge over a road, a walkway behind a cliff, a tower you can circle
• Sparse overlays - A handful of cells above the grid, not a second grid to maintain
• Ramps - Fractional offsets that climb a surface in even steps
• Caller-named picking - A point over a bridge has two answers, and you say which you meant

• Layered cost maps - Stack danger, terrain, and faction layers independently
• Per-agent weights - Two agent types read one layer and disagree about it
• Baked resolution - Twelve layers cost the search exactly as much as none
• Radial and path stamps - Falloff brushes around a point or along a route
• Region rebaking - Move a threat every frame without touching the rest of the map

• Chebyshev distance transform - Two linear sweeps, no per-node box scans
• Size-aware routing - One nav graph serves agents of every radius
• Start relaxation - Agents in tight spots can still path out

• One pass, many agents - Thousands read a direction at near-zero cost
• Multiple goals - Nearest exit, nearest cover, in a single build
• Distance capping - Bound the build on large maps
• Sliced building - Spread the work across frames
• True travel cost - Ask any unit what a destination really costs it, in one lookup

• Supercover string pulling - Removes the staircase without clipping corners
• Movement constraints - Hold a path to four or eight headings for grid-locked characters
• Corner rounding and splines - For anything that cannot turn instantly
• Validated throughout - A shortcut that would clip geometry, climb a cliff, or walk back into priced ground is refused

• Simulated reachability - Jump arcs integrated against your collision data
• Your movement model - Gravity, jump velocity, run speed, terminal fall
• Three link types - Walk, fall, and jump, each with traversal cost in frames
• One-way awareness - Drops that cannot be climbed back up
• Optional arc replay - Let the framework fly the jumps, or read the links and fly them yourself

• Velocity proposal - Writes vx and vy, never moves your instances
• Scoped replanning - Repaths only when a change lands on the route still to walk
• Local avoidance - Separation steering with speed clamping
• Nothing hidden - Every behaviour is a public call, so your own agent class loses nothing

• Layout-accurate cells - Draws diamonds and hexagons, not squares
• Layer-aware - Raised cells draw where they sit, with a line to the ground beneath
• Flow field arrows - Direction and distance ramp per cell
• Clearance and cost ramps - See exactly what an agent type pays
• Reachability - Colour by connected component, for any agent size
• Search frontier - Watch open and closed sets expand across frames
• Platformer link graph - Colour-coded arcs, filterable and focusable

// Create
grid  = gmnav_grid_create(60, 40, gmnav_layout_create(gmnav_layout.ORTHO, 32, 32));
gmnav_grid_import_tilemap(grid, layer_tilemap_get_id("Tiles_Collision"));

sched = gmnav_scheduler_create(grid, 2000, 4);
agent = gmnav_agent_create(sched, x, y, 12, 3);

// Step
gmnav_scheduler_update(sched);
gmnav_agent_update(agent);

x += agent.vx;
y += agent.vy;

// Anywhere
gmnav_agent_goto(agent, target_x, target_y);

danger = gmnav_costlayer_create(grid, "danger");
gmnav_costlayer_stamp_radial(danger, player_x, player_y, 200, 12, 2);

grunt = gmnav_costprofile_create(grid, "grunt");
gmnav_costprofile_add(grunt, danger, 1);
gmnav_costprofile_bake(grunt);

gmnav_scheduler_request(sched, from, to, gmnav_priority.NORMAL, false, grunt);

var _ov = gmnav_overlay_create(grid);

var _deck = [];
for (var _c = 5; _c <= 9; _c++) array_push(_deck, gmnav_overlay_add(_ov, _c, 10, 1));

gmnav_overlay_link(_ov, gmnav_grid_node(grid, 4, 10), _deck[0], gmnav_link.STAIR, true);
gmnav_overlay_finish(_ov);

move   = gmnav_movement_create(0.5, 7, 3, 9, 16, 32);
pgraph = gmnav_platgraph_create(grid, move);
gmnav_platgraph_bake(pgraph);

// path[i] is a ledge, links[i] is how you reach it
var _path  = gmnav_scheduler_get_path(ticket);
var _links = gmnav_scheduler_get_links(ticket);

• API Reference - Every function with its arguments, return shape, edge cases, and known behaviours
• Getting Started - From an empty project to a moving agent, then each subsystem in the order you are likely to need it
• Tutorials - Nineteen chapters, from what pathfinding is to a navigation system you can see and diagnose

Shortest paths Dijkstra, E. W. (1959) "A Note on Two Problems in Connexion with Graphs", Numerische Mathematik, 1, 269-271 Hart, P. E., Nilsson, N. J. and Raphael, B. (1968) "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107

Distance transforms and clearance Rosenfeld, A. and Pfaltz, J. L. (1966) "Sequential Operations in Digital Picture Processing", Journal of the ACM, 13(4), 471-494 Borgefors, G. (1986) "Distance Transformations in Digital Images", Computer Vision, Graphics, and Image Processing, 34(3), 344-371

Grid traversal and line of sight Amanatides, J. and Woo, A. (1987) "A Fast Voxel Traversal Algorithm for Ray Tracing", Eurographics '87

Curves and corner rounding Catmull, E. and Rom, R. (1974) "A Class of Local Interpolating Splines", in Barnhill, R. E. and Riesenfeld, R. F. (eds.) Computer Aided Geometric Design, Academic Press, 317-326

Steering and local avoidance Reynolds, C. W. (1987) "Flocks, Herds and Schools: A Distributed Behavioral Model", SIGGRAPH '87, 25-34 Reynolds, C. W. (1999) "Steering Behaviors For Autonomous Characters", Game Developers Conference

Flow fields Emerson, E. (2013) "Crowd Pathfinding and Steering Using Flow Field Tiles", in Rabin, S. (ed.) Game AI Pro, CRC Press

Hex grids Patel, A. "Hexagonal Grids", Red Blob Games