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

1. 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
2. Drag&Drop does not update node properties causing misinterpretation of locations.
3. Neighbouring safe-nodes are not updated when passing by, causing safe-nodes to become lock-points.
4. Shortest distance is far from being found every time.
5. Sometimes it fails to find a path, even though a path exists (this is related to II.).

The Algorithm

Right, this is a step-by-step about how my half-broken implementation of A* works

1. Get start position
2. Get goal position
3. Start at 0,0 go to grid.width, grid.height and map each node with aprox. distance to goal
4. Set Current Position to starX, startY
5. Check surrounding distance from surrounding nodes to goal, save all distances
6. Pick shortest distance, if two nodes have the same distance, the priorety is Down, Up, Right, Left
7. Set Current Position to the node with the shortest distance if it's not a wall or a locked node
8. 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
9. Repeat 5. to 8. until goal is found

Click here to close this box

Found goal 527 out of 899 times (59%) | About | How it works | Source (the fun stuff is in /lib/js/scripts.js and don't judge me... i write ugly code)