RadiusAreaProvider Feedback

[NineSigma]

I have no problem with the technical workings of RAP - in fact it seems to work great, and it's significantly faster than I expected. There is an issue with communicating the intent and design of the class, and there is an important (or at least it seems to me) missing element in the library that would grease the wheels of this class and provide that extra boost of utility for many of the other functions.

The documentation for RAP recommends holding onto a single instance of the class for as long as possible due to heavy costs under the hood. However, it's not really clear why that is unless you glance over the source of Positions(). When you're in the editor, Positions() looks a lot like the kind of property that just returns a field. Even the documentation only just barely hints that it is the main workhorse of the class. A simple renaming to CalculatePositions() or similar would be a good start. The documentation should not be expanded, really, but it should be adjusted. Specific recommendations would be mentioning the current radius and how that would differ from a new radius. There's a consideration to moving some of the comments from class heading into the method heading.

Again, it's just about communicating the design and intent of the class. Renaming the function and/or splashing a few adjectives around in the documentation would make it a lot more clear. Having a few unusual things like Coord.Get() and RAP.Positions() is not a problem at all if you put them front and center, with respect to documentation.

As for other related feedback, one thing that I've found myself doing with high frequency, particularly in relation to RAP, is dealing with the issue of unique Coords. I was just looking at my overall code today and found that a surprising amount of it was devoted to carrying around containers of Coords and doing lots of checks on them, particularly whether a Coord was already present in the container. You can imagine the relation here to RAP.

In some instances, this has actually caused fairly extensive utility-work where I'm hunting for C# solutions to dealing with uniqueness. All experienced C# developers have probably run into List.Contains( item) eating up every CPU cycle in the western hemisphere, but it was a new thing for me. I eventually settled on a "good enough for now" HashSet solution and will probably have to revisit that in the future when the demand for cycles expands.

It didn't occur to me until today that avoiding this type of distraction is exactly the reason I favor this library so much. I'm not sure whether this fits with your vision, but it seems to me that a container optimized specifically to carry around and manipulate Coords could provide a lot of leverage to the library.

Thanks very much for all your work on this library; I find myself eagerly anticipating upcoming features and docs.

[Chris3606]

Thank you for the feedback!

I definitely see your point about the RAP.Positions() function -- it seems very much like a property and it isn't indicated well that it's performance intensive/the main workhorse. A rename to CalculatePositions or Calculate in general would absolutely go a long way toward cleaning this up, and will likely end up in the next released version (along with a documentation tweak).

As for the uniqueness problem, HashSets are the most common solution, you're not alone there. Your hash-set solution though will likely hold out for a fairly long time, depending on where it's used -- Coord provides a custom GetHashCode implementation which uses a pretty efficient hash calculation (particularly when considering only coordinates in range (-3, -3) to (255, 255)). This is to say that the hashing algorithm provided has a particularly low collision rate when dealing when coordinates in that range, so the HashSet-type solution isn't as bad as it might seem.

Other than that hashing algorithm that makes HashSet not terribly inefficient, the closest class to what' you're talking about, I believe, in GoRogue currently is MapArea (in GoRogue.MapGeneration). It's effectively a wrapper around the HashSet that I believe provides some of the functionality you are looking for, including some "operations" (union, intersection, that type of thing). It's not the most memory efficient though, as it uses both a List of Coords and corresponding HashSet of those Coords internally, to preserve insertion order. This may change in the future, though, as the more I look at it the more I debate whether keeping both is necessary. Furthermore, since Coords have a particularly small memory footprint, the extra memory usage will likely not be a problem.

but it seems to me that a container optimized specifically to carry around and manipulate Coords could provide a lot of leverage to the library.

When you say "manipulate Coords", what sort of operations are you referring to? I'd certainly be open to adding a class, or extending a current one, if we can establish what sort of features are useful in that context.

[Chris3606]

Another note: As I think about this, I do start to think it might be beneficial for RadiusAreaProvider to expose its Positions() as a MapArea, rather than the current list -- it would more easily enable Contains() type operations on the result. I'll have to think about and investigate this.

[NineSigma]

MapArea does seem to hold some of the functionality I was talking about. I've actually never even used or read MapArea except for the Rectangle.GetExactUnion() method***, apparently. As the wiki fills out more, it will make stuff a lot more obvious to, let's say, less savvy programmers like myself.

It's interesting reading over MapArea because there seems to be a natural convergence of ideas here. At the moment, I'm just using a HashSet, but I envisioned at the time (of surrender) having to come back and write something bigger with both a HashSet and a List. For my purposes I wanted a List for fast random access (i.e. 'give me a random Coord in the list') and a HashSet for fast uniqueness checks.

***On that note, is there a more clever way to get all the Coords in an area than GetExactUnion( myRect, myRect)?

---

The most demanding code involving Coords is map generation algorithms, and depending on the flavor of algorithm I'm often doing a Coord-by-Coord operation. The most common task is dividing Coords into distinct sets like open/closed or walkable/not or available/not. This means Add() is the most used utility. For most of these divisions, sets are mutually exclusive and so Add() is coupled unavoidably with Contains() or similar-type operation.

The next most common task with Coords is returning a random Coord from a set. This is used in numerous algorithms. This operation is quite fast with a List and fairly slow with a HashSet. This is available (at a glance) by just putting a random index on the MapArea.Positions() return.

The next most common operation I see is Remove() which is notably missing from MapArea. This one is too important for many usages to do without, and you can't modify the Positions() return so it would have to be explicitly added into the class. It would involve a lot of extra code as well to make sure the boundaries are always correct. Might not be the way to go.

But there are other types of common operations/manipulations on containers of Coords that are seemingly beyond the scope/intention of MapArea. Off the top of my head, a list of useful functionality for a hypothetical new instrument:

container.Add/Remove/Contains( Coord c)
Coord container.GetRandomCoord()
container.SortByDistance( Coord reference, Distance type)
container.Next() to go with the SortByDistance
bool container.ShiftBy( Coord deltaR, Rect bound) - shifts every held Coord by a specific amount if the results are all within the boundary
Container container.Intersect/Union(Container aDifferentContainer)

I'm constantly using operations like this but in a messy, disconnected way - I'm sure there are other sensible ones to consider for such an instrument. Coords are the superstar/central object of the library. Hopefully you can see what I mean about something like this gluing lots of GoRogue functionality together. Maybe it would be separate from MapArea or maybe MapArea could just get a bit more buff. I'm no library architect, but in my mind, the idea of a "universal" Coord container seems like it could fit into many places.

---

On the topic of MapArea as a return type, I would say that it's better in general if the library "promotes" itself. Return types can always be "recast" by foreach etc. unless there are critical performance considerations. From my perspective, having things return library-specific types makes for cleaner code.

[Chris3606]

I may have more comments here later when I'm not typing on a phone, however:

Without the wiki I do realize it is difficult to locate and utilize features, particularly for something like MapArea which originally was only intended for map generation. This is why working on the wiki has significantly increased in priority recently - the problem is something I hope to remedy.

I can definitely see a case for a separate data structure, or an extension/introduction of inheritance tree to the existing map area. There are a number of operations that might make sense to add, cited in your example.

As for extracting a random position, this should actually be quite easy with the existing MapArea. The Positions property in MapArea returns IReadOnlyList. GoRogue provides an extension method for IReadOnlyList called RandomItem that returns a random item from the list, so provided using GoRogue; is included in the source file, one should be able to get a random position using myMapArea.Positions.RandomItem().

[NineSigma]

I retooled one of my more intensive mapgen algos to use MapArea (since it didn't require Remove() ). I'm very happy with the performance so far, and I'm glad you suggested it. I've also started placing RandomItem() in various places - a very nice extension!

[Chris3606]

Glad it's working out! I do actually recommend checking out the Utility.cs file in general, if you haven't already. It contains the RandomItem extension method previously discussed, along with a similar method RandomIndex, as well as a number of other extension methods for various C# data structures.

[Chris3606]

Closing this issue for the sake of organization, see above noted issues for issues open specific to the enhancements discussed.