swarm-0.5.0.0: 2D resource gathering game with programmable robots
LicenseBSD-3-Clause
Safe HaskellSafe-Inferred
LanguageHaskell2010

Swarm.Game.Step.Pathfinding

Description

Implementation of the path command for robots.

Design considerations

One possible design of the path command entailed storing a computed shortest path and providing a mechanism to retrieve parts of it later without recomputing the whole thing. However, in general the playfield can be dynamic and obstructions may appear that invalidate a given computed shortest path. Therefore, there can be limited value in caching a computed path for use across ticks.

Instead, in the current implementation a complete path is computed internally upon invoking the path command, and just the direction of the first "move" along that path is returned as a result to the caller.

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.

Synopsis

Documentation

data PathfindingTarget Source #

Shortest paths can either be computed to the nearest entity of a given type or to a specific location.

Constructors

LocationTarget Location 
EntityTarget EntityName

Note: navigation to entities does not benefit from the distance heuristic optimization of the A* algorithm.

pathCommand Source #

Arguments

:: (HasRobotStepState sig m, Has (State GameState) sig m) 
=> Maybe Integer

Distance limit

-> Cosmic Location

Starting location

-> PathfindingTarget

Search goal

-> m (Maybe Direction) 

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, than it is permissible for that entity to be Unwalkable.