A* alternative to heap

Unity Engine
1

I’m currently working on my second parthfinding routine (the first one, Breadth, didn’t work out for me)
Sebastian Lague has a great tutorial on this and I’m building my script using his explanation of the process.

Now I’m at the optimisation part of the tutorial, I understand the ‘heap’ principle. Why it is nescesary to decrease searching through the ‘openList’.

Using open areas with obstacles or narrow corridors (in my case) your path mosly leads in straight lines, no deviation. The ‘openList’ gets bigger and bigger, collecting new nodes storing the old ones from several iterations back who will probably never get used. (… probably). Making it harder and harder to loop through the openList.

But I started thinking.

For example. If you start out with a fCost of 200, there will never be an fCost lower than 200 because 200 is the shortes route. So when you search for neighbouring nodes and find another node with fCost 200 this is obviously the right path to take.

Why not add a ‘preferedList’. If the current node finds a neighbor (or multiple) with the same fCost there will not be any other better nodes in the openList because you are already working with the lowest fCost. The open List only contains of higher fCost nodes stored in it.

Higher fCost found in neigbours are stored in the openList, same fCost are stored in the ‘preferedList’.
If the ‘preferredList’ is empty, search through the openList for a (or multiple) nodes with the lowest fCost and repopulate the ‘preferredList’.

If the node finds a lower fCost node, move all nodes from preferredList to openList, put the new found lowest fCost node in the ‘preferredList’ and continue the routine.

Any thoughts?

2

I was trying to implement a full blown A* once in rpg maker … one key optimization I found, in this harsh environment, is that you can probably concatenate multiple node into a single one.

Jump search a* does this by basically flood searching convex (rectangular) area to collapse as a single node.

In my case I was using waypoints instead of grid, and

  • any node (waypoint node) between node that had more than 2 (I named them “branch node”) was collapse into a single node (adding the cost together),
  • any waypoint between a branch and a dead end (node with only one neighbor) was collapsed into the dead end.

It make sense as all major routing decision mostly happen at branch. You only need a simplified pathfinding in each local group.

SO the idea is that as you unroll the open list, you can probably concatenate node into group, which accelerate traversal, and also allow a run time cache for further querying down the road, and help with dynamic environment because you would only update the relevant list group.

1 Like
3

I’m making a 3d basebuilder without a fixed map size.

So I’m using nodes that are part of the prefab structures the player puts together on the map.

In worst case the player builds something resembling a plate of spaghetti made up out of small corridors. I can’t imagine how I could implement sectioning.