Looking for a native heap collection for A* implementation

[ember isle]

I'm currently working on an A* implementation, mainly following the one specified in this series of videos: https://www.youtube.com/watch?v=-L-WgKMFuhE&list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW&index=1
On the episode 4, He beings to implement a Heap for optimization. i've already finished his setup and now i'm looking to implement this into Jobs, however, i cant find a good NativeHeap<> collection for this. is there any good ways to get one? i know unity has a Collections package but i dont think it has an actual Heap collection.

[celest solstice]

It'd probably be best if you looked at a more up to date tutorial, the logic behind A* hasn't changed, but there are tutorials where people are using native collections already, like this one https://youtu.be/1bO1FdEThnU

[ember isle]

oh crap

i had no idea codemonkey had a guide for it!

i absolutely love codemonkey

thanks, i'll take a look at it tomorrow,

[molten stag]

I adapted a C# implementation of a heap queue to be a native collection. Though I don't remember where the original code comes from.
https://pastebin.com/HP5DmPP6
I use this for A* in Dice Kingdoms https://www.reddit.com/r/Unity3D/comments/xrznn5/combat_stress_test_with_600_units_many/

I did not do benchmarks, but in theory the heap is a great improvement over a list.

[ember isle]

i'm very close to getting this to work with codemonkey's video, but i'm hitting a wall

so, i'll go ahead and isolate this into a separate project

and probably send the unity package here for help, considering i'm at my wit's end

[ember isle]

wait i think i got it

nope, ok i'm packaging this up

Ok, here's the implementation itself.

The package requires the collections unity package to be installed since it uses a native hashset for the closed set instead of a native list.

by itself, the sample scene bundled with the package has my implementation ready for testing, where there's a world, an End game object and Start game object. inside the "AStar" game object is the implementation itself.

AStarNodeGrid: takes care of holding a serialized node grid, and as well as letting the end user bake the grid into a SerializedNodeGrid

SerializedNodeGrid: contains well, a serialized node grid. the node grid itself serializes the least amount of data needed, and allows you to create a PathNode array which are the nodes used on the A* algorithm

Pathfinding system: it's where the A* implementation resides. the issue seems to be that the "End" node is never being assigned a parent index (-1), while the rest of the nodes inside the NativeArray of nodes do have an assigned parent index. ( > -1). as such whenever it tries to retrace the path, it cant because the end node doesnt have a parent

i'd greatly appreciate it if any of you, or well, anyone could help me, i've been stuck on this for a while and i need it ready for a presentation next week

[ember isle]

Right, I almost forgot, it's version 2022.4

I forgot the revision number

[ember isle]

Bump

[deft dust]

have you found the answer?
you can just write a unsafeminheap by yourself as usual but you have to pass the pointer to it in job system (i havent run my astar in job systemyet but i have tested pass the pointer to a unsafeList to job then add(something) is possible)

[ember isle]

right

i mean,this isnt precisely related to the heap collection anymore

since now i'm just trying to get the implementation to work

should i make another post for it?

[deft dust]

i see your previous message so you already have a native min heap
but what is "work" means? give the smallest value in O(log n) (and optimized)? support parallelism?

[ember isle]

my implementation of A* currently fails to properly set the end node's parent, despite the fact there are no obstacles to reach said parent node

so by "work" i mean fixing the issue i just mentioned

i'll probably implement the heap solution Marc mentioned once i manage to get the baseline part working

wait, i think i fixed it

yeah i did, i'm... unsure how, lol

this just concerns me but oh well, at least it works

[deft dust]

i see your problem now.....
my implementation similar to: (i have slightly optimized it so not exactly the same)
set the start node
enqueue start node
fetch the smallest node
for all neighbors
if f cost<neighbor's cost then enqueue and set its parent
i believe the reason is you havent correctly set the parent when relax the neighbors, you can have a look

[ember isle]

aye, thats what i'm doing

                var neighbours = nodeGrid.GetNeighbouringNodeIndices(currentNode);
                for(int i = 0; i < neighbours.Length; i++)
                {
                    int neighbourIndex = neighbours[i];
                    if (closedSet.Contains(neighbourIndex))
                        continue;

                    PathNode neighbourNode = pathNodeArray[neighbourIndex];
                    if(!neighbourNode.Available)
                    {
                        continue;
                    }

                    var currentXY = new float2(currentNode.x, currentNode.y);
                    var neighbourXY = new float2(neighbourNode.x, neighbourNode.y);

                    float hCost = CalculateDistanceCost(currentXY, neighbourXY);
                    float newMovementCostToNeighbour = currentNode.gCost + hCost;
                    if (newMovementCostToNeighbour < neighbourNode.gCost)
                    {
                        neighbourNode.gCost = newMovementCostToNeighbour;
                        neighbourNode.hCost = hCost;
                        neighbourNode.parentIndex = currentNode.nodeIndex;
                        pathNodeArray[neighbourNode.nodeIndex] = neighbourNode;

                        if (!openList.Contains(neighbourNode.nodeIndex))
                            openList.Add(neighbourNode.nodeIndex);
                    }
                }
                neighbours.Dispose();```

or at least i think so

unless, is it supposed to be the g cost or f cost?

i forgot

the unity package i posted above has my implementation btw, if you want to take a closer look ig

[deft dust]

F=g+h
I have to sleep now… hope other else solve your problem

[ember isle]

https://i.gyazo.com/a2bcc37cf950e5cd3ad79087fda4d76c.mp4
very close now, but since this isnt related to the heap collection anymore i might go elsewhere for the problem, idk yet

[deft dust]

Not related to your problem, I believe you are using a wrong heuristic (you use manhattans distance in diagonal movement)

[ember isle]

I have no clue what that means

But if it's the fact that it favours a lotore diagonal movement instead of cardinal, then yeah

I've already fixed it

[ember isle]

apologies, what's this IOrder<int> interface in your pastebin?

[deft dust]

I mean You are using a inappropriate heuristic to calculate the h cost ,but if the cost of diagonal movement is the same as orthogonal,then fine

[molten stag]

The goal was to have a compare interface that is burst compatible. But maybe it can be done more simply

[ember isle]

Compare isn't compatible with burst?