plan_genpath.cpp

巫魔问题求解

#include "Plan.h"
#include <Wum_Base/src/Cell.h>
#include "ClientMap.h"
#include "WorldModel.h"
#include "Effector.h"
#include <Wum_Server/src/Explorer.h>
#include <Wum_Tool/src/Math.h>
#include "Thinker.h"
#include <algorithm>

using namespace _algorithm;
using namespace _base;
using namespace _server;
/////////////////////////////////////////////
Cell *Plan::GenTargetPlace(void)
{
    if (this->TheWorldModel().TheClientMap().IsNoSolution())
    {
        return &this->TheWorldModel().TheClientMap().TheCell(0,0);
    }
    for (unsigned int i=0; i<this->TheWorldModel().GetClientMap().GetKnownCells().size(); i++)
    {
        if (this->TheWorldModel().GetClientMap().GetKnownCells()[i]->GetType() & Cell::CT_Gold)
        {
            ClientMap::Tool_InsertToVector(this->TheWorldModel().TheClientMap().TheSafeCells(), this->TheWorldModel().TheClientMap().TheKnownCells()[i]);
            return this->TheWorldModel().TheClientMap().TheKnownCells()[i];
        }
    }
    for (unsigned int i=this->TheWorldModel().GetClientMap().GetSafeCells().size()-1; i>0; i--)
    {
        if (!(this->TheWorldModel().GetClientMap().GetSafeCells()[i]->IsHasCame()))
        {
            return this->TheWorldModel().GetClientMap().GetSafeCells()[i];
        }
    }
    return 0;
}

////////////////////////////////////////////
Plan::TPath Plan::GenPath(int from, int to)
{
    TPath path;
    if (from < 0 || to < 0)
    {
        return path;
    }
    //Dijkstra
    const std::vector<Cell*> &safe_cells = this->TheWorldModel().GetClientMap().GetSafeCells();
    std::vector<std::vector<unsigned int> > distance(safe_cells.size(), std::vector<unsigned int>(safe_cells.size(), _tool::INFINITY));
    std::vector<std::vector<unsigned int> > best_paths(safe_cells.size(), std::vector<unsigned int>());
    std::vector<unsigned int> cur_distance(safe_cells.size(), _tool::INFINITY);
    std::vector<bool> cur_d_tags(safe_cells.size(), true);
    //初始化distance
    for (unsigned int i=0; i<safe_cells.size(); i++)
    {
        distance[i][i] = 0;
        for (unsigned int j=i+1; j<safe_cells.size(); j++)
        {
            if (_tool::Abs((int)safe_cells[i]->GetX() - (int)safe_cells[j]->GetX()) +
                _tool::Abs((int)safe_cells[i]->GetY() - (int)safe_cells[j]->GetY()) == 1)
            {
                distance[i][j] = distance[j][i] = 1;
            }
        }
    }
    cur_distance[from] = 0;
    best_paths[from].push_back(from);
    for (unsigned int i=0; i<safe_cells.size(); i++)
    {
        unsigned int min_dist = _tool::INFINITY;
        int min_tag = -1;
        for (unsigned int j=0; j<safe_cells.size(); j++)
        {
            if (cur_d_tags[j] && min_dist > cur_distance[j])
            {
                min_dist = cur_distance[j];
                min_tag = j;
            }
        }
        if (min_tag == -1)
        {
            return TPath();
        }
        cur_d_tags[min_tag] = false;

        for (unsigned int j=0; j<safe_cells.size(); j++)
        {
            if (cur_d_tags[j] && distance[min_tag][j] != _tool::INFINITY)
            {
                if (cur_distance[min_tag]+distance[min_tag][j] < cur_distance[j])
                {
                    cur_distance[j] = cur_distance[min_tag]+distance[min_tag][j];
                    best_paths[j] = best_paths[min_tag];
                    best_paths[j].push_back(j);
                }
            }
        }
    }

    TPath tmp_return;
    //后续处理
    for (unsigned int i =0; i<best_paths[to].size(); i++)
    {
        tmp_return.push_back(this->TheWorldModel().TheClientMap().TheSafeCells()[best_paths[to][i]]);
    }
    return tmp_return;
}

////////////////////////////////////////////
void Plan::GenTasks(void)
{
    if (this->mTasks.size() > 0)
    {
        return;
    }
    while (this->mPaths.size() != 0 && 
        this->mPaths.begin()->size() <= 1)
    {
        this->mPaths.erase(this->mPaths.begin());
    }
    if (this->mPaths.size() != 0)
    {
        Cell &from = *this->mPaths[0][0];
        Cell &to = *this->mPaths[0][1];
        
        if (from.GetX() != to.GetX() ||
            from.GetY() != to.GetY())
        {
            unsigned int dest_dir = Explorer::ED_None;
            if (from.CellLeft() == &to)
            {
                dest_dir = Explorer::ED_Left;
            }
            else if (from.CellRight() == &to)
            {
                dest_dir = Explorer::ED_Right;
            }
            else if (from.CellUp() == &to)
            {
                dest_dir = Explorer::ED_Up;
            }
            else if (from.CellDown() == &to)
            {
                dest_dir = Explorer::ED_Down;
            }
            unsigned int dir = this->TheWorldModel().GetInfo().mDirection;
            switch ((dest_dir-dir)%4)
            {
            case 1:
                this->mTasks.push_back(O_TurnLeft);
                break;

            case 2:
                this->mTasks.push_back(O_TurnRight);
                this->mTasks.push_back(O_TurnRight);
                break;

            case 3:
                this->mTasks.push_back(O_TurnRight);
                break;

            case 0:
                break;
            }
            this->mTasks.push_back(O_GoAhead);
        }
        this->mPaths.begin()->erase(this->mPaths.begin()->begin());
    }
    while ((this->mPaths.size() != 0) && (this->mPaths[0].size() <= 1))
    {
        this->mPaths.erase(this->mPaths.begin());
    }

}