Path Symmetry

The past couple of weeks I've been wrestling with video editing in order to put together a very short video for my father's memorial service. The state of video codecs and containers (in terms of what can go in what, and which platforms support which) is truly awful. Go software patents, eh? Spurring innovation and so forth.

Windows Movie Maker also turns out to be truly awful. I wasted way too much time. You get what you pay for, I suppose. I ended up purchasing AVS Video Editor, which I'm not linking since it also seems to be only intermittently functional.

In the meantime I came across this interesting article about speeding up A* pathfinding on a grid: Jump point search.

Daniel Harabor makes an excellent point: Having lots of equally-good paths between start and destination just kills A* performance because it must examine every possibility on the chance that one of them turns out to be superior. Here's an example of a situation where there are multiple possible paths (one of which is highlighted):

The path must consist of four horizontal moves and three diagonal moves, but they can be made in any order. Imagine a deck of seven cards, four of which say go east and three of which say go northeast. There are 7! ways you can order those cards. Since there is no difference between the go east cards or between the go northeast cards you divide out by the number of ways you can order those. This is 7 choose 3 (or 7 choose 4), which is 7! / (4! * 3!). The end result is 35 distinct paths. (One of my programming interview questions is about this sort of thing, by the way.)

Daniel speeds up A* by navigating the search space in such a way that only one style of movement is ever used: diagonal moves first, followed by the horizontal or vertical moves. His article is a bit misleading because he is plotting only the nodes that go into the "open" priority queue, and this number is vastly lower with his approach than it is in the basic A* algorithm. However! His algorithm is still looking at all the same grid squares; it's just doing less work at each.

My pathfinding implementation is designed to pick from among all the available equally-good paths with equal probability (in order to make groups of moving units move a bit more chaotically), so it isn't compatible with jump point search. (You could also imagine a pathfinding algorithm that tries to interleave the moves in a way to most closely approximate straight-line movement, which would also not be compatible with jump point search.) It has got me thinking about ways to squash symmetry out of my pathfinding, though.