游戏邦在:
杂志专栏:
gamerboom.com订阅到鲜果订阅到抓虾google reader订阅到有道订阅到QQ邮箱订阅到帮看

分享AI寻径设计的射线追踪法

发布时间:2013-09-22 15:42:26 Tags:,,,,

作者:Stanley Handschuh

寻径的方法主要有两种,一是动态的,二是静态的。二者的区别在于,路径是即时生成的还是预设的。无论是哪种情况,路径都可以由客户端或服务器生成。一般来说,动态路径是在客户端生成的,然后根据自服务器的更新而变化。然而,静态路径既可以由客户端也可以由服务器生成。静态路径通常是服务器生成的,因为这样开发者就可以修改要点并同时改变所有客户端。

在开放或封闭空间中的寻径有一个共同形式,那就是使用射线追踪法。其原理就是B-Line,即在最短的距离之间使用最少数量的节点生成最短的路径。射线追踪法最常见的使用情况是用它制作静态地图。这通常是用于游戏中的小镇或城市,玩家通常有几个经常访问的静态点。图1是一张城市地图,彩色点表示目标点。

AIPRC1(from gamasutra)

AIPRC1(from gamasutra)

一个点代表一个玩家经常访问的点。绿色点是玩家进入城市的点,红色点是玩家离开城市必经的点。我们的玩家希望在不走重复路线的情况下游览城市的每一个地点。作为人类,我们想象出达到所有目标的最快路径。逻辑上说,玩家会从绿色点依次移动到黄色点、灰色点、紫色点、棕色点和红色点。但计算机怎么知道人类的这种逻辑,又怎么找到这种达到所有目标的路径?为此,系统要依靠寻径方法。这时可以使用B-Line逻辑,尽管产生相同结果所需的时间比射击追踪法要更长一些。两种方法的区别在于,在B-Line中,系统一个点一个点地追踪最佳路径。而在射线追踪法中,各个点都发射出预设的方向射线,标记着和射线之是的交点。当把玩家角色从一个地点移动到另一个地点时,系统就利用这些交点形成的节点。首先,最好使用简单的算法,所以最好的办法是从各个点移动,在八个基本方向上发出射线。这些射线应该从所有节点同时发出。图2显示了节点发出射线的结果:

AIPRC2(from gamasutra)

AIPRC2(from gamasutra)

所有射线发出后,系统必须找到它们之间的交点。这些点有两个功能:一是角色移动的停止点;二是作为射线发射的新节点。这样节点就可以覆盖整张地图,使玩家具有多条移动路径。这些不同的点是必须的,因为玩家可以选择手动寻径或系统自动寻径。然而,在我们的案例中,系统将把静态地点与动态移动系统的概念—-允许玩家随心所欲地移动相结合,使玩家不受预设路径的限制。在图3中,用圆圈圈出来的点是静态移动中唯一可以使用的点,而其他点则是后来生成的。

AIPRC3(from gamasutra)

AIPRC3(from gamasutra)

如图所示,灰色点、紫色点和棕色点之间有许多交点。但绿色点和黄色点只有一个交点。为了直观,图4移除了不产生交点的线;还移除了交点与墙体之间的交点。这样我们就能比较清楚地看到计算机可以生成的最佳路径。

AIPRC4(from gamasutra)

AIPRC4(from gamasutra)

正如之前所说的,寻径是为了找到不重复的路线。为了达到这个目标,必须先定义单一的路径。当评估不同的可用路径时,可能使用到许多不同的节点。但为了简单,图5没有显示所有交点。这不是最短的路径,但是可能被选择的路径。

AIPRC5(from gamasutra)

AIPRC5(from gamasutra)

在图5的例子中,顺序与原来所说的是不同的。那是因为有时候系统可能选择不同于玩家的路径。所以计算机系统如何运作这个方法?几乎没有什么引擎能够一次性搜索所有可能的射线。然而,许多引擎能够在2D网格上放出射线,然后在移除它们以前使它们保持有效的状态,以用于交点检测。最好的做法是,让系统计算所有点出发的射线,在绘制各条射线之时检测所有可能的交点。当找到交点,就生成一个节点。找到所有可能的节点后,系统可以利用这些节点生成玩家一般情况下会选择的动态路径。在静态系统中,当玩家选择自动寻径时,系统就会利用这些被储存起来的节点。但正如之前的案例表明,并非所有节点和路径都产生了。

为此,系统必须使用节点生成剩下的路径。在开头时提到,这生成更有深度的地图,但仍然不完整。如果我们看看图2,会发现节点路径内仍然有空隙。为了完善地图,我们还要做一件事。算法必须使用那些节点发出更多射线。在图6中,可能的新射线用黑线标出。

AIPRC6(from gamasutra)

AIPRC6(from gamasutra)

仍然有空隙。在地图的左半边,显然有空隙。为了解决这个问题,可以使用新的节点来完善地图。结果表现在图7中。然而,左下角的地方还是有很大的空隙。

AIPRC7(from gamasutra)

AIPRC7(from gamasutra)

最后一步可以使用的是B线概念。B线的基础就是做一个三角形,以生成路径。一般情况下,这个三角形是用于寻找直角的斜边的。然而,在这个案例中,算法被颠倒了。我们知道,绿色点和红色点会在有空隙的地图区域内形成三角。图8显示了使用已知路径和最后节点产生的B线三角形:

AIPRC8(from gamasutra)

AIPRC8(from gamasutra)

使用了这个三角形后,生成了两个新节点。那两个节点像其他结点一样,用来完善地图路径。左下方的节点不是很有用,但直角三角形斜边的右上方的节点特别有用。这种方法和算法的结合经常用于制作游戏世界中的静态地图,但在动态变化中的环境中,实际执行比本文所说的要复杂得多。因此,还要使用其他方法,但如果正确使用射线追踪法,也是非常有效的。然而,射线追踪法可以作为其他方法的补充,比如用于寻找两条路径的交点。这普遍使用于武器交火和碰撞检测。任何问题都没有唯一正确的解决方案,但这个概念可以使逻辑更加人性化。(本文为游戏邦/gamerboom.com编译,拒绝任何不保留版权的转载,如需转载请联系:游戏邦

AI Pathfinding Ray Casting

by Stanley Handschuh

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.(source:gamasutra)


上一篇:

下一篇: