About A*
This is my implementation of the A* algorithm written in Javascript and spawned by PHP. It is supposed to find
the shortest distance between two nodes, if that doesn't happen, it will try to find A path from node A to node B.
More information can be found on wiki's A* page or by googling a bit
Current Flaws
- Sometimes it teleports to the reversed X,Y position (if it's 1,8 it will teleport to 8,1).. I dunno why this happens
- Drag&Drop does not update node properties causing misinterpretation of locations.
- Neighbouring safe-nodes are not updated when passing by, causing safe-nodes to become lock-points.
- Shortest distance is far from being found every time.
- Sometimes it fails to find a path, even though a path exists (this is related to II.).
(click me to close this box)
The Algorithm
Right, this is a step-by-step about how my half-broken implementation of A* works
- Get start position
- Get goal position
- Start at 0,0 go to grid.width, grid.height and map each node with aprox. distance to goal
- Set Current Position to starX, startY
- Check surrounding distance from surrounding nodes to goal, save all distances
- Pick shortest distance, if two nodes have the same distance, the priorety is Down, Up, Right, Left
- Set Current Position to the node with the shortest distance if it's not a wall or a locked node
- Lock previous node so we can't go back there, because if we do, the outcome will be the same, and we
will be stuck in an infinite loop
- Repeat 5. to 8. until goal is found
Click here to close this box