Swarm.Game.Step.Path.Finding

Implementation of the Path command for robots.

Design considerations

In general the playfield can be dynamic, and obstructions may appear that invalidate a given computed shortest path. Therefore, there would be limited value in a command that returns an entirely static computed path that is somehow stored on the client side (i.e. inside a swarm-lang program).

In the current implementation, a complete path is computed internally upon invoking the path command and doled out incrementally across ticks. Each path invocation returns the direction of the next "move" along the computed shortest path.

This internally stored path is re-used across invocations until some event invalidates its cache (see Swarm.Game.Step.Path.Cache).

Max distance

We allow the caller to supply a max distance, but also impose an internal maximum distance to prevent programming errors from irrecoverably freezing the game.

Documentation

pathCommand :: HasRobotStepState sig m => PathfindingParameters (Cosmic Location) -> m (Maybe (Direction, Int))

Swarm command arguments are converted to idiomatic Haskell types before invoking this function, and conversely the callsite is also responsible for translating the output type to a swarm value.

The cost function is uniformly 1 between adjacent cells.

Viable paths are determined by walkability. If the goal type is an Entity, then it is permissible for that entity to be Unwalkable.

See Swarm.Game.Step.Path.Cache for caching details.