My code is merely a port of IanM's DBP code. I know a little about how the algorithm works but not enough to write it myself. (though it's something I'm working on).
What I can tell you is a concept for fixing the issue with staggered maps. A* works greats with tile maps, but it's not limited to tiles. It will actually work for any shape or size tiles, or in the case of the algorithm, nodes. You just have to tell the algorithm how your nodes are laid out on the map. When the search progresses to the next possible node, you tell it where it can travel from there. So it's important to understand how your map is drawn and how tiles are ordered.
A typical orthogonal map, using a 4-way search path (does not check diagonals).
It's pretty simple to see what tiles get checked. If the current tile is [X,Y] then the 3 tiles you check would be:
[X-1, Y]
[X, Y+1]
[X+1, Y]
With a pyramid isometric map, it's the same concept and the tiles are just as easy as they technically fall into the same grid pattern like above. But you said staggered, so the standard library won't handle them without modification. Staggered maps can be drawn 4 different ways. Rows or columns can be staggered on the X or Y axis. And then you have the option to stagger either the odd or even rows.
We're still checking only 3 extra tiles from the current tile, it's just their relative coordinates are different than the other two map types. This is where you'd need to modify the algorithm, how it calculates the next tile positions to check.
[X, Y-1]
[X+1, Y-1]
[X+1, Y+1]
Obviously, this depends on how you numbered your tiles (how you've drawn them in order)
The same concept applies for a hexagonal map, which is essentially just a staggered isometric map really.
"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
