From 411d2f6d6a6e5370d33f0f54b2f2de7147a9d977 Mon Sep 17 00:00:00 2001 From: jacopograndi Date: Mon, 6 Sep 2021 20:11:36 +0200 Subject: started ai --- game/ai/action.cpp | 76 +++++++++++++++++++++++++++++++++++++++ game/ai/action.h | 52 +++++++++++++++++++++++++++ game/ai/engine.h | 66 ++++++++++++++++++++++++++++++++++ game/ai/evaluator.h | 30 ++++++++++++++++ game/ai/generator.h | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++ game/ai/performer.h | 49 +++++++++++++++++++++++++ game/ai/tactic.h | 32 +++++++++++++++++ game/entity.h | 16 +++++++-- game/ground.cpp | 14 ++++---- game/gst.cpp | 22 +++++++++--- game/gst.h | 13 ++++++- game/load.cpp | 2 -- 12 files changed, 458 insertions(+), 16 deletions(-) create mode 100644 game/ai/action.cpp create mode 100644 game/ai/action.h create mode 100644 game/ai/engine.h create mode 100644 game/ai/evaluator.h create mode 100644 game/ai/generator.h create mode 100644 game/ai/performer.h create mode 100644 game/ai/tactic.h (limited to 'game') diff --git a/game/ai/action.cpp b/game/ai/action.cpp new file mode 100644 index 0000000..63218ba --- /dev/null +++ b/game/ai/action.cpp @@ -0,0 +1,76 @@ +#include "action.h" + +bool ai::compare_action(ai::action a, ai::action b) { + return (a.heuristic < b.heuristic); +} + +std::string ai::action::to_string () { + if (type == actype::attack) { + if (abs(x-mx)+abs(y-my) != 0) { + return "[" + std::to_string(x) + ", " + std::to_string(y) + "]" + + " move " + + "[" + std::to_string(mx) + ", " + std::to_string(my) + "]" + + " attack " + + "[" + std::to_string(tx) + ", " + std::to_string(ty) + "]"; + } else { + return "[" + std::to_string(x) + ", " + std::to_string(y) + "]" + + " attack " + + "[" + std::to_string(tx) + ", " + std::to_string(ty) + "]"; + } + } + if (type == actype::heal) { + if (abs(x-mx)+abs(y-my) != 0) { + return "[" + std::to_string(x) + ", " + std::to_string(y) + "]" + + " move " + + "[" + std::to_string(mx) + ", " + std::to_string(my) + "]" + + " heal " + + "[" + std::to_string(tx) + ", " + std::to_string(ty) + "]"; + } else { + return "[" + std::to_string(x) + ", " + std::to_string(y) + "]" + + " heal " + + "[" + std::to_string(tx) + ", " + std::to_string(ty) + "]"; + } + } + if (type == actype::convert) { + if (abs(x-mx)+abs(y-my) != 0) { + return "[" + std::to_string(x) + ", " + std::to_string(y) + "]" + + " move " + + "[" + std::to_string(mx) + ", " + std::to_string(my) + "]" + + " convert " + + "[" + std::to_string(tx) + ", " + std::to_string(ty) + "]"; + } else { + return "[" + std::to_string(x) + ", " + std::to_string(y) + "]" + + " convert " + + "[" + std::to_string(tx) + ", " + std::to_string(ty) + "]"; + } + } + if (type == actype::move) { + return "[" + std::to_string(x) + ", " + std::to_string(y) + "]" + + " move " + + "[" + std::to_string(mx) + ", " + std::to_string(my) + "]"; + } + if (type == actype::build) { + if (abs(x-mx)+abs(y-my) != 0) { + return "[" + std::to_string(x) + ", " + std::to_string(y) + + "]" + " move " + + "[" + std::to_string(mx) + ", " + std::to_string(my) + + "]" + " build " + + std::to_string(v); + } else { + return "[" + std::to_string(mx) + ", " + std::to_string(my) + + "]" + " build " + + std::to_string(v); + } + } + if (type == actype::train) { + return "[" + std::to_string(x) + ", " + std::to_string(y) + "]" + + " train " + std::to_string(v); + } + if (type == actype::trade) { + return "[" + std::to_string(x) + ", " + std::to_string(y) + "]" + + " trade " + std::to_string(v); + } + if (type == actype::tech) { + return "tech " + std::to_string(v); + } +} \ No newline at end of file diff --git a/game/ai/action.h b/game/ai/action.h new file mode 100644 index 0000000..12da451 --- /dev/null +++ b/game/ai/action.h @@ -0,0 +1,52 @@ +#ifndef ACTION_H +#define ACTION_H + +#include +#include + +namespace ai { + +enum actype { + attack, heal, convert, build, train, trade, move, tech +}; + +class action { + public: + action (actype type, int v) : + type(type), v(v) {} + action (actype type, int x, int y, int v) : + type(type), x(x), y(y), v(v) {} + action (actype type, int x, int y, int mx, int my) : + type(type), x(x), y(y), mx(mx), my(my) {} + action (actype type, int x, int y, int mx, int my, int v) : + type(type), x(x), y(y), mx(mx), my(my), v(v) {} + action (actype type, int x, int y, int mx, int my, int tx, int ty) : + type(type), x(x), y(y), mx(mx), my(my), tx(tx), ty(ty) {} + action (actype type, int x, int y, int mx, int my, int tx, int ty, int v) : + type(type), x(x), y(y), mx(mx), my(my), tx(tx), ty(ty), v(v) {} + + action (const action& rhs) { + type = rhs.type; x = rhs.x; y = rhs.y; mx = rhs.mx; my = rhs.my; + tx = rhs.tx; ty = rhs.ty; v = rhs.v; + } + action& operator=(const action& rhs) { + type = rhs.type; x = rhs.x; y = rhs.y; mx = rhs.mx; my = rhs.my; + tx = rhs.tx; ty = rhs.ty; v = rhs.v; + } + + actype type; + int x, y; // start + int mx, my; // moved + int tx, ty; // target + int v; // value (id of trainee, building or f/g trade, or tech id) + + float heuristic { 0 }; + + std::string to_string (); +}; + +bool compare_action(action a, action b); + +} + +#endif \ No newline at end of file diff --git a/game/ai/engine.h b/game/ai/engine.h new file mode 100644 index 0000000..d3755e1 --- /dev/null +++ b/game/ai/engine.h @@ -0,0 +1,66 @@ +#ifndef ENGINE_H +#define ENGINE_H + +#include + +#include +#include +#include +#include + +#include "../ground.h" +#include "../gst.h" + +#include "action.h" +#include "tactic.h" +#include "generator.h" +#include "evaluator.h" +#include "performer.h" + +namespace ai { + +class engine { + public: + engine (Gst &gst) : init(gst) {} + Gst &init; + + tactic get_best () { + tactic t { search(init, 4) }; + std::cout << t.to_string(); + return t; + } + + tactic search (Gst &gst, int depth) { + generator gen { gst }; + std::vector tactics = gen.tactics(); + tactic best; best.eval = std::numeric_limits::lowest(); + for (tactic t : tactics) { + performer perf { gst }; + Gst next { perf.apply(t) }; + t.eval = negamax(next, depth, gst.turn); + std::cout << "depth " << depth << " eval " << t.eval << "\n"; + if (t.eval > best.eval) best = t; + } + return best; + } + + float negamax (Gst gst, int depth, int player) { + //for (int i=0; i<3-depth; i++) std::cout << " "; std::cout << depth << "\n"; + if (depth == 0) { + evaluator eval { gst }; + return eval.eval(player); + } + float value = std::numeric_limits::lowest(); + generator gen { gst }; + auto tactics = gen.tactics(); + for (tactic t : tactics) { + performer perf { gst }; + Gst next { perf.apply(t) }; + value = fmax(value, negamax(next, depth-1, -player)); + } + return -value; + } +}; + +} +#endif \ No newline at end of file diff --git a/game/ai/evaluator.h b/game/ai/evaluator.h new file mode 100644 index 0000000..75684de --- /dev/null +++ b/game/ai/evaluator.h @@ -0,0 +1,30 @@ +#ifndef EVALUATOR_H +#define EVALUATOR_H + +#include + +#include +#include + +#include "../ground.h" +#include "../gst.h" + +namespace ai { + +class evaluator { + public: + evaluator (Gst gst) : gst(gst) {} + Gst gst; + + float eval (int player) { + float val = 0; + for (Entity &ent : gst.entities) { + int own = (int)(ent.owner != player)*2-1; + val += own*(ent.info->cost[0] + ent.info->cost[1])*(ent.hp/100.0f); + } + return val; + } +}; + +} +#endif \ No newline at end of file diff --git a/game/ai/generator.h b/game/ai/generator.h new file mode 100644 index 0000000..c6cb288 --- /dev/null +++ b/game/ai/generator.h @@ -0,0 +1,102 @@ +#ifndef GENERATOR_H +#define GENERATOR_H + +#include + +#include +#include + +#include "../ground.h" +#include "../gst.h" +#include "action.h" +#include "tactic.h" +#include "performer.h" + +namespace ai { + +const int maxiter = 100000; + + +class generator { + public: + generator (Gst &gst) : init(gst) {} + Gst &init; + + std::vector valid_actions (Gst &gst) { + Ground &gr = gst.inv->ground; + std::vector acts; + for (Entity &ent : gst.entities) { + if (ent.done) continue; + if (ent.owner != gst.turn) continue; + + std::vector ent_acts; + + std::vector moves = gr.move_area(gst, ent); + for (auto move : moves) { + int mx = move%gr.sizex, my = move/gr.sizex; + action act { actype::move, ent.x, ent.y, mx, my }; + + performer perf { gst }; + Gst next { gst }; + next = perf.act(next, act); + Entity &matk = next.get_at(mx, my); + std::vector atks = gr.attack_targets(next, matk); + for (auto atk : atks) { + int tx = atk%gr.sizex, ty = atk/gr.sizex; + action act_atk { actype::attack, ent.x, ent.y, + mx, my, tx, ty }; + Entity &mdef = next.get_at(tx, ty); + + BattleResult res = gst.battle_res(matk, mdef); + float heur = (mdef.hp-res.def_hp); + heur *= (mdef.info->cost[0] + mdef.info->cost[1]); + act_atk.heuristic = heur; + ent_acts.push_back(act_atk); + } + + int dist = 999999; + int pos = gst.get_nearest_enemy(ent, dist); + float heur = 1.0f/dist; + act.heuristic = heur; + ent_acts.push_back(act); + } + std::sort(ent_acts.begin(), ent_acts.end(), compare_action); + for (int i=0; i<3 && i acts { valid_actions(gst) }; + if (acts.size() == 0) break; + performer perf { gst }; + int j = n % (acts.size()); + n /= acts.size(); + action &act = acts[j]; + gst = perf.act(gst, act); + t.acts.push_back(act); + //std::cout << act.to_string() << std::endl; + } + return t; + } + + std::vector tactics () { + std::vector ts; + for (int i=0; i<3; i++) { + int n = i; + tactic t = valid_tactic(n); + if (n > 0) break; + ts.push_back(t); + } + return ts; + } +}; + +} +#endif \ No newline at end of file diff --git a/game/ai/performer.h b/game/ai/performer.h new file mode 100644 index 0000000..472773b --- /dev/null +++ b/game/ai/performer.h @@ -0,0 +1,49 @@ +#ifndef PERFORMER_H +#define PERFORMER_H + +#include + +#include +#include + +#include "../ground.h" +#include "../gst.h" +#include "action.h" +#include "tactic.h" + +namespace ai { + +class performer { + public: + performer (Gst &gst) : init(gst) {} + Gst &init; + + Gst apply (tactic t) { + Gst next { init }; + for (action a : t.acts) { + next = act(next, a); + } + next.end_day(); + return next; + } + + Gst& act (Gst &gst, action a) { + if (a.type == actype::move) { + Entity &ent = gst.get_at(a.x, a.y); + ent.x = a.mx; ent.y = a.my; + ent.moved = 1; ent.done = true; + } + if (a.type == actype::attack) { + Entity &ent = gst.get_at(a.x, a.y); + ent.x = a.mx; ent.y = a.my; + ent.moved = 1; + Entity &def = gst.get_at(a.tx, a.ty); + gst.battle(ent, def); + ent.done = true; + } + return gst; + } +}; + +} +#endif \ No newline at end of file diff --git a/game/ai/tactic.h b/game/ai/tactic.h new file mode 100644 index 0000000..7eefef9 --- /dev/null +++ b/game/ai/tactic.h @@ -0,0 +1,32 @@ +#ifndef TACTIC_H +#define TACTIC_H + +#include +#include + +#include "action.h" + +namespace ai { + +class tactic { + public: + tactic () { } + + std::vector acts; + float eval = 0; + + // copy constructor + tactic (const tactic& rhs) { acts = rhs.acts; eval = rhs.eval; } + tactic& operator=(const tactic& rhs) { acts = rhs.acts; eval = rhs.eval; } + + std::string to_string () { + std::string str = "tactic eval= " + std::to_string(eval) + "\n"; + for (action act : acts) { + str += act.to_string() + "\n"; + } + return str; + } +}; + +} +#endif \ No newline at end of file diff --git a/game/entity.h b/game/entity.h index 62e352e..a15ebdb 100644 --- a/game/entity.h +++ b/game/entity.h @@ -50,22 +50,32 @@ namespace EntityClass { class Entity { public: - Entity(int x, int y, EntityInfo *info, int owner) + Entity (int x, int y, EntityInfo *info, int owner) : x(x), y(y), info(info), owner(owner) { moved = 0; hp = 100; } + // copy constructor + Entity (const Entity& rhs) { + building = rhs.building; hp = rhs.hp; x = rhs.x; y = rhs.y; + done = rhs.done; moved = rhs.moved; info = rhs.info; + fights = rhs.fights; owner = rhs.owner; + } + Entity& operator=(const Entity& rhs) { + building = rhs.building; hp = rhs.hp; x = rhs.x; y = rhs.y; + done = rhs.done; moved = rhs.moved; info = rhs.info; + fights = rhs.fights; owner = rhs.owner; + }; bool operator==(Entity oth) { return x == oth.x && y == oth.y && info->unit == oth.info->unit; } int building { 0 }; - float hp; /**/ + float hp; int x, y; bool done = false; int moved; EntityInfo *info; int fights { 0 }; - int owner; }; diff --git a/game/ground.cpp b/game/ground.cpp index 5f58717..cd67751 100644 --- a/game/ground.cpp +++ b/game/ground.cpp @@ -65,23 +65,25 @@ std::vector Ground::move_area (Gst &gst, Entity &ent) { int movecost = gst.inv->tiles[tiles[t]].move_cost; if (movecost > maxcost) movecost = maxcost; int walkedm = maxf.m - movecost; - bool obstructed = false; + bool obs_enemy = false, obs_friend = false; for (Entity &e : gst.entities) { - if (e.owner != ent.owner && at(e.x, e.y) == t) { - obstructed = true; + if (at(e.x, e.y) == t) { + if (e.owner != ent.owner) obs_enemy = true; + else obs_friend = true; break; } } - if (walkedm >= 0 && !obstructed) { + if (walkedm >= 0 && !obs_enemy) { frontier.emplace_back(t, walkedm); - moves.push_back(t); + if (!obs_friend) { + moves.push_back(t); + } } } } visited.push_back(maxf.pos); } - std::cout << "iters: " << iter; return moves; } diff --git a/game/gst.cpp b/game/gst.cpp index 52dfe81..334844a 100644 --- a/game/gst.cpp +++ b/game/gst.cpp @@ -261,8 +261,8 @@ BattleResult Gst::battle_res (Entity &atk, Entity &def) { } void Gst::battle (Entity &atk, Entity &def) { - std::cout << "! attack " << atk.info->name << "(hp:" << atk.hp << "), " - << def.info->name << "(hp:" << def.hp << ") \n"; + /*std::cout << "! attack " << atk.info->name << "(hp:" << atk.hp << "), " + << def.info->name << "(hp:" << def.hp << ") \n";*/ auto result = battle_res(atk, def); atk.hp = result.atk_hp; @@ -271,8 +271,8 @@ void Gst::battle (Entity &atk, Entity &def) { if (atk.info->unit == 1) atk.fights += 1; if (def.info->unit == 1) def.fights += 1; - std::cout << "! result " << atk.info->name << "(hp:" << atk.hp << "), " - << def.info->name << "(hp:" << def.hp << ") \n"; + /*std::cout << "! result " << atk.info->name << "(hp:" << atk.hp << "), " + << def.info->name << "(hp:" << def.hp << ") \n";*/ clear_dead(); } @@ -320,6 +320,20 @@ void Gst::convert (Entity &atk, Entity &def) { } +int Gst::get_nearest_enemy (Entity &ent, int &mindist) { + auto &ground = inv->ground; + int pos = -1; mindist = 9999999; + for (Entity &oth : entities) { + if (oth.owner == ent.owner) continue; + int dist = abs(oth.x-ent.x) + abs(oth.y-ent.y); + if (dist < mindist) { + mindist = dist; + pos = ground.at(oth.x, oth.y); + } + } +} + + std::vector Gst::get_possible_trains (Entity &ent) { Player &player = get_player(ent.owner); auto &cls = ent.info->train_class; diff --git a/game/gst.h b/game/gst.h index e86ddc5..376026e 100644 --- a/game/gst.h +++ b/game/gst.h @@ -68,11 +68,20 @@ class Gst { public: Gst(Inv *inv) : inv(inv) { } + // copy constructor + Gst (const Gst& rhs) { + inv = rhs.inv; entities = rhs.entities; players = rhs.players; + turn = rhs.turn; day = rhs.day; + } + Gst& operator=(const Gst& rhs) { + inv = rhs.inv; entities = rhs.entities; players = rhs.players; + turn = rhs.turn; day = rhs.day; + }; + Inv *inv; std::vector entities; std::vector players; - int turn { 0 }; int day { 0 }; @@ -97,6 +106,8 @@ class Gst { void heal (Entity &atk, Entity &def); void convert (Entity &atk, Entity &def); + int get_nearest_enemy (Entity &ent, int &mindist); + std::vector get_possible_trains (Entity &ent); std::vector get_possible_builds (Entity &ent); diff --git a/game/load.cpp b/game/load.cpp index 9f58c7d..ea4e9e7 100644 --- a/game/load.cpp +++ b/game/load.cpp @@ -145,8 +145,6 @@ void load_json (Inv &inv) { tech.bonus.aff_all = b["aff_all"]; } } - - std::cout << tech.id << tech.bonus.to_string() << std::endl; inv.techs.push_back(tech); } } \ No newline at end of file -- cgit v1.2.3-54-g00ecf