Agents.jl : how to smartly implement Triangular and Hexagonal Grids

[Rouzaire]

Hello everyone,

First of all, I would like to thank the devs for the great piece of work that is Agents.jl .

In the world of two dimensional lattice, the square one is ubiquitous in numerical simulations. In this package, the square lattice GridSpace and its one-agent-per-node counterpartGridSpaceSingle are subtypes of the abstract type AbstractGridSpace .

Yet, at least in physics and hence for my work, triangular and hexagonal (aka honeycomb) lattices are very useful.
For instance

• the triangular lattice and its 6 nearest neighbours is the closest one to a continuum description. Some artifacts of the square lattice just disappear with the triangular lattice.
• the hexagonal lattice and its 3 nearest neighbours is useful to study simple magnetic frustration for instance.

Question
Does anyone have any idea about how I could easily extend the concept of GridSpace to TriGridSpace and HexGridSpace , as the only crucial function that differs is the search for nearest neighbours ?

Trials
I have tried to define a struct TriGridSpace <: GridSpace but I get the error invalid subtyping in definition of TriGridSpace since (if I understood correctly) GridSpace is a concrete (thus leaf) type.
I have also tried to simply add a weird metric to the already existing chebychev / euclidian / manhattan to transform a square lattice into a triangular one but it would lose the genericity of the whole thing with respect to a 3D space.

Many thanks in advance,
Ylann Rouzaire

[Datseris]

Hello! Thanks a lot for the kind words! I’m very interested in helping you implement a hexagonal grid (I’m not convinced yet that triangular is also necessary if one has hexagonal, but oh well).

Have you seen Developer Docs · Agents.jl ? That’s the place to start. It tells you the basics of what is needed to create a new space type. You should also look at the implementations in the source code for GraphSpace and GridSpace.

The hard part is for you to decide how the space will keep track of agents position and how it will find their neighbors. I know there are ways to represent a hexagonal grid with a standard orthogonal array, that could be on direction. MASON, an ABM in Java, also has hexagonal grid although I doubt reading its source code would be easy. In any case that’s the hard task, the rest is extending API functions which is rather straightforward.

You cannot create a hexagonal grid with creating a fancy metric, at least not in Agents.jl. It would be too complex and inefficient way to do it. You need a new space.

My recommendation is for you to open a Pull Request at Agents.jl in which you try to add a hexagonal grid and there developers and other people may comment and help you. I’m a bit busy at the moment but I’ll be chiming in from time to time.

Yes, GridSpace is concrete, you need AbstractGridSpace.

[Rouzaire]

Thank you for the quick answer !

My Answer

Have you read the docs ?

Yes, I have read the docs of Agents.jl and of Graphs.jl (which strangely does not seem to export basic regular lattices …). I have also read part of the source code of Agents.jl but I still lack a general point of view.

You cannot create a hexagonal grid with creating a fancy metric, at least not in Agents.jl. It would be too complex and inefficient way to do it. You need a new space.

I agree, I just stated it for completeness. In fact, I have already run my own simulations on 2D triangular lattices and indeed, one can use a simple 2D matrix to store the positions and the only difference (apart from plotting, which can become tricky or very inefficient) is accessing the neighbours.

My recommendation is for you to open a Pull Request.

That would be the first time I participate in a collaborative project. Funnily, the only theoretical knowledge I have of it actually comes from one of your videos : Good Scientific Code Workshop.

Motivation

A quick point on the on the utility of the triangular lattice, which you appear to doubt.
First, I once again state that the triangular lattice is the closest one can possibly get to the continuum space, which means that this is the lattice that minimizes the most the artifacts that discrete lattices usually induce in Agent Based Simulations. For example, I don’t think I will come back to the usual square for my research.
Then, I mention that a lot of well-known physics phenomena differ if taking place on hexagonal / square / triangular lattices. I take for illustration the Percolation threshold problem, easily extendable to active agents. Plus, here the triangular lattice has a very simple (1/2) site percolation threshold and a complicated yet theoretically tractable bond threshold 2\,\sin (\pi/18), I believe it could one day serve as a benchmark for more advanced research.

Suggestions / Ideas

In my opinion, the Agents.jl package would gain from an even easier way to define new subtypes of GridSpace (triangular / hexagonal, even the very common Kagome lattice etc).

Correct me if I’m wrong but I think that the methods add_agent_to_space! , remove_agent_from_space! etc should not depend on the specific type of grid you want.

While I am at it : since the recent addition of GridSpaceSingle is a great idea and will benefit a lot of users, here is another suggestion :
To help/simplify further creation of discrete lattices, would it be imaginable to integrate the property “single” into the struct itself, as already done for the property “periodic” : GridSpace{Dimension,Periodic,Single} ?
It makes conceptual sense and would avoid code duplication for new subtypes of GridSpace (TriGridSpace and TriGridSpaceSingle for instance) .

Many thanks,
Once again, please let me know if something is unfeasible as I’m novice to collaborative code.

[Datseris]

@Rouzaire

apart from plotting, which can become tricky or very inefficient

Agents are always scatterplotted according to their posiiton. Plotting is unaffected as far as I can tell.

@Rouzaire

Funnily, the only theoretical knowledge I have of it actually comes from one of your videos

That’s good enough !

@Rouzaire

A quick point on the on the utility of the triangular lattice, which you appear to doubt.

Sure, having a triangular lattice is totally fine. I did my PhD in graphene so I am biases towards hexagonal You should implement what fits your problem better.

@Rouzaire

Correct me if I’m wrong but I think that the methods add_agent_to_space! , remove_agent_from_space! etc should not depend on the specific type of grid you want.

You are wrong unfortnately so I have to correct you These methods are about how the space internally stores agents. Already in GridSpace and GridSpaceSingle this is different, one being an array of vector, the other an array of integers. So, this cannot be less complicated than it is now. In a triangular space, agent position would agent be mapped differently to the internal representation which is not exposed to the user.

@Rouzaire

To help/simplify further creation of discrete lattices, would it be imaginable to integrate the property “single” into the struct itself, as already done for the property “periodic” : GridSpace{Dimension,Periodic,Single} ?

Yes, this is possible, because it simply represents the internal array element type. At the moment it wouldn’t remove any duplications yet it would complicate the source code more. Once you have a working implementation of a triangular space we can see if this indeed removes duplications and is worthy to do.

---

At the moment it is not clear to me yet how you would implement the triangular space so that it is performant. Remember: nearest neigbhor searches is the main thing to be implemented performantly. That’s why I am advocating for a pull request. Most of your suggestions are feasible, but this doesn’t necessarily mean that they are worthy to do. To judge that, we would need some initial working code.