Tilemap Path Finding ( a* ) (beta)

Arcade
1

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:

image
image1042×253 33.6 KB

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 :slight_smile:

17 Likes
2

Awesome!! Can’t wait to use this

4 Likes
3

amazing - I always wanted to learn about a* but seems to hard to figure out -

1 Like
4

Ah sounds good, I’ll try and make some time on an afternoon this week to do a little write up on how it works / how it and BFS / DFS / Dijkstra’s are all basically the same thing; will be a good test to see if I still know how to teach :slight_smile:.

For now, if you are curious, I always used to recommend Dijkstra’s Algorithm - Computerphile and A* (A Star) Search Algorithm - Computerphile when students were confused; there are a few minor stumbles / typos, but they’re by far the best resource I found for explaining how the searching algorithms work (and fairly quick too, under half hour total) ~

1 Like
5

I think you could visualize the search frontier if you ran the algo super slow. Maybe the game update can read the state of the algorithm and paint it.

2 Likes
6

Yeah, decided to do that real quick before as it was easy enough / fun animation

tan is normal / part of path, black is wall, yellow means the tile is in the heap / being considered, orange means tile has been evaluated, and at the end it shows the path in green as it backtracks to find the solution. I included two but anyone can draw their own easily enough if they want to see how it works in different scenarios (just be sure to keep the end point up to date).

Worth noting for some of the small paths it won’t necessarily seem like a large improvement over a flood fill; in this case that’s emphasized by starting in top left and going to bottom right. I can probably add a bit more in the heuristic to more accurately nail down cost (e.g. if you’re moving upwards and the goal is below you, you’re actually costing at least two moves – maybe can compare heuristic to parent heuristic and if worse penalize extra)… have to think about that a bit more to confirm if that’s admissible

4 Likes
7

@jwunderl I’ve been playing around with this extension in my latest project. It’s great. Thanks for making it!

… also, I may have a couple of requests. :blush:

  1. I’d love for the ability to know if a sprite is currently following a path.
  2. It might also be nice to have an event raised when a path is completed—though checking #1 in an on game update would probably be an okay next best solution…
  3. It’d also be really nice to be able to cancel a path. I tried giving it an empty path, but that didn’t seem to have an effect. The best way I’ve found is to assign a new path that routes the sprite to the tile it’s currently on… but this sometimes results in some odd jittering. I think ideally cancelling would either leave the sprite where it is (even if it’s between tiles) or let the sprite continue moving to the next step in the path, and stop once it reaches it.
1 Like
8
  1. That’s a very reasonable thing to add, yes
  2. I haven’t thought too much on how to expose this, but it’s implemented here with a callback: https://github.com/jwunderl/arcade-tilemap-a-star/blob/master/path-following.ts#L134 – the issue is mainly just that the inline event handler blocks (e.g. run in parallel sort of ones) don’t currently work with parameters, making it basically useless in blocks due to global variables – needs editor fixes
  3. Giving a null path or setting speed to 0 used to remove the path, and I would say that’s the expected behavior; I think that just got changed at some point and will probably be fixed

Worth noting @darzu has been adding to this extension as well, I believe at this point he rewrote the path following section almost entirely.

(Also just noticed I never gave my explanation on how a-star works, had some work things come up. Probably worth doing that at some point)

2 Likes
9
  1. Yes, that would be a great thing to add
  2. Instead of inline handler, I think it’d make sense to have a “on (sprite) of kind (player) finishes (path)” regular event
  3. Yes, I probably introduced this regression, this should stop.

Some other wish-list ideas, some are far out:
a. a way to tell progress along the path
b. a way to path a single sprite (or group of sprites) to any tile of a certain kind (e.g. go to water)
c. an option to use a-star when telling a sprite to follow another sprite (instead of b-lining it, and easier than a game-update loop that constantly computes a new path)
d. cooperative pathing: when several sprites of a destination with overlapping paths, they figure out how to move aside or pause to each other pass (hard problem; also we don’t generally have sprite “bumping” physics)

2 Likes
10

Yeah, a top level event with kind will work just fine for #2 I suppose (I guess when i was thinking about it before I was focused on keeping the package small / just a few blocks).

For (a) we could do a starting implementation by just returning a getter for the sprites currentIndex / path length?

I thought we had added (b)? I can take a look at doing that tonight if you want, I know about how it’ll look.

I think @richard has © implemented in his game? Maybe we could just steal the code for that and wrap it in a block?

(d) Hm, yeah this will be hard (but it does sound like a good “nothing to do this weekend” sort of project, like all situations where you need to avoid deadlocks). I’m imagining we could even do something cute like make it so sprites follow on the side of the path if they’re not tile size, so you could have roads that little 8x8 cars could drive in both directions on, that would be an adorable little city building game

2 Likes
11

The code is pretty simple, it just recalculates the paths in a background fiber. I trigger it whenever the target sprite moves outside of a given range (30 pixels in my case). Would definitely need to be tested on hardware because I expect a large tilemap or a lot of followers at the same time will be pretty slow. That might be fine though

1 Like
12

BTW the bitmask in that code is just there to stop enemies from piling up in the same location. It would be awesome to have some sort of built-in behavior that stops the enemies from overlapping at their destinations. I think that’s never really desirable in the follow scenario.

1 Like
13

Errr… I guess it is desirable if one sprite is chasing another. Would be a great option though!

1 Like
14

Yeah the more I’m thinking of it the more I REALLY want to make a little simcity style “make streets for cars to follow” with little 6x6 or so cars, but it’ll take some time to figure out how to properly do efficient scheduling for that.

4 Likes
15

Perhaps related to this, I think it’d be neat if pathing could specify a set of tiles types that sprites could use (e.g. road tiles), instead of just “anything but walls”.

Essentially a “whitelist” of valid tiles (e.g. roads) instead of a “blacklist” of tiles to avoid (e.g. walls).

This decoupling with walls could be nice, because walls are used for many reasons. In one of my games I temporarily set a bunch of a walls, do the pathing, then unset those wall locations just so I can get pathing to work how I want.

2 Likes
16

Yup, easy to add the functionality. Maybe we should file issues on the repo to track? Most of these seem like ~ half hour to hour changes that we could get through, just need to track em (and this applies to anyone - if anyone’s got requests for any of my extensions, it’s really helpful to get feature requests!)

1 Like
17

Yup, I’ll file some.

Strategically I think it makes sense to put basically as many useful blocks as we want into this extension and then see how useful they are through a few games and put only the most useful ones in the scene category eventually (or maybe not at all).

1 Like
18

image
image1602×1160 159 KB

File some if I missed any!

4 Likes
19

Just so you know I completed these requests, but to be fair I did it while watching TV / still need to do some more testing. I also moved them to a new group, so they’re easier to find / not nestled in with other scene things

image
image1335×837 79.5 KB

#1: block for this, as well as % complete. I also have % complete as 0 - 100 for now (to be consistent with Math.percentChance), one behavior I’m not sure on is the return value if the sprite is not following a path - I chose 100% as ‘trivially completed’, which also makes it easier to be consistent with behavior when you finish a path (as we remove the handler)
#2: added top level handler that takes a kind and gives you the sprite that has completed the path and the final location of the path (/ the location the sprite is now at).
#3 is done by passing 0 / null for speed or a null / empty path.

7 Likes
20

So for this can you add some code to where it will follow another sprite