be54ba3aace9ecff1535e1d40e083e9a228d1b7d

Committed 28 Mar 2025 04:37AM UTC coverage: 96.93% (+0.08%) from 96.847%

Build # be54ba3aace9ecff1535e1d40e083e9a228d1b7d

Build Type

Pull #1

github

Committed by

eskil

Commit Message

test more elixit otp combos

Pull Request Pull Request #1: V3 branch

Run Details

66 of 67 new or added lines in 5 files covered. (98.51%)

7 existing lines in 3 files now uncovered.

221 of 228 relevant lines covered (96.93%)

245.79 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.1

/lib/polygon_map.ex

defmodule Scurry.PolygonMap do
  @moduledoc """
  Utility functions to work on a polygon map.

  A polygon map is a set of a primary polygon - the **main** boundary that
  outlines the world - and a list of polygons that make **holes** in the main
  polygon.

  See `Polygon` for details on how polygons are composed.

  The use case is eg. making a map (the **main** polygon) with obstacles (the
  **holes**), and use the `Astar` module to find the shortest path between
  points in the map.
  """

  alias Scurry.Polygon
  alias Scurry.Vector
  use Scurry.Types

  @doc """
  Given a polygon map (`world` & `holes`), returns a list of vertices for a
  walkmap for A-star search


  ## Params
  * `world`, a polygon that defines the outer boundary
  * `holes`, a list of polygons that define holes/obstacles inside `world`.

  ## Returns

  The vertices that are the `worlds`'s concave vertices and the convex ones of
  the `holes`.

  These are used when generating the walk map, since only the `world`'s concave
  and the `holes`' convex ones limit where you can traverse in a 2D map.

  See [Quickstart](quickstart.html) for a concrete example.
  """
  @spec get_vertices(polygon(), list(polygon())) :: list(vector())
  def get_vertices(world, holes) do
    {concave, _convex} = Polygon.classify_vertices(world)

    convex =
      Enum.reduce(holes, [], fn points, acc ->
        {_concave, convex} = Polygon.classify_vertices(points)
        acc ++ convex
      end)

    concave ++ convex
  end

  @doc """
  Given a polygon map (main & holes) and list of vertices, makes the graph.

  ## Params
  * `cost_fun`, a `node, node :: cost` function, defaults to `Scurry.Vector.distance/2`

  ## Todo

  This should ideally take `line_of_sight` as a function so users can
  customise which vertices can reach each other. But for now, users can make
  the graph themselves just as easily.
  """
  @spec create_graph(polygon(), list(polygon()), list(vector()), (vector(), vector() -> float())) :: %{vector() => {vector(), float()}}
  def create_graph(world, holes, vertices, cost_fun \\ nil)

  def create_graph(world, holes, vertices, nil) do
    create_graph(world, holes, vertices, &Vector.distance/2)
  end

  def create_graph(world, holes, vertices, cost_fun) do
    get_edges(world, holes, vertices, vertices, cost_fun)
  end

  @doc """
  Given a polygon map (main & holes), list of vertices and the initial graph,
  extend the graph with extra `points`.

  This is used to "temporarily" expand the fixed walk graph with the start and
  end-point. This is a performance optimisation that saves work by reusing the
  fixed nodes and extend it with the moveable points.

  ## Params
  * `polygons`, a `%{main: [...], hole: [...], hole2: [...]}` polygon map.
  * `graph`, the fixed graph, eg. created via `create_graph/2`.
  * `vertices` the nodes used to create `graph`.
  * `points` a list of coordinates, `[{x, y}, {x, y}...]`, to extend with
  * `cost_fun`, a `node, node :: cost` function, defaults to `Vector.distance`

  Returns an extended graph plus the combined list of vertices and new points,
  `{new_graph, new_vertices}`.
  """
  def extend_graph(graph, polygon, holes, vertices, points, cost_fun \\ nil)

  def extend_graph(graph, polygon, holes, vertices, points, nil) do
    extend_graph(graph, polygon, holes, vertices, points, &Vector.distance/2)
  end

  def extend_graph(graph, polygon, holes, vertices, points, cost_fun) do
    # To extend the graph `graph` made up up `vertices` with new points
    # `points`, we need to find three sets of edges (sub-graphs). The ones from
    # the new points to the existing vertices, vice-versa, and between the new
    # points.
    set_a = get_edges(polygon, holes, points, vertices, cost_fun)
    set_b = get_edges(polygon, holes, vertices, points, cost_fun)
    set_c = get_edges(polygon, holes, points, points, cost_fun)

    # Merge the three new sub-graphs into graph. This uses Map.merge with a
    # merge func that combines values for identical keys to extend them instead
    # of replacing, and dedupes.
    merge_fun = fn _k, v1, v2 ->
      Enum.dedup(v1 ++ v2)
    end

    graph =
      graph
      |> Map.merge(set_a, merge_fun)
      |> Map.merge(set_b, merge_fun)
      |> Map.merge(set_c, merge_fun)

    {graph, vertices ++ points}
  end

  @doc """
  Find the nearest point on the line that is inside the map and outside a hole.

  ## Params
  * `polygon`, a list of `{x, y}` vertices. This is the main boundary map.
  * `holes`, a list of lists of `{x, y}` vertices. These are holes within
    `polygon`.
  * `point` a tuple of coordinates (`{x, y}`) describing a point

  The function will return a new point `{bx, by}` for b such that;

  * if `{bx, by}` is outside the main map, the new b is the closest point on
    the main map.

  * if b is inside the main map, but also inside a hole, the new bis the
    closest point on the holes edges.
  """
  def nearest_point([], _, point) do
    point
  end

  def nearest_point(polygon, holes, point) do
    nearest_point_helper(polygon, holes, point, Polygon.is_inside?(polygon, point))
  end

  defp nearest_point_helper(_, holes, point, true) do
    nearest_point_in_holes(holes, point)
  end

  defp nearest_point_helper(points, _holes, point, false) do
    nearest_boundary_point_helper(points, point)
  end

  defp nearest_point_in_holes([], point) do
    point
  end

  defp nearest_point_in_holes([hole | holes], point) do
    nearest_point_in_holes_helper(
      [hole | holes],
      point,
      Polygon.is_inside?(hole, point, allow_border: false)
    )
  end

  defp nearest_point_in_holes_helper([_hole | holes], point, false) do
    nearest_point_in_holes(holes, point)
  end

  defp nearest_point_in_holes_helper([hole | _holes], point, true) do
    nearest_boundary_point_helper(hole, point)
  end

  defp nearest_boundary_point_helper(polygon, point) do
    {x, y} = Polygon.nearest_point_on_edge(polygon, point)

    # This is a problematic area - we want to round towards the start of the
    # line Eg. in complex.json scene, clicking {62, 310} yields {64.4, 308.8},
    # which naive rounding makes {64, 309}. This however places us *back*
    # *inside* the hole.

    # Some options are; try all four combos or floor/ceil and see which yields
    # the minimal distance - wrong, since the start might be on the far side of
    # a hole.

    # Shorten towards start? Same thing.

    # Actually run A-star to compute all four rounding and pick the shortest
    # path - that's a bit cpu heavy.

    # Compute all four rounding options and pick one that's *not* inside the
    # hole, and don't allow it to be on the border.

    p = {round(x), round(y)}
    a = {ceil(x), ceil(y)}
    b = {ceil(x), floor(y)}
    c = {floor(x), ceil(y)}
    d = {floor(x), floor(y)}

    cond do
      Polygon.is_outside?(polygon, p, allow_border: false) ->
        p

      Polygon.is_outside?(polygon, a, allow_border: false) ->
        a

      Polygon.is_outside?(polygon, b, allow_border: false) ->
        b

      Polygon.is_outside?(polygon, c, allow_border: false) ->
        c

      Polygon.is_outside?(polygon, d, allow_border: false) ->
        d
    end

    # If none of the points are outside, we'll pleasantly crash and we should
    # improve this to continuously move outwards a reasonable amount until
    # we're outside.
  end

  @doc """
  Checks if there's a line-of-sight (LOS) from `start` to `stop` within the map.

  ## Params
  * `polygon`, a list of `{x, y}` vertices. This is the main boundary map.
  * `holes`, a list of lists of `{x, y}` vertices. These are holes within
    `polygon`.
  * `line` a tuple of points (`{{ax, ay}, {bx, by}}`) describing a line.

  Returns `true` if there's a line-of-sight and none of the main polygon or
  holes obstruct the path. `false` otherwise.

  As the map consists of a boundary polygon with holes, LOS implies a few things;

  * If either `start` or `stop` is outside `polygon`, the result will be
    false. Even if both are outside, that's not considered a valid LOS.
  * If the distance between `start` and `stop` is tiny (< 0.1 arbitrarily), LOS
    is true.
  * Next, it checks that the line between `start` and `stop` has no
    intersections with `polygon` or `holes`.
  * Finally it checks if the middle of the line between `start` and `stop` is
    inside `polygon` and outside all holes - this ensures that corner-to-corner
    across a hole isn't considered a LOS.
  """
  def is_line_of_sight?(polygon, holes, line) do
    {start, stop} = line

    cond do
      not Polygon.is_inside?(polygon, start) or not Polygon.is_inside?(polygon, stop) ->
        false

      Vector.distance(start, stop) < 0.1 ->
        true

      not Enum.all?([polygon] ++ holes, fn points -> is_line_of_sight_helper(points, line) end) ->
        false

      true ->
        # This part ensures that two vertices across from each other are not
        # considered LOS. Without this, eg. a box-shaped hole would have
        # opposing corners be a LOS, except that the middle of the line falls
        # inside the hole per this check.
        middle = Vector.div(Vector.add(start, stop), 2)

        cond do
          not Polygon.is_inside?(polygon, middle) ->
            false

          Enum.all?(holes, fn hole -> Polygon.is_outside?(hole, middle, allow_border: false) end) ->
            true

          true ->
            false
        end
    end
  end

  defp is_line_of_sight_helper(polygon, {x, y} = line) do
    # We get all intersections and reject the ones that are identical to the
    # line. This allows us to enable "allow_points: true", but only see
    # intersections with other lines and _other_ polygon vertices (points).
    # This is necessary since we're always calling this with a line between two
    # polygon vertices. Without this, having "allow_points: true", every such
    # line would immediately intersect at both ends.

    Polygon.intersections(polygon, line, allow_points: true)
    |> Enum.map(fn {x, y} -> {round(x), round(y)} end)
    |> Enum.reject(fn p -> p == x or p == y end) ==
      []
  end

  # Get all edges from points_a and point_b for which there's line-of-sight.
  defp get_edges(polygon, holes, points_a, points_b, cost_fun) do
    is_reachable? = fn a, b -> is_line_of_sight?(polygon, holes, {a, b}) end

    # O(n^2) check all vertice combos for reachability...
    {_, all_edges} =
      Enum.reduce(points_a, {0, %{}}, fn a, {a_idx, acc1} ->
        {_, inner_edges} =
          Enum.reduce(points_b, {0, []}, fn b, {b_idx, acc2} ->
            # NOTE: this is where the edge value is becomes the key in the
            # graph. This is why a_idx and b_idx are available here, in case we
            # want to change it up to be the indexes into points. Unless those
            # two sets are the same, using the indexes makes no sense.
            if a != b and is_reachable?.(a, b) do
              {b_idx + 1, acc2 ++ [{b, cost_fun.(a, b)}]}
            else
              {b_idx + 1, acc2}
            end
          end)

        {a_idx + 1, Map.put(acc1, a, inner_edges)}
      end)

    Map.new(all_edges)
  end
end

1	defmodule Scurry.PolygonMap do
2	@moduledoc """
3	Utility functions to work on a polygon map.
4
5	A polygon map is a set of a primary polygon - the main boundary that
6	outlines the world - and a list of polygons that make holes in the main
7	polygon.
8
9	See `Polygon` for details on how polygons are composed.
10
11	The use case is eg. making a map (the main polygon) with obstacles (the
12	holes), and use the `Astar` module to find the shortest path between
13	points in the map.
14	"""
15
16	alias Scurry.Polygon
17	alias Scurry.Vector
18	use Scurry.Types
19
20	@doc """
21	Given a polygon map (`world` & `holes`), returns a list of vertices for a
22	walkmap for A-star search
23
24
25	## Params
26	* `world`, a polygon that defines the outer boundary
27	* `holes`, a list of polygons that define holes/obstacles inside `world`.
28
29	## Returns
30
31	The vertices that are the `worlds`'s concave vertices and the convex ones of
32	the `holes`.
33
34	These are used when generating the walk map, since only the `world`'s concave
35	and the `holes`' convex ones limit where you can traverse in a 2D map.
36
37	See [Quickstart](quickstart.html) for a concrete example.
38	"""
39	@spec get_vertices(polygon(), list(polygon())) :: list(vector())
40	def get_vertices(world, holes) do
41	{concave, _convex} = Polygon.classify_vertices(world)	5✔
42
43	convex =	5✔
44	Enum.reduce(holes, [], fn points, acc ->
45	{_concave, convex} = Polygon.classify_vertices(points)	6✔
46	acc ++ convex	6✔
47	end)
48
49	concave ++ convex	5✔
50	end
51
52	@doc """
53	Given a polygon map (main & holes) and list of vertices, makes the graph.
54
55	## Params
56	* `cost_fun`, a `node, node :: cost` function, defaults to `Scurry.Vector.distance/2`
57
58	## Todo
59
60	This should ideally take `line_of_sight` as a function so users can
61	customise which vertices can reach each other. But for now, users can make
62	the graph themselves just as easily.
63	"""
64	@spec create_graph(polygon(), list(polygon()), list(vector()), (vector(), vector() -> float())) :: %{vector() => {vector(), float()}}
65	def create_graph(world, holes, vertices, cost_fun \\ nil)	2✔
66
67	def create_graph(world, holes, vertices, nil) do
68	create_graph(world, holes, vertices, &Vector.distance/2)	2✔
69	end
70
71	def create_graph(world, holes, vertices, cost_fun) do
72	get_edges(world, holes, vertices, vertices, cost_fun)	4✔
73	end
74
75	@doc """
76	Given a polygon map (main & holes), list of vertices and the initial graph,
77	extend the graph with extra `points`.
78
79	This is used to "temporarily" expand the fixed walk graph with the start and
80	end-point. This is a performance optimisation that saves work by reusing the
81	fixed nodes and extend it with the moveable points.
82
83	## Params
84	* `polygons`, a `%{main: [...], hole: [...], hole2: [...]}` polygon map.
85	* `graph`, the fixed graph, eg. created via `create_graph/2`.
86	* `vertices` the nodes used to create `graph`.
87	* `points` a list of coordinates, `[{x, y}, {x, y}...]`, to extend with
88	* `cost_fun`, a `node, node :: cost` function, defaults to `Vector.distance`
89
90	Returns an extended graph plus the combined list of vertices and new points,
91	`{new_graph, new_vertices}`.
92	"""
93	def extend_graph(graph, polygon, holes, vertices, points, cost_fun \\ nil)	1✔
94
95	def extend_graph(graph, polygon, holes, vertices, points, nil) do
96	extend_graph(graph, polygon, holes, vertices, points, &Vector.distance/2)	1✔
97	end
98
99	def extend_graph(graph, polygon, holes, vertices, points, cost_fun) do
100	# To extend the graph `graph` made up up `vertices` with new points
101	# `points`, we need to find three sets of edges (sub-graphs). The ones from
102	# the new points to the existing vertices, vice-versa, and between the new
103	# points.
104	set_a = get_edges(polygon, holes, points, vertices, cost_fun)	2✔
105	set_b = get_edges(polygon, holes, vertices, points, cost_fun)	2✔
106	set_c = get_edges(polygon, holes, points, points, cost_fun)	2✔
107
108	# Merge the three new sub-graphs into graph. This uses Map.merge with a
109	# merge func that combines values for identical keys to extend them instead
110	# of replacing, and dedupes.
111	merge_fun = fn _k, v1, v2 ->	2✔
112	Enum.dedup(v1 ++ v2)	14✔
113	end
114
115	graph =	2✔
116	graph
117	\|> Map.merge(set_a, merge_fun)
118	\|> Map.merge(set_b, merge_fun)
119	\|> Map.merge(set_c, merge_fun)
120
121	{graph, vertices ++ points}
122	end
123
124	@doc """
125	Find the nearest point on the line that is inside the map and outside a hole.
126
127	## Params
128	* `polygon`, a list of `{x, y}` vertices. This is the main boundary map.
129	* `holes`, a list of lists of `{x, y}` vertices. These are holes within
130	`polygon`.
131	* `point` a tuple of coordinates (`{x, y}`) describing a point
132
133	The function will return a new point `{bx, by}` for b such that;
134
135	* if `{bx, by}` is outside the main map, the new b is the closest point on
136	the main map.
137
138	* if b is inside the main map, but also inside a hole, the new bis the
139	closest point on the holes edges.
140	"""
141	def nearest_point([], _, point) do
142	point	1✔
143	end
144
145	def nearest_point(polygon, holes, point) do
146	nearest_point_helper(polygon, holes, point, Polygon.is_inside?(polygon, point))	6✔
147	end
148
149	defp nearest_point_helper(_, holes, point, true) do
150	nearest_point_in_holes(holes, point)	5✔
151	end
152
153	defp nearest_point_helper(points, _holes, point, false) do
154	nearest_boundary_point_helper(points, point)	1✔
155	end
156
157	defp nearest_point_in_holes([], point) do
158	point	1✔
159	end
160
161	defp nearest_point_in_holes([hole \| holes], point) do
162	nearest_point_in_holes_helper(	6✔
163	[hole \| holes],
164	point,
165	Polygon.is_inside?(hole, point, allow_border: false)
166	)
167	end
168
169	defp nearest_point_in_holes_helper([_hole \| holes], point, false) do
170	nearest_point_in_holes(holes, point)	2✔
171	end
172
173	defp nearest_point_in_holes_helper([hole \| _holes], point, true) do
174	nearest_boundary_point_helper(hole, point)	4✔
175	end
176
177	defp nearest_boundary_point_helper(polygon, point) do
178	{x, y} = Polygon.nearest_point_on_edge(polygon, point)	5✔
179
180	# This is a problematic area - we want to round towards the start of the
181	# line Eg. in complex.json scene, clicking {62, 310} yields {64.4, 308.8},
182	# which naive rounding makes {64, 309}. This however places us back
183	# inside the hole.
184
185	# Some options are; try all four combos or floor/ceil and see which yields
186	# the minimal distance - wrong, since the start might be on the far side of
187	# a hole.
188
189	# Shorten towards start? Same thing.
190
191	# Actually run A-star to compute all four rounding and pick the shortest
192	# path - that's a bit cpu heavy.
193
194	# Compute all four rounding options and pick one that's not inside the
195	# hole, and don't allow it to be on the border.
196
197	p = {round(x), round(y)}	5✔
198	a = {ceil(x), ceil(y)}	5✔
199	b = {ceil(x), floor(y)}	5✔
200	c = {floor(x), ceil(y)}	5✔
201	d = {floor(x), floor(y)}	5✔
202
203	cond do	5✔
204	Polygon.is_outside?(polygon, p, allow_border: false) ->
205	p	3✔
206
207	Polygon.is_outside?(polygon, a, allow_border: false) ->	2✔
208	a	1✔
209
210	Polygon.is_outside?(polygon, b, allow_border: false) ->	1✔
211	b	1✔
212
UNCOV 213	Polygon.is_outside?(polygon, c, allow_border: false) ->	×
UNCOV 214	c	×
215
UNCOV 216	Polygon.is_outside?(polygon, d, allow_border: false) ->	×
UNCOV 217	d	×
218	end
219
220	# If none of the points are outside, we'll pleasantly crash and we should
221	# improve this to continuously move outwards a reasonable amount until
222	# we're outside.
223	end
224
225	@doc """
226	Checks if there's a line-of-sight (LOS) from `start` to `stop` within the map.
227
228	## Params
229	* `polygon`, a list of `{x, y}` vertices. This is the main boundary map.
230	* `holes`, a list of lists of `{x, y}` vertices. These are holes within
231	`polygon`.
232	* `line` a tuple of points (`{{ax, ay}, {bx, by}}`) describing a line.
233
234	Returns `true` if there's a line-of-sight and none of the main polygon or
235	holes obstruct the path. `false` otherwise.
236
237	As the map consists of a boundary polygon with holes, LOS implies a few things;
238
239	* If either `start` or `stop` is outside `polygon`, the result will be
240	false. Even if both are outside, that's not considered a valid LOS.
241	* If the distance between `start` and `stop` is tiny (< 0.1 arbitrarily), LOS
242	is true.
243	* Next, it checks that the line between `start` and `stop` has no
244	intersections with `polygon` or `holes`.
245	* Finally it checks if the middle of the line between `start` and `stop` is
246	inside `polygon` and outside all holes - this ensures that corner-to-corner
247	across a hole isn't considered a LOS.
248	"""
249	def is_line_of_sight?(polygon, holes, line) do
250	{start, stop} = line	136✔
251
252	cond do	136✔
253	not Polygon.is_inside?(polygon, start) or not Polygon.is_inside?(polygon, stop) ->	136✔
254	false
255
256	Vector.distance(start, stop) < 0.1 ->	133✔
257	true
258
259	not Enum.all?([polygon] ++ holes, fn points -> is_line_of_sight_helper(points, line) end) ->	133✔
260	false
261
262	true ->	98✔
263	# This part ensures that two vertices across from each other are not
264	# considered LOS. Without this, eg. a box-shaped hole would have
265	# opposing corners be a LOS, except that the middle of the line falls
266	# inside the hole per this check.
267	middle = Vector.div(Vector.add(start, stop), 2)	98✔
268
269	cond do	98✔
270	not Polygon.is_inside?(polygon, middle) ->	1✔
271	false
272
273	Enum.all?(holes, fn hole -> Polygon.is_outside?(hole, middle, allow_border: false) end) ->	97✔
274	true
275
276	true ->	17✔
277	false
278	end
279	end
280	end
281
282	defp is_line_of_sight_helper(polygon, {x, y} = line) do
283	# We get all intersections and reject the ones that are identical to the
284	# line. This allows us to enable "allow_points: true", but only see
285	# intersections with other lines and _other_ polygon vertices (points).
286	# This is necessary since we're always calling this with a line between two
287	# polygon vertices. Without this, having "allow_points: true", every such
288	# line would immediately intersect at both ends.
289
290	Polygon.intersections(polygon, line, allow_points: true)
291	\|> Enum.map(fn {x, y} -> {round(x), round(y)} end)	292✔
292	\|> Enum.reject(fn p -> p == x or p == y end) ==	256✔
293	[]
294	end
295
296	# Get all edges from points_a and point_b for which there's line-of-sight.
297	defp get_edges(polygon, holes, points_a, points_b, cost_fun) do
298	is_reachable? = fn a, b -> is_line_of_sight?(polygon, holes, {a, b}) end	10✔
299
300	# O(n^2) check all vertice combos for reachability...
301	{_, all_edges} =	10✔
302	Enum.reduce(points_a, {0, %{}}, fn a, {a_idx, acc1} ->
303	{_, inner_edges} =	38✔
304	Enum.reduce(points_b, {0, []}, fn b, {b_idx, acc2} ->
305	# NOTE: this is where the edge value is becomes the key in the
306	# graph. This is why a_idx and b_idx are available here, in case we
307	# want to change it up to be the indexes into points. Unless those
308	# two sets are the same, using the indexes makes no sense.
309	if a != b and is_reachable?.(a, b) do	148✔
310	{b_idx + 1, acc2 ++ [{b, cost_fun.(a, b)}]}
311	else
312	{b_idx + 1, acc2}
313	end
314	end)
315
316	{a_idx + 1, Map.put(acc1, a, inner_edges)}
317	end)
318
319	Map.new(all_edges)	10✔
320	end
321	end

eskil / scurry / be54ba3aace9ecff1535e1d40e083e9a228d1b7d

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous