Support Translation of Coordinates Spaces for Algorithms

[Ven0maus]

I had some trouble getting the supplied AStar algorithm to properly work with a chunked grid. Eg. An entity coordinate was outside of the specified width/height of the internal array used in AStar algorithm. Seems like the pathfinding is always fixed to be positions between 0 and width*height. It would always return no path, since it could not map a world position into the array.

I made an implementation based on this here where you specify the entity and its view range: https://github.com/Venom0us/Mordred/blob/main/Mordred/Entities/PathFinding.cs (The entity could be changed by a positionGetter)

I don't know if it's worth it to include something similar? It basically translates the world position onto the internal grid and vice versa. The only downside is that the pathfinder is only good to be used by that specific entity. (as the entitity(or positionGetter) would always represent the center of the internal array at all times)

[Chris3606]

Hi,

Yep, I think I see what you're saying.

Summary/TLDR

• IMO this is a limitation with the currently supplied portions of the grid view system, and affects all algorithms that use it, not just pathing. Similar logic applies to FOV, SenseMap, or anything else using a grid view.
• Therefore, solving the problem would seem to be a function of adding something to the grid view implementation (which resides in TheSadRogue.Primitives) which allows algorithms to be aware of viewport translations.
• Doing it based on the concept of an entity/object is probably too concrete for the library implementation, however a position is fine.
• This translation is partially implemented by Viewport<T> and UnboundedViewport<T> however these are both still based on a grid view, meaning the base map still must define a set of values from (0, 0) to (Width - 1, Height - 1), which in this scenario, would still require translation. The Viewport<T>` class and similar should probably be implementing some more abstract interface encompassing the concept of arbitrary coordinate translation, to avoid imposing this limitation where it is inconvenient.

Background

The issue you're encountering here is, as you alluded to, inherit in the current implementation of the grid view system, which virtually all GoRogue algorithms (including pathing) use. To be clear on the design considerations that led to this; the grid view system (intentionally) limits itself to defining a coordinate space of (0, 0) to (Width - 1, Height - 1), inclusive, for a number of reasons.

Arguably, the most compelling reason is because it enables significant optimizations to the algorithm, when compared to a structure where the width and height is not known. For example, when Contains, rather than enumeration, is the primary operation needed on a set of points, using a BitArrayView the size of the grid to represent a set of positions is many times faster than using a HashSet<Point>, even when using an optimized hashing algorithm.

In general, this is not a limitation because either a grid is of a defined size, or the area on which an algorithm should operate is of a defined size, and both cases can be represented by grid views; however it does involve some manual grid-view creation in cases like the one you've cited, and there may be room for improvement on that front.

The other notable reason, is that it avoids over-complicating the interface. An algorithm needs needs to know little more than how to retrieve a value for a given (local) coordinate to function; therefore, the interface implementing more than that could reduce the number of use cases for which it is intuitively compatible.

Nonetheless, I do see a use case for coordinate-space translated grid views, which I believe can be supported while adhering to the intent of the above design decisions. Viewport<T> attempts to implement some concept of translating coordinate schemes, but implements primarily the concept of translating a larger grid view to a smaller one which can be positioned on the large one (like you might a top-down camera). This does not easily support all use cases, primarily for two reasons:

• Algorithms such as AStar still have no concept of whether they are using a viewport of not; so they cannot perform coordinate translation on the inputs to public functions.
• The concept is based on the concept of representing a subset of a larger grid view, and as such is subject to the same limitations as all grid views are (namely, a coordinate space defined from (0, 0) to (Width - 1, Height - 1). If you need to perform some coordinate translation get to that point (as you do in your chunk-loaded map use case), the viewport is not of direct use.

Solution Design Considerations

The most compelling case for adding some sort of support for coordinate-space translated coordinates (eg translating a global coordinate to an local x/y normalized to (0, 0) -> (Width - 1, Height - 1)) is that providing this functionality, as you learned, currently requires wrapping the algorithms themselves. This is because, if the algorithms themselves are not aware of the fact that there is some sort of coordinate-space translation going on, they can't perform any coordinate translation on what a user passes in, or the result they hand back to the user. Your use case is a great example of this; if a user is performing coordinate translation in order to retrieve a grid view for AStar, they probably want to still pass global coordinates to the ShortestPath function, and have the algorithm perform the translation if needed.

The flip side, is that users who are not performing the translation don't need any feature related to doing so. Therefore, in the ideal case, we want to avoid negatively impacting aspects of the design for those users as much as reasonable. These include:

• The complexity of the API
• The performance of the algorithm

In particular, these considerations rule out some otherwise obvious solutions. One thing that, ideally, we do not want to do, is have the user specify a Func used to perform coordinate translation when creating an AStar or other algorithm instance; first because it complicates the API (although this is solved via the use of a default argument), and more importantly because it is very likely to impact performance, even for users that don't need to perform coordinate translation. Most algorithms, to include FOV and AStar, access the value of various positions in their grid view frequently; therefore the overhead of an additional function call can actually matter from a performance perspective. Func is particularly impactful here (compared to a virtual function or other method of specifying code to run) because, the JIT compiler in the dotnet runtime is not particularly good at optimizing Func calls; namely, it seems to almost never be able to inline them (even when the equivalent virtual function sometimes can be inlined). This is why, in more recent versions of GoRogue, internal structures such as GameFramework.Map go out of their way to avoid the use of LambdaGridView (opting to go for custom interface implementations instead); because it does, in some cases, impact performance in a meaningful way.

Proposal 1

In line with these considerations, I would propose something in the neighborhood of the following changes. Any code listed here is purely conceptual in nature; names, syntax, and even details of the API likely need to be tweaked, etc:

1. Add an interface similar to the following to the primitives library:

// Represents grid views that are translating between coordinate spaces.
// Any algorithm which gets specified a grid view that implements this may
// assume that there is a global coordinate space which is different than the one
// they use, and that their public interface should operate in terms of the global
// coordinate space.
public interface ICoordSpaceTranslatingGridView<T> : IGridView<T>
{
    public Point GlobalToLocalPosition(Point globalPos);
    public Point LocalToGlobalPosition(Point localPos);
}

2. Modify Viewport<T> and similar classes to implement this interface, something like:

public class Viewport<T> : ICoordSpaceTranslatingGridView<T>
{
public Point GlobalToLocalPosition(Point globalPos) => globalPos - ViewArea.Position;
public Point LocalToGlobalPosition(Point localPos) => globalPos + localPos;

/* Existing implementation here */
}

3. Modify algorithms to be aware of if their viewport implements this interface, something like:

public class AStar
{
    public Path? ShortestPath(Point start, Point end, bool assumeEndpointsWalkable = true)
    {
        if (WalkabilityView is ICoordSpaceTranslatingGridView<bool> csView)
        {
            start = csView.GlobalToLocalPosition(start);
            end = csView.GlobalToLocalPosition(end);
        }
        
        // Modifications to the Path structure are also required, but omitted here for brevity
        CallCurrentShortestPathAlgo(start, end, assumeEndpointsWalkable);
    }
    /* Existing implementation here */
}

Solution Analysis

The above proposal tries to reach a solution which is as generic as possible, while preserving any possible performance attributes for cases where translation is not necessary. It attempts to do so while incurring as few breaking changes as possible, and in a way that is portable to nearly any algorithm.

The Good

• The above solution (in concept) allows algorithms to be aware of if their grid view is representing a local coordinate space which is different than the global one a user uses, which enables the algorithms to perform the intended translation.
• Because the solution is almost entirely contained within the existing grid view concept:
  • Virtually no breaking changes (only breaking for those currently using Viewport with these algorithms)
  • Virtually no performance cost for people not performing coordinate translation. In the above example, the added performance cost would be:
    • The cost of the ICoordSpaceTranslatingGridView cast-and-check, which occurs only once per shortest-path call
    • The cost of checking if it is needed to perform the local-to-global translation of points added to the resulting path. This scales with the length of the path, rather than the number of nodes visited, and as such is (hopefully) trivial compared to the other operations.
  • Minimized performance cost for those who are performing coordinate translation (and the flexibility to decide performance attributes therein). In short, it leaves the performance vs ease of use decisions up to the user
    • The only truly mandatory cost during the pathing operation, is exactly the same as what it is for those who are not performing translation.
    • If a user wants to implement a traditional, translate-coordinates-as-requested model, they can do that, more or less exactly as Viewport<T> or your example would do; the indexer performs translation just like the GlobalToLocal and such functions do.
    • If a user needs to avoid the overhead of performing the translation on every indexer access, they could do that by maintaining a cache of local-coordinate values in an ArrayView or BitArrayView, and have the indexers access values with no translation, but still implement the ICoordSpaceTranslatingGridView to perform translation.
• The method of providing this functionality is standardized, so it's easily portable to virtually any algorithm where it makes sense
• The method of providing this functionality makes as few assumptions about the user's architecture as possible; it assumes only that they have a global coordinate space and want public API functions to perform translation.

The Bad

• It adds depth to the grid view inheritance structure; which could make the API as a whole more complex to understand, in entirety.
  • In particular, the solution is non-obvious to a user who hasn't specifically read documentation about it. A user looking at the constructor or function signatures for AStar will see no indication that it supports coordinate translation.
• It could potentially allow algorithms which appear like they should support translation, but do not; if an algorithm forgets to check for the interface type and perform translation, passing a ICoordSpaceTranslatingGridView will have no effect.

Proposal 2 coming soon...

[Chris3606]

Proposal 2

The following is an attempt to simplify the API of proposal 1 without losing many of the benefits.

1. Create an interface (possibly in the primitives library):

public interface ICoordinateSpaceTranslator
{
    public Point GlobalToLocalPosition(Point position);
    public Point LocalToGlobalPosition(Point position);
}

Additionally, probably provide concrete implementations of this interface that fit common scenarios.

2. Modify algorithms to take one of these as a parameter, for example:

public class AStar
{
    public AStar(IGridView<bool> walkabilityView, Distance distanceMeasurement, ICoordinateSpaceTranslator? coordinateSpaceTranslator = null)
            : this(walkabilityView, distanceMeasurement, null, null, 1.0)
        {
            CoordinateSpaceTranslator = coordinateSpaceTranslator;
        }
    /* Similar modifications to other constructors */
}

3. Modify the algorithms to use the coordinate space translator, if it exists, for example:

public class AStar
{
    public Path? ShortestPath(Point start, Point end, bool assumeEndpointsWalkable = true)
    {
        if (CoordinateSpaceTranslator != null)
        {
            start = CoordinateSpaceTranslator.GlobalToLocalPosition(start);
            end = CoordinateSpaceTranslator.GlobalToLocalPosition(end);
        }
        
        // Modifications to the Path structure are also required, but omitted here for brevity
        CallCurrentShortestPathAlgo(start, end, assumeEndpointsWalkable);
    }
    /* Existing implementation here */
}

Solution Analysis

The above solution tries to allow algorithms to be aware of coordinate translation taking place, in a generic way that provides similar benefits to the first proposal. However, this is an attempt to simplify the API and make it more obvious for new users, and less likely to result in subtle bugs.

The Good

• The above solution (in concept) allows algorithms to be aware of if their grid view is representing a local coordinate space which is different than the global one a user uses, which enables the algorithms to perform the intended translation.
• Just by looking at the constructor of an an algorithm, it is more obvious (compared to the first proposal) that an algorithm supports viewport translation.
• It is less likely to create subtle bugs where an algorithm (library-side or user created) can accept a grid view that implements the "translation" interface, but not perform the correct cast-and-check.
• The implementation doesn't add to the inheritance/composition relationship already present in IGridView, which may simplify the overall interface
• Few breaking changes (typically only reflection use cases or those affected by the addition of a default parameter)
• Virtually no performance cost for people not performing coordinate translation. In the above example, the added performance cost would be:
  • The cost of checking for null in the CoordinateSpaceTranslator parameter, which occurs only once per shortest-path call
  • The cost of checking if it is needed to perform the local-to-global translation of points added to the resulting path. This scales with the length of the path, rather than the number of nodes visited, and as such is (hopefully) trivial compared to the other operations.
• Minimized performance cost for those who are performing coordinate translation (and the flexibility to decide performance attributes therein). In short, it leaves the performance vs ease of use decisions up to the user
  • Same concept examples as proposal 1
• The method of providing this functionality is standardized, so it's easily portable to virtually any algorithm where it makes sense
• The method of providing this functionality makes as few assumptions about the user's architecture as possible; it assumes only that they have a global coordinate space and want public API functions to perform translation.

The Bad

• It is not up to the grid view implementation as to whether public translation occurs. This has both "feature" and "unintuitive behavior" arguments. One on hand, certain grid views such as ArrayView or BitArrayView could be useful, as-is, both with and without a coordinate translator. On the other hand, it would rarely make sense to use a Viewport<T> without one; and doing so may produce behavior that is somewhat difficult to debug.
  • The only solution to this is to couple it to the grid view; but as outlined in proposal 1, this is less flexible from an existing grid-view re-use standpoing and as such has its own problems. Arguably, this is less of an issue than some of the "API functionality is non-obvious" issues of proposal 1, because at least the functionality is somewhat obvious and the API documentation for Viewport<T> can explicitly state "you should probably be using a coordinate translator with this".

[Chris3606]

Overall, I advocate for proposal 2. It seems to offer the feature via the least complicated API and little to no performance tradeoffs. Furthermore, the convenience of using Func or lambdas can still be obtained in this method, for users who are OK with the performance hit, because a LambdaCoordinateSpaceTranslator can be provided.

As for the primary disadvantage (decoupling from the grid view); although this could create undesired behavior, it can also be a feature; for example, perhaps it does make sense to use a Viewport<T> without a translator, if entities all defined their own coordinate schemes in some case.

[Chris3606]

One additional challenge (with either proposal) is how to handle algorithms like FOV, which expose their results as a grid view. Because the results are a grid view, they are implicitly in the local coordinate space. This is unique, compared to AStar, where the Path can simply be returned in global coordinates and no additional translation is ever required.

Since the results are persistently exposed to the user in a grid view (which uses the algorithm's local coordinate space), there are two unique challenges:

• Translation must take place even after the calculation has completed
• The definition of the coordinate space must not change between when a calculation occurs and when a value is retrieved, for the global to local translation to still be valid.

The first issue implies that simply exposing the results as a grid view is insufficient, since a grid view defines a coordinate space from (0, 0) to (Width - 1, Height - 1); eg. a local coordinate space. Some additional translation layer must therefore exist to allow a user to retrieve values from the result view with positions defined in their "global" coordinate space.

The second issue implies that there are restrictions on when a coordinate translator should record/update offsets used in the calculation. Consider a case where a coordinate space translation is based upon an entity's position in a global coordinate space. The translation might be defined as localPosition = globalPosition - entitysUpperLeftViewportPosition. This definition, with no other constraints, functions properly for AStar, where the translation of the result happens as a part of the algorithm; however for FOV, it could cause an issue. If, for example, FOV is calculated, then the entity moves, then a result is accessed, the translator must still define its translation based on the entitysUpperLeftViewportPosition value that existed when the calculation occurred, which is not the current one. Arguably, this situation is undesireable anyway for FOV, because if the entity moves the FOV probably should have recalculated in order to be accurate. Nonetheless, this is a situation the current proposal's interface would allow, and there may be coordinate space definitions and/or situations for which this is non-apparent.

Proposal 2.1

In order to properly support the above scenarios, the following changes to proposal 2 could be made:

1. Define the ICoordinateSpaceTranslator interface to the following:

public interface ICoordinateSpaceTranslator
{
    public Point GlobalToLocalPosition(Point position);
    public Point LocalToGlobalPosition(Point position);
    public Point UpdateSpaceDefinition(); // New function
}

2. Algorithms in their "calculate" function should call UpdateSpaceDefinition() before calculating.

3. An interface should be added something to this effect:

public interface IGridViewTranslator<T>
{
    IGridView<T> GridView {get; }

    T this[Point globalPos];
    T this[int x, int y]; // Same as above
    T this[int index]; // Forwards to GridView directly
}

3. ResultView or similar views in algorithms would consist of a structure like this when translation is involved:

public class GridViewTranslator<T> : IGridViewTranslator<T>
{
    public IGridView<T> GridView {get; }
    public ICoordinateSpaceTranslator Translator {get;}
    
    public T this[Point globalPos] => LocalGridView[Translator.GlobalToLocalPosition(globalPos)];
    public T this[int globalX, globalY] => this[new Point(globalX, globalY)];
    public T this[int index] => LocalGridView[index];

    /* Define Positions iterator to iterate over global positions */
}

In cases where no translation is involved, the grid view could instead be a dummy implementation of IGridViewTranslator<T> that doesn't actually perform any translation (the hope being the compiler is able to optimize this fairly well).

The Good

• Allows translation of result values
• Adds to the ICoordinateTranslator interface methods which indicate that the coordinate translation space must remain static until instructed otherwise via the update function
• Avoids mass backwards compatibility breakage in at least common circumstances; the new type used for ResultView is fairly compatible with the old one API wise, although there are a lot of extension methods which don't exist for IGridViewTranslator that would for IGridView.

The Bad

• Adds complexity to the interface structure. Unavoidable to a certain extent; we're adding features and with features come complexity; but a concern is it could make the system as a whole less parsable to new users.
• Technically breaks backwards compatibility for some cases, although the fix is simple

[Chris3606]

Note that a branch of the primitives library exists which mostly provides a proof of concept. It still needs to be tested in actual GoRogue algorithms and the results benchmarked against the non-translating counterparts.