AI - FlowField(流场寻路)

FlowField流场寻路，利用网格存储每个点对目标点的推力，网格上的单位根据对于推力进行移动。用于大量单位进行寻路对于同一目的地的寻路，常用于rts游戏等。

对应一张网格地图(图中黑块是不可行走区域)
在这里插入图片描述

生成热度图

计算所有网格对于目标点(图中红点)网格的路径距离。(每个格子的移动距离算作1)。
通过dijkstra算法遍历出每个格子的路径距离.(a *算法启发函数结果为0就是dijkstra算法。之前NavMesh寻路有说明过a *算法)

void FlowFieldScene::createHeadMap() {
    unordered_map<int, float> openList;
    unordered_map<int, float> closeList;
    _distNode->removeAllChildren();

    _dist.clear();
    //FlowFieldMathHelper::mapHeight 地图高度，即地图在y轴上的格子数
    for (int i = 0; i <= FlowFieldMathHelper::mapHeight; i++) {
        vector<float> d;
        d.resize(FlowFieldMathHelper::mapWidth + 1, 0);
        _dist.push_back(d);
    }

	//转换实际位置到网格坐标的位置
    Vec2 gridPos = FlowFieldMathHelper::getGridPos(_touchBeganPosition);
    //每个网格都有个唯一id
    int gridId = FlowFieldMathHelper::getGridIdByGridPos(gridPos.x, gridPos.y);
    openList.emplace(gridId, 0);
    while (!openList.empty()) {
        pair<int, float> node = *openList.begin();
        for (auto n : openList) {
            if (node.second > n.second) node = n;
        }
        openList.erase(node.first);
        closeList.insert(node);
        Vec2 gridPos = FlowFieldMathHelper::getGridPosById(node.first);
        _dist[gridPos.y][gridPos.x] = node.second;
        //FlowFieldMathHelper::getNeighbor获取周边的格子，计算热度图四向就够
        auto neighbors = FlowFieldMathHelper::getNeighbor(node.first);
        for (auto neighbor : neighbors) {
        //isBlock 判断是否是阻挡格
            if (isBlock(neighbor.first)) continue;
            if (closeList.find(neighbor.first) != closeList.end()) continue;
            if (openList.find(neighbor.first) == openList.end()) {
                openList.emplace(neighbor.first, neighbor.second + node.second);
            }
            else {
                if (openList[neighbor.first] > neighbor.second + node.second) {
                    openList[neighbor.first] = neighbor.second + node.second;
                }
            }
        }
    }
}

在这里插入图片描述

生成向量图

生成热度图之后，遍历每个网格，查找他所有相邻的网格(8向)，选择到目标点路径距离最小的网格(阻挡网格的路径距离无穷大)，把当前网格的向量指向对应网格，最终生成矢量图
(注意，当周围有阻挡网格时，要判断不能斜向穿过阻挡格)
在这里插入图片描述
当矢量是左上(-1,1)左下(-1,-1)右上(1,1)右下(1,-1),判断目标格子周围的阻挡格

//静止倾斜穿过障碍物
bool FlowFieldScene::checkObliqueAngleBlock(int gridX, int gridY, int offsetX, int offsetY) {
    if (offsetX * offsetY == 0) return false;
    if (isBlock(gridX + offsetX, gridY) || isBlock(gridX, gridY + offsetY)) return true;
    return false;
}

生成向量图

void FlowFieldScene::createVectorMap() {
    _vectorNode->clear();
    _vectorMap.clear();
    for (int y = 0; y <= FlowFieldMathHelper::mapHeight; y++) {
        for (int x = 0; x <= FlowFieldMathHelper::mapWidth; x++) {
            if (_dist[y][x] == 0) continue;
            Vec2 direct;
            float neighborDist = -1;
            for (int offsetX = -1; offsetX <= 1; offsetX++) {
                for (int offsetY = -1; offsetY <= 1; offsetY++) {
                    int toX = x + offsetX;
                    int toY = y + offsetY;
                    if (isBlock(toX, toY)) continue;
                    else if (x == toX && y == toY) continue;
                    else if (toX < 0 || toX > FlowFieldMathHelper::mapWidth) continue;
                    else if (toY < 0 || toY > FlowFieldMathHelper::mapHeight) continue;
                    if ( neighborDist == -1 || neighborDist > _dist[toY][toX] ) {
                        if (checkObliqueAngleBlock(x, y, offsetX, offsetY)) continue;
                        neighborDist = _dist[toY][toX];
                        direct = Vec2(offsetX, offsetY);
                    }
                }
            }
            _vectorMap.emplace(FlowFieldMathHelper::getGridIdByGridPos(x, y), direct);
        }
    }
}

设置转向力

根据设置的流场向量获得转向力

//_flowFieldDirect为设置的当前格子流场转向力方向
Vec2 MoveNode::flowField() {
    if (_flowFieldDirect == Vec2::ZERO) return Vec2::ZERO;
    Vec2 desiredVelocity = _flowFieldDirect * _dtSpeed;

    Vec2 steering;
    if (MoveSmooth) steering = desiredVelocity - _velocity;
    else steering = desiredVelocity;
    return steering;
}

加入之前的steering系统，转向系统，集群模拟

void MoveNode::update(float dt)
{
    findNeighbourObjs();
    _dtSpeed = _speed * dt;
     Vec2 steering = Vec2::ZERO;
     steering += seek(_tarPos);
     steering += flee();
     steering += wander();
     steering += pursuit();
     steering += cohesion();
     steering += separation();
     steering += alignment();
     steering += flowField();
     steering = turncate(steering, _maxForce);
     steering *= ( 1 / (float)_mass );
     _velocity += steering;

    _velocity += wallAvoid();

    _velocity = turncate(_velocity, _maxSpeed * dt);
    updatePos();
}

此时如果直接取当前所在网格的向量作流场力的方向，会出现两个问题

void FlowFieldScene::update(float dt) {
    for (auto node : _moveNodes) {
        int gridId = FlowFieldMathHelper::getGridId(node->getPosition());
        Vec2 direct = _vectorMap[gridId];
        node->setFlowFieldDirect(direct);
    }
}

1.如果转向力所占的权重不够大，会导致物体转向不及时，并且可能插入阻挡格的情况
请添加图片描述

2.如果增大转向力所占权重，又容易导致物体直接贴着网格边缘行走，而非沿着中线行走
请添加图片描述

为了改善这种情况，通常会根据所处当前格的不同位置，选取不同方向的三个相邻网格，加上自身网格的4个向量进行线插值
在这里插入图片描述
进行双线性插值

双线性插值

在这里插入图片描述
获取4个向量后，先把网格y值相同的向量，进行两两线性插值，再把求出的两个新向量进行线性插值即可

注意，双线性插值的话，如果目标点再阻挡格旁边，而阻挡格又没有向量(取0)的话，目标会直接穿过阻挡格
请添加图片描述

因此如果获取的网格是阻挡格，则直接取阻挡网格指向当前格的方向做插值。
这个是只有流场力的单独优化，实际项目中，不同力的权重可能不同，真正避免与阻挡物碰撞。还是要加上专门的碰撞避免处理(如阻挡物周围加力场，ORCA等)
在这里插入图片描述
在这里插入图片描述

Vec2 FlowFieldScene::bilinearInterpolation(Vec2 curPosition) {
    Vec2 gridPos = FlowFieldMathHelper::getGridPos(curPosition);
    int offsetX, offsetY;
    if (curPosition.x < gridPos.x * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen / 2) offsetX = -1;
    else if (curPosition.x == gridPos.x * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen / 2) offsetX = 0;
    else offsetX = 1;
    if (curPosition.y < gridPos.y * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen / 2) offsetY = -1;
    else if (curPosition.y == gridPos.y * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen / 2) offsetY = 0;
    else offsetY = 1;


    Vec2 v1, v2, v3, v4;
    v1 = getVectorByGridPos(gridPos);
    bool noX = gridPos.x == FlowFieldMathHelper::mapWidth || isBlock(gridPos.x + offsetX, gridPos.y);
    //if (noX) v2 = getVectorByGridPos(gridPos);
    if (noX) v2 = Vec2(-offsetX, 0);
    else v2 = getVectorByGridPos(gridPos + Vec2(offsetX, 0));
    bool noY = gridPos.y == FlowFieldMathHelper::mapHeight || isBlock(gridPos.x, gridPos.y + offsetY);
    //if (noY) v3 = getVectorByGridPos(gridPos);
    if (noY) v3 = Vec2(0, -offsetY);
    else v3 = getVectorByGridPos(gridPos + Vec2(0, offsetY));
    //if (noX || noY) v4 = getVectorByGridPos(gridPos);
    if (noX || noY) Vec2(-offsetX, -offsetY);
    else v4 = getVectorByGridPos(gridPos + Vec2(offsetX, offsetY));;
    float xWeight = abs(curPosition.x - gridPos.x * FlowFieldMathHelper::gridLen - FlowFieldMathHelper::gridLen / 2) / FlowFieldMathHelper::gridLen;
    v1 = v1.lerp(v2, xWeight);
    v3 = v3.lerp(v4, xWeight);

    float yWeight = abs(curPosition.y - gridPos.y * FlowFieldMathHelper::gridLen - FlowFieldMathHelper::gridLen / 2) / FlowFieldMathHelper::gridLen;

    Vec2 direct = v1.lerp(v3, yWeight);
    direct.normalize();
    return direct;
}

void FlowFieldScene::update(float dt) {
    for (auto node : _moveNodes) {
        int gridId = FlowFieldMathHelper::getGridId(node->getPosition());
            Vec2 direct = bilinearInterpolation(node->getPosition());
//            Vec2 direct = _vectorMap[gridId];
            node->setFlowFieldDirect(direct);
    }
}

通过双线性插值的方式，物体的行动轨迹会更加靠近与正中路线。
请添加图片描述

流场力和一些其他力结合的效果

请添加图片描述

源码

FlowField.h

#ifndef __FLOW_FIELD_SCENE_H__
#define __FLOW_FIELD_SCENE_H__

#include "cocos2d.h"
#include "CrowdSimulation/MoveNodeManager.h"
USING_NS_CC;
using namespace std;

class FlowFieldScene : public Scene
{
public:
	static Scene* createScene();

    virtual bool init();

    virtual bool onTouchBegan(Touch* touch, Event* unused_event);


    // implement the "static create()" method manually
    CREATE_FUNC(FlowFieldScene);

    void createHeadMap();
    void showHeatInfo();
    void createVectorMap();
    bool checkObliqueAngleBlock(int gridX, int gridY, int offsetX, int offsetY);
    bool isBlock(int gridX, int gridY);
    bool isBlock(int gridId);

    void resetMoveNode();

    Vec2 getVectorByGridPos(Vec2 gridPos);

    Vec2 bilinearInterpolation(Vec2 curPosition);

    void update(float dt);

protected:
    EventListenerTouchOneByOne* _touchListener;
    Vec2 _touchBeganPosition;
    DrawNode* _mapDrawNode;
    Node* _distNode;
    DrawNode* _vectorNode;

    DrawNode* _tarDot;

    unordered_map<int, bool> _blockGridIdMap;

    vector<vector<float>> _dist;
    unordered_map<int, Vec2> _vectorMap;
    MoveNodeManager* _manager;
    vector<MoveNode*> _moveNodes;
};

#endif

FlowField.cpp

#include "FlowFieldScene.h"
#include "FlowFieldMathHelper.h"

Scene* FlowFieldScene::createScene()
{
    return FlowFieldScene::create();
}

vector<pair<Vec2, Vec2>> blockLine = {
    make_pair(Vec2(200,400), Vec2(200,300)),
    make_pair(Vec2(220,400), Vec2(220,300)),
    make_pair(Vec2(240,400), Vec2(240,300)),
    make_pair(Vec2(260,550), Vec2(260,250)),
    make_pair(Vec2(280,350), Vec2(600,350)),
    make_pair(Vec2(700, 280), Vec2(1100, 280)),
    make_pair(Vec2(750, 330), Vec2(1150, 330)),
    make_pair(Vec2(115, 115), Vec2(115, 150)),
    make_pair(Vec2(115, 115), Vec2(215, 115)),
    make_pair(Vec2(270, 87), Vec2(666, 87)),
    make_pair(Vec2(777, 575), Vec2(1233, 575)),
    make_pair(Vec2(500, 400), Vec2(500, 466)),
    make_pair(Vec2(370, 222), Vec2(577, 222)),
    make_pair(Vec2(888, 124), Vec2(1277, 124)),
};

static void problemLoading(const char* filename)
{
    printf("Error while loading: %s\n", filename);
    printf("Depending on how you compiled you might have to add 'Resources/' in front of filenames in FlowFieldScene.cpp\n");
}

// on "init" you need to initialize your instance
bool FlowFieldScene::init()
{
    //
    // 1. super init first
    if (!Scene::init())
    {
        return false;
    }
    auto visibleSize = Director::getInstance()->getVisibleSize();
    Vec2 origin = Director::getInstance()->getVisibleOrigin();

    auto layer = LayerColor::create(Color4B(255, 255, 255, 255));
    layer:setContentSize(visibleSize);
    this->addChild(layer);

    auto node = DrawNode::create();
    this->addChild(node);
//    for (int i = FlowFieldMathHelper::gridLen; i < visibleSize.width; i += FlowFieldMathHelper::gridLen) {
//        node->drawSegment(Vec2(i, 0), Vec2(i, 640), 1, Color4F(0, 0, 0, 0.3));
//    }
//    for (int i = FlowFieldMathHelper::gridLen; i < visibleSize.height; i += FlowFieldMathHelper::gridLen) {
//        node->drawSegment(Vec2(0, i), Vec2(1400, i), 1, Color4F(0, 0, 0, 0.3));
//    }
    for (auto line : blockLine) {
        if (line.first.x == line.second.x) {
            auto minY = min(line.first.y, line.second.y);
            auto maxY = max(line.first.y, line.second.y);
            int gridMinY = minY / FlowFieldMathHelper::gridLen;
            int gridMaxY = maxY / FlowFieldMathHelper::gridLen + 1;
            int gridX = line.first.x / FlowFieldMathHelper::gridLen;
            for (auto y = gridMinY; y <= gridMaxY; y ++) {
                int id = FlowFieldMathHelper::getGridIdByGridPos(gridX, y);
                _blockGridIdMap.emplace(id, true);
            }
            Vec2 v1 = Vec2(gridX, gridMinY);
            Vec2 v2 = Vec2(gridX, gridMaxY);
            vector<Vec2> v = {
                Vec2(v1.x * FlowFieldMathHelper::gridLen, v1.y * FlowFieldMathHelper::gridLen),
                Vec2(v1.x * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen, v1.y * FlowFieldMathHelper::gridLen),
                Vec2(v1.x * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen, v2.y * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen),
                Vec2(v1.x * FlowFieldMathHelper::gridLen, v2.y * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen),
            };
            node->drawPolygon(reinterpret_cast<Vec2*>(v.data()), v.size(), Color4F(0, 0, 0, 1), 0, Color4F(0, 0, 0, 0));
        }
        else if (line.first.y == line.second.y) {
            auto minX = min(line.first.x, line.second.x);
            auto maxX = max(line.first.x, line.second.x);
            int gridMinX = minX / FlowFieldMathHelper::gridLen;
            int gridMaxX = maxX / FlowFieldMathHelper::gridLen + 1;
            int gridY = line.first.y / FlowFieldMathHelper::gridLen;
            for (auto x = gridMinX; x <= gridMaxX; x++) {
                int id = FlowFieldMathHelper::getGridIdByGridPos(x, gridY);
                _blockGridIdMap.emplace(id, true);
            }
            Vec2 v1 = Vec2(gridMinX, gridY);
            Vec2 v2 = Vec2(gridMaxX, gridY);
            vector<Vec2> v = {
                Vec2(v1.x * FlowFieldMathHelper::gridLen, v1.y * FlowFieldMathHelper::gridLen),
                Vec2(v2.x * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen, v1.y * FlowFieldMathHelper::gridLen),
                Vec2(v2.x * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen, v1.y * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen),
                Vec2(v1.x * FlowFieldMathHelper::gridLen, v1.y * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen),
            };
            node->drawPolygon(reinterpret_cast<Vec2*>(v.data()), v.size(), Color4F(0, 0, 0, 1), 0, Color4F(0, 0, 0, 0));
        }
    }

    _mapDrawNode = DrawNode::create();
    this->addChild(_mapDrawNode);

    _distNode = Node::create();
    this->addChild(_distNode);
    _vectorNode = DrawNode::create();
    this->addChild(_vectorNode);

    _tarDot = DrawNode::create();
    this->addChild(_tarDot);
    _tarDot->drawDot(Vec2::ZERO, 5, Color4F(1, 0, 0, 1));
    _tarDot->setPosition(Vec2(777, 444));

    _touchListener = EventListenerTouchOneByOne::create();
    _touchListener->setSwallowTouches(true);
    _touchListener->onTouchBegan = CC_CALLBACK_2(FlowFieldScene::onTouchBegan, this);
    this->getEventDispatcher()->addEventListenerWithSceneGraphPriority(_touchListener, layer);

    _manager = new MoveNodeManager();
    this->scheduleUpdate();
    return true;
}

bool FlowFieldScene::onTouchBegan(Touch* touch, Event* event)
{
    _touchBeganPosition = touch->getLocation();
    CCLOG("==========》 %f， %f", _touchBeganPosition.x, _touchBeganPosition.y);
    if (FlowFieldMathHelper::getGridId(_touchBeganPosition) == -1) {
        resetMoveNode();
        return true; 
    }

    _tarDot->setPosition(_touchBeganPosition);
    createHeadMap();
    createVectorMap();
//    resetMoveNode();
    return true;
}

void FlowFieldScene::update(float dt) {
    for (auto node : _moveNodes) {
        int gridId = FlowFieldMathHelper::getGridId(node->getPosition());
            Vec2 direct = bilinearInterpolation(node->getPosition());
//            Vec2 direct = _vectorMap[gridId];
            node->setFlowFieldDirect(direct);
    }
}

Vec2 FlowFieldScene::getVectorByGridPos(Vec2 gridPos) {
    return _vectorMap[FlowFieldMathHelper::getGridIdByGridPos(gridPos.x, gridPos.y)];
}

Vec2 FlowFieldScene::bilinearInterpolation(Vec2 curPosition) {
    Vec2 gridPos = FlowFieldMathHelper::getGridPos(curPosition);
    int offsetX, offsetY;
    if (curPosition.x < gridPos.x * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen / 2) offsetX = -1;
    else if (curPosition.x == gridPos.x * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen / 2) offsetX = 0;
    else offsetX = 1;
    if (curPosition.y < gridPos.y * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen / 2) offsetY = -1;
    else if (curPosition.y == gridPos.y * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen / 2) offsetY = 0;
    else offsetY = 1;


    Vec2 v1, v2, v3, v4;
    v1 = getVectorByGridPos(gridPos);
    bool noX = gridPos.x == FlowFieldMathHelper::mapWidth || isBlock(gridPos.x + offsetX, gridPos.y);
    //if (noX) v2 = getVectorByGridPos(gridPos);
    if (noX) v2 = Vec2(-offsetX, 0);
    else v2 = getVectorByGridPos(gridPos + Vec2(offsetX, 0));
    bool noY = gridPos.y == FlowFieldMathHelper::mapHeight || isBlock(gridPos.x, gridPos.y + offsetY);
    //if (noY) v3 = getVectorByGridPos(gridPos);
    if (noY) v3 = Vec2(0, -offsetY);
    else v3 = getVectorByGridPos(gridPos + Vec2(0, offsetY));
    //if (noX || noY) v4 = getVectorByGridPos(gridPos);
    if (noX || noY) Vec2(-offsetX, -offsetY);
    else v4 = getVectorByGridPos(gridPos + Vec2(offsetX, offsetY));;
    float xWeight = abs(curPosition.x - gridPos.x * FlowFieldMathHelper::gridLen - FlowFieldMathHelper::gridLen / 2) / FlowFieldMathHelper::gridLen;
    v1 = v1.lerp(v2, xWeight);
    v3 = v3.lerp(v4, xWeight);

    float yWeight = abs(curPosition.y - gridPos.y * FlowFieldMathHelper::gridLen - FlowFieldMathHelper::gridLen / 2) / FlowFieldMathHelper::gridLen;

    Vec2 direct = v1.lerp(v3, yWeight);
    direct.normalize();
    return direct;
}

void FlowFieldScene::createHeadMap() {
    unordered_map<int, float> openList;
    unordered_map<int, float> closeList;
    _distNode->removeAllChildren();

    _dist.clear();
    for (int i = 0; i <= FlowFieldMathHelper::mapHeight; i++) {
        vector<float> d;
        d.resize(FlowFieldMathHelper::mapWidth + 1, 0);
        _dist.push_back(d);
    }

    Vec2 gridPos = FlowFieldMathHelper::getGridPos(_touchBeganPosition);
    int gridId = FlowFieldMathHelper::getGridIdByGridPos(gridPos.x, gridPos.y);
    openList.emplace(gridId, 0);
    while (!openList.empty()) {
        pair<int, float> node = *openList.begin();
        for (auto n : openList) {
            if (node.second > n.second) node = n;
        }
        openList.erase(node.first);
        closeList.insert(node);
        Vec2 gridPos = FlowFieldMathHelper::getGridPosById(node.first);
        _dist[gridPos.y][gridPos.x] = node.second;
        auto neighbors = FlowFieldMathHelper::getNeighbor(node.first);
        for (auto neighbor : neighbors) {
            if (isBlock(neighbor.first)) continue;
            if (closeList.find(neighbor.first) != closeList.end()) continue;
            if (openList.find(neighbor.first) == openList.end()) {
                openList.emplace(neighbor.first, neighbor.second + node.second);
            }
            else {
                if (openList[neighbor.first] > neighbor.second + node.second) {
                    openList[neighbor.first] = neighbor.second + node.second;
                }
            }
        }
    }
//    showHeatInfo();
}

void FlowFieldScene::showHeatInfo() {
    _distNode->removeAllChildren();
    for (int y = 0; y <= FlowFieldMathHelper::mapHeight; y++) {
        for (int x = 0; x <= FlowFieldMathHelper::mapWidth; x++) {
            if (!isBlock(x, y)) {
                auto num = Label::create();
                num->setColor(Color3B(0, 255, 0));
                //num->setSystemFontSize(20);
                num->setSystemFontSize(20);
                _distNode->addChild(num);
                auto s = to_string(_dist[y][x]);
                //num->setString(s.substr(0, s.find(".") + 2));
                num->setString(s.substr(0, s.find(".")));
                num->setPosition(Vec2(x * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen / 2, y * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen / 2));
            }
        }
    }
}

bool FlowFieldScene::isBlock(int gridX, int gridY) {
    return isBlock(FlowFieldMathHelper::getGridIdByGridPos(gridX, gridY));
}
bool FlowFieldScene::isBlock(int gridId) {
    return _blockGridIdMap.find(gridId) != _blockGridIdMap.end();
}

//静止倾斜穿过障碍物
bool FlowFieldScene::checkObliqueAngleBlock(int gridX, int gridY, int offsetX, int offsetY) {
    if (offsetX * offsetY == 0) return false;
    if (isBlock(gridX + offsetX, gridY) || isBlock(gridX, gridY + offsetY)) return true;
    return false;
}

void FlowFieldScene::createVectorMap() {
    _vectorNode->clear();
    _vectorMap.clear();
    for (int y = 0; y <= FlowFieldMathHelper::mapHeight; y++) {
        for (int x = 0; x <= FlowFieldMathHelper::mapWidth; x++) {
            if (_dist[y][x] == 0) continue;
            Vec2 direct;
            float neighborDist = -1;
            for (int offsetX = -1; offsetX <= 1; offsetX++) {
                for (int offsetY = -1; offsetY <= 1; offsetY++) {
                    int toX = x + offsetX;
                    int toY = y + offsetY;
                    if (isBlock(toX, toY)) continue;
                    else if (x == toX && y == toY) continue;
                    else if (toX < 0 || toX > FlowFieldMathHelper::mapWidth) continue;
                    else if (toY < 0 || toY > FlowFieldMathHelper::mapHeight) continue;
                    if ( neighborDist == -1 || neighborDist > _dist[toY][toX] ) {
                        if (checkObliqueAngleBlock(x, y, offsetX, offsetY)) continue;
                        neighborDist = _dist[toY][toX];
                        direct = Vec2(offsetX, offsetY);
                    }
                }
            }
//            Vec2 v1 = Vec2(x * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen / 2, y * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen / 2);
//            Vec2 v2 = v1 + (direct * FlowFieldMathHelper::gridLen / 2);
//            _vectorNode->drawSegment(v1, v2, 1, Color4F(0, 0, 1, 1));
            _vectorMap.emplace(FlowFieldMathHelper::getGridIdByGridPos(x, y), direct);
        }
    }
}

void FlowFieldScene::resetMoveNode() {
    if (_moveNodes.empty()) {
        for (int i = 0; i < 100; i++) {
            auto moveNode = _manager->getFlowFieldNode();
            this->addChild(moveNode);
            _moveNodes.push_back(moveNode);
        }
    }
    float width = FlowFieldMathHelper::mapWidth * FlowFieldMathHelper::gridLen;
    float height = FlowFieldMathHelper::mapHeight * FlowFieldMathHelper::gridLen;
    for (auto node : _moveNodes) {
        Vec2 v;
        do {
            v.x = RandomHelper::random_real<float>(10, width-10);
            v.y = RandomHelper::random_real<float>(10, height-10);
        } while (isBlock(FlowFieldMathHelper::getGridId(v)));
        node->setPos(v);
        //Vec2 vg = FlowFieldMathHelper::getGridPos(v);
        //node->setPos(Vec2(vg.x * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen / 2, vg.y * FlowFieldMathHelper::gridLen + FlowFieldMathHelper::gridLen / 2));
    }
}

FlowFieldMathHelper.h

#pragma once
#ifndef __FLOWFIELD_MATH_H__
#define __FLOWFIELD_MATH_H__

#include "cocos2d.h"
USING_NS_CC;
using namespace std;

class FlowFieldMathHelper
{
public:
	static Vec2 getGridPos(Vec2 pos);
	static int getGridId(Vec2 pos);
	static int getGridIdByGridPos(int gridX, int gridY);
	static vector<pair<int, float>> getNeighbor(int gridId);
	static Vec2 getGridPosById(int gridId);

	static const int gridLen = 24;
	static const int mapWidth = 1400 / gridLen - 1;
	static const int mapHeight = 640 / gridLen - 1;

};

#endif

FlowFieldMathHelper.cpp

#include "FlowFieldMathHelper.h"

Vec2 FlowFieldMathHelper::getGridPos(Vec2 pos) {
	return Vec2(int(pos.x / gridLen), int(pos.y / gridLen));
}

int FlowFieldMathHelper::getGridId(Vec2 pos) {
	Vec2 v = getGridPos(pos);
	return getGridIdByGridPos(v.x, v.y);
}

int FlowFieldMathHelper::getGridIdByGridPos(int gridX, int gridY) {
	if (gridX < 0 || gridX > mapWidth) return -1;
	if (gridY < 0 || gridY > mapHeight) return -1;
	return gridX + gridY * (mapWidth + 1);
}

Vec2 FlowFieldMathHelper::getGridPosById(int gridId) {
	int x = gridId % (mapWidth + 1);
	int y = (gridId - x) / (mapWidth + 1);
	return Vec2(x, y);
}

vector<pair<int, float>> FlowFieldMathHelper::getNeighbor(int gridId) {
	Vec2 pos = getGridPosById(gridId);
	vector<pair<int, float>> ret;
	/*for (int offsetX = -1; offsetX <= 1; offsetX++) {
		for (int offsetY = -1; offsetY <= 1; offsetY++) {
			int x = pos.x + offsetX;
			int y = pos.y + offsetY;
			if (x == pos.x && y == pos.y) continue;
			else if (x < 0 || x > mapWidth) continue;
			else if (y < 0 || y > mapHeight) continue;
			else if (x == pos.x || y == pos.y) ret.push_back(make_pair(getGridIdByGridPos(x, y), 1));
			else ret.push_back(make_pair(getGridIdByGridPos(x, y), 1.5));
		}
	}*/
	for (int offsetX = -1; offsetX <= 1; offsetX++) {
		for (int offsetY = -1; offsetY <= 1; offsetY++) {
			int x = pos.x + offsetX;
			int y = pos.y + offsetY;
			if (x == pos.x && y == pos.y) continue;
			else if (x < 0 || x > mapWidth) continue;
			else if (y < 0 || y > mapHeight) continue;
			else if (x == pos.x || y == pos.y) ret.push_back(make_pair(getGridIdByGridPos(x, y), 1));
		}
	}
	return ret;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/202186.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Flutter】graphic图表实现tooltip一段时间后自动隐藏

【Flutter】graphic图表实现tooltip一段时间后自动隐藏

概述 graphic图表中提供了自定义tooltip的事件&#xff0c;可通过selections中on和clear配置手势选项和可识别设备&#xff0c;默认情况下tooltip需要双击隐藏&#xff0c;但这并不符合我们的需求。通过调研发现&#xff0c;若想实现tooltip隔几秒后隐藏&#xff0c;可通过Str…
阅读更多...
西工大网络空间安全学院计算机系统基础实验一（9, 10, 11, 12, 13）

西工大网络空间安全学院计算机系统基础实验一（9, 10, 11, 12, 13）

还是那句话&#xff0c;专心做好你自己的&#xff0c;老老实实把基础打好&#xff0c;不要被其他人带跑节奏&#xff0c;不要跟他打&#xff0c;跟着这系列博客&#xff0c;稳扎稳打一步一步来。即使你VMware workstation没下载好&#xff0c;即使你Ubuntu虚拟机没配好&#xf…
阅读更多...
【数据挖掘】国科大刘莹老师数据挖掘课程作业 —— 第三次作业

【数据挖掘】国科大刘莹老师数据挖掘课程作业 —— 第三次作业

Written Part 1. 基于表 1 1 1 回答下列问题&#xff08;min_sup40%, min_conf75%&#xff09;&#xff1a; Transaction IDItems Bought0001{a, d, e}0024{a, b, c, e}0012{a, b, d, e}0031{a, c, d, e}0015{b, c, e}0022{b, d, e}0029{c, d}0040{a, b, c}0033{a, d, e}0038…
阅读更多...
【计算机网络笔记】交换机

【计算机网络笔记】交换机

系列文章目录 什么是计算机网络&#xff1f; 什么是网络协议&#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能&#xff08;1&#xff09;——速率、带宽、延迟 计算机网络性能&#xff08;2&#xff09;…
阅读更多...
Vue3依赖注入

Vue3依赖注入

适用场景 尤其针对一个变量需要从顶层组件开始透传&#xff0c;途径很多个子组件最后在第n代子组件使用的时候。对于这些途经的子组件而言&#xff0c;它们不但不使用而且完全不关心该变量具体是什么&#xff0c;只是作为一个传递工具罢了。这种情况下&#xff0c;使用依赖注入…
阅读更多...
asla四大开源组件应用示例（alsa-lib、alsa-utils、alsa-tools、alsa-plugins）

asla四大开源组件应用示例（alsa-lib、alsa-utils、alsa-tools、alsa-plugins）

文章目录 alsa设备文件/dev/snd//sys/class/sound/proc/asoundalsa-lib示例1alsa-utilsalsa-toolsalsa-plugins参考alsa设备文件 /dev/snd/ alsa设备文件目录位于，/dev/snd，如下所示 root@xboard:~#ls /dev/snd -l total 0 drwxr-xr-x 2 root root 60 Nov 6 2023 …
阅读更多...
vuepress-----7、发布在GitHub

vuepress-----7、发布在GitHub

# 7、发布在GitHub 在你的项目中&#xff0c;创建一个如下的 deploy.sh 文件&#xff08;请自行判断去掉高亮行的注释&#xff09;: #!/usr/bin/env sh# 确保脚本抛出遇到的错误 set -e# 生成静态文件 npm run docs:build# 进入生成的文件夹 cd docs/.vuepress/dist# 如果是发…
阅读更多...
PTA_2023年软件设计综合实践_10(回溯法与分治限界法)

PTA_2023年软件设计综合实践_10(回溯法与分治限界法)

7-1 桥本分数 将1-9九个数不重复地赋给不同的9个元素 &#xff0c;实现形如a/bcd/eff/hi 的形式。例&#xff1a;1/265/784/39 1/325/967/84 &#xff08;注意&#xff1a;1/265/784/39 和5/781/264/39 只能算一种解&#xff09;&#xff0c;共有多少种不同的解。 语言选C #…
阅读更多...
36 - 电商系统表设计优化案例分析

36 - 电商系统表设计优化案例分析

如果在业务架构设计初期&#xff0c;表结构没有设计好&#xff0c;那么后期随着业务以及数据量的增多&#xff0c;系统就很容易出现瓶颈。如果表结构扩展性差&#xff0c;业务耦合度将会越来越高&#xff0c;系统的复杂度也将随之增加。这一讲我将以电商系统中的表结构设计为例…
阅读更多...
服务器数据恢复—V7000存储raid5崩溃导致上层卷无法使用的数据恢复案例

服务器数据恢复—V7000存储raid5崩溃导致上层卷无法使用的数据恢复案例

服务器数据恢复环境&#xff1a; 某品牌V7000存储中有一组由几十块硬盘组建的raid5阵列。上层操作系统为windows server&#xff0c;NTFS分区。 服务器故障&#xff1a; 有一块硬盘出现故障离线&#xff0c;热备盘自动上线替换离线硬盘。在热备盘上线同步数据的过程&#xff0c…
阅读更多...
【springboot】idea项目启动端口被占用

【springboot】idea项目启动端口被占用

问题 idea本地启动springboot项目端口老是被占用 解决 关闭被占用的端口进程 步骤: 1. winR打开程序框 2. 查出被占用端口的进程id netstat -ano | finderstr 端口号 例如 netstat -ano | finderstr 81013.杀死进程 taskkill /pid 进程id -t -f 例如 taskkill /pid 2…
阅读更多...
TZOJ 1369 求绝对值

TZOJ 1369 求绝对值

答案&#xff1a; #include<stdio.h> int main() {double a0.0; 要求输入实数&#xff0c;实数包括小数&#xff0c;所以不能用int&#xff0c;只能用浮点型doublewhile (scanf("%lf", &a) ! EOF) //多组数据输入{if (a < 0.0) //如果是负数a -a…
阅读更多...
用IDEA创建Java类时，自动生成作者、时间和版本号、注释等信息

用IDEA创建Java类时，自动生成作者、时间和版本号、注释等信息

1.File->settings… 2、Editor->File and Code Templates->Includes->File Header(双击)&#xff0c;然后在右边输入框内输入代码即可 代码可以直接复制 /*** Author 作者名* Date ${DATE} ${TIME}* version 1.0* 注释*/上边你也可以自定义生成的内容。
阅读更多...
Spring 日志

Spring 日志

日志的作用: 1.定位和发现问题 2.系统监控 3.数据采集 观察日志 先写一段打印日志的代码 日志内容 日志级别分类 默认日志级别是Info,级别一下的就不打印了 Spring 帮我们集成了日志框架,我们直接使用即可 我们测试一下用日志框架打印日志是如何 我们就会发现打印的结果跟…
阅读更多...
内测分发平台应用的异地容灾和负载均衡处理和实现思路

内测分发平台应用的异地容灾和负载均衡处理和实现思路

内测分发平台应用的异地容灾和负载均衡处理和实现思路 ​ 内测分发平台在软件开发过程中起着至关重要的作用&#xff0c;它不仅可以帮助开发者将应用程序传播给内部测试人员&#xff0c;还可以收集反馈、跟踪错误并改进产品。然而&#xff0c;为了确保一个平稳、连贯的内测过…
阅读更多...
血的教训--kail系统免密centos7的坑【高版本ssh免密低版本ssh的坑】

血的教训--kail系统免密centos7的坑【高版本ssh免密低版本ssh的坑】

血的教训–kail系统免密centos7的坑【高版本ssh免密低版本ssh的坑】 最近下载了一个2023版本的kail系统&#xff0c;但是经过几次设置免密后&#xff0c;ssh过去一直让提供密码&#xff0c;所以就仔细的分析了一下&#xff0c;果然还是发现了点猫腻 接上一个博客&#xff0c;大…
阅读更多...
运算放大器

运算放大器

一、运算放大器的概念 1&#xff09;运算放大器具有两个输入端和一个输出端还有两个电源端&#xff0c;其中标有“”号的输入端为“同相输入端”&#xff0c;另一只标有“一”号的输入端为“反相输入端” 2&#xff09;运放的供电一般有两种方式&#xff1a;单电源和双电源 单…
阅读更多...
谱方法学习笔记-上(超详细)

谱方法学习笔记-上(超详细)

谱方法学习笔记&#x1f4d2; 谱方法学习笔记-下(超详细) 声明&#xff1a;鉴于CSDN使用 K a T e X KaTeX KaTeX 渲染公式&#xff0c; KaTeX \KaTeX KATE​X 与 L a T e X LaTeX LaTeX 不同&#xff0c;不支持直接的交叉引用命令&#xff0c;如\label和\eqref。 KaTeX \KaT…
阅读更多...
SpringBoot+网易邮箱登录注册

SpringBoot+网易邮箱登录注册

文章目录 SpringBoot网易邮箱登录注册pom.xmlapplication.ymlsqlUserEmail.javaUserEmailMapper.javaUserEmailMapper.xmlEmailService.javaUserEmailService.javaUserEmailServiceImpl.javaUserEmailController.javaregister1.html 编写前参考 SpringBoot网易邮箱登录注册 po…
阅读更多...
文生视频的发展史及其原理解析：从Gen2、Emu Video到PixelDance、SVD、Pika 1.0

文生视频的发展史及其原理解析：从Gen2、Emu Video到PixelDance、SVD、Pika 1.0

前言 考虑到文生视频开始爆发&#xff0c;比如11月份就是文生视频最火爆的一个月 11月3日&#xff0c;Runway的Gen-2发布里程碑式更新&#xff0c;支持4K超逼真的清晰度作品(runway是Stable Diffusion最早版本的开发商&#xff0c;Stability AI则开发的SD后续版本)11月16日&a…
阅读更多...
最新文章

Copyright @ 2022~2023