aoi

README

AOI (Area of Interest) Library

This library provides implementations of Area of Interest algorithms for spatial partitioning. Currently, it includes implementations for the following algorithms:

1. 九宫格 (Grid Manager)

   • A simple grid-based AOI algorithm dividing the area into a grid of cells and associating entities with the corresponding grid cells.

2. 四叉树 (Quadtree)

   • A hierarchical spatial partitioning algorithm dividing the area into four quadrants recursively, optimizing the search for entities within a specified range.

Usage:

九宫格 (Grid Manager)

// Example Usage:
aoiManager := NewGridManager(startX, startY, areaWidth, gridCount)
aoiManager.Add(x, y, "player1")
aoiManager.Delete(x, y, "player1")
result := aoiManager.Search(x, y)

// Example Usage:
quadTree := NewQuadTree(startX, startY, areaWidth)
quadTree.Add(x, y, "player1")
quadTree.Delete(x, y, "player1")
result := quadTree.Search(x, y)

Features:

• Both implementations support adding, deleting, and searching for entities within a specified area of interest.
• The Grid Manager uses a simple grid-based approach, while the Quadtree provides a hierarchical and optimized solution for larger and dynamic environments.

TODO:

Implement additional commonly used AOI algorithms:

• R-树 (R-tree)
• 六边形网格 (Hexagonal Grid)
• 基于事件的算法 (Event-driven Approaches)

License

This AOI Library is licensed under the MIT License.

Documentation

Index

• type AOI
  • func NewGridManager(startX, startY, areaWidth, gridCount int) AOI
  • func NewQuadTree(xStart, yStart, width float64) AOI
• type Entity
• type Grid
  • func NewGrid(gid int) *Grid
• type GridManager
  • func (g *GridManager) Add(x, y float64, key string)
  • func (g *GridManager) Delete(x, y float64, key string)
  • func (g *GridManager) Search(x, y float64) []string
• type Node
  • func NewSonNode(xStart, yStart float64, parent *Node) *Node
  • func (n *Node) Add(x, y float64, name string)
  • func (n *Node) Delete(x, y float64, name string)
  • func (n *Node) Search(x, y float64) []string
• type QuadTree

Types

type AOI

type AOI interface {
	Add(x, y float64, name string)         // Add an entity to the AOI
	Delete(x, y float64, name string)      // Delete an entity from the AOI
	Search(x, y float64) (result []string) // Search for entities within a specified range
}

AOI (Area of Interest) represents an interface for managing entities within a specific area.

func NewGridManager

func NewGridManager(startX, startY, areaWidth, gridCount int) AOI

NewGridManager initializes a new GridManager with the specified parameters.

func NewQuadTree

func NewQuadTree(xStart, yStart, width float64) AOI

NewQuadTree initializes a new QuadTree with the specified parameters.

type Entity

type Entity struct {
	X, Y float64
	Key  string
}

Entity represents an object with coordinates and a key.

type Grid

type Grid struct {
	GID      int      // Grid ID
	Entities sync.Map // Entities within the current grid
}

Grid represents a grid with a unique identifier and entities within it.

func NewGrid

func NewGrid(gid int) *Grid

NewGrid creates a new grid with the specified ID.

type GridManager

type GridManager struct {
	StartX    int // X-coordinate of the left boundary of the AOI
	StartY    int // Y-coordinate of the upper boundary of the AOI
	AreaWidth int // Width of each grid (assuming square grids)
	GridCount int // Number of grids in each row/column
	// contains filtered or unexported fields
}

GridManager implements AOI (Area of Interest) using a rectangular grid.

func (*GridManager) Add

func (g *GridManager) Add(x, y float64, key string)

Add adds an entity to the appropriate grid based on its coordinates.

func (*GridManager) Delete

func (g *GridManager) Delete(x, y float64, key string)

Delete removes an entity from the grid based on its coordinates.

func (*GridManager) Search

func (g *GridManager) Search(x, y float64) []string

Search retrieves a list of entity keys within the specified coordinates' range.

type Node

type Node struct {
	Leaf      bool      // Indicates whether the node is a leaf node
	Deep      int       // Depth of the node in the quadtree
	AreaWidth float64   // Width of the grid (assuming square grids)
	XStart    float64   // Starting X-coordinate of the node's area
	YStart    float64   // Starting Y-coordinate of the node's area
	Tree      *QuadTree // Pointer to the quadtree
	Child     [4]*Node  // Child nodes (quadrants)
	Entities  *sync.Map // Entities within the node
}

Node represents a node in the quadtree.

func NewSonNode

func NewSonNode(xStart, yStart float64, parent *Node) *Node

NewSonNode creates a new child node with the specified parameters.

func (*Node) Add

func (n *Node) Add(x, y float64, name string)

Add adds an entity to the quadtree based on its coordinates.

func (*Node) Delete

func (n *Node) Delete(x, y float64, name string)

Delete removes an entity from the quadtree based on its coordinates.

func (*Node) Search

func (n *Node) Search(x, y float64) []string

Search retrieves a list of entity keys within the specified coordinates' range.

type QuadTree

type QuadTree struct {
	*Node
	// contains filtered or unexported fields
}

QuadTree represents a quadtree data structure for spatial partitioning.