Scurry

An A-star 2D polygon map search implementation and set of polygon, geometry and vector utility functions for Elixir.

Possible use cases cover game path finding or general graph searches.

Quickstart

• See the quickstart.
• Or on hex.pm docs.
• And [full API] reference](https://hexdocs.pm/scurry/api-reference.html).

WxWidgets Demo

Start the WxWidgets demo of A-star by running Scurry.Wx.start();

$ mix deps.get
$ mix compile
$ iex -S mix
Erlang/OTP 25 [erts-13.1.3] [source] [64-bit] [smp:8:8] [ds:8:8:10] [async-threads:1] [jit:ns] [dtrace]

Interactive Elixir (1.18.1) - press Ctrl+C to exit (type h() ENTER for help)

Scurry (vx.y.z)
---------------

An a-star 2d polygon map search implementation and library for elixir

Using config from config/config.exs

For WxWidget demo run Scurry.Wx.start()

Go forth and find... 🐿️

iex(1)> Scurry.Wx.start()

• The start point is the green crosshair.
• The cursor position is the red crosshair if inside the main polygon, gray if outside.
• Moving the mouse will show a line from start to the cursor.
  • It'll be green if the there's a line of sight, meaning no obstacles.
  • It'll be gray if not, and there'll be a small red crosshair at the first obstacle intersection, and small gray crosshair all subsequent intersections in the line of sight.
• Holding down left mouse button will show full search graph in bright orange and a thick green path for the found path.
• Releasing the left mouse button resets the start to there.
  • You can place the start outside the main polygon.

How to use

Adding scurry to your list of dependencies in mix.exs:

def deps do
  [
    {:scurry, "~> 2.0"},
  ]
end

Update your dependencies:

$ mix deps.get

Commit mix.lock file as desired.

Internals

Full API documentation than this see the hexdocs, especially see the quickstart.

mix docs
open doc/index.html

Vectors

In lib/vector.ex you'll find the basic vector operations (dot, cross, length, add/sub) needed. A vector is a tuple of numbers, {x, y}.

Lines

A line is a tuple of vectors, {{x1, y1}, {x2, y2}}.

Polygon

In lib/plygon.ex you'll find the various polygon related functions, such as line of sight, nearest point, convex etc.

A polygon is a list of vertices (nodes) that are {x, y} tuples that represent screen coordinates.

In elixir, it looks like

polygon = [{x, y}, {x, y}, ...]

• The screen coordinate 0, 0 is upper left
• The x-axis goes left-to-right and y-axis top-to-bottom.
• Polygons must be defined clockwise and not-closed. This is important for convex/concave vertex checks.
• The polygon will be treated as closed with the last coordinate connected to the first.

Polygon map

The wxwidgets demo map is loaded from a json file, and looks like

{
  "polygons": [
    "main": [
      [x, y], [x, y], [x,y], ...
    ],
    "hole1": [
      [x, y], [x, y], [x,y], ...
    ],
    "hole2": [
      [x, y], [x, y], [x,y], ...
    ]
  ]
}

The demo loads the polygon data, and the polygon named main is the primary walking area - as complex as it needs to be.

Subsequent polygons (not named main) are added as holes/obstacles within it - non-walkable areas.

Polygons must not be be closed (meaning last [x, y] json point being equal to the first), this will be handled internally.

The polygon name isn't used internally, only by the wxwidgets demo to pick the primary boundary and which are holes.

Graph

The A-star graph doesn't need to be a polygon map. It just needs to be map from node to a list of {node, cost} edges.

A node just has to be a term that elixir can use as a map key.

For the 2D map search, it is a map from a vertex (aka vectors) to a list of {vertex, cost}. This is computed from the polygon map using a set of vertices. This set is composed of;

• the main polygon's concave shape (pointing into the world)
• the holes' convex shapes (point out of( the hole, into* the world)

and PolygonMap.get_vertices/2 creates this.

vertices = [
  {x1, y1} = vertex1,
  {x2, y2} = vertex2,
  {x3, y3} = vertex3,
  ...
]

This is transformed to a graph (PolygonMap.create_graph/4) given the polygon, holes, vertices (from above) and cost function.

Assuming a cost_fun/2 that has type vertex, vertex :: cost, the graph looks like;

graph = %{
  vertex1 => [
    vertex2, cost_fun(vertex1, vertex2),
    vertex3, cost_fun(vertex1, vertex3),
    vertex4, cost_fun(vertex1, vertex4),
  ],
  # When expressed as "vertex = {x, y}" (ie. vectors)
  {x1, x2} => [
    {{x2, y2}, cost_fun({x1, y2}, {x2, y2})},
    {{x3, y3}, cost_fun({x1, y2}, {x3, y3})},
    ...
  ],
  ...
}

Note: create_graph uses PolygonMap.is_line_of_sight?/3 to determine if two vertices should have an edge. This is currently not configurable or passed as a function. Having that functionality would allow for configurably behaviour, such as passing through/flying over obstacles.

The default cost_fun and heur_fun (see later) is the euclidean distance been the two points. The difference between the two is, cost_fun is used while computing the graph and heur_fun while computing the path. Typically they will be the same but that is dependent on use case.

# Euclidean distance cost function
cost_fun = fn a, b -> Vector.distance(a, b) end

A-star

In the context of A-star, we use the terminology node instead of vertex since we're describing graphs. In the example, each node is a polygon vertex/vector (ie. {x, y}).

A node is opaque to the algorithm, it just uses them as keys for it's internal state maps and arguments to heur_fun. indexes.

The A-star algorithm main call is Astar.search/4 and takes.

• graph to search. The graph should be constructed as

graph = %{
  node1 => [
    node2, cost_fun(node1, node2),
    node3, cost_fun(node1, node3),
    node4, cost_fun(node1, node4),
  ],
  # When doing 2d-map, nodes are vectors, {x, y}
  {x1, x2} => [
    {{x2, y2}, cost_fun({x1, y2}, {x2, y2})},
    {{x3, y3}, cost_fun({x1, y2}, {x3, y3})},
    ...
  ],
  ...
}

• start and stop, the nodes to find a path between. When doing 2d-map pathfinding, these are typically added to create a temporay graph to search, using PolygonMap.extend/5

• heur_fun function node, node :: cost computes the heuristic cost. The default is the euclidian distance.

# Euclidean distance heuristic function
fn a, b -> Vector.distance(a, b) end

The state it maintains and returns

• shortest_path_tree, a map of edges, node_a => node_b, where node_b is the "previous" node from node_a that is the shortest path.

• queue priority queue / list [node, node, ...] sorted on the cost (see f_cost below) of the path from start to node to stop.

• frontier map of node => node (prev) that have been reached and edges yet to try and have been added to the queue. It's a map, so when we visit a node, we can add how we reached it to shortest_path_tree.

• g_cost, map node => cost with the minimal current cost from the start to node. Each iteration compare the current node's g_cost against the value in the map. If it's less, we've found a shorter path to this node and update the g_cost map.

• f_cost, map node => cost with the "total cost" of path from start, via node, to stop. This means the computed minimal cost from start to node (g_cost) plus the heuristic cost via heur_fun. This is used to reorder queue.

shortest_path_tree is the most relevant field, and can be converted to a path using Astar.path/1.

Within astar.ex, there's two steps; search & getting the path. search returns the full state, and path could be extended to return the cost along the path if needed. It can fetch this from g_cost.

Maintainers corner

New release

To make a new release.

Preconditions

• build test etc
• Logged into hex via mix hex..., check using mix hex.user whoami

Steps

1. Increase version in mix.exs
2. mix hex.publish

Todo

Speed up graph extension by caching cachable cost_fun results in a state.

That might mean making a genserver version that has the state supports extend/search using calls/casts.