This extension can be used to find the shortest path between two points on a tilemap, and to make a sprite follow that path. This could be useful in situations like a tower defense game, where you have enemies that need to move along a path from the start to the end.

Quick note that this extension is definitely in a ‘beta’ form; the blocks ‘work’ but may change after trying it out a bit more / there may be more additions. Also, I’ll almost definitely change how the path following works; right now it’s a very fragile / was just quickly put together – if you try and change the velocity of the sprite, or the sprite is too large to fit through a path (i.e. sprite is larger than 16x16 most of the time), the path following logic will just break / act sporadically.

Anyways, for now, here’s an example:

press a to spawn a chicken that will go from the top left tile (0,0) to the bottom right (39, 39). Press B to show the calculated path layed out (1/10 of a second per tile delay just for illustration)

Here’s the extension itself:

The extension currently adds the blocks to the bottom of the tilemap group in scene, but that may change in the future:

Also note that depending on the size of the tilemap the computation might take a moment; for example, calculating the path on the 40x40 grid currently seems to take ~~ 100ms on my `PyGamer`

. If you have a large tile map, you likely will want to compute the path at the start of the game / level, instead of recreating it each time you use it (even after I spend some more time trying to optimize things, it will likely always be fairly intensive for large maps - a 40x40 map has 1600 tiles – a* does try to optimize things by searching ‘likely’ paths first though, which means that typically you won’t get absolute worst case behaviors)

Also, if anyone’s interested in how it works I’m happy to write up an explanation; the class I TAed for the last few quarters I was at UW included graphs and graph searching (which is the core of this path finding algorithm), but it was a 300 level course. It will take a bit of thinking to come up with drawings / good explanations to make sure it’s intuitive, as it’s fairly simple once you get it but often seems very scary the first time you see it / until there’s a light bulb moment