AI Pathfinding Ray Casting

    There are two major types of pathfinding the first is dynamic the second is static. The difference between the two is whether the path is generated in real-time or predefined. In either case the path can be created and held either on the client or the server. Typically dynamic paths are created on the client and changed as updates are received from the server. However, static paths can be either held on the client or the server. Often static paths are held on the server since it allows the developers to modify the points and effect all clients simultaneously.

    One common form of path finding through open or closed spaces uses ray casting. The method behind ray casting is a B-Line formula to create the shortest path using the least number of nodes over the shortest distance. To best illustrate how ray casting can be used is to utilize it to create a static map. This is often used within a town or city within a game. There are often static points that players visit often. Image 1 displays the city map and all of the relevant points of interest.

    Each colored dot represents a place the player would visit often. The green dot is where the player enters the city and the red dot is the last place the player has to go before leaving on his next adventure. Our player wants to visit every location without having to backtrack. As a human we can mentally find the fastest route to hit all the squares. Logically the player would start at the Green moves to Yellow, Grey, Purple, Brown then red. But how would the computer know this and how will the computer find the path to achieve these goals? To do this the system would rely on a path finding method. The B-Line logic could be used however the results take longer then ray casting and produce the same results. The difference is in a B-Line the system traces a path from dot to dot searching for the best path. With ray casting each dot will cast lines in predefined directions marking where the rays cross each other. These crossing create the nodes the system will utilize when moving the player form location to location. As a start it is best to use a simple algorithm, so the best way is to move from each point and send out a ray in each of the eight standard cardinal directions. These rays should be cast from all nodes at the same time. Image 2 displays what it might look like to the computer.

    Next after all of the rays are cast the system must search out the intersections. These points have two functions. The first will be a stopping point for the character to move about. The second is the node could be used to create a new ray cast location. These can be used to produce a full-scale map allowing movement through the whole zone providing multiple routes. These different roots are necessary since the player has the option to move both manually or through the automated system. However in our example the system will leave the locations static allowing a simple explanation but with understanding of the concept the developer could utilize a dynamic movement system letting the player move how they want to and not restrict them do the predefined paths only. In Image 3 the intersection points are circled. These will be the only points used in the static example but others could be created in the future.

    As the image shows there are quite a few intersection points between the Grey, Purple and Brown dots. But the Red and Yellow only appear to have one good entry point. For a visual reference Image 4 removes the unimportant lines that do not lead to an intersection. It also removes the lines that go from an intersection onto the wall. This allows us to visually see the best path that the computer could create.

    As previously mentioned the goal of this path is to find a route that does not double back in any way. In order to achieve this goal a single path needs to be defined. When reviewing the different paths available it is possible to use dozens of different nodes. But to simplify the visual Image 5 does not have any intersection paths. This is not the shortest possible path but it is a single possible path that could be chosen.

    In the example shown in Image 5 the order is different from the visual reference mentioned originally. That is because sometimes the system might choose paths in a different way than a person would normally think. So how does this work in the computer system? Very few engines have the capability to search all possible rays at a single time. However many engines have the ability to cast the rays on a 2D grid and leave them active for intersection checks before being removed. The best method is to have the system cast each ray from every dot and during the drawing of each ray have it check for all possible intersections before terminating on a wall. When an intersection is found a node is created. After all possible nodes are found the system can utilize those to create the dynamic path selection that a player would normally use. In a static system these nodes are stored and then used whenever the player chooses a location to move to automatically. But as the previous example shows not all possible nodes and paths were created.

    In order to do this the system must use the nodes to create the remaining paths. As mentioned at the beginning this creates a more in depth map of the world but it is still not complete. If we look at Image 2 there are obviously still gaps within the node paths. To finish the map there is another step that must be done. The algorithm will have to take the nodes and cast more rays from those locations. Image 6 displays some of the possible new rays in Black.

    While this does help some sections of the map there are still gaps. On the left side of the map it is obvious there are still gaps. To resolve this it is possible to use the new nodes to complete the map. Image 7 does this in areas. However as it does close out areas there is still a large gap that has a long walk between locations on the lower left corner.

    The last step that can be used is a B-Line concept. The basis of a B-Line is to create a triangle to create the path. Normally the triangle is used to find the hypotenuse. However in this case the algorithm will be reversed. It is known that the green and red squares will create a triangle in the area of the map that there is a gap so using the known paths and creating the B-Line Triangle the Final nodes are created in Image 8.

    With the usage of this one triangle two new nodes were created. Those two nodes can now be used like the others and complete the map. The lower left node is not very useful but the upper right one in the center of the hypotenuse is perfect to finish the left side of the map. This combination of methods and algorithms is commonly used to create static maps within persistent worlds. It is however far too complex as explained here to generate within a dynamically changing environment. Because of this other methods are preferred but when used correctly within its application the ray cast node definition is highly effective. However, the ray cast method can be used to supplement other methods in a simpler form such as looking for a point that two paths would cross. This is commonly used for weapons fire and collision detection. There is no single correct solution to any problem but the concepts make the humanized logic possible.