Navigation

grid A* pathfinding with a click-to-move character.

▶ Run in browser

Tags: 2d

NavGrid2D is the engine’s grid pathfinder. Build one with a size in cells, mark the walls with set_solid(x, y), and find_path(from_cell, to_cell) returns the shortest walkable route as a list of (x, y) cells, both ends included. It returns an empty list when either end is off the grid or solid, or when no route exists.

corners decides whether a route may step diagonally past the corner of a wall. "never", used here, keeps every step orthogonal. "strict" (the default) allows a diagonal only when both cells it passes between are free, "relaxed" when either is, and "always" allows every diagonal.

The scene works in cell units: cell (x, y) covers x..x+1 by y..y+1, so its centre is (x + 0.5, y + 0.5). Each frame the node’s scale and position fit the grid to the window, which scales everything on_draw draws, and to_local maps a press back into cell units. The character walks the route waypoint by waypoint at a steady speed with Vec2.move_toward, and the green cells are the part of the route still ahead. A new press re-plans from the cell the character is walking to, so it never cuts through a wall. A press on a wall or an unreachable cell is ignored.

Click or tap a free cell to walk there.

Source

"""Navigation: grid A* pathfinding with a click-to-move character.

`NavGrid2D` is the engine's grid pathfinder. Build one with a size in cells, mark the walls
with `set_solid(x, y)`, and `find_path(from_cell, to_cell)` returns the shortest walkable
route as a list of `(x, y)` cells, both ends included. It returns an empty list when either
end is off the grid or solid, or when no route exists.

`corners` decides whether a route may step diagonally past the corner of a wall. `"never"`,
used here, keeps every step orthogonal. `"strict"` (the default) allows a diagonal only when
both cells it passes between are free, `"relaxed"` when either is, and `"always"` allows
every diagonal.

The scene works in cell units: cell `(x, y)` covers `x..x+1` by `y..y+1`, so its centre is
`(x + 0.5, y + 0.5)`. Each frame the node's `scale` and `position` fit the grid to the
window, which scales everything `on_draw` draws, and `to_local` maps a press back into cell
units. The character walks the route waypoint by waypoint at a steady speed with
`Vec2.move_toward`, and the green cells are the part of the route still ahead. A new press
re-plans from the cell the character is walking to, so it never cuts through a wall. A press
on a wall or an unreachable cell is ignored.

Click or tap a free cell to walk there.
"""

import math

from simvx.core import Anchor, CanvasLayer, Label, NavGrid2D, Node2D, Pointer, Vec2, on_input
from simvx.graphics import App

COLS, ROWS = 20, 15
SPEED = 5.0  # cells per second


class NavigationDemo(Node2D):
    dynamic = True  # the character moves every frame

    def on_ready(self):
        self.grid = NavGrid2D(COLS, ROWS, corners="never")
        walls = [(x, 5) for x in range(5, 15)] + [(8, y) for y in range(2, 10)] + [(x, 10) for x in range(3, 8)]
        for x, y in walls:
            self.grid.set_solid(x, y)
        self.player = Vec2(1.5, 1.5)
        self.route: list[tuple[int, int]] = []  # cells still to walk, the next one first

        # Example help overlay: not part of the technique shown.
        hud = self.add_child(CanvasLayer())
        hud.add_child(Label("Click or tap a free cell to walk there", anchor=Anchor.BOTTOM_LEFT, inset=10))

    @on_input(Pointer.PRIMARY)
    def walk_to(self, event):
        x, y = self.to_local(event.position)
        start = self.route[0] if self.route else (math.floor(self.player.x), math.floor(self.player.y))
        # An empty path (a wall, off the grid, or unreachable) keeps the current walk.
        self.route = self.grid.find_path(start, (math.floor(x), math.floor(y))) or self.route

    def on_update(self, dt):
        width, height = self.viewport_size
        cell = min(width / COLS, height / ROWS)
        self.scale = (cell, cell)
        self.position = ((width - COLS * cell) / 2, (height - ROWS * cell) / 2)

        if self.route:
            x, y = self.route[0]
            self.player = self.player.move_toward((x + 0.5, y + 0.5), SPEED * dt)
            if self.player == (x + 0.5, y + 0.5):
                self.route.pop(0)

    def on_draw(self, renderer):
        for x in range(COLS):
            for y in range(ROWS):
                colour = (0.75, 0.22, 0.22) if self.grid.is_solid(x, y) else (0.12, 0.12, 0.16)
                renderer.rect((x, y), (0.97, 0.97), fill=colour)
        for x, y in self.route:
            renderer.rect((x + 0.1, y + 0.1), (0.77, 0.77), fill=(0.24, 0.68, 0.28))
        renderer.circle(self.player, 0.33, fill=(0.24, 0.71, 1.0))


if __name__ == "__main__":
    App(title="Navigation", width=800, height=600).run(NavigationDemo())