A-Star Ties and Weights/Penalties

I'm unable to make sense of the Pathing/Astar.cs tie-breaker (i.e. how it chooses between nodes of equal weight). There are some remarks in the comments, but they are fairly vague. In cases like this, a full explanation often will not fit snugly into a method comment (I can definitely understand that). Nonetheless the tie-breaker plays a significant role in the macro-level behavior of entities following A* paths, so it's a consideration for something to mention on the wiki in the future.

The A* implementation seems very optimized as far as performance goes, so I would guess that it is in a finalized or near-finalized state. I'm wondering if there is something in it that prevents a weight map in addition to the walkability map as an input. Glancing over the code, at line 130:

nodes[index].F = (float)_distanceMeasurement.Calculate(start, end); // Completely heuristic for first node

You could seemingly just add an indexed weight from an ArrayMap to this line and it would carry on none the wiser. I could be missing something or there could be other considerations I haven't thought about.

Just for 100% clarity, in this implementation weights would instead be more like fixed penalties (i.e. instead of multiplying anything, they would be additive). So if you have a tile type that is weighted '0', the implementation would carry on as usual. But if you have a tile type that is weighted '2' or '11', then those values would be conceptually added to the distance away from the starting point.

/edit - I was just refreshing myself on the various documentation available and noticed that weighted A* is planned on the roadmap.

I'm unable to make sense of the Pathing/Astar.cs tie-breaker (i.e. how it chooses between nodes of equal weight).

The code is admittedly more vague and more sparsely commented than I'd like. The "tie-breaking" is tricky to explain succinctly because it is neither necessary for the function of the algorithm, nor directly and completely present in the existing code (it requires knowledge of how the 3rd party priority queue library I'm using functions).

First, I would say "tie-breaking" is not the right word to describe it. A more precise word is "smoothing". A shortest path would be found even if the private AStar.neighbors() function just returned all the neighbors in an arbitrary order. The purpose of returning them in the very specific order it does is to "smooth" the returned path, making it look more natural (in the cases that it is possible to do so without sacrificing path length). Let us use Manhattan distance (4-way movement) as an example. If the neighbors were just returned in the standard order used by AdjacencyRule.CARDINALS.Clockwise(), a shortest path would indeed be found, but the path would likely look very "blocky". On a completely open map, you would have a path where all movement along the X-axis would happen before all movement on the Y-axis. While this is technically a shortest path, it looks more natural if we instead try moving in the direction closest to the destination first, which creates a path that "looks" more like a direct line between two points: smooth

This is the purpose of the neighbors() function working the way it does. It is designed to take as a parameter a line (or rather, a vector, eg. delta-x and delta-y values representing a line). It then returns the neighbors in order of how "close" they are to that line. In this way, in AStar.ShortestPath(...), when we wish to check the neighbors of a given cell, we check neighbors "closest" to a line between that cell and the destination first.

The last potentially confusing part is left = right = Direction.GetDirection(-dx, -dy); -- notably, that -dx and -dy are being passed, rather than dx and dy. This has the effect of "inverting" the line being passed in, so that values are returned in an order such that the values are returned farthest away from the original line first, rather than closest. We want this to be the case because, given values with the same priority, the priority queue implementation AStar uses returns the last value it received first. Thus, to check the values in order of closest to farthest, we need to invert the order. This is the most performant way I could find to accomplish this.

Finally, it is worthy of note that upon detailed inspection of the neighbors()/cardinalNeighbors() algorithm, you may note that the neighbors are not returned in exactly closest-to-line order with respect to the orientating line. The first value will indeed be the closest to the inverted line, but depending on where the line lines with respect to that first direction (whether it was counter-clockwise of the direction returned and we rounded clockwise, or it was clockwise of the direction returned and we rounded counter-clockwise), all subsequent pairs might end up being returned in exactly inverted order. This is known, and perfectly fine because, once again, all the algorithm is designed to do is get us close to a more natural path -- it doesn't have to be exact. A shortest path will be found either way -- the correctness of the order only affects how "natural" the path looks. The existing algorithm smooths out the paths more than well enough to make them look natural, and fixing the ordering to be 100% perfect would cause the entire AStar.ShortestPath algorithm to become less performant.

...so it's a consideration for something to mention on the wiki in the future.

I am indeed aware that the code inside of the AStar class is pretty gnarly, and definitely poorly explained. It doesn't necessarily do things in the most intuitive ways, in most cases for the sake of acquiring every inch of speed I could for it during run-time. While I'm certainly open to good ways to explain it all, if it comes down to it, I don't have a problem with the internal code not being super-readable, because it's faster and more accurate than just about any other implementation of AStar for C# I could find. Furthermore, the thinking was that the specifics of the internals are relatively unimportant, since all it affects is the "smoothness" of the path. On the wiki, however, I could definitely at least show output and explain that the peculiar ordering creates the smoothing effect. When I write that section of the wiki, I'll also be looking into giving some details on the implementation itself.

The A* implementation seems very optimized as far as performance goes, so I would guess that it is in a finalized or near-finalized state. I'm wondering if there is something in it that prevents a weight map in addition to the walkability map as an input.

This AStar implementation is more or less finished, yes. Including a version that takes a weight map is actually on the agenda. It will may end up being a separate class, however, since having a weight map does prevent certain potential future optimizations that assume uniform cost (for example, implementing jump-point pathfinding).

Thanks!

Excellent explanation - thanks very much for that, Chris. You're right that 'tie-breaking' isn't the best term; A* algorithms always have some kind of neighbor-ordering process that determines the overall aesthetic of paths. It's most obvious in 4-way maps, exactly as you said, because naive implementations will bias the N-S and E-W directions of the path just by the ordering of their code.

I agree completely that it doesn't matter if performance-critical code is easily decipherable. In an ideal world, none of the code is looked at, anyway (hah), that ought to be the role of the headers/docs in a library. It's easy to see that the roguelike dev community is hooked on diffusion maps, but I much prefer A for its straightforwardness and speed. I've been running pathfinding tests, and your A implementation is very fast - I definitely would not want that changed.

Just updated to 1.3 a little while ago.

I was surprised at the somewhat lack of optimization in a few of the AStar implementations I've seen as I compared to others through its development process. That much said, I do admit that, in large part, the speed of mine is due to the excellent priority queue implementation I'm using, which I looked at the source for and would be absolutely painful to write from the start (it goes so far as to use unmanaged code in critical areas).

It's easy to see that the roguelike dev community is hooked on diffusion maps

I believe you may have meant Dijkstra maps (aka goal maps)? In this case, I will say that dijkstra maps have their uses. They may be used in simple cases a lot for things they probably shouldn't be (which is part of why I tried to make sure I had a solid AStar implementation before tackling goal maps), but in terms of creating things like safety-maps or auto-explore maps, or fueling desire-driven AI, they can be really useful. I will say that the famous roguebasin article you're probably familiar with on them describes a method of creating them that isn't the most optimized, which is part of why GoRogue didn't have an implementation of them long ago.

Just updated to 1.3 a little while ago.

Out of curiosity, how do you feel about the fact that it wasn't a major version release (aka. 2.0), and yet broke backwards compatibility somewhat significantly as it did? It certainly wasn't my idea of ideal, but once I realized that the RNG rewrite would break it, I didn't want to wait until an appropriate 2.0 release point to get that out there (since from a mathematical standpoint GoRogue RNG desperately needed some work).

Also, since weighted area maps are on the roadmap (as is the documentation upgrade), I'm going to close this issue for the sake of organization. Feel free to continue to comment on it, particularly if there is an aspect of it that was unaddressed.

Closing the topic makes perfect sense because the concerns were answered in an exhaustive way.

On the other topics:

a) Dijkstra maps: Particularly when reading that article, the algorithm seems to have little to do with Dijkstra's pathfinding algorithm and much more resembles what, in a physics or engineering context, would be called a diffusion process.

Imagine some kind of source that naturally spreads out, like a loud sound that diminishes over distance. If we give the sound some value like '8' then this initially could be represented as:

xxxxx xxxxx xxx8x xxxxx

We might discover or derive a rule about how the sound diminishes with distance - for example one type of possible rule might be that the sound diminishes subtractively with distance:

56666 56777 56787 56777

Another type of rule might be that it halves every unit interval:

11222 12444 12484 12444

This kind of process is exactly what the author of that article is describing, just with a different numerical convention. He has some 'sources' on the map (goals) that spread outwards from their locations. Instead of his source starting out big and diminishing over distance (positive diffusion coefficient, which is what is found in physical processes), it starts out small and grows as its spreads (negative diffusion coefficient). That's my personal take on it. The name will probably stick regardless.

b) 1.3: The biggest 'break' in compatibility for me was actually the namespace shuffling. As far as compatibility and versioning, the only thing that really matters is not breaking compatibility with the same version.

I hadn't got around to tuning any RNG yet in my project, but I can say that I like the distributions in the Troscheutz library a lot more than the Gaussian generator that was previously provided. Almost all of my RNG that has to do with map generation works better, in principle, with a biased distribution rather than a flat one, and the Troschuetz options cover every conceivable need.

Actually one thing that caught me off guard was that I checked to see whether the FOV convention was reversed and the class header reads:

...One may access this class /// like a 2D array of doubles (FOV values), wherein the values will range from 0.0 to 1.0, where /// 1.0 means the corresponding map grid coordinate is at maximum visibility, and 0.0 means the /// cooresponding coordinate is outside of FOV entirely (not visible).

And yet the constructor says

...The resistance map to use to calculate FOV. Values of 1.0 are considered blocking to FOV, /// while other (lower) values are considered to be not blocking.

Experiment reveals that the convention remains unchanged (1.0 is still blocked, 0.0 is visible).

much more resembles what, in a physics or engineering context, would be called a diffusion process.

"Diffusion maps" is actually a good way to describe them in that context. The RIPPLE algorithm used in SenseMap actually models diffusion in the context of light or sound a bit more closely, although is a good deal slower unfortunately (one of those areas I've been looking to optimize for quite some time but haven't got around to figuring out exactly how I want to do it).

Actually one thing that caught me off guard was that I checked to see whether the FOV convention was reversed and the class header reads:

That's actually just once again poor wording on my part. The first quoted section refers to the result of calculating FOV, the second to the resistance map used to calculate it. That is, if I have instance myFov that uses IMapView<double> instance myResistanceMap, and I call myFov.Calculate(...).. myResistanceMap locations are 0.0 if they are visible (do not block light), and 1.0 if they completely block light. In contrast, in the resulting FOV, a location with a value of 1.0 is maximally lit (likely the light source), whereas a location with FOV value of 0.0 is not lit, eg. outside of the range of the light-source. These being in some sense opposite of each other is yet another reason I'm leaning toward reversing the resistance map convention as discussed in issue #28.

Chris3606 / GoRogue

A-Star Ties and Weights/Penalties #30