金庆的专栏

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  423 随笔 :: 0 文章 :: 454 评论 :: 0 Trackbacks

How are dtLinks created in NavMesh

(Jin Qing's Column, Nov., 2022)

dtLink defines a link between 2 polygons. It is an internal data structure.

A dtLink is owned by its source polygon.

The links are used in findPath(), to search all the neighbor polygons, from the current best polygon.

dtLink has 2 required fields:

  • neighbor: the neighbor polygon reference that is linked to.
  • edge: index of the polygon edge that owns this link. It is used in getPortalPoints() and raycast().

If the link is a boundary link, which links to other tile, then it has more fields:

  • side: defines on which side the link is. 8 sides. It is used in findPath() and raycast().
  • bmin: defines the minimum sub-edge area.
  • bmax: defines the maximum sub-edge area. bmin and bmax are used in portal finding.

Links are not saved to navmesh file. They are created on navmesh loading in addTile().

dtNavMesh::addTile() add a tile to the navmesh. A tile is a square block of the map.

The main job of dtNavMesh::addTile() is to create links inside this tile and between this tile and other tiles. Actually a block indexed by (x, y) of constant size has many layers for multi-floor map. A dtMeshTile is actually a layer with an index of (x, y, layer).

5 steps to create all links:

connectIntLinks() iterates all the polygons in the tile and create links for them by the help of neighbors information of the polygons.

2. Base off-mesh connections

baseOffMeshLinks() bases off-mesh connections to their starting polygons and connect connections inside the tile.

Off-mesh connection is between 2 points which are inside a tile or between 2 adjacent tiles.

For each off-mesh connection, there creates a specific polygon consisting of 2 vertices. See DT_POLYTYPE_OFFMESH_CONNECTION.

baseOffMeshLinks() creates 2 links for each off-mesh connection:

  • From the off-mesh connection polygon to the source polygon
  • From the source polygon to the off-mesh connection polygon

The destinaton polygon of the off-mesh connection is skipped here.

connectExtOffMeshLinks() with the source and target tile be this tile.

connectExtOffMeshLinks() searches off-mesh connections that are from this tile to the target tile by checking the side direction of the connection.

It creates a link from off-mesh connection polygon to the target tile. For bidirectional connection, it also creates a link from the target polygon to the off-mesh connection polygon.

So for each off-mesh connection of this tile, 3 or 4 links are created by baseOffMeshLinks() and connectExtOffMeshLinks(), one on the source polygon, one on the destination polygon and 1/2 on the off-mesh connection polygon.

4. Connect with layers in current tile

For each layer other than this layer in this tile:

  • Create links from this layer to other layer
  • Create links from other layer to this layer
  • Create links of the off-mesh connection from this layer to other layer
  • Create links of the off-mesh connection from other layer to this layer

5. Connect with neighbour tiles

Check 9 neighbor tiles' layers, and create links just like previous step:

  • Create links from this layer to neighnor layer
  • Create links from neighnor layer to this layer
  • Create links of the off-mesh connection from this layer to neighnor layer
  • Create links of the off-mesh connection from neighnor layer to this layer

By now, for every off-mesh connection of all the loaded tiles, 3/4 links are created.

Reference

  • https://blog.csdn.net/icebergliu1234/article/details/80322392
posted on 2022-11-18 10:03 金庆 阅读(30) 评论(0)  编辑 收藏 引用 所属分类: 1. C/C++2. 网游开发

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理