I was following a tutorial someone made for Unity to create an A*Pathfinding - and I was successful so far. The pathfinding itself works flawlessly. But the performance…
Then I tried the heap sort optimization. And while I understand the theory, I must admit it’s too complicated to translate whatever he’s doing into a BP workable format.
Maybe someone can help me understand what he’s doing and show me how it’s done in BP.
Hey. I’m also trying to make the heap optimization in BPs. Did you figure it out?
Also, how did you approach when calling the FindPath function? How did you pass in the Seeker and Target position? Also, are you running the FindPath from the Event Tick?
Did this myself just a week ago.
You can use an array to be the heap by accessing certain indexes based on formulas.
To get a parent of index i, subtract 1 and divide by 2.
To get each child, double index i and add 1 or 2. you need to verify that each index is valid, or the index does not have any children or just 1.
Parent=(i-1)/2
Child 1 = i2+1, child 2 =i2+2
Add to the heap by adding at the last index and perform a bubble operation.
When pulling from the heap, grab index 0 and replace it with the last member, then perform a bury operation.
Update a member by updating its value and bubble it, since it will only be updated if it has a better value. You’ll want the member to know its index in the heap.
Bubble involves getting the parent and comparing their values. If Current has better value, swap the members.
Bury involves comparing Current with each child and swap with the best value child if needed.
Swap by setting the array element with the other member, and also updating the member with its new position in the array.
I can provide more details but that’s the overview and hopefully it will be enough. Since if I show screenshots of my setup, it can differ for how you handle the nodes. For example, I don’t reference the nodes but wanted a pure data approach. It’s also unfinished and riddled with debugging nodes. I’ll tell you, debugging the heap is the worst.
I will try this when I reach this stage. Right now I’m stuck on, how should I set up the FindPath function, like from where should I feed in the position of the start and end node.