The difficulty has always been in how many things you look at. Tiles or objects. With static maps you can quite easily structure things so that you don't ha

The difficulty has always been in how many things you look at. Tiles or objects. With static maps you can quite easily structure things so that you don't have to look at very much at all. When things are dynamic tests such as 'look at the thing in the way' suddenly get harder because you have to determine for any given point A) is something in the way? and B) what is it? The simplest and most memory hungry thing would be to have a tile map where every tile has a precalculated map on the direction to go to reach every other tile. If you used that as a basis for optimisation you can rapidly improve, for instance an easy first step is to not store any direction data for areas where the path in a straight line is optimal. Optimize more and you can reduce the scale of data and compute required to calculate the map you can eventually calculate the map quicker and often for only the start and end points you care about. Follow those optimisations far enough and you end up with many of the algorithms used today. If you have a lot of things moving in a dense area, often the optimal is to maintain a bitmap of 'Something is here' making presence detection trivial. If you then do a 8 passes over that bitmap for each direction you can go (for square tiles) you can create 8 further maps with a count recording when that pass last saw an obstruction. That lets you implement a very fast jump point search where instead of scanning tile by tile you can jump to the next obstruction in order to either find the way around or find the dead end. I think the algorithm mentioned in the article is essentially a jump point search but not going into how the "select the optimal point for bypassing the obstacle" is done. Again this comes back to static/dymamic and how to determine that point. If using object outlines, can objects scale or rotate? You could probably do a reasonable version of jump point with convex hulls around objects and simple fast-out distance functions. A single object system would have difficulty dealing when multiple objects have overlapping bounds though. Two S shaped objects that are overlapping in their bounds might have a path possible through them but it is likely to not involve the optimal passing point of each individual shape alone is not on the path between them. So the ideal is different for static/dynamic, dense/sparse, or memory availability, but all of those factors come back to how they influence how you decide what to look at and how to ignore irrelevant information.