Create 3D space

[jackiekazil]

Discussed in #1631

^{Originally posted by jackiekazil April 13, 2023}
RE: This paper - https://pure.manchester.ac.uk/ws/portalfiles/portal/216122722/FULL_TEXT.PDF

Some Python frameworks for agent-based Modelling do exist, among which we would
like to acknowledge MESA [50]. Many of our design choices align with theirs, but
critical improvements made on the implementation include us supporting three dimensional environments. This is fundamental, for example, to accurately model biological phenomena as highlighted in multiple publications [51–53].

It should be noted for all the domains that are using Mesa, there seems to be an increasing growth in the medical/bio fields.

[jackiekazil]

Important related discussion -- #1500

[EwoutH]

Doing a deep dive in ABM environments, and in the spatial dimension 3D indeed looks like an obvious next step.

Probably some concept of height/elevation would also be useful, even if it's not full 3D-space. For example, animals could use more energy walking uphill, water could flow from low to high, temperatures could be lower at higher altitudes.

In the current grids that could be as simple by adding a "elevation" property to each grid cell. An implementation of #1889 could potentially help with that.

[EwoutH]

This could be a specific implementation of that:

• Add Triangle mesh space #1896

[victorsouza89]

Hey! I was thinking a bit about this problem. This implementation seems important. In addition to the many applications in three dimensions (as the medical one cited), the N-dimensional case is useful if some similarity in parameters leads to interaction. I can think of drones that communicate iff they are close and tuning into a similar frequency for example (in this case the actual neighbors are defined by a distance function in a 4D space, x, y, z and frequency).

My first idea to approach was a somewhat lazy one. I thought on mapping the $n$-dimensional World into a 1 or 2-dimensional one. This is possible as $n<\infty$ and would mean adopting a matrix-representations of tensors. I guess this mapping can be also used to adapt the distance functions and the retrieving of neighbors. This tentative would mean being able to reuse the existing Grid and ContinuousSpace functions. There are some problems with this approach however. First, I fear this mapping would may be realized in too many operations, so it can bring performance issues in big examples. Second, this i think would be less legible and some natural incompatibility will arise (for example I would be not sure on how adapting the HexGrid).

The best idea to solve this is, then, to rewrite most of the classes at mesa/space.py I think. In reflecting about this I highlighted some points that could be a roadmap and represent doubts:

1. It seems natural to me that the first implementation to try is on Single and Multi N-Grids. As suggested in Proposal: Adding Cell Properties to Grids in Mesa #1889, I think this is an opportunity to unifying the two of then (by introducing a 'capacity' property for cells). What do you think about it? This is the most simple case, in which each cell is a N-hiper-cube (having 2N neighbors).
2. Also, I read the Create a N-dimensional grid #1500 discussion and, despite of the performance concerns, I thought using numpy's ndarray, for compatibility and simplicity. Do you think it's not a good idea? Do you have some alternative in mind?
3. As a second step, I thought on trying to implement the N-ContinuousSpace class. I think it's important to allow an easy definition of not trivial metrics in these scenarios, as for high dimensional space the euclidean distance is frequently not the most useful. Do you agree?
4. Finally, inspired by the HexGrid, I thought on implementing a N-Hiper-P-Polygonal Grid, that allows defining cells as having P neighbors. This also relates to the Add Triangle mesh space #1896, as this would allow triangular grids. Do you think it's useful?

I'm thinking on writing a proposal to GSOC based on these implementations. Do you think its feasible (I think it would be a medium or large project but not sure)? Do you have any other remarks or think of something that would be a nice implementation in this context? Thanks!

[victorsouza89]

I reflected further on the last item. Finding a tessellation for an arbitrary polygon in a arbitrary euclidean space is a way more complicated problem than I was considering. In $\mathbb{R}^2$ there are only three regular ones. They're exactly the ones induced by the square, the hexagon and the triangle. In higher dimension things are kinda complicated. It seems to me that a feasible approach would be implementing the three regular tesselations in $\mathbb{R}^2$ and generalizing to higher dimensions.

This paper describes a good way of implementing both the hexagonal and the triangular grids and finding their neighbors in $\mathbb{R}^2$. That shall be easy. Also, I already figured a way of generalizing the hexagonal grid to $\mathbb{R}^n$. I guess the triangular case will be similar.

Describing my idea. Following the paper's definitions, the cells on an hexagonal grid are in $H^2 = \{ (x,y,z) \in \mathbb{Z}^3 : x+y+z=0 \}$. For $\mathbb{R}^n$, it suffits defining the space is $H^n = \{(x_i) \in \mathbb{R}^{n+1} : \sum x_i = 0\}$. Adopting the natural metric $d(p, q) = \frac{\sum |p_i - q_i|}{2}$ there are going to be, then, $n(n+1)$ neighbors for each cell.

I think, after this, that the scope of my proposal is more or less done: To implement n-dimensional variations for Grid, HexGrid, TriangularGrid and the continuous case. I'm still though a bit hesitant about how to classify the project (medium or large).

I'll try to start writing a definitive version of it and send until Monday. I know that there are probably a lot of people contacting you right now but I would appreciate some feedback if you can do it. In any case, I hope to talk soon! :)