Hi everyone,

Today, I would like to talk about pathfinding. The way I would usually tackle it would be by using some sort of grid and navigating in it using A* (or a variant like Theta* for any-angle path-planning), or using a navigation mesh. I felt like a grid would not fit really well into the way I handle the entities in my world, and I felt like generating navigation meshes would be a bit of a pain. So I decided to experiment with a custom algorithm, based on raycasting. Here are the first results:

The way it work is the following:

→I try to cast a ray from the source (the character) to its target. If we don't have any collision, then we can simply keep this direction. Otherwise, I add a node to the path at the collision point, and then cast two rays at the corners of the obstacle (giving two different cases to explore):

(also note that since my entities are not point, but are rather disk with a non-zero radius, I increase the size of all my obstacles by the radius in all directions before doing my collision tests)

→Then, if I encounter any other obstacle, I repeat the operation. Otherwise, I add the node to the path, and I try to attain the other side of the current obstacle by casting a new ray (in each case) toward the other corner. Again, if we encounter any obstacle we repeat the operations above, otherwise we add the corner to the path, and we cast a new ray from the current position toward the target destination:

It is actually very important to try to attain the other side of the obstacle instead of directly trying to go toward the target destination after attaining the first corner, to avoid a deadlock in the following case:

(also note that it is also important to not add the node immedialty at the corner, but move it a bit toward the exterior)

→I store these intermediate target nodes in a multimap, indexed by the total length of the path from the start to the last source position. So that, when I finally get to my desired target destination, I know I have probably the shortest path in all the pathes I tried (and clearly not the shortest path that exists, as you can see on the examples above !).

→Finally, the last step is to simplify the path, so that we take shortcuts whenever we can. The way I do it is by starting at the first node of the path I created, then I try to cast a ray to the other nodes of the path, starting from the last one (the target destination). If I don't have a collision, I can remove all the intermediate nodes. Then, I continue simplifying starting from this last node with no collision, etc. On our first example, it would give something like this:

It clearly does not give always the best path, but it seems to work well-enough in normal conditions. I don't know yet how well this would work in a super-complicated environment. Moreover, I need to figure out a way to improve performances since raycasting is not a super cheap operation (and especially because the number of rays increases really fast because we split in two every time we hit, and we can loose a lot of time with bad pathes stuck in a loop).