A* Search

Share your Projects
,
1

Hello! I'm back with another project, a bit more sophisticated than my other projects. I translated the pseudocode on the Wikipedia page for A* Search into Snap! code, with some modifications to make it compatible of course.

Reposition the start point however you'd like, and it will attempt to create an unblocked path from itself to the bottom right of the grid once you press space to confirm.

If you wish to give optimization insights for implementing the A* algorithm in Snap!, please tell me.

KNOWN BUGS:
None

PREVIOUS BUGS:
The pathfinding algorithm would fail or malfunction if you place the dot too far to the left or top edges of the box.

The pathfinding algorithm would fail if you place the point on the left side of the T. (Note: I didn't actually find a solution for this, I just deduced that the A* Search doesn't appear to work very well in linear spaces, I'm not sure why, but I cannot fathom a solution right now sadly.)

2

image
image615×504 21 KB

after calculation when placing top too far on the top left

3

I get the same error if I start in that entirely enclosed box near the bottom right of the orange-brownish structure in the center.

4

I clicked the big green flag in the middle of the display, then clicked space, and it did its thing. Then I wanted to try a different starting point so I clicked the green flag at the top of the frame, moved the black dot, hit space. It worked fine, except that after I clicked the green flag, all the buttons at the top disappeared, so I couldn't get a third trial. This is using the project embed in your forum message.

5

Oh strange, I never have gotten that error before, only a failure.

It's not enclosed, you're starting inside of it which makes the pathfinding algorithm get stuck.

I couldn't tell you how that happened, do you want the project link?

6

I mean, its four neighbors to N, E, W, and S are all blocked.

7

What I meant is that there is not a path there at all, it's outside the boundaries of the graph.