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@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)

On 10/1/21 12:44 PM, Danny Arends wrote:

search.openlist.sort!("a.f < b.f")();

// 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); }
}

I think your struct is different than this, because this only happens if aliasing is inside the struct being sorted (i.e. it has pointers). Your presented struct doesn't have pointers, and the code you linked to is completely parameterized on the struct type.

If it does have pointers, you are not allowed to swap the values if either points to each other (or themselves).

-Steve

On Friday, 1 October 2021 at 17:53:24 UTC, Steven Schveighoffer wrote:

Thanks Steve for saving Friday,

The struct has indeed a parent pointer, It's a pretty big struct so just posted the excerpt (sorry). So that's the cause then.

So how to sort this N[] object by f() then ?

The pointer is only used to be traversed back after the search has finished. Is there a sort() algorithm that avoids swapping the items themselves and e.g. just returns the indexes so I can reorder the original array myself ?

Danny