Sort bug / strangeness
Danny Arends
Danny.Arends at gmail.com
Fri Oct 1 16:44:08 UTC 2021
Hey all,
Using a modified 3D A* tile searching algorithm, full code see:
https://github.com/DannyArends/CalderaD/blob/master/src/math/search.d
I get the following AssertError, 'sometimes' but not always on
running the code:
mutation.d(2816): Swap: rhs points to lhs.
the first time I hit Phobos is because I call the
std.algorithm.sorting.sort function to sort my open list (just an
array of search node objects);
```
search.openlist.sort!("a.f < b.f")();
```
sneakily f here is a @property function of the object, which just
computes and returns a float:
```
// sum of cumulative cost of this node + predecessors + heuristic
struct Node {
float g; // cost of this node + it's predecessors
float h; // heuristic estimate of distance to goal
@nogc @property float f() nothrow const { return(this.g +
this.h); }
}
```
For the life of me I cannot fathom, how 2 function calls would
end up pointing to the same memory location ?
To mention (might be relevant or not, I'm lost badly), the search
struct around the map is parameterized. because I want to give
objects the ability to have their own map walker definition (eg.
ground, ground+air, ground+shallow water ). I am using the
following wrapper struct:
```
struct Search(M, N) {
N[] openlist; // Astar open list
N[] closedlist; // Astar closed list
}
```
Anyone got some idea what I'm doing wrong, or explain me why I am
messing up my Dijkstra here ?
Thanks,
Danny
Full stack trace/ dump below:
```
core.exception.AssertError at C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\mutation.d(2816): Swap: rhs points to lhs.
----------------
0x000000014008A2E3 in d_assert_msg
0x0000000140056F35 in
std.algorithm.mutation.swap!(searchnode.Node).swap at
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\mutation.d(2816)
0x0000000140057A07 in
std.algorithm.mutation.swapAt!(searchnode.Node[]).swapAt at
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\mutation.d(3090)
0x00000001400582BE in std.algorithm.sorting.medianOf!(binaryFun,
Flag.no, searchnode.Node[], ulong, ulong, ulong).medianOf at
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\sorting.d(4237)
0x0000000140057DF4 in std.algorithm.sorting.getPivot!(binaryFun,
searchnode.Node[]).getPivot at
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\sorting.d(1620)
0x0000000140057112 in
std.algorithm.sorting.quickSortImpl!(binaryFun,
searchnode.Node[]).quickSortImpl at
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\sorting.d(2124)
0x0000000140056FB5 in std.algorithm.sorting.sort!("a.f < b.f",
SwapStrategy.unstable, searchnode.Node[]).sort at
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\sorting.d(1905)
0x0000000140050C1F in search.step!(search.Search!(Map, Node),
searchnode.Node).step at C:\Github\CalderaD\src\math\search.d(119)
0x000000014005012E in search.performSearch!(map.Map,
searchnode.Node).performSearch at
C:\Github\CalderaD\src\math\searchnode.d(11)
0x000000014004723B in map.testGenMap at
C:\Github\CalderaD\src\game\map.d(125)
0x000000014004CD9E in main.run at
C:\Github\CalderaD\src\main.d(32)
0x000000014004CD3E in D main at C:\Github\CalderaD\src\main.d(25)
```
More information about the Digitalmars-d-learn
mailing list