RoServer/RO_Server_Trunk-branch_bt/roserver/baseserver/aoi/aoi.go

package aoi

//"gopkg.in/fatih/set.v0"
import (
	"math"
	"rocommon/util"
	"roserver/baseserver/set"
	"sort"
	"sync"
	"time"
)

const (
	LISTTYPE_X = 1
	LISTTYPE_Y = 2

	FIND_NUM_MAX = 10
)

type AoiVector2 struct {
	X float32
	Y float32
	Z float32
}

//set https://studygolang.com/articles/16224?fr=sidebar
//https://github.com/qq362946/AOI
type aoiInfo struct {
	MoveSet      set.Interface
	MoveOnlySet  set.Interface
	EnterSet     set.Interface
	LeaveSet     set.Interface
	MoveNoNtfSet set.Interface
}
type aoiLinkNode struct {
	Next *AoiObject
	Pre  *AoiObject
}

type AoiObject struct {
	Id          uint64
	Pos         *AoiVector2
	AoiInfo     *aoiInfo
	node        *Node
	updateCount int32

	rect *QuadBounds
}

func NewAoiObject(id uint64, x, y float32, z float32) *AoiObject {
	obj := new(AoiObject)
	obj.Id = id
	obj.Pos = &AoiVector2{X: x, Y: y, Z: z}
	obj.updateCount = 0
	obj.AoiInfo = &aoiInfo{}
	obj.AoiInfo.MoveSet = set.New(set.NonThreadSafe)
	obj.AoiInfo.MoveOnlySet = set.New(set.NonThreadSafe)
	obj.AoiInfo.EnterSet = set.New(set.NonThreadSafe)
	obj.AoiInfo.LeaveSet = set.New(set.NonThreadSafe)
	obj.AoiInfo.MoveNoNtfSet = set.New(set.NonThreadSafe)

	return obj
}

func (this *AoiObject) SetNode(node *Node) {
	this.node = node
}

func (this *AoiObject) SetPosition(x, y float32) {
	this.Pos.X = x
	this.Pos.Y = y
}

func (this *AoiObject) GetMoveSize() int32 {
	return int32(this.AoiInfo.MoveSet.Size())
}

///////////////////////
type Aoi struct {
	nodes     map[uint64]*AoiObject
	xNodeList *SkipList
	yNodeList *SkipList

	AoiArea *AoiVector2

	quadTree *QuadTreeNode
}

var newNodePool = sync.Pool{
	New: func() interface{} {
		node := &Node{Forward: make([]*Node, SKIPLIST_MAXLEVEL)}
		node.ValueList = make(map[uint64]*AoiObject)
		//v.(*AoiObject).SetNode(node)
		//node.addValue(v.(*AoiObject))
		return node
	},
}

func NewAoi() *Aoi {
	aoi := &Aoi{}
	aoi.nodes = make(map[uint64]*AoiObject)
	aoi.xNodeList = NewSkipList(LISTTYPE_X)
	aoi.yNodeList = NewSkipList(LISTTYPE_Y)
	aoi.quadTree = NewQuadTree(8, &QuadBounds{-10000, -10000, 10000, 10000})

	aoi.AoiArea = &AoiVector2{10, 10, 0}
	return aoi
}

func (this *Aoi) GetNode(uid uint64) *AoiObject {
	if data, ok := this.nodes[uid]; ok {
		return data
	}
	return nil
}

func (this *Aoi) GetAllNode() map[uint64]*AoiObject {
	return this.nodes
}

func (this *Aoi) PrintStackList() {
	this.xNodeList.PrintSkipList()
}

/**
新加入AOI
*/
func (this *Aoi) Enter(uid uint64, callback func(*AoiObject), x, y, z float32, forceUpdate bool, isMaster bool) *AoiObject {
	if data, ok := this.nodes[uid]; ok {
		return data
	}

	//todo...可以使用pool
	obj := NewAoiObject(uid, x, y, z)

	this.xNodeList.Insert(obj)
	//this.yNodeList.Insert(obj)

	this.nodes[uid] = obj
	if obj.node == nil {
		util.InfoF("enter error") //insert操作失败
	}

	this.updateWithArea(obj, callback, *this.AoiArea, x, y, forceUpdate, isMaster)

	//this.PrintStackList()
	return obj
}

var profileTime time.Duration
var nowTime = util.GetCurrentTimeNow()
var profileCount int32 = 0

//更新节点
func (this *Aoi) Update(id uint64, callback func(*AoiObject), area AoiVector2, x, y float32, isMaster bool) (*AoiObject, bool) {
	if data, ok := this.nodes[id]; ok {
		profileCount++
		//nowTime := time.Now()
		obj, ret := this.updateWithArea(data, callback, area, x, y, false, isMaster)
		//this.PrintStackList()
		//return this.updateWithArea(data, area,x ,y)
		//profileTime += time.Now().Sub(nowTime)
		if util.GetCurrentTimeNow().Sub(nowTime) > time.Second {
			nowTime = util.GetCurrentTimeNow()
			/*
				oobb := this.nodes[6735728018393727041]
				log.Println("aoiUpdate[1000]:", oobb.Id,profileTime,
					len(oobb.AoiInfo.MoveSet.List()),
					len(oobb.AoiInfo.EnterSet.List()),
					len(oobb.AoiInfo.LeaveSet.List()),
					len(oobb.AoiInfo.MoveOnlySet.List()))
			*/

			profileCount = 0
			profileTime = 0
		}
		return obj, ret
	}
	return nil, false
}

//callback 处理必须可见玩家列表(目前只包括情侣)
func (this *Aoi) updateWithArea(obj *AoiObject, callback func(*AoiObject), area AoiVector2, x, y float32, forceUpdate bool, isMaster bool) (*AoiObject, bool) {
	//移动到新的位置
	this.move(obj, x, y)

	//减少更新频率，发3次移动包，做一次视野更新
	//obj.updateCount++
	//if obj.updateCount%3 != 0 && !forceUpdate {
	//	return obj, false
	//}
	//obj.updateCount = 0

	//把AOI节点转换到旧的节点里
	tempMoveSet := obj.AoiInfo.MoveSet.Copy()
	//obj.AoiInfo.MoveOnlySet = obj.AoiInfo.MoveSet.Copy()

	//ghost不做处理
	if !isMaster {
		return obj, true
	}

	//查找范围坐标
	this.find(obj, area)
	if callback != nil {
		callback(obj)
	}

	//差集计算(属于MoveSet，不属于MoveOnlySet)
	obj.AoiInfo.EnterSet = set.Difference(obj.AoiInfo.MoveSet, tempMoveSet)
	//属于MoveSet，不属于EnterSet
	obj.AoiInfo.MoveOnlySet = set.Difference(obj.AoiInfo.MoveSet, obj.AoiInfo.EnterSet)

	obj.AoiInfo.LeaveSet = set.Difference(tempMoveSet, obj.AoiInfo.MoveOnlySet)

	/*
		//差集计算(属于MoveSet，不属于MoveOnlySet)
		//obj.AoiInfo.EnterSet = set.Difference(obj.AoiInfo.MoveSet, obj.AoiInfo.MoveOnlySet)

		//obj.AoiInfo.LeaveSet = set.Difference(obj.AoiInfo.MoveOnlySet, obj.AoiInfo.MoveSet)

		//属于MoveSet，不属于EnterSet
		obj.AoiInfo.MoveOnlySet = set.Difference(obj.AoiInfo.MoveSet, obj.AoiInfo.EnterSet)
	*/

	//把自己加入别的玩家的进入列表中，否则别的玩家移动时如果离开你的视野不会发送离开消息
	//可以用主动跟新自己的方式来避免
	for _, data := range obj.AoiInfo.EnterSet.List() {
		otherNode := this.GetNode(data.(uint64))
		if otherNode != nil {
			if otherNode.GetMoveSize() >= FIND_NUM_MAX {
				//obj.AoiInfo.MoveNoNtfSet.Add(otherNode.Id)
				otherNode.AoiInfo.MoveNoNtfSet.Add(obj.Id) //用来标记当前玩家的移动不需要发送给otherNode玩家
			}
			otherNode.AoiInfo.MoveSet.Add(obj.Id)
		}
	}

	return obj, true
}

//更新节点
func (this *Aoi) UpdateNew(id uint64, callback func(*AoiObject), area AoiVector2, x, y float32, isMaster bool) (*AoiObject, bool) {
	if data, ok := this.nodes[id]; ok {
		profileCount++
		//nowTime := time.Now()
		obj, ret := this.updateWithAreaNew(data, callback, area, x, y, false, isMaster)
		//this.PrintStackList()
		//return this.updateWithArea(data, area,x ,y)
		//profileTime += time.Now().Sub(nowTime)
		if util.GetCurrentTimeNow().Sub(nowTime) > time.Second {
			nowTime = util.GetCurrentTimeNow()
			/*
				oobb := this.nodes[6735728018393727041]
				log.Println("aoiUpdate[1000]:", oobb.Id,profileTime,
					len(oobb.AoiInfo.MoveSet.List()),
					len(oobb.AoiInfo.EnterSet.List()),
					len(oobb.AoiInfo.LeaveSet.List()),
					len(oobb.AoiInfo.MoveOnlySet.List()))
			*/

			profileCount = 0
			profileTime = 0
		}
		return obj, ret
	}
	return nil, false
}

func (this *Aoi) updateWithAreaNew(obj *AoiObject, callback func(*AoiObject), area AoiVector2, x, y float32, forceUpdate bool, isMaster bool) (*AoiObject, bool) {
	//移动到新的位置
	this.move(obj, x, y)

	//减少更新频率，发3次移动包，做一次视野更新
	//obj.updateCount++
	//if obj.updateCount%3 != 0 && !forceUpdate {
	//	return obj, false
	//}
	//obj.updateCount = 0

	//把AOI节点转换到旧的节点里
	tempMoveSet := obj.AoiInfo.MoveSet.Copy()
	//obj.AoiInfo.MoveOnlySet = obj.AoiInfo.MoveSet.Copy()

	//ghost不做处理
	if !isMaster {
		return obj, true
	}

	//查找范围坐标
	this.find(obj, area)
	if callback != nil {
		callback(obj)
	}

	//差集计算(属于MoveSet，不属于MoveOnlySet)
	obj.AoiInfo.EnterSet = set.Difference(obj.AoiInfo.MoveSet, tempMoveSet)
	//属于MoveSet，不属于EnterSet
	obj.AoiInfo.MoveOnlySet = set.Difference(obj.AoiInfo.MoveSet, obj.AoiInfo.EnterSet)

	obj.AoiInfo.LeaveSet = set.Difference(tempMoveSet, obj.AoiInfo.MoveOnlySet)

	/*
		//差集计算(属于MoveSet，不属于MoveOnlySet)
		//obj.AoiInfo.EnterSet = set.Difference(obj.AoiInfo.MoveSet, obj.AoiInfo.MoveOnlySet)

		//obj.AoiInfo.LeaveSet = set.Difference(obj.AoiInfo.MoveOnlySet, obj.AoiInfo.MoveSet)

		//属于MoveSet，不属于EnterSet
		obj.AoiInfo.MoveOnlySet = set.Difference(obj.AoiInfo.MoveSet, obj.AoiInfo.EnterSet)
	*/

	//把自己加入别的玩家的进入列表中，否则别的玩家移动时如果离开你的视野不会发送离开消息
	//可以用主动跟新自己的方式来避免
	//for _, data := range obj.AoiInfo.EnterSet.List() {
	//	otherNode := this.GetNode(data.(uint64))
	//	if otherNode != nil {
	//		if otherNode.GetMoveSize() >= FIND_NUM_MAX {
	//			//obj.AoiInfo.MoveNoNtfSet.Add(otherNode.Id)
	//			otherNode.AoiInfo.MoveNoNtfSet.Add(obj.Id) //用来标记当前玩家的移动不需要发送给otherNode玩家
	//		}
	//		otherNode.AoiInfo.MoveSet.Add(obj.Id)
	//	}
	//}

	return obj, true
}

func (this *Aoi) move(obj *AoiObject, x, y float32) {
	//移动x
	this.moveX(obj, x)

	//移动y
	//this.moveY(obj, y)

	obj.SetPosition(x, y)
}

func (this *Aoi) moveX(obj *AoiObject, x float32) {
	if math.Abs(float64(obj.Pos.X-x)) <= 0 {
		return
	}

	this.xNodeList.RemoveNode(obj)
	obj.Pos.X = x
	this.xNodeList.Insert(obj)
}

func (this *Aoi) moveY(obj *AoiObject, y float32) {
	if math.Abs(float64(obj.Pos.Y-y)) <= 0 {
		return
	}

	this.yNodeList.RemoveNode(obj)
	obj.Pos.Y = y
	this.yNodeList.Insert(obj)
}

func (this *Aoi) find(obj *AoiObject, area AoiVector2) *AoiObject {
	obj.AoiInfo.MoveSet.Clear()

	//查找X轴时会考虑Y轴的数值，所有这边只需要找X轴即可
	this.findX(obj, area)

	//this.findY(obj, area)

	//当前节点列表(节点上所在的玩家列表)
	if len(obj.node.ValueList) > 1 {
		for id, _ := range obj.node.ValueList {
			if id == obj.Id {
				continue
			}
			if !obj.AoiInfo.MoveSet.Has(id) {
				obj.AoiInfo.MoveSet.Add(id)
			}
		}
	}

	return obj
}

type aoiDistance struct {
	objUid uint64
	dis    float32
}

func (this *Aoi) findX(obj *AoiObject, area AoiVector2) {
	bNextOut := false
	bPreOut := false
	findNum := FIND_NUM_MAX

	//查找过程中扫描个数上限
	//processLimitNum := findNum
	processLimitNumPre := findNum
	processLimitNumNext := findNum

	var rangeDisList []*aoiDistance
	//向后查找
	curNext := obj.node.Forward[0]
	//向前查找
	curPre := obj.node.Pre
	for {
		if !bNextOut {
			if curNext == nil || curNext.Value == nil {
				bNextOut = true
				continue
			}
			if this.getDeltaValue(obj.Pos.X, curNext.Value.Pos.X) > area.X {
				bNextOut = true
				continue
			} else {
				if len(curNext.ValueList) > 1 {
					for id, tmpObj := range curNext.ValueList {
						//todo...后续添加做好友处理
						tmpDis := this.distance(obj.Pos, tmpObj.Pos)
						rangeDisList = append(rangeDisList, &aoiDistance{objUid: id, dis: tmpDis})
						processLimitNumNext--
						if processLimitNumNext <= 0 {
							break
						}
						//obj.AoiInfo.MoveSet.Add(id)
						//findNum--
						//if findNum <= 0 {
						//	break
						//}
					}
				} else {
					dis := this.distance(obj.Pos, curNext.Value.Pos)
					if dis <= area.X {
						rangeDisList = append(rangeDisList, &aoiDistance{objUid: curNext.Value.Id, dis: dis})
						processLimitNumNext--
						//obj.AoiInfo.MoveSet.Add(curNext.Value.Id)
						//findNum--
					}
				}
			}
			curNext = curNext.Forward[0]
			if processLimitNumNext <= 0 {
				break
			}
		}

		if !bPreOut {
			//id==0为header节点
			if curPre == nil || curPre.Value == nil || curPre.Value.Id <= 0 {
				bPreOut = true
				continue
			}
			if this.getDeltaValue(obj.Pos.X, curPre.Value.Pos.X) > area.X {
				bPreOut = true
				continue
			} else {
				if len(curPre.ValueList) > 1 {
					for id, tmpObj := range curPre.ValueList {
						tmpDis := this.distance(obj.Pos, tmpObj.Pos)
						rangeDisList = append(rangeDisList, &aoiDistance{objUid: id, dis: tmpDis})
						processLimitNumPre--
						if processLimitNumPre <= 0 {
							break
						}
						//obj.AoiInfo.MoveSet.Add(id)
						//findNum--
						//if findNum <= 0 {
						//	break
						//}
					}
				} else {
					dis := this.distance(obj.Pos, curPre.Value.Pos)
					if dis <= area.X {
						rangeDisList = append(rangeDisList, &aoiDistance{objUid: curPre.Value.Id, dis: dis})
						processLimitNumPre--
						//obj.AoiInfo.MoveSet.Add(curPre.Value.Id)
						//findNum--
					}
				}
			}
			curPre = curPre.Pre
			if processLimitNumPre <= 0 {
				break
			}
		}

		if bNextOut && bPreOut {
			break
		}
	}

	if len(rangeDisList) > 0 {
		sort.Slice(rangeDisList, func(i, j int) bool {
			if math.Abs(float64(rangeDisList[i].dis-rangeDisList[j].dis)) < 0.0001 {
				return rangeDisList[i].objUid < rangeDisList[j].objUid
			} else {
				return rangeDisList[i].dis < rangeDisList[j].dis
			}
		})

		tmpLen := len(rangeDisList)
		if tmpLen > findNum {
			tmpLen = findNum
		}
		for idx := 0; idx < tmpLen; idx++ {
			obj.AoiInfo.MoveSet.Add(rangeDisList[idx].objUid)
		}
	}

	//test
	//this.PrintStackList()
}

func (this *Aoi) findY(obj *AoiObject, area AoiVector2) {
	//向后查找
	curNext := obj.node.Forward[0]
	for {
		if curNext == nil || curNext.Value == nil {
			break
		}
		if this.getDeltaValue(obj.Pos.Y, curNext.Value.Pos.Y) > area.Y {
			break
		} else if this.getDeltaValue(obj.Pos.X, curNext.Value.Pos.X) <= area.X {
			if this.distance(obj.Pos, curNext.Value.Pos) <= area.Y {
				for id, _ := range curNext.ValueList {
					obj.AoiInfo.MoveSet.Add(id)
				}
			}
		}
		curNext = curNext.Forward[0]
	}
	//向前查找
	curPre := obj.node.Pre
	for {
		if curPre == nil || curPre.Value == nil || curPre.Value.Id <= 0 {
			break
		}
		if this.getDeltaValue(obj.Pos.Y, curPre.Value.Pos.Y) > area.Y {
			break
		} else if this.getDeltaValue(obj.Pos.X, curPre.Value.Pos.X) <= area.X {
			if this.distance(obj.Pos, curPre.Value.Pos) <= area.Y {
				for id, _ := range curPre.ValueList {
					obj.AoiInfo.MoveSet.Add(id)
				}
			}
		}
		curPre = curPre.Pre
	}
}

func (this *Aoi) LeaveNode(uid uint64) []interface{} {
	node := this.GetNode(uid)
	if node == nil {
		return nil
	}

	this.xNodeList.RemoveNode(node)
	//this.yNodeList.RemoveNode(node)
	delete(this.nodes, uid)

	for _, data := range node.AoiInfo.MoveSet.List() {
		if otherNode := this.GetNode(data.(uint64)); otherNode != nil {
			otherNode.AoiInfo.LeaveSet.Add(uid)
		}
	}

	return node.AoiInfo.MoveSet.List()
}

func (this *Aoi) distance(a, b *AoiVector2) float32 {
	deltaX := a.X - b.X
	deltaY := a.Y - b.Y
	//使用近似距离
	//return float32(math.Abs(float64(deltaX)) + math.Abs(float64(deltaY)))
	return float32(math.Sqrt(float64(deltaX*deltaX + deltaY*deltaY)))
}

func (this *Aoi) getDeltaValue(f1, f2 float32) float32 {
	deltaValue := f1 - f2
	if deltaValue <= 0 {
		return -deltaValue
	}
	return deltaValue
}