11. MMO在线游戏AOI算法-DEV365 开发者社区

在研究当前项目案例之前，本节将提供MMO Games中使用的基本地图算法的介绍。

游戏中的AOI（感兴趣领域）算法可以视为基本核心，因为许多游戏逻辑都是由AOI进入和退出事件驱动的。此外，众多网络同步数据源于AOI进入和退出事件。因此，基于它的强大AOI算法和优化对于增强游戏性能至关重要。

为了实现这一目标，有必要为每个玩家建立一个AOI。当对象的状态发生变化时，需要向所有玩家广播信息。 AOI覆盖范围内的玩家将收到此广播消息并做出相应的回应。

当当前游戏演示的AOI的所需功能是在服务器上的玩家或NPC的状态更改时，向附近的玩家广播消息。当玩家进入NPC的警报区域时，AOI模块将消息发送给NPC，然后以适当的AI操作做出响应。

接下来，让我们继续为Zinx应用程序服务器演示的项目构建。首先创建“ MMO_GAME”目录作为服务器端游戏应用程序的主要项目目录。

11.1基于网络的AOI算法实现

在深入研究AOI算法的实现之前，让我们首先创建一个2D地图以可视化AOI的概念，如图11.1所示。

图11.1

我们将当前坐标系分为20个同等大小的单元。 X轴和Y轴坐标范围为0到250。每个轴分为5个截面，每个轴都将每个部分视为沿该轴的单元。这导致2D坐标系中总共25个单元格ID，通过组合X和Y轴指数形成。

。

让我们定义计算中使用的一些变量和公式：

（1）AOI地图的尺寸，总尺寸为250x250：

w x轴的宽度
l y轴的长度

w = 250, l = 250

（2）X轴上的单元格：

nx = 5

（3）y轴上的单元格：

ny = 5

（4）沿x轴的每个单元的宽度：

dx = w / nx
(i.e., dx = 250 / 5 = 50)

（5）每个单元沿y轴的长度：

dy = l / ny
(i.e., dy = 250 / 5 = 50)

（6）单元格的X轴索引：IDX，范围为0至4
（7）单元格的y轴索引：偶然，范围为0至4

（8）单元格ID：

id = idy * nx + idx

从上面的公式中，您可以根据单元格的坐标确定单元格ID。

（9）单元格的坐标：

x-axis coordinate index: idx = id % nx
y-axis coordinate index: idy = id / nx

必须根据图11.1仔细阅读和执行基本计算以了解所提供的公式。在实施后续代码逻辑时，这将有助于理解。

请注意，应针对图11.1引用上述公式。鼓励读者阅读并根据图进行简单的计算，以更好地掌握概念并为即将到来的代码实施做准备。

11.2实施AOI网格结构

在本节中，我们将基于上一节中提供的公式实现与AOI网格相关的数据结构，算法和接口。我们将在“核心”模块中组织AOI模块。首先，在“ mmo_game”目录中创建一个“核心”文件夹，然后创建一个“ grid.go”文件。该文件将包含与AOI网格相关算法的实现。代码如下：

// mmo_game/core/grid.go

package core

import "sync"

/*
   A grid class within a map
*/
type Grid struct {
    GID       int             // Grid ID
    MinX      int             // Left boundary coordinate of the grid
    MaxX      int             // Right boundary coordinate of the grid
    MinY      int             // Upper boundary coordinate of the grid
    MaxY      int             // Lower boundary coordinate of the grid
    playerIDs map[int]bool    // IDs of players or objects in the current grid
    pIDLock   sync.RWMutex    // Lock to protect the playerIDs map
}

// Initialize a grid
func NewGrid(gID, minX, maxX, minY, maxY int) *Grid {
    return &Grid{
        GID:       gID,
        MinX:      minX,
        MaxX:      maxX,
        MinY:      minY,
        MaxY:      maxY,
        playerIDs: make(map[int]bool),
    }
}

提供的代码定义了网格数据结构。每个网格代表一个单元格，并且图可以分为多个此类网格。 MinX，MaxX，MinY和MaxY值代表每个网格的边界。 playerIDs地图跟踪网格中存在的播放器或物体的IDs。 pIDLock是一个并发的读取锁，可保护playerIDs地图。 GID代表网格的唯一标识符。

请注意，playerIDs地图将玩家或对象的ID用作地图数据结构中的键。该代码是实现AOI网格结构的基础，对于AOI算法实现的即将到来的步骤至关重要。

网格类需要具有多种能力：

ï¼1ï¼将播放器添加到当前的网格单元格，名为add（）的方法，如下：

//mmo_game/core/grid.go

// Add a player to the current grid
func (g *Grid) Add(playerID int) {
    g.pIDLock.Lock()
    defer g.pIDLock.Unlock()

    g.playerIDs[playerID] = true
}

（2）从当前的Grid单元格中删除一个名为Remove()的方法，如下：

//mmo_game/core/grid.go

// Remove a player from the grid
func (g *Grid) Remove(playerID int) {
    g.pIDLock.Lock()
    defer g.pIDLock.Unlock()

    delete(g.playerIDs, playerID)
}

（3）检索存储在当前网格中的所有播放器ID，名为GetPlayerIDs()的方法，返回了一片播放器ID，如下实现：

//mmo_game/core/grid.go

// Get all players in the current grid
func (g *Grid) GetPlayerIDs() (playerIDs []int) {
    g.pIDLock.RLock()
    defer g.pIDLock.RUnlock()

    for k := range g.playerIDs {
        playerIDs = append(playerIDs, k)
    }

    return
}

（4）打印当前电网的自参数信息的记录方法，名为String()的方法，如下：

//mmo_game/core/grid.go

// Print information method
func (g *Grid) String() string {
    return fmt.Sprintf("Grid id: %d, minX:%d, maxX:%d, minY:%d, maxY:%d, playerIDs:%v",
        g.GID, g.MinX, g.MaxX, g.MinY, g.MaxY, g.playerIDs)
}

11.3实施AOI管理模块

如果将Grid视为元素，则许多Grid细胞可以组成AOI（感兴趣的区域）区域。本节定义了AOI管理模块，该模块提供了管理所有网格的功能。使用AOI管理模块，可以添加创建的Grid对象以进行管理。

在mmo_game/core目录中创建一个名为aoi.go的文件。该文件主要实现与AOI管理模块相关的功能。在以下代码中定义AOI管理器的数据结构：

// mmo_game/core/aoi.go
package core

/*
   AOI Management Module
*/
type AOIManager struct {
    MinX  int           // Area's left boundary coordinate
    MaxX  int           // Area's right boundary coordinate
    CntsX int           // Number of grids in the x-direction
    MinY  int           // Area's upper boundary coordinate
    MaxY  int           // Area's lower boundary coordinate
    CntsY int           // Number of grids in the y-direction
    grids map[int]*Grid // All grids present in the current area, key = grid ID, value = grid object
}

/*
   Initialize an AOI area
*/
func NewAOIManager(minX, maxX, cntsX, minY, maxY, cntsY int) *AOIManager {
    aoiMgr := &AOIManager{
        MinX:  minX,
        MaxX:  maxX,
        CntsX: cntsX,
        MinY:  minY,
        MaxY:  maxY,
        CntsY: cntsY,
        grids: make(map[int]*Grid),
    }

    // Initialize all grids in the AOI initialization area
    for y := 0; y < cntsY; y++ {
        for x := 0; x < cntsX; x++ {
            // Calculate grid ID
            // Grid number: id = idy *nx + idx (using grid coordinates to get grid number)
            gid := y*cntsX + x

            // Initialize a grid and place it in the AOI map, key is the current grid's ID
            aoiMgr.grids[gid] = NewGrid(gid,
                aoiMgr.MinX+x*aoiMgr.gridWidth(),
                aoiMgr.MinX+(x+1)*aoiMgr.gridWidth(),
                aoiMgr.MinY+y*aoiMgr.gridLength(),
                aoiMgr.MinY+(y+1)*aoiMgr.gridLength())
        }
    }

    return aoiMgr
}

AOIManager仍然包含边界坐标，例如MinX，MinY，MaxX和MaxY，以及代表X和Y轴上网格单元的数量的CntsX和CntsY。成员属性网格管理使用地图在当前的AOIManager区域中存在网格。键是每个网格的``IDS，并且值是网格对象。

NewAOIManager()方法用于初始化AOI区域并返回AOIManager对象。在初始化过程中，AOIManager为该区域的所有网格创建并计算网格IDs和边界。它创建了总共CntsX * CntsY网格，使用前面提到的公式计算每个网格的ID和边界，并将创建的网格添加到网格集合中。

AOIManager区域网格管理模块还包括其他方法，例如获得X轴中每个网格的宽度和长度，并打印当前区域中所有网格的坐标和信息。

代码实现如下：
`go
// mmo_game/core/aoi.go

//在x轴方向上获取每个网格的宽度
func（m *aoimanager）gridwidth（）int {
返回（m.maxx -m.minx） / m.cntsx
}

//在x轴方向上获取每个网格的长度
func（m *aoimanager）gridlength（）int {
返回（M.Maxy -M.Miny） / m.cntsy
}

// String（）打印信息的方法
func（m *aoimanager）string（）字符串{
s：= fmt.sprintf（“ aoimanager：\ nminx：％d，maxx：％d，cntsx：％d，miny：％d，maxy：％d，cntsy：％d，cntsy：aoi manager中的％d \ n网格：\ n” ，
M.Minx，M.Maxx，M.CNTSX，M.Miny，M.Maxy，M.Cntsy）
_，网格：= range m.grids {
s += fmt.sprintln（网格）
}

    return s

}
`
以上代码创建了一个AOI管理模块，该模块可以理解为包含多个网格的2D矩形地图。 NewAOIManager()构造方法将映射分为多个较小的网格，并初始化其坐标。计算方法很简单，涉及基本的几何计算。

11.4计算9网格

AOI算法中的一个必不可少的概念是“九个网格”，它涉及确定与给定网格相邻的所有网格。由于Grid是四边形，如果网格不在AOI区域的边界上，则自身与其他八个周围网格的结合会导致9个网格。当玩家从一个区域移动到另一个区域时，九个网格的概念主要用于MMO游戏中，以触发一系列逻辑。这包括诸如显示玩家的视野，过渡地图和确定技能范围之类的任务。因此，计算AOI区域每个网格的九个网格的能力是AOIManager必须具有的关键功能。

11.4.1根据网格ID找到相邻的网格

根据给定的网格ID确定相邻的网格时，需要考虑几种情况：

（1）当中心网格不在AOI区域的边界上时，周围的九个网格可以完全填充，如图11.3所示。

图11.3

（2）当中心网格位于AOI区域的四个角时，如图11.4所示。

图11.4

（3）当中心网格位于AOI边界上（不是在拐角处）时，周围的网格缺少一列或一行，如图11.5所示。

图11.5
所有三种情况都可以使用统一算法解决。该方法涉及动态绘制向量。要确定特定网格的周围九个网格，您可以首先检查与当前网格的左侧和右侧是否有网格。然后，对上下的行执行相同的检查。这样，通过执行两个检查循环，您可以确定当前网格周围的相邻网格，如图11.6所示。

图11.6

在图11.6中描述的情况下，中央节点是带有GID 16的网格，该过程开始遍历Grid 16 is located to identify the grids to its left and right. This results in a set of Grids with IDS 15、16和17. Next, the column where Grid 15 is situated is examined to identify any grids above and below it, leading to a set of Grids with IDS 10、15和20. Similar logic is applied to grids 11、16、16、16、11、14，以及21, as well as grid51gridsgrids 15、16和17. Next, the column where Grid 15 is situated is examined to identify any grids above and below it, leading to a set of Grids with ID的行开始。 12、17和22. The resulting set of grids, including Grid 16`本身形成了完整的九个网格社区。

对于中央网格位于AOI区域的一个角落的情况，如图11.7所示，适用相同的逻辑。

图11.7

如果网格位于AOI区域的一个角落，则该算法保持不变，除了在第一个矢量遍历期间，将有一部分无法包括在内。例如，在处理GID 0并确定其九个网格社区的网格时，首先涉及检查是否有左右的网格，从而导致包含IDs 0 and 1的集合。接下来，基于网格0和1，进行检查以确定上方和下方是否有网格，分别导致集合0, 5和1, 6。这两个迭代的组合代表了网格0的九个网格社区。

最终场景涉及中央网格位于AOI区域的边界上。在这种情况下，可以采用上述相同的方法来确定九个网格区域。例如，如果我们想找到网格5的九个网格社区，我们首先检查是否有左右的网格，从而导致set 5, 6。然后，基于Grids 5 and 6，我们分别确定上方和下方是否有网格，从而产生0, 5, 10和1, 6, 11。最终，在此过程中遍历的所有网格构成了中央网格的九个网格社区，带有GID5。

在函数GetSurroundGridsByGid()和以下代码中定义了如上所述确定上述周围网格的算法：

//mmo_game/core/aoi.go

// Get the surrounding nine grids information based on the given grid's GID
func (m *AOIManager) GetSurroundGridsByGid(gID int) (grids []*Grid) {
    // Check if the gID exists
    if _, ok := m.grids[gID]; !ok {
        return
    }

    // Add the current gid to the list of grids
    grids = append(grids, m.grids[gID])

    // Get the X-axis index of the current grid based on gid
    idx := gID % m.CntsX

    // Check if there's a grid to the left of the current idx
    if idx > 0 {
        grids = append(grids, m.grids[gID-1])
    }
    // Check if there's a grid to the right of the current idx
    if idx < m.CntsX-1 {
        grids = append(grids, m.grids[gID+1])
    }

    // Extract all grids from the current x-axis for further traversal,
    // and determine whether each grid has a grid above and below it

    // Get the collection of grid ids in the current x-axis
    gidsX := make([]int, 0, len(grids))
    for _, v := range grids {
        gidsX = append(gidsX, v.GID)
    }

    // Traverse the grids on the x-axis
    for _, v := range gidsX {
        // Calculate in which row the grid is located
        idy := v / m.CntsX

        // Check if there's a grid above the current idy
        if idy > 0 {
            grids = append(grids, m.grids[v-m.CntsX])
        }
        // Check if there's a grid below the current idy
        if idy < m.CntsY-1 {
            grids = append(grids, m.grids[v+m.CntsX])
        }
    }

    return
}

检查代码中的左右和顶部邻近网格时，考虑边界点很重要。如果未满足边界条件，则表明该特定方向没有网格。

11.4.2基于坐标确定九个网格

另一种情况是，当玩家只知道自己的坐标时。在这种情况下，我们如何确定玩家AOI的九个网格中存在哪些玩家？为了实现这一目标，我们需要设计一个界面，该界面基于坐标来计算相邻的九个网格中的播放器。

总体方法是首先计算当前玩家坐标所属的网格ID。然后，根据获得的网格ID，我们可以检索有关周围九个网格的信息。此过程如图11.9。

图11.9

基于播放器坐标获得当前的网格ID是通过接口GetGIDByPos()完成的，如以下代码中实现：

//mmo_game/core/aoi.go

// Get the corresponding grid ID based on x and y coordinates
func (m *AOIManager) GetGIDByPos(x, y float32) int {
    gx := (int(x) - m.MinX) / m.gridWidth()
    gy := (int(y) - m.MinY) / m.gridLength()

    return gy * m.CntsX + gx
}

此外，根据播放器的X和Y坐标，将所有播放器ID在周围的九个网格中获取的接口定义如下：

//mmo_game/core/aoi.go

// Get all PlayerIDs within the surrounding nine grids based on x and y coordinates
func (m *AOIManager) GetPIDsByPos(x, y float32) (playerIDs []int) {
    // Get the grid ID to which the coordinates belong
    gID := m.GetGIDByPos(x, y)

    // Get information about the surrounding nine grids based on grid ID
    grids := m.GetSurroundGridsByGid(gID)
    for _, v := range grids {
        playerIDs = append(playerIDs, v.GetPlayerIDs()...)
        fmt.Printf("===> grid ID : %d, pids : %v  ====", v.GID, v.GetPlayerIDs())
    }

    return
}

该接口的方法是首先调用GetGIDByPos()以确定坐标所属于的网格，从而获得GID。接下来，通过调用函数GetSurroundGridsByGid()检索有关周围九个网格的信息，它获得了网格集合。最后，它从集合中的每个网格中提取所有播放器ID信息。

11.5 AOI区域网格增加和删除操作

在本节中，我们将在Aoimanager内实施与网格相关的添加和删除操作。这些方法的实现相对简单，如以下代码所示：

//mmo_game/core/aoi.go

// Get all player IDs within a current grid based on GID
func (m *AOIManager) GetPidsByGid(gID int) (playerIDs []int) {
    playerIDs = m.grids[gID].GetPlayerIDs()
    return
}

// Remove a player ID from a grid
func (m *AOIManager) RemovePidFromGrid(pID, gID int) {
    m.grids[gID].Remove(pID)
}

// Add a player ID to a grid
func (m *AOIManager) AddPidToGrid(pID, gID int) {
    m.grids[gID].Add(pID)
}

// Add a player to a grid based on x and y coordinates
func (m *AOIManager) AddToGridByPos(pID int, x, y float32) {
    gID := m.GetGIDByPos(x, y)
    grid := m.grids[gID]
    grid.Add(pID)
}

// Remove a player from the corresponding grid based on x and y coordinates
func (m *AOIManager) RemoveFromGridByPos(pID int, x, y float32) {
    gID := m.GetGIDByPos(x, y)
    grid := m.grids[gID]
    grid.Remove(pID)
}

11.6 AOI模块的单位测试

实现与AOI相关的所有功能后，执行单元测试以验证AOI模块提供的功能很重要。在MMO_GAME/CORE DIRECTORY中创建一个名为aoi_test.go的单元测试文件，并实现两个测试用例：testNewaoimanager（）和TestAOIManagerSuroundGridsByGid()。这是代码：

//mmo_game/core/aoi_test.go

package core

import (
    "fmt"
    "testing"
)

func TestNewAOIManager(t *testing.T) {
    aoiMgr := NewAOIManager(100, 300, 4, 200, 450, 5)
    fmt.Println(aoiMgr)
}

func TestAOIManagerSuroundGridsByGid(t *testing.T) {
    aoiMgr := NewAOIManager(0, 250, 5, 0, 250, 5)

    for k, _ := range aoiMgr.grids {
        // Get the surrounding grids for the current grid
        grids := aoiMgr.GetSurroundGridsByGid(k)
        // Get all the IDs of the surrounding grids
        fmt.Println("gid : ", k, " grids len = ", len(grids))
        gIDs := make([]int, 0, len(grids))
        for _, grid := range grids {
            gIDs = append(gIDs, grid.GID)
        }
        fmt.Printf("grid ID: %d, surrounding grid IDs are %v\n", k, gIDs)
    }
}

测试TestNewAOIManager()用于验证AOI（感兴趣的区域）区域的构建，并在AOI区域构建后提供了信息的详细输出。测试结果如下：

AOIManager:
minX: 100, maxX: 300, cntsX: 4, minY: 200, maxY: 450, cntsY: 5
Grids in AOI Manager:
Grid id: 1, minX: 150, maxX: 200, minY: 200, maxY: 250, playerIDs: map[]
Grid id: 5, minX: 150, maxX: 200, minY: 250, maxY: 300, playerIDs: map[]
Grid id: 6, minX: 200, maxX: 250, minY: 250, maxY: 300, playerIDs: map[]
Grid id: 12, minX: 100, maxX: 150, minY: 350, maxY: 400, playerIDs: map[]
Grid id: 19, minX: 250, maxX: 300, minY: 400, maxY: 450, playerIDs: map[]
Grid id: 7, minX: 250, maxX: 300, minY: 250, maxY: 300, playerIDs: map[]
Grid id: 8, minX: 100, maxX: 150, minY: 300, maxY: 350, playerIDs: map[]
Grid id: 10, minX: 200, maxX: 250, minY: 300, maxY: 350, playerIDs: map[]
Grid id: 11, minX: 250, maxX: 300, minY: 300, maxY: 350, playerIDs: map[]
Grid id: 15, minX: 250, maxX: 300, minY: 350, maxY: 400, playerIDs: map[]
Grid id: 18, minX: 200, maxX: 250, minY: 400, maxY: 450, playerIDs: map[]
Grid id: 0, minX: 100, maxX: 150, minY: 200, maxY: 250, playerIDs: map[]
Grid id: 3, minX: 250, maxX: 300, minY: 200, maxY: 250, playerIDs: map[]
Grid id: 4, minX: 100, maxX: 150, minY: 250, maxY: 300, playerIDs: map[]
Grid id: 14, minX: 200, maxX: 250, minY: 350, maxY: 400, playerIDs: map[]
Grid id: 16, minX: 100, maxX: 150, minY: 400, maxY: 450, playerIDs: map[]
Grid id: 2, minX: 200, maxX: 250, minY: 200, maxY: 250, playerIDs: map[]
Grid id: 9, minX: 150, maxX: 200, minY: 300, maxY: 350, playerIDs: map[]
Grid id: 13, minX: 150, maxX: 200, minY: 350, maxY: 400, playerIDs: map[]
Grid id: 17, minX: 150, maxX: 200, minY: 400, maxY: 450, playerIDs: map[]

测试TestAOIManagerSuroundGridsByGid()验证了九个网格系统的周围网格计算结果是否正确。执行结果如下：

gid :  3  grids len =  6
grid ID: 3, surrounding grid IDs are [3 2 4 8 7 9]
gid :  5  grids len =  6
grid ID: 5, surrounding grid IDs are [5 6 0 10 1 11]
gid :  6  grids len =  9
grid ID: 6, surrounding grid IDs are [6 5 7 1 11 0 10 2 12]
gid :  11  grids len =  9
grid ID: 11, surrounding grid IDs are [11 10 12 6 16 5 15 7 17]
gid :  18  grids len =  9
grid ID: 18, surrounding grid IDs are [18 17 19 13 23 12 22 14 24]
gid :  2  grids len =  6
grid ID: 2, surrounding grid IDs are [2 1 3 7 6 8]
gid :  4  grids len =  4
grid ID: 4, surrounding grid IDs are [4 3 9 8]
gid :  7  grids len =  9
grid ID: 7, surrounding grid IDs are [7 6 8 2 12 1 11 3 13]
gid :  8  grids len =  9
grid ID: 8, surrounding grid IDs are [8 7 9 3 13 2 12 4 14]
gid :  19  grids len =  6
grid ID: 19, surrounding grid IDs are [19 18 14 24 13 23]
gid :  22  grids len =  6
grid ID: 22, surrounding grid IDs are [22 21 23 17 16 18]
gid :  0  grids len =  4
grid ID: 0, surrounding grid IDs are [0 1 5 6]
gid :  1  grids len =  6
grid ID: 1, surrounding grid IDs are [1 0 2 6 5 7]
gid :  13  grids len =  9
grid ID: 13, surrounding grid IDs are [13 12 14 8 18 7 17 9 19]
gid :  14  grids len =  6
grid ID: 14, surrounding grid IDs are [14 13 9 19 8 18]
gid :  16  grids len =  9
grid ID: 16, surrounding grid IDs are [16 15 17 11 21 10 20 12 22]
gid :  17  grids len =  9
grid ID: 17, surrounding grid IDs are [17 16 18 12 22 11 21 13 23]
gid :  23  grids len =  6
grid ID: 23, surrounding grid IDs are [23 22 24 18 17 19]
gid :  24  grids len =  4
grid ID: 24, surrounding grid IDs are [24 23 19 18]
gid :  9  grids len =  6
grid ID: 9, surrounding grid IDs are [9 8 4 14 3 13]
gid :  10  grids len =  6
grid ID: 10, surrounding grid IDs are [10 11 5 15 6 16]
gid :  12  grids len =  9
grid ID: 12, surrounding grid IDs are [12 11 13 7 17 6 16 8 18]
gid :  15  grids len =  6
grid ID: 15, surrounding grid IDs are [15 16 10 20 11 21]
gid :  20  grids len =  4
grid ID: 20, surrounding grid IDs are [20 21 15 16]
gid :  21  grids len =  6
grid ID: 21, surrounding grid IDs are [21 20 22 16 15 17]
PASS
ok      zinx/zinx_app_demo/mmo_game/core    0.002s

TestAOIManagerSuroundGridsByGid()的结果匹配了显示的结构和图11.2。验证证实，九个网格计算结果与图中所描绘的结构一致。

MMO游戏源代码

https://github.com/aceld/zinx/tree/master/zinx_app_demo/mmo_game

[zinx]

[ZINX应用程序 - MMO游戏案例研究]

<10. Application Case Study using the Zinx Framework>
<11. MMO Online Game AOI Algorithm>

作者：
不和谐：https://discord.gg/xQ8Xxfyfcz
zinx：https://github.com/aceld/zinx
github：https://github.com/aceld
Aceld的家：https://yuque.com/aceld