root/deus/forward_search.cpp

/** 
 * forward_search.cpp
 */

#include "forward_search.h"
#include <qdatetime.h>
#include <set>
using std::set;

list<PlanNode *> matching_nodes;
World* buildWorld(PlanNode *n);
bool npcEqual(NPC *n1, NPC *n2);


bool forward_search(int time_ms)
{
        QTime t;
        t.start();

        matching_nodes.clear();
        return forward_search_rec(forward_root, time_ms, &t);
}


bool forward_search_rec(PlanNode *n, int time_ms, class QTime *t)
{
        bool match = false;
        list<Operator>* ops;
        std::list<Operator>::iterator It;
        //if (t->elapsed() > time_ms) return false;

        // This must be the new root!
        if (!n) {
                Operator op;
                op.code = OP_NOOP;
                forward_root = n = new PlanNode(op, 0);
        }

        World *w = buildWorld(n);

        // See if this state is a match!
        /* Steve ruined all my fun.
        std::vector<PlanNode *>::iterator It1;
        for (It1 = regression_roots.begin(); It1 != regression_roots.end(); It1++)
                match |= matches_reverse(n, *It1);
        */

        // Only expand leaves
        if (n->isLeaf()) 
        {
                ops = GetGregOperators(w);
                for (It = ops->begin(); It != ops->end(); It++) {
                        PlanNode *new_node = new PlanNode(*It, n->depth + 1);
                        new_node->icon->ul_x = n->icon->ul_x + ICON_W + 200;
                        new_node->icon->ul_y = n->icon->ul_y + (20*ICON_H*(rand()/(double)RAND_MAX) - (10*ICON_H));
                        n->branches.push_back(new_node);
                }
        }
        else
        {
                std::vector<PlanNode*>::iterator It1;
                for (It1 = n->branches.begin(); It1 != n->branches.end(); It1++)
                        forward_search_rec(*It1, time_ms, t);
        }

        // Look at children, here, if you want to

        return match;
}


bool matches_reverse(PlanNode *node, PlanNode *root)
{
        bool match = false;
        PlanNode *n;
        std::vector<PlanNode *>::iterator It;
        set<PlanNode *> visited;
        list<PlanNode *> queue;
        queue.push_back(root);

        while (!queue.empty())
        {
                n = queue.front(); queue.pop_front();
                
                if (n && visited.find(n) == visited.end())
                {
                        visited.insert(n);
                        
                        // if world state matches
                        //if (n...) {
                        //      matching_nodes.push_back(n);
                        //      match = true
                        //}

                        // Parents and children
                        for (It = n->branches.begin(); It != n->branches.end(); It++)
                                queue.push_back(*It);
                        for (It = n->prevs.begin(); It != n->prevs.end(); It++)
                                queue.push_back(*It);
                }
        }

        return match;
}


World* buildWorld(PlanNode *n)
{
        // Copy the world
        World * w = new World();
        std::vector<NPC>::iterator It1;
        for (It1 = real_world->NPCs.begin(); It1 != real_world->NPCs.end(); It1++)
                w->NPCs.push_back(*It1);
        std::vector<Item>::iterator It2;
        for (It2 = real_world->Items.begin(); It2 != real_world->Items.end(); It2++)
                w->Items.push_back(*It2);
        std::vector<Location>::iterator It3;
        for (It3 = real_world->Locations.begin(); It3 != real_world->Locations.end(); It3++)
                w->Locations.push_back(*It3);
        w->map_height = real_world->map_height;
        w->map_width = real_world->map_width;

        if (!n) return w;


        // Find path to real world
        Operator *o;
        list<Operator*> path;
        PlanNode *node = n;
        while (node) {
                path.push_back(&(n->Op));
                if (node->prevs.size() > 0)
                        node = node->prevs[0];  // all paths lead to rome
                else node = NULL;
        }

        // Rebuild the world
        while (path.size() > 0) 
        {
                o = path.front(); path.pop_front();

                // apply operator to fake world
                DoOps(w, o);
        }

        return w;
}


bool worldEqual(World *w1, World *w2)
{
        if (w1->map_height != w2->map_height)   return false;
        if (w1->map_width != w2->map_width)             return false;

        std::vector<GameObject>::iterator It1, It2;
        for (It1 = w1->NPCs.begin(), It2 = w2->NPCs.begin(); 
                It1 != w1->NPCs.end(), It2 != w2->NPCs.end(); It1++, It2++)
                if (!npcEqual((NPC*)It1, (NPC*)It2)) return false;

        // HACK: No items...
        // HACK: Locations will never change...

        return true;
}


bool npcEqual(NPC *n1, NPC *n2)
{
        if (n1->name != n2->name)               return false;
        if (n1->xcoord = n2->xcoord)    return false;
        if (n1->ycoord = n2->ycoord)    return false;
        
        std::map<string,int>::iterator It1, It2;
        for (It1 = n1->attributes.begin(), It2 = n2->attributes.begin();
                It1 != n1->attributes.end(), It2 != n2->attributes.end();
                It1++, It2++)
                        if (*It1 != *It2) return false;

        std::map<std::pair<string,int>, int>::iterator It3, It4;
        for (It3 = n1->relationships.begin(), It4 = n2->relationships.begin();
                It3 != n1->relationships.end(), It4 != n2->relationships.end(); 
                It3++, It4++)
                        if (*It1 != *It2) return false;

        return true;
}


list<std::pair<std::pair<World*,PlanNode*>, Condition> > 
GetWorldStates(Condition &c)
{
        World *w;
        list<std::pair<std::pair<World*,PlanNode*>, Condition> > l;

        PlanNode *n;
        std::vector<PlanNode *>::iterator It;
        set<PlanNode *> visited;
        list<PlanNode *> queue;
        queue.push_back(forward_root);

        while (!queue.empty())
        {
                n = queue.front(); queue.pop_front();
                
                if (n && visited.find(n) == visited.end())
                {
                        visited.insert(n);
                        
                        if (n->isLeaf()) {
                                w = buildWorld(n);
                                Condition cond = CheckWorldState(w, c);
                                l.push_back(std::pair<std::pair<World*,PlanNode*>, Condition>(
                                        std::pair<World*,PlanNode*>(w,n), cond));
                        }

                        // Parents and children
                        for (It = n->branches.begin(); It != n->branches.end(); It++)
                                queue.push_back(*It);
                        for (It = n->prevs.begin(); It != n->prevs.end(); It++)
                                queue.push_back(*It);
                }
        }

        return l;
}