# Grids 2.1

Grids 2.1 was accepted today. It contains a few minor fixes and improvements.

First, we fixed all the examples that were not working. (We also removed two “examples” that was really our “scratch pad” testing scenes and should not have been part of the package in the first place.) We also removed some warnings that we did not spot before. There are a few remaining; they will be eliminated in the update we will post by the end of the week.

We also added a range-finding example. Range-finding gives you all the cells that lie within a certain range (where cells can have arbitrary costs or distances), or alternatively, give you all the cells in range and their costs.

We also improved memory allocation in all the path-finding and range-finding algorithms. We did not entirely eliminated memory allocation though. In many games, this is not a problem, but sometimes it is. We cannot completely solve this problem without reducing the flexibility of the algorithm (which makes it possible, for instance, to specify an arbitrary neighbor function). However, the algorithm is very straight-forward to adapt to avoid allocations completely. If you find it to be a problem, you can create a version form ours pretty quickly to do this. Mostly, this entails replacing generic code with specific code to avoid delagates and behind-the-scene foreach methods. If you need help with this, please ask us on the Knowledge Base.

The node editor we shipped with the first version of Grids is still a bit rough around the edges (from a UX viewpoint). As a first step to improve it, we made it possible to rename nodes (click on the name to edit it) and gave nodes better default names. We also made it possible to disable nodes. When a node is disabled, it simply routes the inputs to the outputs. This is useful especially when working with maps, where you may want to temporarily “take out” a node to see what is going on. We used to do this manually *all the time* when constructing more complicated maps.

One user pointed out that our division operator, as defined on GridPoints, were inconsistent with the C# division operator on integers. This affects only negative numbers. In C#, division by a negative number -n is defined as (-n) / m = – (n / m). There is an alternative definition (this is used by some languages such as Python) where (-n) / m = floor(- ((float) n / m)). In grids, we only use the latter type of division – because we use division to partition grid, and the latter definition gives equal-sized partitions. So we defined the division operator to implement this behaviour. However, it is probably not what programmers expect: if p is a grid point, then most programmers would expect p / n = (p.X / n, p.Y / n). So now we made it so. The old functionality is still there (in the method Div), and that is probably the one you should use in most cases. But at least most programmers will not get surprising behaviour.

On a side note: division is a big deal for us when it comes to grids. In the early days of the development of Grids 1, we frequently looked at how square grid algorithms and data structures could be adapted to hex grids. The algorithms fell into three classes – those that rely on neighbor relationships, those that rely on the notion of straight lines (like “three in a row” in match games), and those that rely on partitioning (such as quad trees and correlated noise). The first class was easily adapted because they were essentially graph algorithms. The second class was also easy to adapt, because hex grids – like square grids – can be treated like a vector space where a line is formed by adding a direction to a starting point. But it took a long time to crack the last class in a general way. We did some of it using grid-colorings as a strut – but over time we discovered the key is a type of division (as we explain in the third section of Hex Geometry for Game Developers). A lot of the design of Grids 2 was shaped by those ideas, and we will write more on that in the future.

In the meantime, we always like to hear your questions, so please ask us 🙂