Implement ranged attacks
[homm5.git] / h5.cpp
1 #include <vector>
2 #include <algorithm>
3 #include <string_view>
4 #include <string>
5 #include <sstream>
6 #include <iostream>
7 #include <iomanip>
8 #include <deque>
9
10 std::deque<std::string> linebuffer;
11 struct shushout {
12         std::deque<std::string>& left;
13         bool newline = true;
14         bool has_data()
15         {
16                 auto uneven_line = [&] {
17                         return (left.front().empty() || left.front().front() == '[');
18                 };
19                 while (!left.empty() && uneven_line()) {
20                         std::cout << left.front() << '\n';
21                         left.pop_front();
22                 }
23                 return !left.empty();
24         }
25 } xout{linebuffer};
26
27 struct _endl {} nl;
28
29 void print_left(shushout& shu)
30 {
31         auto& left = shu.left;
32         if (shu.has_data()) {
33                 std::cout << left.front();
34                 left.pop_front();
35         } else {
36                 std::cout << "                       ";
37         }
38         std::cout << "  |  ";
39         shu.newline = false;
40 }
41
42 shushout& operator<<( shushout& shu, _endl const& )
43 {
44         if (shu.newline)
45                 print_left( shu );
46         std::cout << '\n';
47         shu.newline = true;
48         return shu;
49 }
50
51 template<typename T>
52 shushout& operator<<( shushout& shu, T const& s )
53 {
54         if (shu.newline)
55                 print_left( shu );
56         std::cout << s;
57         return shu;
58 }
59
60 enum class ability_category {
61         passive,
62         pre_attack,
63         pre_damage,
64         post_damage,
65         post_enemy_retaliation,
66         defensive,
67         pre_turn,
68         post_turn,
69         activated
70 };
71
72 struct creature_stack;
73 struct creature_ability {
74         ability_category cat;
75         virtual void add(creature_stack& stack) {}
76 };
77
78
79 struct creature {
80         std::string_view name;
81
82         int attack;
83         int defence;
84
85         unsigned max_hp;
86
87         struct {
88                 unsigned min;
89                 unsigned max;
90         } dmg;
91
92         unsigned speed;
93         unsigned initiative;
94
95         std::vector< creature_ability* > specials;
96 };
97
98 struct effect;
99 struct effect_base {
100         //virtual void add(creature_stack& stack) = 0;
101         virtual std::string_view name() = 0;
102         virtual void remove(creature_stack& stack) = 0;
103         virtual void begin_turn(effect& eff, creature_stack& target) {}
104 };
105
106 // TODO: map[ effect_over_kind ] -> vector[ effect ]
107 struct effect {
108         int counter = 0;
109         int duration;
110         bool removed_on_damage = false;
111         effect_base* base;
112         double value = 0.0;
113 };
114
115 struct damage_context {
116         creature_stack& from;
117         creature_stack& to;
118         int attack;
119         int defence;
120 };
121
122 #include <cmath>
123 struct vec2d {
124         int x, y;
125         double length() const
126         {
127                 return std::sqrt(x*x+y*y);
128         }
129 };
130 struct point2d {
131         int x, y;
132 };
133 vec2d operator-(point2d a, point2d b)
134 {
135         return {a.x-b.x,a.y-b.y};
136 }
137 bool operator==(point2d a, point2d b)
138 {
139         return a.x == b.x && a.y == b.y;
140 }
141 bool operator!=(point2d a, point2d b)
142 {
143         return a.x != b.x || a.y != b.y;
144 }
145
146 bool operator<(point2d a, point2d b)
147 {
148         return a.x < b.x || (a.x == b.x && a.y < b.y);
149 }
150
151 struct creature_stack {
152         creature_stack(::creature const& creature, unsigned count, point2d pos, int team)
153                 : creature{creature}, count{count}, pos{pos}, team{team}
154         {
155                 hp     = int(creature.max_hp);
156                 max_hp = int(creature.max_hp);
157
158                 for (auto* ability : creature.specials)
159                         ability->add( *this );
160         }
161
162         creature_stack(::creature const& creature, unsigned count, point2d pos)
163                 : creature_stack{ creature, count, pos, -1 }
164         {
165         }
166
167         std::string describe() const
168         {
169                 auto name = std::string(creature.name);
170                 name += '[';
171                 name += std::to_string(count);
172                 name += ']';
173                 return name;
174         }
175
176         void step_turn()
177         {
178                 if (dead()) return;
179                 for (auto& effect : effects) {
180                         effect.counter += 10;
181                         if (effect.counter > effect.duration)
182                                 effect.base->remove(*this);
183                 }
184                 auto it = std::remove_if(begin(effects),end(effects),[](auto e) { return e.counter > e.duration; } );
185                 effects.erase( it, end(effects) );
186                 if (disabled)
187                         return;
188                 initiative += creature.initiative;
189         }
190
191         void begin_turn()
192         {
193                 retaliations = max_retaliations;
194                 for ( auto func : pre_turn )
195                         func( *this );
196                 for ( auto e : effects )
197                         e.base->begin_turn( e, *this );
198         }
199
200         bool dead() const
201         {
202                 return count == 0;
203         }
204
205         void wait()
206         {
207                 initiative += 50;
208                 xout << describe() << " waits" << nl;
209         }
210         
211         void move(point2d newpos)
212         {
213                 pos = newpos;
214                 xout << describe() << " moves to " << pos.x << ',' << pos.y << nl;
215         }
216
217         unsigned apply_damage( int dmg )
218         {
219                 auto orig = count;
220                 unsigned kills = dmg / max_hp;
221                 dmg = dmg % max_hp;
222
223                 kills = std::min( kills, count );
224                 count -= kills;
225
226                 if (count > 0) {
227                         if (dmg >= hp) {
228                                 if (count > 1)
229                                         hp += max_hp;
230                                 count -= 1;
231                         }
232                         hp -= dmg;
233                 }
234
235                 if (count == 0)
236                         die();
237                 return orig - count;
238         }
239
240         void die()
241         {
242                 hp = 0;
243                 initiative = 0;
244         }
245
246         ::creature creature;
247         unsigned count;
248
249         int hp;
250         int max_hp;
251
252         point2d pos;
253
254         int team = -1;
255
256
257         double shot_damage = 1.0;
258         double melee_damage = 1.0;
259
260         unsigned num_ranged_attacks = 0;
261         unsigned shots = 0;
262
263         unsigned initiative = 0;
264
265         unsigned max_retaliations = 1;
266         unsigned retaliations = max_retaliations;
267
268         bool disabled = false;
269         bool blocks_retaliation = false;
270
271         std::vector<effect> effects;
272         std::vector<void(*)(damage_context&)> pre_damage;
273         std::vector<void(*)(creature_stack&)> pre_turn;
274         std::vector<void(*)(creature_stack&, creature_stack&)> post_enemy_retaliation;
275         std::vector<void(*)(creature_stack&, creature_stack&)> post_damage;
276 };
277
278 void regenerate( creature_stack& stack );
279 struct ability_regenerate : creature_ability {
280         ability_regenerate()
281         {
282                 cat = ability_category::pre_turn;
283         }
284         void add(creature_stack& stack) override
285         {
286                 stack.pre_turn.push_back( regenerate );
287         }
288 } regeneration;
289
290 struct ability_no_retaliation : creature_ability {
291         ability_no_retaliation()
292         {
293                 cat = ability_category::passive;
294         }
295         void add(creature_stack& stack) override
296         {
297                 stack.blocks_retaliation = true;
298         }
299 } no_retaliation;
300
301 struct bad_shooter : creature_ability {
302         bad_shooter()
303         {
304                 cat = ability_category::passive;
305         }
306         void add(creature_stack& stack) override
307         {
308                 stack.shots = 6;
309                 stack.shot_damage = 0.5;
310                 stack.num_ranged_attacks = 1;
311         }
312 } shooter_half;
313
314 struct normal_shooter : creature_ability {
315         normal_shooter()
316         {
317                 cat = ability_category::passive;
318         }
319         void add(creature_stack& stack) override
320         {
321                 stack.shots = 12;
322                 stack.shot_damage = 1.0;
323                 stack.melee_damage = 0.5;
324                 stack.num_ranged_attacks = 1;
325         }
326 } shooter_normal;
327
328 struct twice_shooter : creature_ability {
329         twice_shooter()
330         {
331                 cat = ability_category::passive;
332         }
333         void add(creature_stack& stack) override
334         {
335                 stack.shots = 24;
336                 stack.shot_damage = 1.0;
337                 stack.melee_damage = 0.5;
338                 stack.num_ranged_attacks = 2;
339         }
340 } shooter_twice;
341
342 #include <random>
343 #include <aw/utility/random/mersenne_twister.h>
344 auto rng = aw::create_mersenne_twister_engine();
345
346 struct effect_poison : effect_base {
347         effect_poison()
348         {
349         }
350         std::string_view name() { return "Poisoned"; }
351         void add(creature_stack& from,creature_stack& stack)
352         {
353                 for (auto e : stack.effects)
354                         if (e.base == this)
355                                 return;
356                 stack.effects.push_back( effect{0,(int)stack.creature.initiative*21,false,this,double(from.count)} );
357                 xout << from.describe() << " poisoned " << stack.describe() << nl;
358         }
359         void remove(creature_stack& stack) override
360         {
361                 xout << "Poison wears off from " << stack.describe() << nl;
362         }
363         void begin_turn(effect& eff, creature_stack& target) override
364         {
365                 int dmg = eff.value;
366                 xout << target.describe() << " suffers " << dmg << " damage from poison";
367                 auto kills = target.apply_damage(dmg);
368                 if (kills > 1)
369                         xout << " (" << kills << ' ' << target.creature.name << 's' << " perish)" << nl;
370                 else if (kills > 0)
371                         xout << " (" << kills << ' ' << target.creature.name << " perishes)" << nl;
372                 else
373                         xout << nl;
374         }
375 } poison_effect;
376
377 struct effect_blind : effect_base {
378         effect_blind()
379         {
380         }
381         std::string_view name() { return "Blinded"; }
382         void add(creature_stack& stack)
383         {
384                 /*for (auto e : stack.effects)
385                         if (e.base == this)
386                                 return;*/
387                 stack.effects.push_back( effect{0,200,true,this} );
388                 stack.disabled = true;
389         }
390         void remove(creature_stack& stack) override
391         {
392                 stack.disabled = false;
393                 xout << "Blind wears off from " << stack.describe() << nl;
394         }
395 } blind_effect;
396
397 void roll_blind( creature_stack& from, creature_stack& to)
398 {
399         if (to.dead())
400                 return;
401         double fhp = (from.count-1)*from.max_hp + from.hp;
402         double thp = (to.count-1)*to.max_hp + to.hp;
403         double chance = 0.25 + ((fhp > thp) ? (0.03*fhp/thp) : (-0.03*thp/fhp));
404         chance = std::max(0.05,chance);
405         chance = std::min(0.75,chance);
406         std::uniform_real_distribution<double> dist(0.0, 1.0);
407         auto roll = dist(rng);
408         //xout << "Blor " << int(roll*100) << '/' << int(chance*100) << nl;
409         if (roll < chance) {
410                 xout << from.describe() << " blind " << to.describe() << nl;
411                 blind_effect.add( to );
412         }
413 }
414
415 void add_poison( creature_stack& from, creature_stack& to )
416 {
417         poison_effect.add( from, to );
418 }
419
420 struct ability_blind : creature_ability {
421         ability_blind()
422         {
423                 cat = ability_category::post_damage;
424         }
425         void add(creature_stack& stack) override
426         {
427                 stack.post_damage.push_back( roll_blind );
428         }
429 } blind;
430
431 struct ability_poison : creature_ability {
432         ability_poison()
433         {
434                 cat = ability_category::post_damage;
435         }
436         void add(creature_stack& stack) override
437         {
438                 stack.post_damage.push_back( add_poison );
439         }
440 } poisoner;
441
442
443
444 unsigned calc_damage( damage_context& ctx )
445 {
446         auto atk = ctx.attack;
447         auto def = ctx.defence;
448         double coef = 1;
449         if (atk > def)
450                 coef = 1 + 0.05*(atk-def);
451         if (atk < def)
452                 coef = 1/(1 + 0.05*(def-atk));
453
454         coef *= ctx.from.count;
455         auto min = ctx.from.creature.dmg.min;
456         auto max = ctx.from.creature.dmg.max;
457         std::uniform_int_distribution<unsigned> dist( min*coef, max*coef );
458         return dist(rng);
459 }
460
461 void ignore_defence_80p( damage_context& ctx )
462 {
463         ctx.defence *= 0.2;
464 }
465
466 struct ability_ignore80p : creature_ability {
467         ability_ignore80p()
468         {
469                 cat = ability_category::pre_damage;
470         }
471         void add(creature_stack& stack) override
472         {
473                 stack.pre_damage.push_back( ignore_defence_80p );
474         }
475 } ignoredef80p;
476
477 void apply_damage( creature_stack& attacker, creature_stack& target )
478 {
479         if (attacker.dead()||target.dead())
480                 return;
481
482         damage_context ctx {
483                 attacker,
484                 target,
485                 attacker.creature.attack,
486                 target.creature.attack
487         };
488
489         for (auto func : attacker.pre_damage)
490                 func( ctx );
491
492         int dmg = calc_damage( ctx ) * attacker.melee_damage;
493         xout << attacker.creature.name << " deals " << dmg << " damage to " << target.describe();
494
495         auto kills = target.apply_damage( dmg );
496
497         if (kills > 1)
498                 xout << " (" << kills << ' ' << target.creature.name << 's' << " perish)" << nl;
499         else if (kills > 0)
500                 xout << " (" << kills << ' ' << target.creature.name << " perishes)" << nl;
501         else
502                 xout << nl;
503         if (target.count > 0) {
504                 auto iend = end(target.effects);
505                 auto it = std::stable_partition(begin(target.effects),iend,[](auto e) { return !e.removed_on_damage; } );
506                 for (auto t = it; t != iend; ++t)
507                         t->base->remove(target);
508                 target.effects.erase( it, end(target.effects) );
509
510                 for (auto func : attacker.post_damage)
511                         func(attacker, target);
512         }
513 }
514
515 void apply_damage_ranged( creature_stack& attacker, creature_stack& target )
516 {
517         if (attacker.dead()||target.dead())
518                 return;
519         damage_context ctx {
520                 attacker,
521                 target,
522                 attacker.creature.attack,
523                 target.creature.attack
524         };
525
526         for (auto func : attacker.pre_damage)
527                 func( ctx );
528
529         auto range = (target.pos-attacker.pos).length();
530
531         int dmg = calc_damage( ctx ) * attacker.shot_damage;
532         if (range > 6.1)
533                 dmg *= 0.5;
534         xout << attacker.creature.name << " deals " << dmg << " damage to " << target.describe();
535         --attacker.shots;
536
537         auto kills = target.apply_damage( dmg );
538
539         if (kills > 1)
540                 xout << " (" << kills << ' ' << target.creature.name << 's' << " perish)" << nl;
541         else if (kills > 0)
542                 xout << " (" << kills << ' ' << target.creature.name << " perishes)" << nl;
543         else
544                 xout << nl;
545         if (target.count > 0) {
546                 auto iend = end(target.effects);
547                 auto it = std::stable_partition(begin(target.effects),iend,[](auto e) { return !e.removed_on_damage; } );
548                 for (auto t = it; t != iend; ++t)
549                         t->base->remove(target);
550                 target.effects.erase( it, end(target.effects) );
551
552                 for (auto func : attacker.post_damage)
553                         func(attacker, target);
554         }
555 }
556
557
558 struct ability_double_strike : creature_ability {
559         ability_double_strike()
560         {
561                 cat = ability_category::post_enemy_retaliation;
562         }
563         void add(creature_stack& stack) override
564         {
565                 stack.post_enemy_retaliation.push_back( apply_damage );
566         }
567 } double_attack;
568
569 bool can_retaliate(creature_stack& stack)
570 {
571         if (stack.dead())
572                 return false;
573         if (stack.retaliations == 0)
574                 return false;
575         if (stack.disabled)
576                 return false;
577         return true;
578 }
579 void retaliate(creature_stack& stack, creature_stack& attacker)
580 {
581         if (!can_retaliate(stack))
582                 return;
583         --stack.retaliations;
584         xout << stack.describe() << " retaliates" << nl;
585         apply_damage( stack, attacker );
586 }
587
588 void shoot(creature_stack& attacker, creature_stack& target)
589 {
590         if (attacker.shots == 0)
591                 return;
592         xout << attacker.describe() << " shoots " << target.describe() << nl;
593         for (auto i = 0u; i < attacker.num_ranged_attacks; ++i)
594                 apply_damage_ranged( attacker, target );
595 }
596
597 void attack(creature_stack& attacker, creature_stack& target)
598 {
599         xout << attacker.describe() << " attacks " << target.describe() << nl;
600         apply_damage( attacker, target );
601         if (!attacker.blocks_retaliation)
602                 retaliate(target, attacker);
603         if (!attacker.disabled)
604         for (auto func : attacker.post_enemy_retaliation)
605                 func( attacker, target );
606 }
607
608 void regenerate(creature_stack& stack)
609 {
610         if (stack.max_hp == stack.hp) return;
611         auto amount = std::min(stack.max_hp - stack.hp, 25);
612         xout << stack.describe() << " regenerates " << amount << " hit points" << nl;
613         stack.hp += amount;
614 }
615
616 #include <chrono>
617 #include <thread>
618
619 //#include <aw/types/containers/queue.h>
620 #include <set>
621 #include <cmath>
622 // hilriously inefficient way to find all nearby targets
623 std::vector<creature_stack*> find_nearby_targets( creature_stack const& s, std::vector<creature_stack>& ss )
624 {
625         std::vector<creature_stack*> result;
626
627         constexpr char free = 0;
628         constexpr char occupied = -1;
629         constexpr char reachable_occupied = -2;
630         constexpr char reachable = 1;
631         char grid[11][11] = {};
632         double drid[11][11] = {};
633         for (int i = 0; i < 11; ++i)
634                 for (int j = 0; j < 11; ++j)
635                         drid[i][j] = 9999;
636
637         for (auto& s : ss)
638                 if (!s.dead())
639                 grid[s.pos.x][s.pos.y] = -1;
640
641         struct node {
642                 double distance;
643                 point2d pos;
644         };
645
646         std::deque<node> queue;
647
648         grid[s.pos.x][s.pos.y] = 0;
649         queue.push_front( {0.0, s.pos} );
650
651         while (!queue.empty()) {
652                 auto n = queue.front();
653                 queue.pop_front();
654
655                 auto d = n.distance;
656                 auto pos = n.pos;
657
658                 if (pos.x < 0 || pos.x > 10) continue;
659                 if (pos.y < 0 || pos.y > 10) continue;
660
661                 if (grid[pos.x][pos.y] == reachable_occupied)
662                         continue;
663                 if (grid[pos.x][pos.y] == occupied) {
664                         grid[pos.x][pos.y] = reachable_occupied;
665                         continue;
666                 }
667
668                 if (d >= drid[pos.x][pos.y])
669                         continue;
670
671                 drid[pos.x][pos.y] = d;
672                 grid[pos.x][pos.y] = reachable;
673
674                 if (d > s.creature.speed)
675                         continue;
676
677                 queue.push_back( {d+1,pos.x+1,pos.y} );
678                 queue.push_back( {d+1,pos.x-1,pos.y} );
679                 queue.push_back( {d+1,pos.x,pos.y+1} );
680                 queue.push_back( {d+1,pos.x,pos.y-1} );
681
682                 queue.push_back( {d+std::sqrt(2),pos.x+1,pos.y+1} );
683                 queue.push_back( {d+std::sqrt(2),pos.x+1,pos.y-1} );
684                 queue.push_back( {d+std::sqrt(2),pos.x-1,pos.y+1} );
685                 queue.push_back( {d+std::sqrt(2),pos.x-1,pos.y-1} );
686         }
687
688         auto team = s.team;
689         for (auto& s : ss)
690                 if (grid[s.pos.x][s.pos.y] == reachable_occupied)
691                         if (!s.dead() && s.team != team)
692                                 result.push_back(&s);
693         auto distance = [&] (auto a, auto b) {
694                 return (a->pos-s.pos).length() < (b->pos-s.pos).length();
695         };
696         std::sort(begin(result),end(result), distance);
697         return result;
698 }
699
700 void highlight_move_area( creature_stack const& s, std::vector<creature_stack>& stacks, point2d cursor )
701 {
702         std::vector<creature_stack*> result;
703
704         creature_stack* yabladay;
705         double grid[11][11] = {};
706         for (int i = 0; i < 11; ++i)
707                 for (int j = 0; j < 11; ++j)
708                         grid[i][j] = 9999;
709
710         struct node {
711                 double distance;
712                 point2d pos;
713         };
714
715         std::deque<node> queue;
716
717         queue.push_front( {0.0, s.pos} );
718
719         while (!queue.empty()) {
720                 auto n = queue.front();
721                 queue.pop_front();
722
723                 auto d = n.distance;
724                 auto pos = n.pos;
725
726                 if (pos.x < 0 || pos.x > 10) continue;
727                 if (pos.y < 0 || pos.y > 10) continue;
728
729                 if (d >= grid[pos.x][pos.y])
730                         continue;
731
732                 grid[pos.x][pos.y] = d;
733
734                 if (d > s.creature.speed)
735                         continue;
736
737                 queue.push_back( {d+1,pos.x+1,pos.y} );
738                 queue.push_back( {d+1,pos.x-1,pos.y} );
739                 queue.push_back( {d+1,pos.x,pos.y+1} );
740                 queue.push_back( {d+1,pos.x,pos.y-1} );
741
742                 queue.push_back( {d+std::sqrt(2),pos.x+1,pos.y+1} );
743                 queue.push_back( {d+std::sqrt(2),pos.x+1,pos.y-1} );
744                 queue.push_back( {d+std::sqrt(2),pos.x-1,pos.y+1} );
745                 queue.push_back( {d+std::sqrt(2),pos.x-1,pos.y-1} );
746         }
747
748
749         char unit[11][11];
750         int  team[11][11] = {};
751
752         for (int i = 0; i < 11; ++i)
753                 for (int j = 0; j < 11; ++j)
754                         unit[i][j] = '.';
755         for (auto& s:stacks)
756                 if (!s.dead()) {
757                         unit[s.pos.x][s.pos.y] = s.creature.name[0];
758                         team[s.pos.x][s.pos.y] = s.team;
759                 }
760
761         bool enabled = false;
762         auto speed = s.creature.speed;
763         std::cout << "\033[1m";
764         std::cout << "-----------------------\n";
765         for (int i = 0; i < 11; ++i) {
766                 for (int j = 0; j < 11; ++j) {
767                         if (grid[i][j] > speed && enabled) {
768                                 std::cout << "\033[49m";
769                                 enabled = false;
770                         }
771                         std::cout << ' ';
772                         if (grid[i][j] < speed && !enabled) {
773                                 std::cout << "\033[41m";
774                                 enabled = true;
775                         }
776                         if (team[i][j] == 1) std::cout << "\033[35m";
777                         if (team[i][j] == 2) std::cout << "\033[32m";
778                         if (team[i][j] == 3) std::cout << "\033[33m";
779                         if (team[i][j] == 4) std::cout << "\033[34m";
780                         if (team[i][j] == 5) std::cout << "\033[31m";
781                         if (point2d{i,j} == cursor)
782                                 std::cout << 'X';
783                         else
784                                 std::cout << unit[i][j];
785                         if (team[i][j] != 0)
786                                 std::cout << "\033[39m";
787                         //if (team[i][j] != 0) ofs << "#";
788                 }
789                 std::cout << " \n";
790         }
791         std::cout << "\033[49m";
792         std::cout << '\n';
793         std::cout << '[';
794         for (auto& s : stacks) {
795                 if (s.dead()) continue;
796                 if (s.team == 1) std::cout << "\033[1;35m";
797                 if (s.team == 2) std::cout << "\033[1;32m";
798                 if (s.team == 3) std::cout << "\033[1;33m";
799                 if (s.team == 4) std::cout << "\033[1;34m";
800                 if (s.team == 5) std::cout << "\033[1;31m";
801                 std::cout << s.creature.name[0];
802                 std::cout << "\033[0m";
803         }
804         std::cout << ']';
805         std::cout << '\n';
806
807         std::cout << s.describe() << '[' << s.hp << '/' << s.max_hp << ']' << '\n';
808         for (auto& e : s.effects) {
809                 std::cout << e.base->name() << " for " << double(e.duration-e.counter)/100 << " turns";
810         }
811         std::cout << '\n';
812 }
813
814 point2d bfs( creature_stack& s, point2d target, std::vector<creature_stack> const& ss )
815 {
816         double grid[11][11];
817
818         for (int i = 0; i < 11; ++i)
819                 for (int j = 0; j < 11; ++j)
820                         grid[i][j] = -1;
821
822         for (auto& s : ss)
823                 if (!s.dead())
824                 grid[s.pos.x][s.pos.y] = -2;
825
826         struct node {
827                 double distance;
828                 point2d pos;
829                 point2d prev;
830         };
831
832         std::deque<node> queue;
833         auto origin = s.pos;
834         grid[origin.x][origin.y] = -1;
835
836         queue.push_front( {0.0, origin, origin} );
837
838         while (!queue.empty()) {
839                 auto n = queue.front();
840                 queue.pop_front();
841
842                 auto pos = n.pos;
843                 if (pos == target)
844                         return n.prev;
845
846                 if (pos.x < 0 || pos.x > 10) continue;
847                 if (pos.y < 0 || pos.y > 10) continue;
848
849                 auto d = n.distance;
850                 if (d > s.creature.speed)
851                         continue;
852                 if (grid[pos.x][pos.y] == -2)
853                         continue;
854                 if (grid[pos.x][pos.y] > d)
855                         grid[pos.x][pos.y] = d;
856                 if (grid[pos.x][pos.y] != -1)
857                         continue;
858                 grid[pos.x][pos.y] = d;
859
860                 queue.push_back( {d+1,{pos.x+1,pos.y},pos} );
861                 queue.push_back( {d+1,{pos.x,pos.y+1},pos} );
862                 queue.push_back( {d+1,{pos.x-1,pos.y},pos} );
863                 queue.push_back( {d+1,{pos.x,pos.y-1},pos} );
864
865                 queue.push_back( {d+std::sqrt(2),{pos.x+1,pos.y+1},pos} );
866                 queue.push_back( {d+std::sqrt(2),{pos.x+1,pos.y-1},pos} );
867                 queue.push_back( {d+std::sqrt(2),{pos.x-1,pos.y+1},pos} );
868                 queue.push_back( {d+std::sqrt(2),{pos.x-1,pos.y-1},pos} );
869         }
870
871         return {-1,-1};
872 }
873
874 point2d bfs2( creature_stack& s, point2d target, std::vector<creature_stack> const& ss )
875 {
876         double grid[11][11];
877
878         for (int i = 0; i < 11; ++i)
879                 for (int j = 0; j < 11; ++j)
880                         grid[i][j] = -1;
881
882         for (auto& s : ss)
883                 if (!s.dead())
884                 grid[s.pos.x][s.pos.y] = -2;
885
886         struct node {
887                 double distance;
888                 point2d pos;
889                 point2d prev;
890         };
891
892         auto origin = s.pos;
893         std::deque<node> queue;
894         grid[origin.x][origin.y] = -1;
895
896         queue.push_front( {0.0, origin, origin} );
897
898         double dist = (target-origin).length();
899         point2d closest = origin;
900
901         while (!queue.empty()) {
902                 auto n = queue.front();
903                 queue.pop_front();
904
905                 auto pos = n.pos;
906                 if (pos.x < 0 || pos.x > 10) continue;
907                 if (pos.y < 0 || pos.y > 10) continue;
908
909                 auto d = n.distance;
910                 if (d > s.creature.speed)
911                         continue;
912                 if (grid[pos.x][pos.y] == -2)
913                         continue;
914
915                 if (grid[pos.x][pos.y] != -1)
916                         continue;
917
918                 auto quy = (target-pos).length();
919                 if (quy < dist) {
920                         dist = quy;
921                         closest = pos;
922                 }
923
924                 grid[pos.x][pos.y] = d;
925
926                 queue.push_back( {d+1,{pos.x+1,pos.y},pos} );
927                 queue.push_back( {d+1,{pos.x,pos.y+1},pos} );
928                 queue.push_back( {d+1,{pos.x-1,pos.y},pos} );
929                 queue.push_back( {d+1,{pos.x,pos.y-1},pos} );
930
931                 queue.push_back( {d+std::sqrt(2),{pos.x+1,pos.y+1},pos} );
932                 queue.push_back( {d+std::sqrt(2),{pos.x+1,pos.y-1},pos} );
933                 queue.push_back( {d+std::sqrt(2),{pos.x-1,pos.y+1},pos} );
934                 queue.push_back( {d+std::sqrt(2),{pos.x-1,pos.y-1},pos} );
935         }
936
937         return closest;
938 }
939
940
941 #include <aw/utility/string/split.h>
942 #include <fstream>
943
944 #include <termios.h>
945 #include <cstdio>
946 #include <unistd.h>
947 struct termios tp, save;
948
949 int main()
950 {
951         tcgetattr(STDIN_FILENO, &tp);
952         save = tp;
953         tp.c_lflag &= ~ECHO;
954         tp.c_lflag &= ~ICANON;
955         tcsetattr(STDIN_FILENO, TCSAFLUSH, &tp);
956         setvbuf(stdin, NULL, _IONBF, 0);
957
958         creature BLACK_DRAGON = {
959                 "black_dragon", 30, 30, 240, {45, 70}, 10, 10,
960                 { }
961         };
962
963         creature EMERALD_DRAGON = {
964                 "Emerald_dragon", 31, 27, 200, {33, 57}, 9, 14,
965                 { }
966         };
967
968         creature HYDRA = {
969                 "hydra", 15, 15, 125, {9, 14}, 5, 7,
970                 {
971                         &no_retaliation,
972                         &regeneration
973                         //&all_targets
974                 }
975         };
976
977         creature MINOTAUR = {
978                 "minotaur", 5, 2, 35, {4, 7}, 5, 8,
979                 {
980                         &double_attack,
981                 }
982         };
983
984         creature ASSASIN = {
985                 "assasin", 4, 3, 14, {2, 4}, 5, 12,
986                 {
987                         &poisoner,
988                         &shooter_half,
989                 }
990         };
991
992         creature UNICORN = {
993                 "unicorn", 17, 17, 77, {10, 20}, 7, 12,
994                 {
995                         &blind
996                 }
997         };
998
999         creature TROGLODYTE = {
1000                 "troglodyte", 5, 4, 6, {1, 3}, 5, 9,
1001                 {
1002                         //&blind_immunity
1003                 }
1004         };
1005
1006         creature CENTAUR = {
1007                 "centaur", 6, 3, 10, {2, 3}, 6, 11,
1008                 {
1009                 }
1010         };
1011
1012         creature PEGASUS = {
1013                 "pegasus", 9, 10, 30, {5, 9}, 9, 12,
1014                 {
1015                 }
1016         };
1017
1018         creature BEHEMOTH = {
1019                 "behemoth", 19, 19, 300, {30, 50}, 6, 11,
1020                 {
1021                         &ignoredef80p
1022                 }
1023         };
1024
1025         creature WOLF_RAIDER = {
1026                 "wolf_raider", 8, 5, 10, {3, 4}, 6, 11,
1027                 {
1028                         &double_attack
1029                 }
1030         };
1031
1032         creature CYCLOP = {
1033                 "cyclop", 17, 13, 70, {16, 20}, 5, 10,
1034                 {
1035                         &shooter_normal
1036                 }
1037         };
1038
1039         creature AZURE_DRAGON = {
1040                 "azure_dragon", 50, 50, 1000, {70, 80}, 10, 15,
1041                 {
1042                 }
1043         };
1044
1045         creature ELVEN_ARCHER = {
1046                 "elven_archer", 5, 4, 14, {5, 8}, 5, 10,
1047                 {
1048                         &shooter_twice
1049                 }
1050         };
1051
1052         creature BLACK_DRAGON_HOMM4 = {
1053                 "Bl4ck_dragon", 40, 40, 240, {55, 110}, 11, 14,
1054                 { }
1055         };
1056
1057         creature TROGLODYTE_HOMM4 = {
1058                 "Trog4odyte", 11, 9, 14, {2, 3}, 6, 10,
1059                 { }
1060         };
1061
1062         int turn = 0;
1063         int turnini = 0;
1064
1065         std::vector<creature_stack> stacks {
1066                 {BLACK_DRAGON, 1, {0,0}, 1},
1067                 {ASSASIN, 45, {0,1}, 1},
1068                 {HYDRA, 5, {0,2}, 1},
1069                 {MINOTAUR, 24,{0,3}, 1},
1070                 {EMERALD_DRAGON, 2,{9,1}, 2},
1071                 {UNICORN, 7,{10,1}, 2},
1072                 {ELVEN_ARCHER, 14,{10,0}, 2},
1073                 {CENTAUR, 40,{10,2}, 2},
1074                 {PEGASUS, 14,{10,3}, 2},
1075                 {BEHEMOTH, 2,{0,10}, 3},
1076                 {AZURE_DRAGON, 1,{2,10},4},
1077                 {WOLF_RAIDER, 27,{0,9}, 3},
1078                 {CYCLOP, 3,{0,8}, 3},
1079                 {BLACK_DRAGON_HOMM4, 1,{10,10},5},
1080                 {TROGLODYTE, 60,{9,10}, 5},
1081                 {TROGLODYTE_HOMM4, 40,{10,9},5},
1082         };
1083
1084         auto teams = [&] {
1085                 auto not_dead = [] (auto s) { return !s.dead(); };
1086                 auto it1 = std::find_if( begin(stacks), end(stacks), not_dead );
1087                 if (it1 == end(stacks))
1088                         return false;
1089                 auto team = [team=it1->team] (auto s) { return !s.dead() && s.team!=team; };
1090                 auto it = std::find_if( begin(stacks),end(stacks), team);
1091                 return it != end(stacks);
1092         };
1093
1094         {
1095                 std::uniform_int_distribution<int> dist(0,25);
1096                 for (auto& s : stacks)
1097                         s.initiative += dist(rng);
1098         }
1099
1100
1101
1102         auto print_field = [&] {
1103                 std::stringstream ss;
1104                 char grid[11][11];
1105                 int  team[11][11] = {};
1106
1107                 for (int i = 0; i < 11; ++i)
1108                         for (int j = 0; j < 11; ++j)
1109                                 grid[i][j] = '.';
1110                 for (auto& s:stacks)
1111                         if (!s.dead()) {
1112                                 grid[s.pos.x][s.pos.y] = s.creature.name[0];
1113                                 team[s.pos.x][s.pos.y] = s.team;
1114                         }
1115                 ss << "-----------------------\n";
1116                 for (int i = 0; i < 11; ++i) {
1117                         for (int j = 0; j < 11; ++j) {
1118                                 ss << ' ';
1119                                 if (team[i][j] == 1) ss << "\033[1;35m";
1120                                 if (team[i][j] == 2) ss << "\033[1;32m";
1121                                 if (team[i][j] == 3) ss << "\033[1;33m";
1122                                 if (team[i][j] == 4) ss << "\033[1;34m";
1123                                 if (team[i][j] == 5) ss << "\033[1;31m";
1124                                 ss << grid[i][j];
1125                                 if (team[i][j] != 0) ss << "\033[0m";
1126                                 //if (team[i][j] != 0) ofs << "#";
1127                         }
1128                         ss << " \n";
1129                 }
1130                 ss << '\n';
1131                 ss << '[';
1132                 for (auto& s : stacks) {
1133                         if (s.dead()) continue;
1134                         if (s.team == 1) ss << "\033[1;35m";
1135                         if (s.team == 2) ss << "\033[1;32m";
1136                         if (s.team == 3) ss << "\033[1;33m";
1137                         if (s.team == 4) ss << "\033[1;34m";
1138                         if (s.team == 5) ss << "\033[1;31m";
1139                         ss << s.creature.name[0];
1140                         ss << "\033[0m";
1141                 }
1142                 ss << ']';
1143                 ss << '\n';
1144
1145                 auto sr = ss.str();
1146                 auto cutacuta = aw::string::cut( sr, "\n");
1147                 for (auto s : cutacuta)
1148                         linebuffer.push_back( (std::string)s );
1149         };
1150
1151         auto do_playerteam_stuff = [&] (creature_stack& s)
1152         {
1153                 using namespace std::chrono_literals;
1154                 std::this_thread::sleep_for(3.50s);
1155                 point2d cursor = s.pos;
1156                 point2d pos{-1,-1};
1157                 creature_stack* target = nullptr;
1158                 while (true) {
1159                         system("clear");
1160                         highlight_move_area(s, stacks, cursor);
1161                         char c = std::cin.get();
1162                         if (c == 'd')
1163                                 ++cursor.y;
1164                         if (c == 'a')
1165                                 --cursor.y;
1166                         if (c == 'w')
1167                                 --cursor.x;
1168                         if (c == 's')
1169                                 ++cursor.x;
1170                         bool comand = false;
1171                         if (c == ' ') {
1172                                 if (s.pos == cursor)
1173                                         break;
1174                                 for (auto& t : stacks) {
1175                                         if (t.dead()) continue;
1176                                         if (t.pos == cursor) {
1177                                                 pos = bfs( s, t.pos, stacks );
1178                                                 if (pos.x != -1) {
1179                                                         target = &t;
1180                                                         comand = true;
1181                                                 }
1182                                                 break;
1183                                         }
1184                                 }
1185
1186                                 pos = bfs2( s, cursor, stacks);
1187                                 comand = true;
1188                         }
1189                         if (comand)
1190                                 break;
1191                 }
1192                 print_field();
1193                 if (pos.x != -1) {
1194                         if (pos != s.pos)
1195                                 s.move( pos );
1196                         if (target)
1197                                 attack( s, *target );
1198                 } else {
1199                         s.wait();
1200                 }
1201                 while (xout.has_data())
1202                         xout << nl;
1203         };
1204
1205
1206         auto has_enemy_near = [&] (creature_stack& s) {
1207                 creature_stack* field[11][11] = {};
1208                 for (int i = 0; i < 11; ++i)
1209                         for (int j = 0; j < 11; ++j)
1210                                 field[i][j] = nullptr;
1211                 for (auto& s:stacks)
1212                         if (!s.dead()) {
1213                                 field[s.pos.x][s.pos.y] = &s;
1214                         }
1215
1216                 auto has_enemy_at = [&] (int x, int y)
1217                 {
1218                         if (x < 0 || x > 10) return false;
1219                         if (y < 0 || y > 10) return false;
1220                         if (!field[x][y]) return false;
1221                         return field[x][y]->team != s.team;
1222                 };
1223
1224                 if (has_enemy_at(s.pos.x-1, s.pos.y-1)) return true;
1225                 if (has_enemy_at(s.pos.x-1, s.pos.y))   return true;
1226                 if (has_enemy_at(s.pos.x-1, s.pos.y+1)) return true;
1227                 if (has_enemy_at(s.pos.x,   s.pos.y-1)) return true;
1228                 if (has_enemy_at(s.pos.x,   s.pos.y+1)) return true;
1229                 if (has_enemy_at(s.pos.x+1, s.pos.y-1)) return true;
1230                 if (has_enemy_at(s.pos.x+1, s.pos.y))   return true;
1231                 if (has_enemy_at(s.pos.x+1, s.pos.y+1)) return true;
1232                 return false;
1233         };
1234
1235         int playerteam = 6;
1236         while ( teams() ) {
1237                 for (auto& stack : stacks)
1238                         stack.step_turn();
1239                 turnini += 10;
1240                 if (turnini >= 100) {
1241                         ++turn;
1242                         xout << "-----------------------" << nl;
1243                         xout << "turn: " << turn << nl;
1244                         turnini -= 100;
1245                 }
1246
1247                 std::sort( begin(stacks), end(stacks), [] (auto a, auto b) {
1248                         return a.initiative > b.initiative;
1249                 });
1250
1251                 for (auto& stack : stacks) {
1252                         if (stack.dead())
1253                                 continue;
1254                         if (stack.initiative < 100)
1255                                 break;
1256                         stack.initiative -= 100;
1257                         stack.begin_turn();
1258                         if (stack.dead())
1259                                 continue;
1260
1261                         if (stack.team == playerteam)
1262                         {
1263                                 do_playerteam_stuff(stack);
1264                                 continue;
1265                         }
1266
1267                         print_field();
1268
1269
1270                         [&] {
1271                                 std::vector<creature_stack*> can_reach = find_nearby_targets( stack, stacks );
1272
1273                                 auto no_retali = [team=stack.team] (auto ss) {
1274                                         auto s = *ss;
1275                                         return team!=s.team&&!s.disabled && !s.dead() && s.retaliations == 0;
1276                                 };
1277                                 auto no_dis = [team=stack.team] (auto ss) {
1278                                         auto s = *ss;
1279                                         return team!=s.team&&!s.disabled && !s.dead();
1280                                 };
1281                                 auto enemy_team = [team=stack.team] (auto ss) {
1282                                         auto s = *ss;
1283                                         return team!=s.team&&!s.dead();
1284                                 };
1285                                 auto enemymy_team = [team=stack.team] (auto ss) {
1286                                         auto s = ss;
1287                                         return team!=s.team&&!s.dead();
1288                                 };
1289                                 auto it = std::find_if(begin(can_reach), end(can_reach), no_retali);
1290                                 if (it == end(can_reach))
1291                                         it = std::find_if(begin(can_reach), end(can_reach), no_dis);
1292                                 if (it == end(can_reach))
1293                                         it = std::find_if(begin(can_reach), end(can_reach), enemy_team);
1294
1295                                 if (it == end(can_reach)) {
1296                                         auto it = std::find_if(begin(stacks), end(stacks), enemymy_team);
1297                                         if (it ==end(stacks)) {
1298                                                 stack.wait();
1299                                                 return;
1300                                         }
1301                                         if (stack.shots != 0 && !has_enemy_near(stack))
1302                                         {
1303                                                 shoot( stack, *it );
1304                                                 return;
1305                                         }
1306                                         auto pos = bfs2(stack,it->pos,stacks);
1307                                         if (pos != stack.pos)
1308                                                 stack.move( pos );
1309                                         else
1310                                                 stack.wait();
1311                                         return;
1312                                 }
1313
1314                                 auto& target = **it;
1315
1316                                 if (stack.shots != 0 && !has_enemy_near(stack) && stack.shot_damage >= stack.melee_damage) {
1317                                         shoot( stack, target );
1318                                         return;
1319                                 }
1320
1321                                 auto pos = bfs( stack, target.pos,stacks );
1322                                 if (pos.x == -1) {
1323                                         std::cerr << "WAT!\n";
1324
1325                                         auto pos = bfs2(stack,target.pos,stacks);
1326                                         if (pos != stack.pos)
1327                                                 stack.move( pos );
1328                                         else
1329                                                 stack.wait();
1330                                 }
1331                                 if (pos != stack.pos)
1332                                         stack.move( pos );
1333
1334                                 attack( stack, target );
1335                                 /*if (stack.creature.name == "hydra") {
1336                                   for (auto& e : stacks)
1337                                   if (e.team != stack.team && &e != &target)
1338                                   apply_damage( stack, e );
1339
1340                                   }*/
1341                         }();
1342
1343                         xout<<nl;
1344                         using namespace std::chrono_literals;
1345                         while (xout.has_data())
1346                                 xout << nl;
1347                         std::this_thread::sleep_for(0.50s);
1348                 }
1349                         //xout << "=" << nl;
1350                         //for (auto& stack : stacks)
1351                         //      xout << stack.describe() << '[' << stack.hp << '/' << stack.max_hp << ']' << nl;
1352                         //xout << "=" << nl;
1353         }
1354
1355         std::partition( begin(stacks), end(stacks), [] (auto s) {
1356                 return !s.dead();
1357         });
1358
1359         print_field();
1360         auto team = stacks[0].team;
1361         xout << "-----------------------" << nl;
1362         xout << "winner: team " << team << ' ';
1363         switch(team) {
1364         case 1: xout << "H5 dungeon"; break;
1365         case 2: xout << "H3 rampart + H5 sylvan"; break;
1366         case 3: xout << "H3 stronghold"; break;
1367         case 4: xout << "H3 azure dragon"; break;
1368         case 5: xout << "H4 chaos + H3 dungeon"; break;
1369         };
1370         for (auto& s : stacks) {
1371                 if (s.dead()) break;
1372                 xout  << s.describe() << " with "<< s.hp << " hit points " << nl;
1373         }
1374         while (xout.has_data())
1375                 xout << nl;
1376
1377         tcsetattr(STDIN_FILENO, TCSANOW, &save);
1378 }