FredrikAugust · September 27, 2018 22:32 · Sep 27, 2018 · Sep 27, 2018 · Sep 27, 2018
diff --git a/README.md b/README.md
@@ -3,7 +3,7 @@ up getting stuck in a situation where I would have to rewrite a lot of the struc
 
 In A* you normally want to keep track of who added to the open list (a parent), so that you don't end up jumping
 to a random tile that's close just because you've been there before -- you have to be a parent. Sadly, I forgot about this
-(silly me), and thus this does not work particularly well for mazes etc.
+(silly me), and thus this does not work particularly well for mazes etc. (Though it works for this example :tada:)
 
 Will probably rewrite this in the near future, though probably not in Elixir, as I do not believe it is a good fit for this
 use-case.

diff --git a/README.md b/README.md
@@ -6,4 +6,6 @@ to a random tile that's close just because you've been there before -- you have
 (silly me), and thus this does not work particularly well for mazes etc.
 
 Will probably rewrite this in the near future, though probably not in Elixir, as I do not believe it is a good fit for this
-use-case.
+use-case.
+
+PS: it should also be noted that this is not meant to be looked at as something I've tried to do my best in -- it was merely a sketch.
diff --git a/README.md b/README.md
@@ -0,0 +1,9 @@
+So, this was a quick attempt at trying to implement the A* pathfinding algorithm in Elixir. Sadly I didn't plan this well enough, and ended
+up getting stuck in a situation where I would have to rewrite a lot of the structure to make it work properly.
+
+In A* you normally want to keep track of who added to the open list (a parent), so that you don't end up jumping
+to a random tile that's close just because you've been there before -- you have to be a parent. Sadly, I forgot about this
+(silly me), and thus this does not work particularly well for mazes etc.
+
+Will probably rewrite this in the near future, though probably not in Elixir, as I do not believe it is a good fit for this
+use-case.
diff --git a/astar.ex b/astar.ex
@@ -0,0 +1,127 @@
+defmodule Astar do
+  @start_pos {0, 0}
+  @end_pos {4, 4}
+
+  @maze [
+    [0, 0, 0, 0, 0],
+    [0, 1, 0, 0, 0],
+    [0, 1, 0, 0, 0],
+    [0, 1, 0, 1, 0],
+    [0, 0, 0, 0, 0]
+  ]
+
+  def distance(nil, _), do: 0
+
+  def distance({x1, y1}, {x2, y2}) do
+    abs(x1 - x2) + abs(y1 - y2)
+  end
+
+  def g(current_pos) do
+    distance(current_pos, @start_pos)
+  end
+
+  def h(current_pos) do
+    :math.pow(abs(elem(current_pos, 0) - elem(@end_pos, 0)), 2) +
+      :math.pow(abs(elem(current_pos, 1) - elem(@end_pos, 1)), 2)
+  end
+
+  def f(%{pos: current_pos}) do
+    g(current_pos) + h(current_pos)
+  end
+
+  def get_pos({x, y}), do: Enum.at(@maze, y) |> Enum.at(x)
+
+  def valid_node(%{pos: {x, y}}) do
+    x >= 0 && x < length(Enum.at(@maze, 0)) && y >= 0 && y < length(@maze)
+  end
+
+  def neighbours(%{pos: {x1, y1}}) do
+    [{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}]
+    |> Enum.map(fn {x2, y2} -> %{pos: {x1 + x2, y1 + y2}, g: nil, h: nil, f: nil} end)
+    |> Enum.filter(&Astar.valid_node/1)
+  end
+
+  def solve do
+    open_list = [%{pos: @start_pos, g: 0, h: 0, f: 0}]
+
+    closed_list = []
+
+    solve(open_list, closed_list)
+  end
+
+  def tap(a) do
+    IO.puts("TAP ...")
+    IO.inspect(a)
+
+    a
+  end
+
+  def solve(open_list, closed_list) do
+    case {open_list, closed_list} do
+      {[], _} ->
+        IO.puts("DONE - no path")
+
+      {_, [%{pos: @end_pos} | _]} ->
+        IO.puts("DONE - path!")
+        IO.puts("PATH: ")
+
+        closed_list
+        |> Enum.reverse()
+        |> Enum.map(& &1.pos)
+        |> Enum.map(&"(#{elem(&1, 0)}, #{elem(&1, 1)})")
+        |> Enum.join(" -> ")
+        |> IO.puts()
+
+      _ ->
+        current_node = Enum.min_by(open_list, & &1.f)
+
+        new_open_list = Enum.reject(open_list, &(&1.pos == current_node.pos))
+        updated_closed_list = [current_node | closed_list]
+
+        IO.inspect(Enum.reverse(Enum.map(updated_closed_list, & &1.pos)))
+        IO.puts("CURRENT POS #{elem(current_node.pos, 0)}-#{elem(current_node.pos, 1)}")
+
+        IO.puts("NEIGHBOURS")
+        IO.inspect(neighbours(current_node))
+
+        IO.puts("NEW OPEN LIST")
+        IO.inspect(new_open_list)
+
+        current_node_neighbours =
+          neighbours(current_node)
+          |> Enum.reject(fn neighbour ->
+            Enum.member?(Enum.map(updated_closed_list, & &1.pos), neighbour.pos)
+          end)
+          |> tap
+          |> Enum.reject(&(get_pos(&1.pos) == 1))
+          |> Enum.map(
+            &%{&1 | g: current_node.g + distance(&1.pos, current_node.pos), h: h(&1.pos)}
+          )
+          |> Enum.map(&%{&1 | f: &1.g + &1.h})
+          |> Enum.map(fn neighbour ->
+            case Enum.member?(Enum.map(open_list, & &1.pos), neighbour.pos) do
+              true ->
+                case neighbour.g > Enum.find(open_list, &(&1.pos == neighbour.pos)) do
+                  true ->
+                    nil
+
+                  false ->
+                    neighbour
+                end
+
+              false ->
+                neighbour
+            end
+          end)
+          |> Enum.reject(&(&1 == nil))
+          |> Enum.sort(fn a, b -> a.h < b.h end)
+          |> tap
+
+        solve(new_open_list ++ current_node_neighbours, updated_closed_list)
+    end
+
+    :ok
+  end
+end
+
+Astar.solve()