I'm trying to implement in Elixir some of the maze generation algorithms from the excellent book Mazes for Programmers by Jamis Buck. In imperative languages like Go or V it's a piece of cake but with Elixir I'm stuck.
A maze is a grid of cells. A cell holds information about in which direction we can move. It is represented as a struct with boolean members (north: true or east: false, etc.). A grid is a map where keys are tuples {col, row} and values are Cells. If mz is a maze, mz.grid[{0, 0}] is the cell located at the upper left corner.
One of the basic operation is to open a path from one cell c1 to another c2 and most of the time, if we can go from c1 to c2, we can also go from c2 to c1 which means this operation modifies both cells. To implement this, I have a function open_to(maze, x, y, direction) which returns a tuple of two cells c1_new and c2_new where the direction information in each cell had been changed. Then I can update the grid with Enum.put(maze.grid, {x, y}, c1_new). Same for c2_new.
One of the most simple algorithm, the binary tree algorithm, needs to visit all cells one by one and open a bidirectional link with one of the neighbors. Bidirectional means that both cells need to be updated and the second cell may be visited only later. I'm stuck at this step as I can't find how to update the grid with the cells returned by open_to(). My Elixir pseudo code is as follows:
def generate(mz) do
Enum.map(mz.grid, fn({{x, y}, c1}) ->
neighbors = [Grid.cell_to(mz, x, y, :north), Grid.cell_to(mz, x, y, :east)]
c2_dir = select_the_neighbor(neighbors) # returns one of :north, :east or nil
# Here! open_to returns the updated cells but what to do with them?
{c1_new, c2_new} = if c2_dir != nil, do: Grid.open_to(mz, x, y, c2_dir)
end)
end
I believe the issue comes from the data structure I've chosen and from the way I go through it, but I can't find another way. Any help is appreciated
If I'm understanding the question it's "how can each step in Enum.map/2 update the maze and have that visible to each other and the final result?".
Where data structures in Elixir are immutable, you don't change the data another variable points to.
As a simple example, putting a key/value pair into a map creates an entirely new map:
iex(1)> map = %{a: 3}
%{a: 3}
iex(2)> Map.put(map, :a, 4)
%{a: 4}
iex(3)> map
%{a: 3}
In a similar fashion, Enum.map/2 isn't intended for modifying anything except the value currently being operated on (and even then only in the new list, not the original). If you want to update some value based on each cell you may be looking for Enum.reduce/3. It enumerates things like Enum.map/2, but it takes a value or "accumulator". The reducer function you pass in is called with an item and the accumulator and ought to return the updated value of the accumulator. Then the final value of that accumulator is what is returned from Enum.reduce/3.
So your pseudo code might look something like this:
def generate(mz) do
# don't use the c1 from enumerating the grid--it could be out of date
# you could also just enumerate the grid coordinates:
# - for x <- 0..width-1, y <- 0..height-1, do: {x, y}
# - Map.keys(mz.grid)
Enum.reduce(mz.grid, mz, fn {{x, y}, _dont_use_this_c1}, mz ->
neighbors = [Grid.cell_to(mz, x, y, :north), Grid.cell_to(mz, x, y, :east)]
if c2_dir = select_the_neighbor(neighbors) do
{c1_new, c2_new} = Grid.open_to(mz, x, y, c2_dir)
mz
|> Map.put({x, y}, c1_new)
|> Map.put(find_x_y(x, y, c2_dir), c2_new)
else
# you have to return a maze, or other iterations will try adding cells to nil
mz
end
end)
end