push startNode onto openList while(openList is not empty) { currentNode = find lowest f in openList if currentNode is final, return the successful path push currentNode onto closedList and remove from openList foreach neighbor of currentNode { if neighbor is not in openList { save g, h, and f then save the current parent add neighbor to openList } if neighbor is in openList but the current g is better than previous g { save g and f, then save the current parent } }
* push startNode onto openHeap while(openList is not empty) { * currentNode = pop from openHeap if currentNode is final, return the successful path * set currentNode as closed foreach neighbor of currentNode { * if neighbor is not set visited { * save g, h, and f then save the current parent and set visited * add neighbor to openHeap } if neighbor is in openList but the current g is better than previous g { save g and f, then save the current parent * reset position in openHeap (since f changed) } }
@Radnen re gist/pathfinder.js - even though your game function is a simple example, I'd still recommend taking a call like GetSystemUpArrow out of the loop.
I have a slow (uses a simple array, I'm updating it to a binary heap) and likely slightly buggy A* pathfinder. The only notable part is that it can automatically create a tile obstruction grid of the map, when using the default map engine. This is slightly ugly, and is only over tiles, not pixels (I was getting out of memory errors with a per-pixel grid), but works pretty well.
I'm going to update the algorithm to JPS, which will easily blow any A* pathfinder out of the water performance wise. JPS is possibly fast enough to do pathfinding in pixel space, so I'm trying to develop an approach to avoid running out of memory for large grids, by storing information directly in 32 or 64-bit (actually a pair of 32-bit) integers.
Why create an obstruction map beforehand? My pathfinder doesn't do this, but it could check while processing, like Beakers. When it visits a node at, say tile (5, 4), then only at that point checks 'IsObstructedAt(name, 5*16, 4*16)' this will take a bit more processing, but less memory lying around. If you move to JPS this would be ideal.
And holy cow, JPS looks awesome. I would love to see this implemented in Sphere. It hasn't yet been done so I'd say try it out. A Per-pixel quadtree version had been made by Kamatsu, but he said it was too slow, even though it should have technically been more than fast enough in any other programming environment (check out his tech demo 'digger'?) I might upload it to the repo if I still have it.
Wasn't Jester intending on changing it so that GetSystem* made new copies in case on-the-fly edits were made to pixels or something?